Rozmieszczanie krzyżyków w tabelce

Permutacje. Kombinacje. Wariacje. Rozmieszczanie kul w urnach. Silnie i symbole Newtona. Przeliczanie zbiorów. Funkcje tworzące. Teoria grafów.
vpprof
Użytkownik
Użytkownik
Posty: 456
Rejestracja: 11 paź 2012, o 11:20
Płeć: Mężczyzna
Lokalizacja: Warszawa
Podziękował: 18 razy
Pomógł: 62 razy

Rozmieszczanie krzyżyków w tabelce

Post autor: vpprof » 20 wrz 2013, o 18:30

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:

Kod: Zaznacz cały

x x x - - -
- - - x - -
x x - - x x
- - x x x x
2 2 3 5 6 6
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):

Kod: Zaznacz cały

x x x x - -
x x - - x x
- - x - x x
- - - x - -
1 1 2 3 4 4
— a to już na pierwszy rzut oka nie jest oczywiste.

Ma ktoś lepszy pomysł?
Rekrutacja Instytut Matematyczny, Uniwersytet Wrocławski (gif)

Kartezjusz
Użytkownik
Użytkownik
Posty: 7251
Rejestracja: 14 lut 2008, o 08:31
Płeć: Mężczyzna
Lokalizacja: Z Bielskia-Białej
Podziękował: 3 razy
Pomógł: 940 razy

Rozmieszczanie krzyżyków w tabelce

Post autor: Kartezjusz » 25 wrz 2013, o 11:44

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

vpprof
Użytkownik
Użytkownik
Posty: 456
Rejestracja: 11 paź 2012, o 11:20
Płeć: Mężczyzna
Lokalizacja: Warszawa
Podziękował: 18 razy
Pomógł: 62 razy

Rozmieszczanie krzyżyków w tabelce

Post autor: vpprof » 25 wrz 2013, o 12:23

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:

Kod: Zaznacz cały

x x x - - -
- - - x - -
x x - - x x
- - x x x x
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…

Kartezjusz
Użytkownik
Użytkownik
Posty: 7251
Rejestracja: 14 lut 2008, o 08:31
Płeć: Mężczyzna
Lokalizacja: Z Bielskia-Białej
Podziękował: 3 razy
Pomógł: 940 razy

Rozmieszczanie krzyżyków w tabelce

Post autor: Kartezjusz » 25 wrz 2013, o 12:31

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

vpprof
Użytkownik
Użytkownik
Posty: 456
Rejestracja: 11 paź 2012, o 11:20
Płeć: Mężczyzna
Lokalizacja: Warszawa
Podziękował: 18 razy
Pomógł: 62 razy

Rozmieszczanie krzyżyków w tabelce

Post autor: vpprof » 25 wrz 2013, o 12:38

Czegoś nie rozumiem. Weźmy ten pierwszy przykładowy rozkład z pierwszego posta:

Kod: Zaznacz cały

x x x - - -
- - - x - -
x x - - x x
- - x x x x
Po zamianie wierszy z kolumnami (czyli chodzi o obrót o 90°, tak?) będzie wyglądał tak:

Kod: Zaznacz cały

- - x x
- - x x
- x - x
x - - x
x - x -
x - x -
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…

Kartezjusz
Użytkownik
Użytkownik
Posty: 7251
Rejestracja: 14 lut 2008, o 08:31
Płeć: Mężczyzna
Lokalizacja: Z Bielskia-Białej
Podziękował: 3 razy
Pomógł: 940 razy

Rozmieszczanie krzyżyków w tabelce

Post autor: Kartezjusz » 25 wrz 2013, o 12:45

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?

vpprof
Użytkownik
Użytkownik
Posty: 456
Rejestracja: 11 paź 2012, o 11:20
Płeć: Mężczyzna
Lokalizacja: Warszawa
Podziękował: 18 razy
Pomógł: 62 razy

Rozmieszczanie krzyżyków w tabelce

Post autor: vpprof » 25 wrz 2013, o 12:58

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?

Kartezjusz
Użytkownik
Użytkownik
Posty: 7251
Rejestracja: 14 lut 2008, o 08:31
Płeć: Mężczyzna
Lokalizacja: Z Bielskia-Białej
Podziękował: 3 razy
Pomógł: 940 razy

Rozmieszczanie krzyżyków w tabelce

Post autor: Kartezjusz » 25 wrz 2013, o 13:04

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ń.

vpprof
Użytkownik
Użytkownik
Posty: 456
Rejestracja: 11 paź 2012, o 11:20
Płeć: Mężczyzna
Lokalizacja: Warszawa
Podziękował: 18 razy
Pomógł: 62 razy

Rozmieszczanie krzyżyków w tabelce

Post autor: vpprof » 25 wrz 2013, o 13:44

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.

Kartezjusz
Użytkownik
Użytkownik
Posty: 7251
Rejestracja: 14 lut 2008, o 08:31
Płeć: Mężczyzna
Lokalizacja: Z Bielskia-Białej
Podziękował: 3 razy
Pomógł: 940 razy

Rozmieszczanie krzyżyków w tabelce

Post autor: Kartezjusz » 25 wrz 2013, o 14:08

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

vpprof
Użytkownik
Użytkownik
Posty: 456
Rejestracja: 11 paź 2012, o 11:20
Płeć: Mężczyzna
Lokalizacja: Warszawa
Podziękował: 18 razy
Pomógł: 62 razy

Rozmieszczanie krzyżyków w tabelce

Post autor: vpprof » 25 wrz 2013, o 14:15

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.
Ostatnio zmieniony 25 wrz 2013, o 16:42 przez vpprof, łącznie zmieniany 2 razy.

Kartezjusz
Użytkownik
Użytkownik
Posty: 7251
Rejestracja: 14 lut 2008, o 08:31
Płeć: Mężczyzna
Lokalizacja: Z Bielskia-Białej
Podziękował: 3 razy
Pomógł: 940 razy

Rozmieszczanie krzyżyków w tabelce

Post autor: Kartezjusz » 25 wrz 2013, o 14:29

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

Kamaz
Użytkownik
Użytkownik
Posty: 127
Rejestracja: 13 kwie 2013, o 13:44
Płeć: Kobieta
Pomógł: 21 razy

Rozmieszczanie krzyżyków w tabelce

Post autor: Kamaz » 25 wrz 2013, o 15:13

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.

vpprof
Użytkownik
Użytkownik
Posty: 456
Rejestracja: 11 paź 2012, o 11:20
Płeć: Mężczyzna
Lokalizacja: Warszawa
Podziękował: 18 razy
Pomógł: 62 razy

Rozmieszczanie krzyżyków w tabelce

Post autor: vpprof » 25 wrz 2013, o 15:31

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:

Kod: Zaznacz cały

x x x - - - (A)
x x x - - - (A)
- - - x x x (B)
- - - x x x (B)
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?

Kamaz
Użytkownik
Użytkownik
Posty: 127
Rejestracja: 13 kwie 2013, o 13:44
Płeć: Kobieta
Pomógł: 21 razy

Rozmieszczanie krzyżyków w tabelce

Post autor: Kamaz » 25 wrz 2013, o 16:44

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.

ODPOWIEDZ