Być może Delta ugości dabanese

Zauważyłem obecność lingwistyki na łamach Delty, więc zapytałem o dabanese. Redaktor MD odpowiedziała, że być może Delta ugości także dabanese, zwłaszcza, gdybym dał zadania. Zadania?! Nie wpadło mi to wcześniej do głowy, bo dabanese ma być prosty, a zadania powinny być nieco trudne. Ale jest to przednia idea - tak, zadania! Podam więc definicję wąskiego syntaksu dabanese (pełny dabanese używa szerokiego syntaksu, który dopuszcza większy zbiór wyrażeń), po czym sformułuję problem nie tyle lingwistyczny, co algorytmiczny.

"Prawdziwy" dabanese używa dabagramów (dabanesowych ideogramów). Z braku odpowiedniej komputerowej grafiki będziemy jednak używać niby-dabagramów, takich ja na przykład

zdr

czyli dowolnych ascii słów (czyli napisów bez żadnych wewnętrznych odstępów), nie zawierających żadnego z sześciu znaków nawiasów { } ( ) [ ]. Pełny dabanese używa wyrażeń. Natomiast wąski dabanese tylko wąsko zdefiniowanych wyrażeń, czyli używa frazy, a pomocniczo także przyciski.

Poniżej teoretycznie mówi się o dabagramach, mimo, że w tekście będą dla ilustracji używał niby-dabagramów. Dlatego nie będę musiał dla ścisłości mówić o odstępach, bo w przypadku grafiki dabagramy są (parami rozłączne oraz) jasno oddzielone zarówno pomiędzy sobą jak i od wszelkich nawiasów. Zatem teoretycznie formalne pojęcie odstępu w dabanese jest zbędne.

Syntaks wąski określony jest poprzez następujące postulaty:

1. dabagram jest frazą;
2. jeżeli F jest frazą, to [F] jest przyciskiem;
3. ciąg fraz i przycisków, upchany pomiędzy klamry { }, jest frazą nieuporządkowaną, jeżeli ciąg ma co najmniej dwa wyrazy, ale nie więcej niż jeden przycisk;
4. ciąg fraz i przycisków, upchany pomiędzy nawiasy ( ), jest frazą uporządkowaną, jeżeli ciąg ma co najmniej dwa wyrazy, ale nie więcej niż jeden przycisk;
5. wszystkie frazy (nieuporządkowane, uporządkowane, i dabagramy) oraz przyciski otrzymane są poprzez skończone stosowanie powyższych postulatów 1-4.
   

Elementy ciągu, z którego powstała dana fraza, nazywamy podfrazami tej frazy.
Frazy nieuporządkowane i uporządkowane, które nie zawierają podfrazy, będącej przyciskiem, nazywamy listami (odpowiednio nieuporządkowanymi lub uporządkowanymi, lub są dabagramem). Widzimy, że dabagramy są listami - będziemy mówić, że długości 1. Ogólnie długość listy jest liczbą jej podfraz.

Frazy nieuporządkowane, różniące się jedynie kolejnością podfraz uważamy w dabanese za identyczne.

Niech * oznacza pewien dabagram. Rozpatrzmy wszystkie frazy w których jedynym dabagramem jest *, przy czym występuje on tylko raz. Jest ich tylko jedna, mianowicie *. Ciekawiej jest gdy dopuścimy jedno lub dwa wystąpienia * we frazie - oto one, pełna lista:

1. *
2. {* *} oraz (* *)
3. {* [*]} oraz ([*] *) oraz (* [*])

- to wszystko, czyli razem 6. Ogólnie, niech F(k n) oznacza liczbę wszystkich fraz, w których występują dabagramy wyłącznie z ustalonego, zadanego zbioru k dabagramów, przy czym we frazie dabagramy razem występują co najwyżej n razy. W szczególności F(1 1) = 1 oraz F(1 2) = 6.

PROBLEM Oblicz F(k n) dla dowolnych k n.

Oczywiście:

TWIERDZENIE 1

F(k 1) = k

dla dowolnego k = 1 2 ...

Policzmy teraz F(2 2). Niech * $ oznaczają dwa różne dabagramy. Wtedy istnieje dokładnie 6 różnych fraz dla każdego z dabagramów * $ - w sumie 12 (w których występuje tylko jeden dabagram co najwyżej 2 razy) - oraz następujące, w których każdy z dabagramów * $ wystepuje raz:

1. {* $} oraz (* $) oraz ($ *) - listy
2. {[*] $} oraz {* [$]} - nieuporządkowane frazy z akcentem
3. ([*] $) oraz ($ [*]) oraz (* [$]) oraz ([$] *) - uporządkowane listy z akcentem
   

Jest ich, jak widzimy, 9. Zatem łącznie z monodabagramowymi otrzymujemy 12+9 = 21:

F(2 2) = 21

Jest to podstawą do policzenia F(k 2) dla dowolnego naturalnego k = 1 2 ...


TWIERDZENIE 2

F(k 2) = 6⋄k + 9⋄(k ## 2)

dla dowolnego k = 1 2 ...


gdzie (k ## 2) := k⋄(k-1) / 2.

Więcej (choć wciąż relatywnie niewiele) można przeczytać o dabanese na przykład tutaj:

dabanese na poewiki   knole o dabanese

gdzie (w obu miejscach) między innymi opisany jest syntaks ogólny oraz podane są pierwsze (dosyć) oficjalne dabagramy (a raczej niby-dabagramy).