Liczba n -bitowych kodów Graya

Kod n-wymiarowy Graya to bijekcja

g : {0,..., 2^n-1} $$\rightarrow$$ {0, 1}ⁿ

taka, że g(k - 1) i g(k) różnią się dokładnie jedną współrzędną, dla 0 < k < 2ⁿ. Kod Graya g nazywamy cyklicznym, gdy g(0) i g(2^n-1) też różnią się dokładnie jedną współrzędną.

Pytamy się o liczbę G(n) wszystkich n -wymiarowych kodów Graya. Można też zapytać o równie ciekawą liczbę CG(n) wszystkich n -wymiarowych, cyklicznych kodów Graya.

W niskich wymiarach można wyobrażać sobie {0, 1}ⁿ jako zbiór wierzchołków n-wymiarowej kostki, a jak ktoś ma n-wymiarową wyobraźnię, to może tak samo postąpić w wymiarze n. Tak więc na oko widać, patrząc na odcinek i kwadrat, że

G(1) = 2, CG(1) = 0

G(2) = 8, CG(2) = 8

Niech odtąd n > 1.

Dla każdej trójki uporządkowanej wierzchołków

(u, v, w)

n-kostki, takich, że (u, v) oraz (v, w) są krawędziami zorientowanymi n-kostki, liczba kodów i kodów cyklicznych Graya g, spełniających

g(0) = u, g(1) = v, g(2) = w

nie zależy od wyboru trójki (u, v, w), czyli jest równa odpowiednio:

G'(n) = G(n)/(2^{n .} n ^. (n - 1))

CG'(n) = CG(n)/(2^{n .} n ^. (n - 1))

Może to dobry kierunek, a może sprowadza na manowce. Dla n = 3 pozwala łatwo sprawdzić, że:

G'(3) = 3CG'(3) = 2

skąd

G(3) = 144CG(3) = 96

Dla wyższych wymiarów metoda ta wymagałaby chyba programowania.

* * *

Szukana liczba jest liczbą ścieżek Hamiltona po nieskierowanym grafie 2ⁿ wierzchołków, w którym każdy wierzchołek jest stopnia n. (Wierzchołki reprezentują n-bitowe ciągi) Liczba krawędzi w tym grafie to s = 2^{n .} n/2.

Spróbujmy najpierw znaleźć liczbę ścieżek Hamiltona w takim grafie, zaczynających się na danym wierzchołku.

Ścieżki Hamiltona można tworzyć w taki sposób: będąc w kolejnym wierzchołku x ścieżki, wybieramy jedną z k krawędzi incydentnych z tym wierzchołkiem (niech będzie (x, y)) i idziemy nią do wierzchołka y. Następnie usuwamy z grafu wszystkie k krawędzie incydentne z wierzchołkiem x.

Z założenia przechodzimy wszystkie wierzchołki, więc usuniemy wszystkie s = 2^{n .} n/2 krawędzi. Można zauważyć jednak, że w każdym kroku mamy tyle możliwości ruchu, ile krawędzi usuwamy. Poza tym nigdy, poza ostatnim wierzchołkiem ścieżki Hamiltona, nie ma takiej sytuacji, że nie ma już żadnego ruchu (z założenia).

Niech a_i oznacza liczbę możliwości ruchu w i-tym kroku tworzenia ścieżki Hamiltona (pamiętając, ze pierwszy wierzchołek mamy zadany), wtedy:

$$\sum_{{i = 1}}^{{2^n - 1}}$$a_i = s = 2^{n .} n/2

dla każdego i = 2...(2ⁿ - 2), 0 < a_i < n

a₁ = n

a_n²-1 = 0

Paweł Olchawa, Włodzimierz Holsztyński, Michał Śliwka, marzec 2002

Linki do oryginalnych dyskusji: [1], [2]