Witam!
Proponuję sklasyfikować sposoby rozmieszczenia X-ów według ich liczby w wierszach. Zamiana miejscami kolumn nie zmienia liczby X-ów w wierszu, a zamiana wierszy zmienia jedynie kolejność. Wystarczy zatem wybrać jako reprezentanta układ, w którym liczby X-ów w wierszach są np. w porządku rosnącym.
Takie reprezentanty można przedstawić w postaci diagramu Younga. Nie pamiętam niestety wzoru na liczbę diagramów Younga o n polach. Postaram się w wolnej chwili coś poszukać - choć pewnie nie ma nic po polsku.
Liczba diagramów Younga o n polach, czyli szukana liczba układów, to liczba różnych rozkładów liczby n na sumę liczb naturalnych w porządku rosnącym.
Może to coś pomoże...
Pozdrawiam,
sG
-- 26 września 2013, 14:38 --
Aha, teraz doczytałem... Rzeczywiście w literaturze funkcjonuje również nazwa diagram Ferresa, aczkolwiek nigdy nie spotkałem jej w tekście matematycznym. Stąd moja nieuwaga...-- 26 września 2013, 15:06 --OK. Mam. Szukana liczba rozkładów to liczba różnych partycji zbioru n-elementowego. Jest to też liczba różnych rozwiązań w liczbach naturalnych r-nia \(\displaystyle{ x_1+2x_2+3x_3+\cdots+nx_n=n}\)
Kamaz, bardzo ładne grafy (jak się takie robi ), trochę nieporęczne, ale i tak dzięki wielkie!
Sir George, mówisz o podziale liczby \(\displaystyle{ ak}\) na nie więcej niż \(\displaystyle{ w}\) składników nie większych od \(\displaystyle{ k}\) — ten wbrew pozorom trudny problem błyskotliwie rozwiązał arek1357 tu: https://www.matematyka.pl/309420.htm (na samym końcu wątku).
Niestety nie opisuje on naszej sytuacji — zwróć uwagę, że np. podział \(\displaystyle{ 12=3+3+3+3}\) generuje kilka „unikalnych” rozkładów:
OK, myślę, że już rozwiązałem na piechotę przypadek \(\displaystyle{ k=6,w=4,a=2}\). Kamaz, mówisz, że wyszło ci \(\displaystyle{ 29}\) rozkładów — ja naliczyłem \(\displaystyle{ 32}\). Czy zgodzisz się przedstawić te pozostałe 16 rozkładów?
Ja swoje przedstawiam poniżej; odcyfrowałem twoje multigrafy i wychodzi na to, że pokrywają się rozkłady nr: 17,18,19,20,24,25,26,27,28,29,30,31,32.
Rozkład 1
x x x x x x
x x x x x x
- - - - - -
- - - - - -
Rozkład 2
x x x x x x
x x x x x -
- - - - - x
- - - - - -
Rozkład 3
x x x x x -
x x x x x -
- - - - - x
- - - - - x
Rozkład 4
x x x x x x
x x x x - -
- - - - x x
- - - - - -
Rozkład 5
x x x x - -
x x x x - -
- - - - x x
- - - - x x
Rozkład 6
x x x x x x
x x x x - -
- - - - x -
- - - - - x
Rozkład 7
x x x x x -
x x x x - x
- - - - x x
- - - - - -
Rozkład 8
x x x x x -
x x x x - x
- - - - x -
- - - - - x
Rozkład 9
x x x x x -
x x x x - -
- - - - x x
- - - - - x
Rozkład 10
x x x x x x
x x x - - -
- - - x x x
- - - - - -
Rozkład 11
x x x - - -
x x x - - -
- - - x x x
- - - x x x
Rozkład 12
x x x x x x
x x x - - -
- - - x x -
- - - - - x
Rozkład 13
x x x x x -
x x x - - -
- - - x x x
- - - - - x
Rozkład 14
x x x x x -
x x x - - x
- - - x x -
- - - - - x
Rozkład 15
x x x x x -
x x x - - x
- - - x x x
- - - - - -
Rozkład 16
x x x x - -
x x x - - -
- - - x x x
- - - - x x
Rozkład 17
x x x x x -
x x x - - x
- - - x - x
- - - - x -
Rozkład 18
x x x x x -
x x x - - -
- - - x - x
- - - - x x
Rozkład 19
x x x x - -
x x x - x -
- - - x - x
- - - - x x
Rozkład 20
x x x x - -
x x x - x -
- - - x x x
- - - - - x
Rozkład 21
x x x x x x
x x - - - -
- - x x - -
- - - - x x
Rozkład 22
x x x x - -
x x - - - -
- - - - x x
- - x x x x
Rozkład 23
x x x x - -
x x - - x x
- - x x x x
- - - - - -
Rozkład 24
x x x x x -
x x - - - x
- - x x - x
- - - - x -
Rozkład 25
x x x x x -
x x - - - x
- - x - - x
- - - x x -
Rozkład 26
x x x x - -
x x - - x -
- - x x - x
- - - - x x
Rozkład 27
x x x x - -
x x - - x -
- - x x x x
- - - - - x
Rozkład 28
x x x x - -
x x - - - -
- - x - x x
- - - x x x
Rozkład 29
x x x - - -
x x - x - -
- - x - x x
- - - x x x
Rozkład 30
x x x x - -
x x - - x x
- - x - x -
- - - x - x
Rozkład 31
x x x x - -
x - - - x x
- x x - x -
- - - x - x
Rozkład 32
x x x - - -
x - - x x -
- x - x - x
- - x - x x
Na wszystkich możliwych układach spełniających założenia działa grupa \(\displaystyle{ S_w\times S_k}\) permutacji wierszy i kolumn. Nas interesuje liczba \(\displaystyle{ N}\) orbit tego działania.
W charakterze rozgrzewki prostsze zadanie.
\(\displaystyle{ X}\) oznacza zbiór wszystkich układów bez utożsamiania tych równoważnych, takich, że w każdym wierszu jest \(\displaystyle{ a}\) krzyżyków.
\(\displaystyle{ W}\) oznacza zbiór orbit działania \(\displaystyle{ S_w}\) na zbiorze \(\displaystyle{ X}\), czyli zbiór orbit ze względu na permutacje wierszy.
Liczbę \(\displaystyle{ |W|}\) można nietrudno wyznaczyć. Następnie nieco modyfikując ideę, lecz istotnie komplikując rachunki, można wyznaczyć liczbę orbit działania \(\displaystyle{ S_w \times S_k}\) na zbiorze wszystkich układów spełniających założenia, czyli liczbę, o którą chodzi w zadaniu.
Zaczniemy więc od \(\displaystyle{ |W|}\), rozgrzewki.
Liczba, której szukamy, to liczba orbit działania \(\displaystyle{ S_w}\) na układy z \(\displaystyle{ X}\), czyli, na mocy lematu Burnside'a:
gdzie \(\displaystyle{ S(\sigma)}\) to zbiór układów niezmienniczych ze względu na permutację wierszy \(\displaystyle{ \sigma}\) (zbiór, a nie jego liczność - przyda się to później). Niech \(\displaystyle{ \sigma}\) będzie iloczynem rozłącznych cykli długości: \(\displaystyle{ C=(c_1,...,c_i)}\), dla \(\displaystyle{ c_{i+1}\ge c_i,}\)\(\displaystyle{ \sum c_i=w}\). Układy stałe ze względu na \(\displaystyle{ \sigma}\) łatwo zliczyć, bo to takie, które mają jednakowe wiersze o numerach z tego samego cyklu. Nietrudno też jest zliczyć wszystkie permutacje o tej samej sygnaturze, czyli będące iloczynem rozłącznych cykli długości \(\displaystyle{ C=(c_1,...,c_i)}\). Zbiór możliwych istotnie różnych sygnatur \(\displaystyle{ \mathcal{C}}\) jest łatwy do wyznaczenia, bo to podziały zbioru \(\displaystyle{ w}\)-elementowego na rozłączne podzbiory.
gdzie \(\displaystyle{ L(C)}\) to liczba permutacji o sygnaturze \(\displaystyle{ C}\), zaś \(\displaystyle{ S(C)}\) to liczba układów stałych ze względu na działanie permutacji o sygnaturze \(\displaystyle{ C}\). Oczywiście formuła będzie dość długa:
Naed Nitram, to jest chyba najbardziej obiecujący sposób potraktowania problemu, jeszcze się przez niego przegryzam, ale mógłbyś tymczasem szybko pokazać, jak on by działał dla omawianego \(\displaystyle{ k=6,w=4,a=2}\)?
Ż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:
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:
Do wyznaczenia indeksów \(\displaystyle{ S_n}\) bezpośrednio na palcach, co mnie się wydaje najszybsze, wystarcza cierpliwość i elementarna kombinatoryka.
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
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:
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}\).
Naed Nitram, wolno mi idzie przegryzanie się przez te wszystkie zagadnienia, głównie z braku czasu, ale dopytam jeszcze tylko:
Naed Nitram pisze: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}\).
Czy tu chodzi o jakiś podział \(\displaystyle{ n}\)? I co oznacza tutaj \(\displaystyle{ n}\), bo najpierw, jako indeks dolny przy \(\displaystyle{ S}\) oznaczało grupę permutacji, później oznaczało długość danych cykli z rozkładów na cykle danych permutacji — a tu?
No i jeszcze odnośnie twojego pierwszego posta:
Naed Nitram pisze:Liczba, której szukamy, to liczba orbit działania \(\displaystyle{ S_w}\) na układy z \(\displaystyle{ X}\), czyli, na mocy lematu Burnside'a:
Łatwo jest zamieniać kombinację kolumnową na jej numer i odwrotnie, więc jest to bardzo pożyteczne przypisywać rozkładom sekwencje numerów kombinacji kolumnowych, bo zamiast krzyżyków mamy numerki (czyli prościej).
Każdą sekwencję numerków możemy uporządkować w kolejności np. niemalejącej — nie musimy więc martwić się permutacjami kolumn, tylko generować po prostu niemalejące ciągi numerów w zakresie \(\displaystyle{ \left[ 1; {w \choose a} \right]}\). Takich ciągów jest tyle ile kombinacji z powtórzeniami, czyli — tak jak napisałeś w którejś wiadomości — \(\displaystyle{ { {w \choose a} +k-1 \choose k}}\).
To oszacowanie daje dla \(\displaystyle{ k=6,\ w=4,\ a=2}\) liczbę rozkładów \(\displaystyle{ {11 \choose 6} = 462}\) czyli dość bliską „prawdziwym” \(\displaystyle{ 32}\) rozkładom.
Ponieważ permutacja wierszy jest dowolna, każdą kombinację kolumnową możemy zamienić na kombinację nr 1. Oczywiście inne kolumny zamienią się na co innego, ale ważne jest, że każdą sekwencję możemy zamienić na sekwencję zaczynającą się od "1". Stąd też wystarczy analizować sekwencje zaczynające się od "1" — pozostałe będą ich kopiami.
Powyższe stwierdzenie pozwala jeszcze lepiej oszacować liczbę rozkładów, mianowicie skoro na pierwszym miejscu stoi zawsze "1", to mamy \(\displaystyle{ k-1}\) miejsc na nasz niemalejący ciąg liczb, a zatem takich ciągów mamy \(\displaystyle{ { {w \choose a} +k-2 \choose k-1}}\), co daje nam zamiast \(\displaystyle{ 462}\) rozkładów \(\displaystyle{ {10 \choose 5} =252}\) rozkłady — wciąż dużo.
Mamy ciągi zaczynające się od jedynki i wśród nich mamy grupy izomorficznych ciągów. Po pierwsze dwa ciągi mogą być izomorficzne tylko wtedy, gdy mają takie same liczby identycznych kolumn, czyli jak gdyby „powstają” z tego samego podziału liczby kolumn (warunek konieczny niewystarczający), np. 6=2+2+1+1 i ciągi \(\displaystyle{ 112234 \sim 122336}\).
Po drugie, skoro każda sekwencja zaczyna się od "1", to wydaje mi się, że wszystkie kopie danej sekwencji powstaną z podstawienia "1" za jakąś inną liczbę tej sekwencji, np. powyższy izomorfizm powstał z podstawienia \(\displaystyle{ 3 \mapsto 1}\) i permutacji wierszy 1432 (bo zauważmy, że jeśli chcemy zamienić 3 na 1, to mamy do wyboru permutacje 1423,1432,4123,4132).
To daje możliwość generowania małej liczby rozkładów i odrzucania tych izomorficznych. Jeszcze trzeba popracować nad tym, żeby stworzyć algorytm generujący następny (oczywiście nieizomorficzny) rozkład na podstawie danego rozkładu.-- 14 lut 2014, o 12:03 --
Ta ilość powinna być oporna na kombinację wierszową i kolumnową,
gdzie P to jak wiadomo rozkład liczby na sumy nierosnące
Według mnie tu nie chodzi o \(\displaystyle{ k \ge {w \choose a}}\) ale o to, że \(\displaystyle{ a=1 \vee a=w-1}\). I wtedy dla każdego podziału \(\displaystyle{ k}\) będzie tylko jeden rozkład, nie wiem co prawda jak to udowodnić, ale to nieważne w tej chwili.
Bo zobacz, w przypadku gdy \(\displaystyle{ k = {w \choose a}}\) wcale tak być nie musi, zob. powyższe rozkłady dla \(\displaystyle{ k=6,\ {w \choose a}= {4 \choose 2}=6}\). Na przykład dla podziału \(\displaystyle{ 6=5+1}\) mamy dwa rozkłady: nr 2 i nr 3…
No ale to za mało, powinno być 32. Spójrz na nie 343812.htm#p5139741
Ja z kolei zauważyłem coś ciekawego, związek liczby składników podziału kolumn na klasy z tym, jakie te kolumny mogą być, ale potem napiszę o tym.
-- 14 lut 2014, o 14:09 --
arek1357 pisze:
\(\displaystyle{ 6=5+1}\)
\(\displaystyle{ 6=4+2}\)
\(\displaystyle{ 6=3+3}\)
dla podwójnego będzie trzy niezależne rozkłady!
Zauważ, że są 2 rozkłady dla 5+1, 2 rozkłady dla 4+2 i 2 rozkłady dla 3+3.
-- 14 lut 2014, o 15:10 --
arek1357 pisze:
Ale może być również:
\(\displaystyle{ 3}\) klasy abstrakcji co generuje \(\displaystyle{ 3}\) niezależne rozkłady
\(\displaystyle{ 4}\) klasy abstrakcji co generuje \(\displaystyle{ 2}\) niezależne rozkłady
\(\displaystyle{ 5}\) klasy abstrakcji co generuje \(\displaystyle{ 1}\) niezależny rozkład
\(\displaystyle{ 6}\) klasy abstrakcji co generuje \(\displaystyle{ 1}\) niezależny rozkład
\(\displaystyle{ 1}\) klasa abstrakcji co generuje \(\displaystyle{ 1}\) niezależny rozkład
co razem daje 11 rozkładów...
Niestety, nadal obstaję przy tym że tych rozkładów jest więcej, konkretnie 32, zresztą niezależnie do tego samego wyniku doszła Kamaz robiąc swoje grafy. Rozumiem że twoje klasy abstrakcji to składniki podziału liczby kolumn tak?
Więc te liczby które ty oznaczasz „niezależny rozkład” to nie rozkład tylko podział liczby kolumn na składniki. Ale w ramach jednego podziału jest więcej niż jeden rozkład krzyżyków. Na przykład podziały na 3 składniki są takie: 6=4+1+1=3+2+1=2+2+2. Ale to nie znaczy że każdy z tych podziałów generuje jeden rozkład — przeciwnie, pierwszy generuje 4, drugi 5, trzeci 3, czyli 12 rozkładów. Są to rozkłady o numerach 6–9, 12–16, 21–23. Są one rozpisane tu 343812.htm#p5139741-- 18 lut 2014, o 13:13 --Jeszcze dorzucę może trywialne spostrzeżenie ale jednak. Otóż każdą kombinację kolumnową możemy przekształcić na "1", więc w szczególności możemy tego dokonać na kombinacji powtarzającej się w ramach danego rozkładu najwięcej razy, czyli tej najdłuższej, np. zamiast 112666 możemy mieć 111266. Przy tworzeniu nowych rozkładów mając dany podział liczby kolumn sprowadza się to po prostu do przypisania "1" największemu składnikowi tego podziału. W ten sposób jeszcze bardziej zawęża się zbiór tworzonych rozkładów.
A co do tego:
vpprof pisze:związek liczby składników podziału kolumn na klasy z tym, jakie te kolumny mogą być
chodziło o to, że na przykładzie tych 32 rozkładów zauważyłem, że mając podział kolumn na 1 składnik możemy użyć tylko kombinacji "1" (oczywiste), na 2 składniki — tylko "2" i "6" (więc mamy tylko sekwencje 111112, 111116, 111122, 111166), na 3 składniki — wszystkich kombinacji, ale tu już się to komplikuje, bo np. te rozkłady są nieizomorficzne:
111223
111224
111225
111226
ale te już są izomorficzne:
111266
111366
111466
111566
Porobiłem trochę rozkładów na mniejszych wartościach i ewidentne jest, że jeden podział liczby kolumn nie generuje tylko jednego rozkładu, nawet jeśli tych kolumn jest tak mało jak 2. Załóżmy \(\displaystyle{ k=2,\ w=4,\ a=2}\).
Mamy podział 2=2 i tu zawsze jest tylko jeden rozkład, oczywiście o sekwencji "11", czyli:
x x
x x
– –
– –
oraz podział 2=1+1 i tu jak byk stoją dwa nieizomorficzne rozkłady i nie ma sposobu, żeby z jednego dostać drugi!
12(=13=14=15)
x x
x –
– x
– –
oraz
16
x –
x –
– x
– x
A poza tym to nieprawda co wcześniej napisałem, że znaczenie ma tylko liczba składników podziału — bo oczywiście przy np. 6=2+2+2 mamy mniej rozkładów niż przy 6=3+2+1 (bo w pierwszym przypadku kolumny mogą się „wymieniać” a w drugim nie).
Dochodzi tu jeszcze jedna sprawa mianowicie węzły jeśli weźmiemy dwie kolumny rozkładu
a krzyżyków to ważne jest ile mają wspólnych wierszy tzn. węzłów.
I teraz tyle będzie różnych rozkładów ile będzie różnych węzłów ,permutacje poziome nie zmieniają
ilości węzłów węzły są niezmiennicze!
I liczenie ile jest węzłów jest dość kłopotliwe chyba.
Chyba o czymś podobnym myślałem. Tyle że nazywam to „polami”, np. jeśli chcielibyśmy budować każdy rozkład zaczynając od jednej kolumny i dodając następne (i na każdym kroku pytając się spośród ilu różnych kolumn możemy tę kolumnę do dodania wybrać), to tworzą się takie pola o różnej wielkości, np. poniżej każde pole jest oznaczone innym kolorem:
x x x x
x x x x
x x x x x x x -
x x x - - - - x
- - - x
I teraz jeśli chcę dodać piątą kolumnę z pięcioma krzyżykami to muszę te krzyżyki jakoś rozlokować w tych polach, czyli mam tyle możliwości ile jest rozwiązań r-nia: \(\displaystyle{ \begin{cases}
r+g+b=5 \\
r \in [1;3] \\
g \in [1;2] \\
b \in [1;2]
\end{cases}}\)
No ja powiem tak żeby była pełna jasność.
Najpierw odrzucam identyczne kolumny bo są niepotrzebne biorę kolumny różne między sobą!
i oznaczam ilość węzłów między dwiema kolumnami np pierwszą i drugą np:
\(\displaystyle{ a_{1,2}=3}\) trzy węzły czyli trzy krzyżyki w obu kolumnach w tym samym wierszu
można przyjąć, że: \(\displaystyle{ a_{i,i}=a}\) , oraz: \(\displaystyle{ a_{i,j}=a_{j,i}}\).
Oczywiście ponieważ kolumny są różne ilość węzłów
musi być mniejsza niż a.
I teraz łatwo zaobserwować, że permutacja kolumn nie zmienia ilości węzłów między dowolnymi kolumnami. Widać że tyle ile jest różnych rozkładów węzłów tyle będzie niezależnych układów macierzy.
Czyli permutacja pozioma nie zmienia wielkości(szerokości klas abstrakcji) równych między sobą kolumn,
oraz nie zmienia układu węzłów między kolumnami.
\(\displaystyle{ a_{i,j}}\) (ilości węzłów)
jak widać tworzą macierz kwadratową symetryczną na przekątnej głównej są \(\displaystyle{ a}\)
-- 24 marca 2014, 14:24 --
x -
x x
x x
- x
np w tym przypadku:
dwie kolumny , cztery wiersze i dwa węzły.
macierz:
\(\displaystyle{ a_{1,2}=a_{2,1}=2}\)
\(\displaystyle{ a_{1,1}=a_{2,2}=3}\)
Niestety układy węzłów nie są niezależne do końca ilość węzłów między np. trzecią i czwartą kolumną
może implikować ilość węzłów między pierwszą a czwartą kolumną itd...
-- 25 marca 2014, 14:53 --
Zauważyłem jeszcze , że zachodzi tu z tymi węzłami tw. Sylwestra.
Węzły mogą być szerokie na dwie, trzy, cztery , itd kolumny,
dodając i odejmując na przemian otrzymamy ilość zajętych wierszy w całej macierzy.
-- 25 marca 2014, 16:30 --
węzły mogą być szerokie na:
\(\displaystyle{ 1,2,3,...,k-1}\)
czyli w jednym wierszu jest możliwych węzłów:
\(\displaystyle{ k-1}\) o długości \(\displaystyle{ 1}\)
\(\displaystyle{ k-2}\) o długości \(\displaystyle{ 2}\)
.............................................
\(\displaystyle{ 1}\) o długości \(\displaystyle{ k-1}\)
Czyli węzłów przypadających na jeden wiersz jest możliwych:
\(\displaystyle{ \frac{k(k-1)}{2}}\)
Oczywiście wszystkie możliwości nie zostaną wykorzystane nigdy i dlatego nie będzie aż tak różowo-- 25 marca 2014, 16:42 --A z tym tw. Sylwestra będzie tak:
