zadanie zadanie: Mamy do dyspozycji pary uporzadkowane o wspolrzednych nalezacych do zbioru {1, 2, 3, ..., n}. Chodzi o to, zeby zaczynajac od dowolnej pary dla danego n ulozyc je w ciag skladajacy sie ze wszystkich mozliwych par dla danego n. Mamy takie warunki: 1. Pierwsza współrzędna kolejnej pary musi być taka sama jak druga współrzędna poprzedniej pary. 2. Utożsamiamy (a,b) z (b,a). 3. Elementy nie moga sie powtarzac. Jak do tego podejść kombinatorycznie np. wykorzystując grafy? Dla n=3 mamy np.: 1) (1,1)(1,2)(2,2)(2,3)(3,3)(3,1) 2) (1,1)(1,3)(3,3)(3,2)(2,2)(2,1) 3) (1,2)(2,2)(2,3)(3,3)(3,1)(1,1) itd. wyszlo mi 12 takich ciagow. Jak je zliczyc kombinatorycznie? Jak obliczyc te ciagi dla pozostalych n?

zadanie: ?

Pytający: Jakkolwiek rozumieć to utożsamianie z warunku drugiego, chyba łatwiej rozwiązać pierwotny problem (z wątku: 387933), czyli niżej pomijam warunek drugi (więc dla a≠b zarówno (a,b) jak i (b,a) są elementami ciągu, czyli interesują nas ciągi n²−elementowe). Niech G_n = (V_n, E_n) będzie grafem skierowanym z pętlami, gdzie: V_n = {1, 2, ..., n}, |V_n|=n E_n = (V_n)², |E_n|=n². Wtedy każdy cykl Eulera w grafie G_n odpowiada n² różnym ciągom, które zliczamy (n², bo na tyle sposobów możemy wybrać pierwszą krawędź ciągu) i oczywiście każdy zliczany ciąg odpowiada dokładnie jednemu cyklowi Eulera. Zatem szukana liczba takich ciągów to a_n = n² * ec(G_n), gdzie ec(G_n) to liczba cyklów Eulera w grafie G_n. Niech G'_n = (V'_n, E'_n}, gdzie: V'_n = V_n E'_n = E_n \ {(a, a): a∊ℕ ∧ a≤n}, |E'_n|=n(n−1). Znaczy G'(n) to G(n) bez pętel. Z twierdzenia: https://en.wikipedia.org/wiki/BEST_theorem mamy: ec(G'_n) = t_w(G'_n) * ∏_v∊V'n((deg(v)−1)!) Oczywiście dla każdego v∊V'_n mamy deg(v)=n−1. Natomiast z: https://en.wikipedia.org/wiki/Kirchhoff%27s_theorem#Kirchhoff's_theorem_for_directed_multigraphs mamy: t_w(G'_n) = det( n−1 −1 ... −1 −1 −1 n−1 ... −1 −1 ... ... ... ... ... −1 −1 ... n−1 −1 −1 −1 ... −1 n−1 ) = nⁿ⁻² // wynik można otrzymać podobnie jak tu: https://math.stackexchange.com/questions/86644/determinant-of-a-specially-structured-matrix-as-on-the-diagonal-all-other-e Czyli: ec(G'_n) = nⁿ⁻²*((n−1−1)!)ⁿ = nⁿ⁻²*((n−2)!)ⁿ Cykle Eulera z G_n możemy otrzymać "dorzucając" pętle do cyklów Eulera z G'_n. W każdym cyklu Eulera w G'_n dla każdego z n wierzchołków mamy n−1 "przejść" przez ten wierzchołek ("wchodzimy" jakąś krawędzią, a nastepnie "wychodzimy" inną). Dla każdego wierzchołka v pętlę (v, v) możemy "dorzucić" właśnie w 1 z tych n−1 "przejść". Dlatego z każdego cyklu Eulera w grafie G'_n możemy otrzymać (n−1)ⁿ różnych cyklów Eulera w grafie G_n poprzez różne "dorzucenia" pętel. Czyli: ec(G_n) = ec(G'_n) * (n−1)ⁿ = nⁿ⁻²*((n−2)!)ⁿ * (n−1)ⁿ = nⁿ⁻²*((n−1)!)ⁿ A stąd szukana liczba ciągów to: a_n = ec(G_n) * n² = nⁿ⁻²*((n−1)!)ⁿ * n² = (n!)ⁿ Przykładowo dla n=2: • jedyny cykl Eulera w G'₂: 1→2→ // to cykl, ostatnia strzałka (krawędź) prowadzi do pierwszej liczby (wierzchołka) • dla każdego takiego cyklu dorzucamy pętlę do 1 z (2−1)=1 przejść przez 1 i do 1 z (2−1) przejść przez 2 (czyli wybraną jedynkę zamieniamy na 1→1 i wybraną dwójkę zamieniamy na 2→2), otrzymujemy cykle Eulera w G₂: 1→1→2→2→ • dla każdego takiego cyklu z pętlami wybieramy 1 z 2²=4 krawędzi jako pierwszą krawędź w ciągu i mamy wszystkie szukane ciągi: 1. ((1, 1), (1, 2), (2, 2), (2, 1)) 2. ((1, 2), (2, 2), (2, 1), (1, 1)) 3. ((2, 2), (2, 1), (1, 1), (1, 2)) 4. ((2, 1), (1, 1), (1, 2), (2, 2)) (może nigdzie po drodze nie napisałem jakichś bzdur )

