Liczba cykli hamiltonowskich na wykresie Sierpińskiego

Jestem nowy na tym forum i jestem tylko fizykiem, który robi to, aby utrzymać swój mózg w dobrej formie, więc proszę okaż łaskę, jeśli nie używam najbardziej eleganckiego języka. Proszę również zostawić komentarz, jeśli uważasz, że inne tagi byłyby bardziej odpowiednie.

Próbuję rozwiązać ten problem, dla którego muszę obliczyć liczbę cykli hamiltonowskich w tym rzędzie Sierpińskiego-wykresu . (Zobacz także powyższy link do definicji i zdjęć wykresów Sierpińskiego)n S $C(n)$$n$$S_n$

Znalazłem , ale musiałem coś pomieszać, ponieważ moje rozwiązanie nie pasuje do podanej wartości . Moja argumentacja składa się z bardzo podstawowych myśli i nie mogę znaleźć błędu. Każda pomoc jest mile widziana. Nawet jeśli wydaje się to długie, myśli stają się trywialne, jeśli spojrzysz na wykresy podczas śledzenia.C ( 5 ) = $C(n)$$C(5) = 71328803586048$

(a) W danym wykresie wywołać zewnętrzne narożniki . Następnie określam następujące ilości: A , B , $S_n$$A,B,C$

$N(n) :=$ liczba Hamiltona ścieżki do .$A$$C$

$\bar{N}(n) :=$ liczba ścieżek od do , które odwiedzają każdy węzeł raz wyjątkiem .C $A$$C$$B$

Nazwie też takie ścieżki - lub - ścieżki typu poniżej.ˉ $N$$\bar{N}$

(b) Łatwo zauważyć, że $N(n)=\bar{N}(n)$ .

Powód jest następujący: Rozważ ścieżkę typu $N$Począwszy od $A$ ścieżka ta ma postać $(A,...,X_1,B,X_2,...,C)$ . Zastępując segment $(X_1,B,X_2)$ przez $(X_1,X_2)$ , otrzymujemy ścieżkę typu $\bar{N}$ . Ta operacja jednoznacznie odwzorowuje wszystkie ścieżki typu $N$ ścieżki typu $\bar{N}$ .

(c) Wyprowadzamy rekurencję .$N(n+1)=2N(n)^3$

Weźmy pod uwagę ścieżkę typu od do i oznaczymy podtróby w zewnętrznych narożnikach przez . Oczywiste jest, że ścieżka typu odwiedzi każdy podtok dokładnie raz, zaczynając od przez do . Rozważmy teraz węzeł w którym dotykają się podteksty i . Istnieją dwie możliwości, gdy ścieżka jest odwiedzana przez ten punkt: (i) przed opuszczeniem lub (ii) po wejściu doA B A , B , C T A , T B , T C N T A T B T C Z T A T $N$$A$$B$$A,B,C$$T_A,T_B,T_C$$N$$T_A$$T_B$$T_C$$Z$$T_A$$T_C$$T_A$$T_C$. W takich przypadkach te trzy podścieżki wewnątrz są rodzajów : (i) lub (II) , odpowiednio. Mając to na uwadze, możemy liczyć$T_A,T_B,T_C$ $N,N,\bar{N}$ $\bar{N},N,N$

$N(n+1)=N(n)N(n)\bar{N}(n)+\bar{N}(n)N(n)N(n)$ i (b) otrzymujemy górny rekurencja.

(d) Rozwiązujemy rekurencję (c) z i otrzymujemy .$N(1)=1$$N(n)=2^{3^0+3^1+...+3^{n-2}}$

(e) Rozważmy cykl hamiltonowski na wykresie . Ponieważ każdy z trzech podrygentów jest połączony z innymi tylko za pomocą dwóch węzłów, jasne jest, że cykl wejdzie do każdego pod-trójkąta dokładnie raz przez jeden węzeł łączący, a następnie „wypełni” go, a na koniec opuści przez drugi węzeł łączący. Stąd cykl Hamiltonian w składa się z trzech podścieżek typu w podtangulach, z których wszystkie mają strukturę . Możemy wnioskować o liczbie cykli hamiltonowskich$S_n$$S_n$$N$$S_{n-1}$

$C(n) = N(n-1)^3$ .

Wynika to jednak dla$n=5$

$C(5) = N(4)^3 = 8192^3=549755813888 \neq 71328803586048$

gdzie to ostatnie należy uzyskać zgodnie ze stroną problemu (link powyżej).

Jeszcze raz dziękuję za wszelką pomoc lub komentarze.

Dobry pomysł! Problem wydaje się znajdować na etapie . Zastąpienie ( X 1 , B , X 2 ) w N- ścieżce przez ( X 1 , X 2 ) daje ˉ N- ścieżkę, ale nie każda ˉ N- ścieżka zawiera ( X 1 , X 2 ) . Więc to nie jest bijection. To tylko mówi N ( n ) ≤ ˉ N ( n ) .$(b)$$(X_1,B,X_2)$$N$$(X_1,X_2)$$\bar{N}$$\bar{N}$$(X_1,X_2)$$N(n) \leq \bar{N}(n)$

Lub możesz faktycznie wykazać, że , co daje N ( n + 1 ) = 3 N 3 .$\bar{N}(n) = 3N(n)/2$$N(n+1) = 3N^3$