Przetasowane kwadraty w kombinatoryce na słowach

Afiliacja: Politechnika Śląska

Miłość niejedno ma imię, a kwadrat niejedno ma znaczenie. Kwadratami są pewne figury płaskie (chociażby ta: \(\square\)), ale też niektóre liczby, na przykład \(289.\) Kwadrat to także męskie imię w tradycji chrześcijańskiej – był nawet św. Kwadrat, zwany Apologetą. Wreszcie kwadratem może być słowo, np. \(\mathtt{TATA},\) \(\mathtt{DZIADZIA}\)…

Mój syn miał dużo szczęścia, że nie wiedziałem o istnieniu tego imienia, gdy przychodził na świat.

A czym jest słowo? Słowo to ciąg znaków pochodzących z ustalonego zbioru, zwanego alfabetem. Dla każdego skończonego słowa \(W=w_1w_2\cdots w_n\) kwadratem jest słowo \(WW=w_1w_2\cdots w_nw_1w_2\cdots w_n.\) Zatem kwadrat można uzyskać, łącząc ze sobą dwie kopie pewnego słowa. Przetasowany kwadrat uzyskamy natomiast, gdy te kopie ze sobą „przetasujemy”: Słowo \(S=s_1s_2\cdots s_{2n}\) nazywamy przetasowanym kwadratem, jeżeli istnieją takie rozłączne zbiory indeksów \({I=\{i_1,i_2,\ldots,i_n\}}\) i \({J=\{j_1,j_2,\ldots,j_n\}},\) że \(i_1<i_2<\ldots<i_n,\) \(j_1<j_2<\ldots<j_n\) oraz dla każdego \(1\leqslant r\leqslant n\) zachodzi \(s_{i_r}=s_{j_r}.\) W myśl tej definicji dwiema „tasowanymi” kopiami tego samego słowa są \(S_1=s_{i_1}s_{i_2}\cdots s_{i_n}\) oraz \(S_2=s_{j_1}s_{j_2}\cdots s_{j_n}\).

Przykładowym przetasowanym kwadratem jest słowo \(\mathtt{01001000}\) – wystarczy przyjąć \(I=\{1,2,3,6\}\) oraz \(J=\{4,5,7,8\}.\) Bezpośrednie użycie definicji jest – jak widać – nieporęczne. Na szczęście istnieją wygodniejsze sposoby reprezentacji faktu, że słowo jest przetasowanym kwadratem: chociażby poprzez podkreślanie liter o indeksach ze zbioru \(I\) i nadkreślanie liter o indeksach ze zbioru \(J\) w słowie \(S\): \[\mathtt{\underline{010}\overline{01}\underline{0}\overline{00}}.\] Oczywiście nie jest prawdą, że przetasowanym kwadratem jest każdy tangram (słowo zawierające parzystą liczbę wystąpień każdej litery z danego alfabetu): świadczy o tym chociażby \(\mathtt{0110}.\) W zbiorze wszystkich \(256\) słów binarnych długości \(8\) dokładnie \(82\) to przetasowane kwadraty. Ogólnie rzecz biorąc, liczba binarnych przetasowanych kwadratów długości \(2n,\) począwszy od \(n=1,\) układa się w ciąg \[2,\ 6,\ 22,\ 82,\ 320,\ 1268,\ 5102,\ 20\,632,\ 83\,972,\ 342\,468,\ldots\] Jak wygląda wzór ogólny tego ciągu? Nie wiadomo, choć są na świecie ludzie, którzy chcieliby go poznać. Zdaje się, że to karkołomne zadanie – zwłaszcza że określenie, czy dane słowo (nawet binarne!) jest przetasowanym kwadratem, jest problemem NP-zupełnym.

W encyklopedii OEIS ciąg ten ma numer A191755.

Z drugiej strony od całkiem niedawna wiemy, że każdy odpowiednio długi binarny tangram prawie na pewno jest przetasowanym kwadratem. „Prawie na pewno” oznacza tutaj, że prawdopodobieństwo, że losowo wybrany binarny tangram jest przetasowanym kwadratem, dąży do \(1\) przy \(n\to\infty.\) Powyższy wynik nie jest trywialny, ale względnie łatwo można wykazać, że liczba binarnych przetasowanych kwadratów długości \(2n\) jest nie mniejsza niż \({2n\choose n}.\) Polecamy Czytelnikom próbę znalezienia algorytmu, który różnym ciągom binarnym o \(n\) jedynkach i \(n\) zerach (tych jest właśnie \({2n\choose n}\)) przypisuje różne przetasowane kwadraty długości \(2n\) (przykład niżej).

Autorami dowodu datowanego na grudzień 2025 są Xiaoyu He i Logan Post z Georgia Institute of Technology w Atlancie.