zadanie: Dziekuje

jc: Też dziękuję kiedyś bezskutecznie próbowałem rozwiązać ten problem.

Pytający: Proszę bardzo. Jeśli nie znalazłbym twierdzenia BEST (jeszcze wczoraj go nie znałem), to moje próby pewnie też byłyby nieskuteczne.

zadanie: W warunku 2. chodziło mi o to, ze w danym ciagu jak uzyje pary (a,b) to juz nie moge uzyc pary (b,a). Jak wowczas obliczyc liczbe takich ciagow? Bo nie ukrywam, ze to jest mi bardziej potrzebne. Chyba, ze mozna wykorzystac to powyzsze.

zadanie: ?

jc: No tak, wydaje się, że twierdzenie dotyczy tylko grafów skierowanych.

zadanie: W jaki sposob to policzyc uwzgledniajac warunek drugi, czyli po uzyciu pary (a,b) nie moge juz uzyc pary (b,a) (tak jak w dominie)?

zadanie: ?

Pytający: Kilkukrotnie nad tym myślałem i wciąż nie wpadłem na rozwiązanie... A fakt, że ponownie o to pytasz po pięciu miesiącach intryguje. Możesz podzielić się tym, do czego potrzebna Ci ta zależność?

Blee: Pytający, czy nie musimy w takim przypadku rozpatrywać grafów nieskierowanych i szukać cyklów Eulerowskich? Dodatkowo w tym momencie wiemy, że dla n = 2k + 2 ; k∊N₊ nie będzie istniał cykl Eulerowski.

Pytający: Dla n=2 też nie istnieje. I racja, wystarczy liczba cyklów Eulera w nieskierowanym grafie pełnym, kilka pierwszych wartości (i sposób obliczania) znalazłem tu: http://www.algana.co.uk/publications/Counting.pdf Jednak my uwzględniamy tu jeszcze pętle, więc mamy: • 1 dla n=1, • 0 dla n=2k, k∊ℕ₊,

	n−1		n 2
• (		)n*(		+n)*ec(Kn) dla n=2k+1, k∊ℕ+.
	2

	n−1
(		)n // jw., tyle jest sposobów "dorzucenia" pętli
	2

	n 2
(		+n) // jw., tyle jest wyborów pierwszej krawędzi w ciągu

Jako ec(K_n) oznaczyłem liczbę cyklów Eulera w nieskierowanym grafie pełnym:

	(n2−3n+1)(n−1)*D((n−3)/2, n−2))
ec(Kn)=		,
	(n−2)3

	(2x+1)!
D(x,y)=y!*[		]y dla całkowitych x, y.
	2x*x!

zadanie: Dziekuje bardzo.

	n−1
A dlaczego jest		"przejsc" przez dany wierzcholek w tym "dorzucaniu" petli?
	2

zadanie: ?

zadanie: ?

Pytający: No przecież w grafie pełnym każdy wierzchołek ma stopień (n−1), a w cyklu Eulera "wykorzystujesz" wszystkie krawędzie, więc w owym cyklu masz właśnie (n−1) "połączeń" z danym wierzchołkiem. W tymże cyklu oczywiście jest ustalona jakaś kolejność wierzchołków, zatem

	n−1
		spośród tych krawędzi jest "wchodzących" (pierwszych w kolejności) i pozostałe
	2

	n−1		n−1
		spośród tych krawędzi jest "wychodzących". Stąd też jest		tychże przejść.
	2		2

Przykładowo dla cyklu (n=3): abc (3−1)=2 krawędzie (połączenia) incydentne z a to: ab, ac // ab=ba; ac=ca; toć to graf nieskierowany

	3−1
natomiast		=1 "przejścia" przez a to:
	2

c→a→b

zadanie: Dziekuje.