Rozmieszczanie krzyżyków w tabelce
: 24 paź 2013, o 22:34
autor: Kamaz
Przepraszam za przeoczenie. Trzech konfiguracji ostatnio nie uwzględniłam.
\(\displaystyle{ \begin{picture}(0,0)
\put(0,0){
\put(0,0){\line(0,1){40}}
\put(40,0){\line(0,1){40}}
\qbezier(0,0)(20,10)(40,0)
\qbezier(0,0)(20,-10)(40,0)
\qbezier(0,0)(20,5)(40,0)
\qbezier(0,0)(20,-5)(40,0)
\put(0,0){\circle*{4}}
\put(40,0){\circle*{4}}
\put(0,40){\circle*{4}}
\put(40,40){\circle*{4}}
}
\put(60,0){
\put(0,0){\line(0,1){40}}
\put(0,0){\line(1,0){40}}
\qbezier(40,0)(50,20)(40,40)
\qbezier(40,0)(30,20)(40,40)
\qbezier(40,0)(45,20)(40,40)
\qbezier(40,0)(35,20)(40,40)
\put(0,0){\circle*{4}}
\put(40,0){\circle*{4}}
\put(0,40){\circle*{4}}
\put(40,40){\circle*{4}}
}
\put(120,0){
\put(0,0){\line(1,0){40}}
\put(0,0){\line(0,1){40}}
\qbezier(40,0)(30,20)(40,40)
\qbezier(40,0)(50,20)(40,40)
\qbezier(0,0)(20,10)(40,0)
\qbezier(0,0)(20,-10)(40,0)
\put(0,0){\circle*{4}}
\put(40,0){\circle*{4}}
\put(0,40){\circle*{4}}
\put(40,40){\circle*{4}}
}
\put(0,-60){
\put(0,0){\line(0,1){40}}
\put(40,0){\line(0,1){40}}
\qbezier(40,0)(30,20)(40,40)
\qbezier(40,0)(50,20)(40,40)
\qbezier(0,0)(20,10)(40,0)
\qbezier(0,0)(20,-10)(40,0)
\put(0,0){\circle*{4}}
\put(40,0){\circle*{4}}
\put(0,40){\circle*{4}}
\put(40,40){\circle*{4}}
}
\put(60,-60){
\put(0,0){\line(1,0){40}}
\put(0,0){\line(0,1){40}}
\qbezier(0,0)(-10,20)(0,40)
\qbezier(0,0)(10,20)(0,40)
\qbezier(40,0)(30,20)(40,40)
\qbezier(40,0)(50,20)(40,40)
\put(0,0){\circle*{4}}
\put(40,0){\circle*{4}}
\put(0,40){\circle*{4}}
\put(40,40){\circle*{4}}
}
\put(120,-60){
\qbezier(0,0)(-10,20)(0,40)
\qbezier(0,0)(10,20)(0,40)
\qbezier(0,0)(20,-10)(40,0)
\qbezier(0,0)(20,10)(40,0)
\qbezier(40,0)(30,20)(40,40)
\qbezier(40,0)(50,20)(40,40)
\put(0,0){\circle*{4}}
\put(40,0){\circle*{4}}
\put(0,40){\circle*{4}}
\put(40,40){\circle*{4}}
}
\put(0,-120){
\put(0,0){\line(1,2){20}}
\put(40,0){\line(-1,2){20}}
\qbezier(0,0)(20,10)(40,0)
\qbezier(0,0)(20,-10)(40,0)
\qbezier(0,0)(20,5)(40,0)
\qbezier(0,0)(20,-5)(40,0)
\put(0,0){\circle*{4}}
\put(40,0){\circle*{4}}
\put(20,40){\circle*{4}}
}
\put(60,-120){
\put(0,0){\line(1,2){20}}
\put(0,0){\line(1,0){40}}
\qbezier(0,0)(20,10)(40,0)
\qbezier(0,0)(20,-10)(40,0)
\qbezier(40,0)(25,15)(20,40)
\qbezier(40,0)(35,25)(20,40)
\put(0,0){\circle*{4}}
\put(40,0){\circle*{4}}
\put(20,40){\circle*{4}}
}
\put(120,-120){
\qbezier(0,0)(20,10)(40,0)
\qbezier(0,0)(20,-10)(40,0)
\qbezier(40,0)(25,15)(20,40)
\qbezier(40,0)(35,25)(20,40)
\qbezier(0,0)(15,15)(20,40)
\qbezier(0,0)(5,25)(20,40)
\put(0,0){\circle*{4}}
\put(40,0){\circle*{4}}
\put(20,40){\circle*{4}}
}
\put(0,-180){
\put(0,0){\line(1,0){40}}
\qbezier(20,0)(30,20)(20,40)
\qbezier(20,0)(10,20)(20,40)
\qbezier(20,0)(25,20)(20,40)
\qbezier(20,0)(15,20)(20,40)
\put(0,0){\circle*{4}}
\put(40,0){\circle*{4}}
\put(20,40){\circle*{4}}
\put(20,0){\circle*{4}}
}
\put(60,-180){
\put(0,0){\line(1,0){40}}
\qbezier(20,0)(30,20)(20,40)
\qbezier(20,0)(10,20)(20,40)
\qbezier(20,0)(10,7)(0,0)
\qbezier(20,0)(10,-7)(0,0)
\put(0,0){\circle*{4}}
\put(40,0){\circle*{4}}
\put(20,40){\circle*{4}}
\put(20,0){\circle*{4}}
}
\put(120,-180){
\qbezier(20,0)(30,20)(20,40)
\qbezier(20,0)(10,20)(20,40)
\qbezier(20,0)(10,7)(0,0)
\qbezier(20,0)(10,-7)(0,0)
\qbezier(20,0)(30,7)(40,0)
\qbezier(20,0)(30,-7)(40,0)
\put(0,0){\circle*{4}}
\put(40,0){\circle*{4}}
\put(20,40){\circle*{4}}
\put(20,0){\circle*{4}}
}
\put(0,-240){
\put(0,0){\line(1,0){40}}
\put(40,0){\line(0,1){40}}
\qbezier(40,0)(50,20)(40,40)
\qbezier(40,0)(30,20)(40,40)
\qbezier(40,0)(45,20)(40,40)
\qbezier(40,0)(35,20)(40,40)
\put(0,0){\circle*{4}}
\put(40,0){\circle*{4}}
\put(40,40){\circle*{4}}
}
\put(60,-240){
\qbezier(0,0)(20,10)(40,0)
\qbezier(0,0)(20,-10)(40,0)
\qbezier(40,0)(50,20)(40,40)
\qbezier(40,0)(30,20)(40,40)
\qbezier(40,0)(45,20)(40,40)
\qbezier(40,0)(35,20)(40,40)
\put(0,0){\circle*{4}}
\put(40,0){\circle*{4}}
\put(40,40){\circle*{4}}
}
\put(120,-240){
\put(0,0){\line(1,0){40}}
\put(40,0){\line(0,1){40}}
\qbezier(0,0)(20,10)(40,0)
\qbezier(0,0)(20,-10)(40,0)
\qbezier(40,0)(50,20)(40,40)
\qbezier(40,0)(30,20)(40,40)
\put(0,0){\circle*{4}}
\put(40,0){\circle*{4}}
\put(40,40){\circle*{4}}
}
\put(0,-300){
\put(0,10){\line(1,0){40}}
\put(0,30){\line(1,0){40}}
\qbezier(0,30)(20,40)(40,30)
\qbezier(0,30)(20,20)(40,30)
\qbezier(0,30)(20,35)(40,30)
\qbezier(0,30)(20,25)(40,30)
\put(0,10){\circle*{4}}
\put(40,10){\circle*{4}}
\put(0,30){\circle*{4}}
\put(40,30){\circle*{4}}
}
\put(60,-300){
\qbezier(0,10)(20,20)(40,10)
\qbezier(0,10)(20,0)(40,10)
\qbezier(0,30)(20,40)(40,30)
\qbezier(0,30)(20,20)(40,30)
\qbezier(0,30)(20,35)(40,30)
\qbezier(0,30)(20,25)(40,30)
\put(0,10){\circle*{4}}
\put(40,10){\circle*{4}}
\put(0,30){\circle*{4}}
\put(40,30){\circle*{4}}
}
\put(120,-300){
\put(0,10){\line(1,0){40}}
\put(0,30){\line(1,0){40}}
\qbezier(0,10)(20,20)(40,10)
\qbezier(0,10)(20,0)(40,10)
\qbezier(0,30)(20,40)(40,30)
\qbezier(0,30)(20,20)(40,30)
\put(0,10){\circle*{4}}
\put(40,10){\circle*{4}}
\put(0,30){\circle*{4}}
\put(40,30){\circle*{4}}
}
\put(60,-360){
\qbezier(0,20)(20,30)(40,20)
\qbezier(0,20)(20,10)(40,20)
\qbezier(0,20)(20,25)(40,20)
\qbezier(0,20)(20,15)(40,20)
\qbezier(0,20)(20,35)(40,20)
\qbezier(0,20)(20,5)(40,20)
\put(0,20){\circle*{4}}
\put(40,20){\circle*{4}}
}
\put(-5,45){.}
\put(170,-365){.}
\end{picture}}\)
Rozmieszczanie krzyżyków w tabelce
: 27 paź 2013, o 23:33
autor: Naed Nitram
To może skomplikuję, żeby uprościć...
Żeby sprawnie zliczać orbity grup permutacji, warto zapoznać się z pojęciem indeksu cyklowego:
Jeśli w rozkładzie permutacji \(\displaystyle{ \sigma\in S_n}\) na rozłączne cykle cykl długości \(\displaystyle{ m}\) występuje \(\displaystyle{ j_m}\) razy, to przyporządkujmy tej permutacji jednomian:
\(\displaystyle{ z(g)=z(g;x_1,...,x_n)=x_1^{i_1}x_2^{j_2}...x_n^{j_n}}\).
Wiadomo więc na przykład, że \(\displaystyle{ 1\cdot j_1+2\cdot j_2+...+n\cdot j_n=n}\), co już wystąpiło w tym wątku w nieco innym kontekscie.
Indeks cyklowy grupy permutacji \(\displaystyle{ G}\), to wielomian:
\(\displaystyle{ Z(G)=Z(G;x_1,...,x_n)=\frac 1{|G|}\sum_{g\in G}z(g)}\).
Indeks cyklowy grup permutacji \(\displaystyle{ S_n}\) łatwo wyznaczyć na wiele różnych sposobów. Na przykład w dwóch liniach kodu z użyciem zależności rekurencyjnej:
\(\displaystyle{ Z(S_n)=\frac 1n\sum_{i=1}^nx_i\cdotZ(S_{n-i})}\).
Do wyznaczenia indeksów \(\displaystyle{ S_n}\) bezpośrednio na palcach, co mnie się wydaje najszybsze, wystarcza cierpliwość i elementarna kombinatoryka.
\(\displaystyle{ Z(S_1)=x_1}\)
\(\displaystyle{ Z(S_2)=\frac 12\cdot(x_1^2+x_2)}\)
\(\displaystyle{ Z(S_3)=\frac 16\cdot(x_1^3+3x_1x_2+2x_3)}\)
\(\displaystyle{ Z(S_4)=\frac 1{24}\cdot (x_1^4+6x_1^2x_2+3x_2^2+8x_1x_3+6x_4)}\)
\(\displaystyle{ Z(S_5)}\) jest już dość paskudny, pominę, bo się tu nie przyda, wypiszę \(\displaystyle{ Z(S_6)}\)
\(\displaystyle{ Z(S_6)=\frac 1{720}\cdot(x_1^6+15x_2^3+15x_2x_1^4+40x_3^2+40x_3x_1^3+45x_2^2x_1^2+90x_4x_1^2+}\)
\(\displaystyle{ +90x_4x_2+120x_5x_1+120x_3x_2x_1+144x_5x_1)}\).
Mamy więc między innymi typy permutacji w grupach \(\displaystyle{ S_4,S_6}\). Indeks cyklowy grupy \(\displaystyle{ S_4\times S_6}\) z działaniem produktowym dość łatwo wyraża się w terminach \(\displaystyle{ Z(S_4)}\) i \(\displaystyle{ Z(S_6)}\) (prawie mnożenie wielomianów) ale do tego konkretnego przypadku się nie przyda.
MAmy \(\displaystyle{ S_4}\) działającą na kolumnach, \(\displaystyle{ S_6}\) na wierszach i w każdej kolumnie \(\displaystyle{ 2}\) krzyżyki.
Niech \(\displaystyle{ (\sigma, \tau)\in S_4\times S_6}\). Interesuje nas liczba:
\(\displaystyle{ S((\sigma,\tau))}\)
układów stałych ze względu na działanie \(\displaystyle{ (\sigma.\tau)}\).
Postaram się trzymać pewien poziom ogólności, choć tutaj wiele się upraszcza.
Niech \(\displaystyle{ s,t}\) będą pewnymi cyklami w rozkładach \(\displaystyle{ \sigma, \tau}\) odpowiednio na rozłączne cykle. Niech \(\displaystyle{ n(s),n(t)}\) to długości tych cykli. Przenumerowując ewentualnie wiersze i kolumny możemy założyć, że nośniki \(\displaystyle{ \supp(s),\supp(t)}\) tych cykli (czyli zbiory numerów kolumn/wierszy permutowanych przez te cykle) to kolejne liczby od 1. To jest \(\displaystyle{ s(1)=2, s(2)=3,...,s(n(s))=1}\) i analogicznie dla \(\displaystyle{ t}\). Krótko mówiąc zakres działania \(\displaystyle{ s,t}\) to prostokąt \(\displaystyle{ n(t)\times n(s)}\) w lewym górnym rogu tablicy. Zauważmy, że ten prostokąt jest niezmienniczy ze względu na działanie \(\displaystyle{ (s,t)}\) wtedy i tylko wtedy, gdy jego przekątne są stałe, to znaczy albo całe przekątne są zakrzyżykowane, albo nie. Liczba przekątnych to \(\displaystyle{ \gcd(n(s),n(t))}\). Przy czym tu rozważamy uogólnione przekątne, czyli rozszerzamy je cyklicznie, w szczególności w tablicy \(\displaystyle{ p\times q}\) dla \(\displaystyle{ \gcd(p,q)=1}\) wszystkie pola leżą na jednej przekątnej.
Stąd ogólny wzór na liczbę prostokątów niezmienniczych na \(\displaystyle{ (s,t)}\) to
\(\displaystyle{ \sum_{i=0}^{\gcd(n(s),n(t))}\binom{\gcd(n(s),n(t))}{i}}\).
Pora więc coś zliczyć w przypadku 6,4,2. Wybierzmy na początek jakiś ciekawy przykład:
\(\displaystyle{ z(\sigma)=x_1x_3}\)
\(\displaystyle{ z(\tau)=x_1x_2x_3}\)
Współczynnik to \(\displaystyle{ 8\cdot 120=960}\) to znaczy w \(\displaystyle{ S_4\times S_6}\) jest \(\displaystyle{ 960}\) par tego samego typu, co \(\displaystyle{ (\sigma,\tau)}\). Mamy 6 możliwych prostokątów. Po narysowaniu nietrudno zliczyć wszystkie możliwe układy o niezmienniczych przekątnych. Jest ich 7. Stąd otrzymujemy wkład do wyniku:
\(\displaystyle{ \frac{7\cdot 960}{24\cdot 720}=\frac{7}{18}}\).
Jest \(\displaystyle{ 55}\) przypadków podziałów prostokątnych, ale wszystkie są łatwe do rozważenia w pamięci.
Moral z tego taki, że wzór ogólny, choć wypisywalny, będzie strasznie długi. Za to nietrudno stosują powyższe rozumowanie wypisać szybki algorytm znajdujący wszystkie możliwe układy. Komponenty tego algorytmu to:
1. Wyznaczenie \(\displaystyle{ Z(S(n))}\).
2. Dla danych \(\displaystyle{ p,q,r}\) podanie liczby możliwych układów krzyżyków o stałych przekątnych w prostokącie o bokach \(\displaystyle{ p,q}\) tak, by w każdej kolumnie było \(\displaystyle{ r}\) krzyżyków - tu można wypisać wzór po prostu: \(\displaystyle{ C\left(\gcd(p,q),\frac{r}{\gcd(p,q)}\right)}\) gdzie \(\displaystyle{ C(i,j)=\binom ij}\) dla całkowitych \(\displaystyle{ j}\) i \(\displaystyle{ C(i,j)=0}\) dla niecałkowitych \(\displaystyle{ j}\).
3. Mając dane zbiory \(\displaystyle{ R_i}\) liczb naturalnych i liczbę naturalną \(\displaystyle{ a}\) podać liczbę możliwości wyboru elementów \(\displaystyle{ r_i}\) ze zbiorów \(\displaystyle{ R_i}\) tak, by \(\displaystyle{ \sum r_i=n}\).