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?
26 mar 13:46
zadanie: ?
28 mar 09:05
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 n2−elementowe). Niech Gn = (Vn, En) będzie grafem skierowanym z pętlami, gdzie: Vn = {1, 2, ..., n}, |Vn|=n En = (Vn)2, |En|=n2. Wtedy każdy cykl Eulera w grafie Gn odpowiada n2 różnym ciągom, które zliczamy (n2, 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 an = n2 * ec(Gn), gdzie ec(Gn) to liczba cyklów Eulera w grafie Gn. Niech G'n = (V'n, E'n}, gdzie: V'n = Vn E'n = En \ {(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) = tw(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: tw(G'n) = det( n−1 −1 ... −1 −1 −1 n−1 ... −1 −1 ... ... ... ... ... −1 −1 ... n−1 −1 −1 −1 ... −1 n−1 ) = nn−2 // 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) = nn−2*((n−1−1)!)n = nn−2*((n−2)!)n Cykle Eulera z Gn 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)n różnych cyklów Eulera w grafie Gn poprzez różne "dorzucenia" pętel. Czyli: ec(Gn) = ec(G'n) * (n−1)n = nn−2*((n−2)!)n * (n−1)n = nn−2*((n−1)!)n A stąd szukana liczba ciągów to: an = ec(Gn) * n2 = nn−2*((n−1)!)n * n2 = (n!)n Przykładowo dla n=2: • jedyny cykl Eulera w G'2: 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 G2: 1122 • dla każdego takiego cyklu z pętlami wybieramy 1 z 22=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 )
28 mar 14:59
zadanie: Dziekuje
29 mar 10:12
jc: Też dziękuję emotka kiedyś bezskutecznie próbowałem rozwiązać ten problem.
29 mar 14:47
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.
29 mar 16:49
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.
29 mar 17:45
zadanie: ?
3 kwi 09:29
jc: No tak, wydaje się, że twierdzenie dotyczy tylko grafów skierowanych.
3 kwi 10:07
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)?
25 sie 15:34
zadanie: ?
29 sie 11:01
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ść?
29 sie 22:33
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.
30 sie 09:13
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 
nawias
n
nawias
nawias
2
nawias
 
• (

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

)n // jw., tyle jest sposobów "dorzucenia" pętli
 2 
 
nawias
n
nawias
nawias
2
nawias
 
(
+n) // jw., tyle jest wyborów pierwszej krawędzi w ciągu
  
Jako ec(Kn) 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! 
30 sie 11:01