szukanie zaawansowane
 [ Posty: 35 ]  Przejdź na stronę 1, 2, 3  Następna strona
Autor Wiadomość
Mężczyzna Offline
PostNapisane: 20 wrz 2013, o 18:30 
Użytkownik

Posty: 453
Lokalizacja: Warszawa
Problem na pewno gdzieś już był, ale chyba nie z taką „oprawą”. Mamy tabelę o w wierszach i 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ć 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 {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 w=4 wiersze, k=6 kolumn i a=2 krzyżyki w każdej kolumnie, mamy {4 \choose 2} =6 możliwych układów krzyżyków w kolumnie, czyli takiemu przykładowemu rozkładowi przypiszemy takie numery:
Kod:
1
2
3
4
5
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 1 do {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:
1
2
3
4
5
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ł? :)
Uniwersytet Wrocławski Instytut Matematyczny - rekrutacja 2018
Góra
Mężczyzna Offline
PostNapisane: 25 wrz 2013, o 11:44 
Użytkownik

Posty: 7360
Lokalizacja: Z Bielskia-Białej
Zamień wiersze z kolumnami. Ile będzie krzyżyków w każdym wierszu.
Góra
Mężczyzna Offline
PostNapisane: 25 wrz 2013, o 12:23 
Użytkownik

Posty: 453
Lokalizacja: Warszawa
No, wtedy będzie a krzyżyków w każdym wierszu. Ale problem będzie zasadniczo ten sam, nie? Bo te 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:
1
2
3
4
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ą {w \choose 2} =  \frac{w^2-w}{2} liczb w zakresie \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…
Góra
Mężczyzna Offline
PostNapisane: 25 wrz 2013, o 12:31 
Użytkownik

Posty: 7360
Lokalizacja: Z Bielskia-Białej
Zauważ że będziesz miał w krzyżyków w każdym wierszu
Góra
Mężczyzna Offline
PostNapisane: 25 wrz 2013, o 12:38 
Użytkownik

Posty: 453
Lokalizacja: Warszawa
Czegoś nie rozumiem. Weźmy ten pierwszy przykładowy rozkład z pierwszego posta:
Kod:
1
2
3
4
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:
1
2
3
4
5
6
- - x x
- - x x
- x - x
x - - x
x - x -
x - x -

W każdym wierszu są a=2 krzyżyki. Przed zamianą w każdej kolumnie były a=2 krzyżyki, ale nie wiem co mi to pomoże…
Góra
Mężczyzna Offline
PostNapisane: 25 wrz 2013, o 12:45 
Użytkownik

Posty: 7360
Lokalizacja: Z Bielskia-Białej
Ewentualnie możesz rozpatrzeć układ równań liniowy wzmiennych z k niewiadomymi z których pewne a w każdej kolumnie jest niezerowych. Co możesz powiedzieć o zamianie wierszy i kolumn?
Góra
Mężczyzna Offline
PostNapisane: 25 wrz 2013, o 12:58 
Użytkownik

Posty: 453
Lokalizacja: Warszawa
Kartezjusz napisał(a):
Ewentualnie możesz rozpatrzeć układ równań liniowy w zmiennych z k niewiadomymi z których pewne 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 napisał(a):
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 a, no i że kolejność wierszy i kolumn nie ma znaczenia. Więc zamienianie jednego z drugim chyba niewiele zmienia… a wg ciebie?
Góra
Mężczyzna Offline
PostNapisane: 25 wrz 2013, o 13:04 
Użytkownik

Posty: 7360
Lokalizacja: Z Bielskia-Białej
na przykład 1 kolumnax, druga y trzecia z czwarta t
Twój układ.
\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ń.
Góra
Mężczyzna Offline
PostNapisane: 25 wrz 2013, o 13:44 
Użytkownik

Posty: 453
Lokalizacja: Warszawa
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ń:
\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:
\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.
Góra
Mężczyzna Offline
PostNapisane: 25 wrz 2013, o 14:08 
Użytkownik

Posty: 7360
Lokalizacja: Z Bielskia-Białej
kwestia oznaczenia zmiennych. t zamieniam na x , z na y , x na t,a y na z
Góra
Mężczyzna Offline
PostNapisane: 25 wrz 2013, o 14:15 
Użytkownik

Posty: 453
Lokalizacja: Warszawa
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 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 426 kopii tych kilkunastu (mniejsza z tym jak to policzyłem). A jeśli 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.
Góra
Mężczyzna Offline
PostNapisane: 25 wrz 2013, o 14:29 
Użytkownik

Posty: 7360
Lokalizacja: Z Bielskia-Białej
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 k razy rozlosować ilość wierszy w każdej kolumnie,ktore będą zawierały pełne miejsca. i podzielić przez w!aby martwić się powtórkami
Góra
Kobieta Offline
PostNapisane: 25 wrz 2013, o 15:13 
Użytkownik

Posty: 128
Dla mnie nawet ten przypadek w=4,k=6,a=2 okazał się ciekawym problemem. Wyszło mi 29, co sprawia że powątpiewam w istnienie prostego kombinatorycznego wzoru.
Góra
Mężczyzna Offline
PostNapisane: 25 wrz 2013, o 15:31 
Użytkownik

Posty: 453
Lokalizacja: Warszawa
Kartezjusz napisał(a):
zostaje nam k razy rozlosować ilość wierszy w każdej kolumnie,ktore będą zawierały pełne miejsca. i podzielić przez w!aby martwić się powtórkami

Rozumiem, że chodzi ci o coś takiego: \frac{{w \choose a}^k}{w!}. Nie jest to niestety rozwiązanie prawidłowe, gdyż w! to liczba permutacji zbioru 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:
1
2
3
4
x x x - - - (A)
x x x - - - (A)
- - - x x x (B)
- - - x x x (B)

wynosi \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 {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? :D
Góra
Kobieta Offline
PostNapisane: 25 wrz 2013, o 16:44 
Użytkownik

Posty: 128
Oto niektóre z nich:

\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 w_1 i w_2 oznacza kolumnę, która ma symbol 'x' w wierszach w_1 i w_2. Dla a=3 zamiast krawędzi musiałyby być trójkąty.

Powyższy rysunek przedstawia te multigrafy, które mają co najmniej 4 multikrawędzie. Jeśli zachodzi potrzeba, mogę narysować też pozostałe.
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 35 ]  Przejdź na stronę 1, 2, 3  Następna strona


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 Rozmieszczanie przedmiotów  ka79zik  1
 rozmieszczanie k różnych kul w n różnych urnach  Z_i_o_M_e_K  1
 rozmieszczanie liter  viki90  7
 Rozmieszczanie cyfr w 4 miejscach  Daisyy  8
 Kombinatoryka - rozmieszczanie kul w pudełkach  cannelle28  0
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl