Matematyka.pl

Problem na pewno gdzieś już był, ale chyba nie z taką „oprawą”. Mamy tabelę o \(\displaystyle{ w}\) wierszach i \(\displaystyle{ k}\) kolumnach. W każdej komórce tej tabeli może być krzyżyk albo nie (coś jak diagram Ferrersa). W każdej kolumnie ma być \(\displaystyle{ a}\) krzyżyków. Kolejność kolumn i kolejność wierszy nie ma znaczenia, więc zmiana kolejności nie tworzy nowego rozkładu krzyżyków. Ile jest rozkładów krzyżyków w tabeli spełniających powyższe warunki?

Ja próbowałem w ten sposób: w każdej kolumnie może być jedna z \(\displaystyle{ {w \choose a}}\) kombinacji, więc każdą z tych kombinacji można ponumerować i każdej kolumnie przypisać taki numer. Na przykład mając \(\displaystyle{ w=4}\) wiersze, \(\displaystyle{ k=6}\) kolumn i \(\displaystyle{ a=2}\) krzyżyki w każdej kolumnie, mamy \(\displaystyle{ {4 \choose 2} =6}\) możliwych układów krzyżyków w kolumnie, czyli takiemu przykładowemu rozkładowi przypiszemy takie numery: Myślniki oznaczają puste kratki. Wtedy tworzenie rozkładów sprowadzałoby się do tworzenia niemalejących ciągów liczb w granicach od \(\displaystyle{ 1}\) do \(\displaystyle{ {w \choose a}}\). (Niemalejących, bo kolejność kolumn się nie liczy, czyli możemy sobie ustalić np. rosnący porządek.)

Szkopuł w tym, że kolejność wierszy też można zmieniać, czyli powyższy rozkład jest równoważny na przykład temu (podaję też numer kombinacji w kolumnie): — a to już na pierwszy rzut oka nie jest oczywiste.

Ma ktoś lepszy pomysł?

Zamień wiersze z kolumnami. Ile będzie krzyżyków w każdym wierszu.

No, wtedy będzie \(\displaystyle{ a}\) krzyżyków w każdym wierszu. Ale problem będzie zasadniczo ten sam, nie? Bo te \(\displaystyle{ a}\) krzyżyków będzie można rozłożyć na różne sposoby, co z kolei będzie kreowało inne rozkłady krzyżyków w całej tabeli.

A dwa rozkłady uważamy za różne, jeśli jednego nie da się otrzymać z drugiego poprzez zmianę kolejności kolumn i/lub wierszy.

Ja jeszcze wpadłem na to, by dla każdej pary wierszy (w tej chwili nie mówię o twojej zamianie wiersze/kolumny) — by dla każdej pary wierszy wypisywać liczby kolumn, które mają krzyżyk w obu wierszach („wspólne kolumny”). Czyli np. w takim rozkładzie: para wierszy #1 i #2 nie posiada żadnej „wspólnej kolumny”, tzn. kolumny, w której byłby krzyżyk i w wierszu #1 i w wierszu #2. Natomiast para #3 i #4 posiada dwie takie wspólne kolumny (są to kolumny piąta i szósta).

Wtedy każdy rozkład byłby opisany sekwencją \(\displaystyle{ {w \choose 2} = \frac{w^2-w}{2}}\) liczb w zakresie \(\displaystyle{ \left\langle 1 ; k \right\rangle}\) — po jednej liczbie dla każdej pary wierszy. Tylko pytanie jest, czy takie przyporządkowanie sekwencji jest bijekcją, czyli czy jednej sekwencji odpowiada tylko jeden rozkład? Nie mam pojęcia jak się zabrać za udowodnienie tego…

Zauważ że będziesz miał w krzyżyków w każdym wierszu

Czegoś nie rozumiem. Weźmy ten pierwszy przykładowy rozkład z pierwszego posta: Po zamianie wierszy z kolumnami (czyli chodzi o obrót o 90°, tak?) będzie wyglądał tak: W każdym wierszu są \(\displaystyle{ a=2}\) krzyżyki. Przed zamianą w każdej kolumnie były \(\displaystyle{ a=2}\) krzyżyki, ale nie wiem co mi to pomoże…

Ewentualnie możesz rozpatrzeć układ równań liniowy \(\displaystyle{ w}\)zmiennych z \(\displaystyle{ k}\) niewiadomymi z których pewne \(\displaystyle{ a}\) w każdej kolumnie jest niezerowych. Co możesz powiedzieć o zamianie wierszy i kolumn?

Kartezjusz pisze:Ewentualnie możesz rozpatrzeć układ równań liniowy \(\displaystyle{ w}\) zmiennych z \(\displaystyle{ k}\) niewiadomymi z których pewne \(\displaystyle{ a}\) w każdej kolumnie jest niezerowych.

A mógłbyś podać przykład takiego układu równań dla przykładowego rozkładu z poprzedniego posta? Bo nie jestem w tej materii zbyt lotny…

Kartezjusz pisze:Co możesz powiedzieć o zamianie wierszy i kolumn?

Szczerze mówiąc, niewiele, bo w moim problemie w zasadzie nie gra roli jak zapiszemy krzyżyki, warunek jest tylko taki że w każdej „linii” (kolumnie albo wierszu) ma być ich łącznie \(\displaystyle{ a}\), no i że kolejność wierszy i kolumn nie ma znaczenia. Więc zamienianie jednego z drugim chyba niewiele zmienia… a wg ciebie?

na przykład 1 kolumna\(\displaystyle{ x}\), druga \(\displaystyle{ y}\) trzecia \(\displaystyle{ z}\) czwarta \(\displaystyle{ t}\)
Twój układ.
\(\displaystyle{ \begin{cases} 0x+0y+z+t=0 \\ 0x+0y+z+t=0 \\ 0x+y+0z+t=0 \\ x+0y+0z+t=0 \\ x+0y+z+0t=0 \\ x+0y+z+0t=0 \end{cases}}\)

Z algebry liniowej wiesz,że całe wiersze i całe kolumny możesz zmieniać miejscami nie zagrażając postaci rozwiazań.

OK, ale cały problem zasadzał się na tym, że niektóre układy wyglądają na różne a w rzeczywistości są takie same i chodzi o to, żeby ich nie zliczać; żeby zliczać tylko te „unikalne”. Każdą tabelkę mogę przekształcić na układ równań (zresztą zanim napisałem na forum to właśnie oznaczałem sobie kolumny jako a, b, c itd., dopiero potem wpadłem na pomysł z krzyżykami) — tylko że to mi nie ułatwia odfiltrowywania układów różniących się tylko kolejnością.

Podany przez ciebie układ równań:
\(\displaystyle{ \begin{cases} z+t=0 \\ z+t=0 \\ y+t=0 \\ x+t=0 \\ x+z=0 \\ x+z=0 \end{cases}}\)
będzie przedstawiał rozkład, który uważamy za identyczny z tym:
\(\displaystyle{ \begin{cases} y+z=0 \\ y+z=0 \\ x+t=0 \\ x+z=0 \\ x+y=0 \\ x+y=0 \end{cases}}\)
co nie jest oczywiste.

A chodzi o to, by zliczyć wszystkie „unikalne” rozkłady krzyżyków, żeby móc stworzyć algorytm który wszystkie je po kolei generuje.

kwestia oznaczenia zmiennych. t zamieniam na x , z na y , x na t,a y na z

No właśnie to jest całe clou zmienianie oznaczeń zminnych odpowiada zmianie kolejności kolumn z krzyżykami (co chyba wizualnie jest prostsze). Tylko że muszę opracować algorytm, który będzie generował wszystkie „unikalne” rozkłady a nie takie, które będą kopiami innych ze zmienioną kolejnością kolumn i/lub wierszy.

W tym prostym przypadku dla \(\displaystyle{ w=4,k=6,a=2}\) jest może kilka–kilkanaście takich rozkładów, podczas gdy metoda opisana przeze mnie w pierwszym poście (tworzenie niemalejących ciągów liczb-numerów kombinacji dla każdej kolumny) wygeneruje mi \(\displaystyle{ 426}\) kopii tych kilkunastu (mniejsza z tym jak to policzyłem). A jeśli \(\displaystyle{ k,w}\) będą w granicach tysiąca czy dziesiątków tysięcy, to na taką stratę czasu obliczeniowego braknie mi życia (mnie, albo Ziemi, albo Wszechświatowi) — stąd mój problem.

Właśnie przez to,że dowiedliśmy tej niezmienności mamy pełną nierozróżnialność. zamiana kolejności wierszy i kolumn nam nic nie znieni, zatem zostaje nam \(\displaystyle{ k}\) razy rozlosować ilość wierszy w każdej kolumnie,ktore będą zawierały pełne miejsca. i podzielić przez \(\displaystyle{ w!}\)aby martwić się powtórkami

Dla mnie nawet ten przypadek \(\displaystyle{ w=4,k=6,a=2}\) okazał się ciekawym problemem. Wyszło mi \(\displaystyle{ 29}\), co sprawia że powątpiewam w istnienie prostego kombinatorycznego wzoru.

Kartezjusz pisze:zostaje nam \(\displaystyle{ k}\) razy rozlosować ilość wierszy w każdej kolumnie,ktore będą zawierały pełne miejsca. i podzielić przez \(\displaystyle{ w!}\)aby martwić się powtórkami

Rozumiem, że chodzi ci o coś takiego: \(\displaystyle{ \frac{{w \choose a}^k}{w!}}\). Nie jest to niestety rozwiązanie prawidłowe, gdyż \(\displaystyle{ w!}\) to liczba permutacji zbioru \(\displaystyle{ w}\)-elementowego, oczywiście przy założeniu, że każdy element tego zbioru (czyli każdy wiersz naszego rozkładu) jest inny — a tu się to założenie nie stosuje. Np. liczba kolejności wierszy takiego rozkładu: wynosi \(\displaystyle{ \frac{4!}{2!2!} = 6}\): AABB, ABAB, ABBA, BAAB, BABA, BBAA — bo ma on dwie pary identycznych wierszy a nie 4 różne wiersze.

Ponadto \(\displaystyle{ {w \choose a}^k}\) da nam nieposortowane kolumny, tak jak gdyby kolejność kolumn miała znaczenie — tak mi się wydaje…

Kamaz, jeśli nie sprawiłoby ci to problemu, mogłabyś wypisać te 29 rozkładów?

Oto niektóre z nich:

\(\displaystyle{ \begin{picture}(0,0)
\put(0,0){\line(1,0){40}}
\put(0,0){\line(3,5){20}}
\put(40,0){\line(-3,5){20}}
\put(0,0){\line(3,2){20}}
\put(40,0){\line(-3,2){20}}
\put(20,13.3333){\line(0,1){20}}
\put(0,0){\circle*{4}}
\put(40,0){\circle*{4}}
\put(20,13.3333){\circle*{4}}
\put(20,33.3333){\circle*{4}}

\put(60,0){
\put(0,0){\line(1,0){40}}
\put(0,0){\line(0,1){40}}
\put(0,40){\line(1,0){40}}
\put(40,0){\line(0,1){40}}
\qbezier(0,0)(30,10)(40,40)
\qbezier(0,0)(10,30)(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}}
\put(0,40){\line(1,0){40}}
\put(0,0){\line(1,1){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(0,-60){
\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,40)(20,30)(40,40)
\qbezier(0,40)(20,50)(40,40)
\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,40){\line(1,0){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){
\put(0,0){\line(1,0){40}}
\put(0,0){\line(0,1){40}}
\put(0,40){\line(1,0){40}}
\put(40,0){\line(0,1){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(0,-120){
\put(0,0){\line(1,0){40}}
\qbezier(0,0)(5,20)(20,30)
\qbezier(0,0)(15,10)(20,30)
\put(40,0){\line(-2,3){20}}
\qbezier(20,30)(15,40)(20,50)
\qbezier(20,30)(25,40)(20,50)
\put(0,0){\circle*{4}}
\put(40,0){\circle*{4}}
\put(20,30){\circle*{4}}
\put(20,50){\circle*{4}}
}


\put(60,-120){
\qbezier(0,0)(20,10)(40,0)
\qbezier(0,0)(20,-10)(40,0)
\put(0,0){\line(2,3){20}}
\put(40,0){\line(-2,3){20}}
\qbezier(20,30)(15,40)(20,50)
\qbezier(20,30)(25,40)(20,50)
\put(0,0){\circle*{4}}
\put(40,0){\circle*{4}}
\put(20,30){\circle*{4}}
\put(20,50){\circle*{4}}
}


\put(120,-120){
\qbezier(0,0)(20,10)(40,0)
\qbezier(0,0)(20,-10)(40,0)
\qbezier(0,0)(5,20)(20,30)
\qbezier(0,0)(15,10)(20,30)
\put(40,0){\line(-2,3){20}}
\put(20,30){\line(0,1){20}}
\put(0,0){\circle*{4}}
\put(40,0){\circle*{4}}
\put(20,30){\circle*{4}}
\put(20,50){\circle*{4}}
}



\put(0,-180){
\put(0,0){\line(1,0){40}}
\qbezier(0,0)(5,20)(20,30)
\qbezier(0,0)(15,10)(20,30)
\qbezier(40,0)(35,20)(20,30)
\qbezier(40,0)(25,10)(20,30)
\put(20,30){\line(0,1){20}}
\put(0,0){\circle*{4}}
\put(40,0){\circle*{4}}
\put(20,30){\circle*{4}}
\put(20,50){\circle*{4}}
}



\put(60,-180){
\put(0,0){\line(1,0){40}}
\qbezier(0,0)(20,10)(40,0)
\qbezier(0,0)(20,-10)(40,0)
\put(0,0){\line(2,3){20}}
\put(40,0){\line(-2,3){20}}
\put(20,30){\line(0,1){20}}
\put(0,0){\circle*{4}}
\put(40,0){\circle*{4}}
\put(20,30){\circle*{4}}
\put(20,50){\circle*{4}}
}



\put(120,-180){
\put(0,0){\line(1,0){40}}
\put(0,0){\line(2,3){20}}
\qbezier(0,0)(5,20)(20,30)
\qbezier(0,0)(15,10)(20,30)
\put(40,0){\line(-2,3){20}}
\put(20,30){\line(0,1){20}}
\put(0,0){\circle*{4}}
\put(40,0){\circle*{4}}
\put(20,30){\circle*{4}}
\put(20,50){\circle*{4}}
}



\put(0,-240){
\put(0,0){\line(1,0){40}}
\put(0,0){\line(2,3){20}}
\put(40,0){\line(-2,3){20}}
\put(20,30){\line(0,1){20}}
\qbezier(20,30)(15,40)(20,50)
\qbezier(20,30)(25,40)(20,50)
\put(0,0){\circle*{4}}
\put(40,0){\circle*{4}}
\put(20,30){\circle*{4}}
\put(20,50){\circle*{4}}
}

\put(-5,45){.}
\put(170,-245){.}

\end{picture}}\)

Wierzchołki multigrafu oznaczają wiersze, a krawędzie kolumny. Krawędź pomiędzy wierzchołkami \(\displaystyle{ w_1}\) i \(\displaystyle{ w_2}\) oznacza kolumnę, która ma symbol 'x' w wierszach \(\displaystyle{ w_1}\) i \(\displaystyle{ w_2}\). Dla \(\displaystyle{ a=3}\) zamiast krawędzi musiałyby być trójkąty.

Powyższy rysunek przedstawia te multigrafy, które mają co najmniej \(\displaystyle{ 4}\) multikrawędzie. Jeśli zachodzi potrzeba, mogę narysować też pozostałe.