bijekcja między rodzinami obiektów kombinatorycznych

kalol · Post autor: **kalol** » 15 mar 2011, o 17:35

treść zadania:

Wskazać bijekcję między następującymi rodzinami obiektów kombinatorycznych:
1) rozmieszczenia k identycznych kul w n oznaczonych szufladkach, nie pozostawiające żadnej szufladki pustej;
2) podziały liczby k na n uporządkowanych, całkowitoliczbowych i dodatnich składników;
3) ciągi binarne złożone z n-1 jedynek i k-n zer.

czy ktoś pomógłby mi rozwiązać te zadanie? z góry dziękuję.

norwimaj · Post autor: **norwimaj** » 15 mar 2011, o 21:51

z 1 do 2:
Liczba kul w \(\displaystyle{ i}\)-tej szufladzie to \(\displaystyle{ i}\)-ty składnik sumy.

z 2 do 3:
Składnik równy \(\displaystyle{ t}\) przechodzi na \(\displaystyle{ t-1}\) zer.
Znak \(\displaystyle{ +}\) przechodzi na jedynkę.

kalol · Post autor: **kalol** » 16 mar 2011, o 08:36

\(\displaystyle{ x_{1}+x_{2}+...+x_{n}=k}\)
\(\displaystyle{ x_{i}}\) - liczba kul wpadających w i-tą szufladę
jest to ciąg binarny
00...0100...01...100...0

czy tak jest z 1 do 3?

ale nadal nie bardzo rozumiem...

norwimaj · Post autor: **norwimaj** » 16 mar 2011, o 08:53

Musisz jeszcze powiedzieć, ile jest zer w ciągach, czyli co znaczą trzy kropeczki.

Można też po prostu stwierdzić, że bijekcja z 1 do 3 jest złożeniem poprzednich dwóch.

kalol · Post autor: **kalol** » 17 mar 2011, o 07:25

a więc jest k-n zer i n-1 jedynek chyba coś zaczynam rozumieć dzięki

norwimaj · Post autor: **norwimaj** » 17 mar 2011, o 08:12

Tyle zer jest w sumie, i dobrze bo tak miało być. Ale Ty musisz dokładnie zdefiniować bijekcję. To znaczy że jeśli dasz komuś przykład rozmieszczenia kul w szufladach, i opis Twojej bijekcji, to ten ktoś na tej podstawie może jednoznacznie stwierdzić, jakiemu konkretnie ciągowi odpowiada to rozmieszczenie kul.

Na przykład możesz w ten sposób:
Jeśli w pierwszej szufladzie znajduje się \(\displaystyle{ i}\) kul, to przed pierwszą jedynką znajduje się \(\displaystyle{ i-1}\) zer.
Jeśli w ostatniej szufladzie znajduje się \(\displaystyle{ i}\) kul, to po ostatniej jedynce znajduje się \(\displaystyle{ i-1}\) zer.
Dla \(\displaystyle{ 1<j<n}\) jeśli w \(\displaystyle{ j}\)-ej szufladzie znajduje się \(\displaystyle{ i}\) kul, to pomiędzy \(\displaystyle{ j-1}\)-ą a \(\displaystyle{ j}\)-ą jedynką znajduje się \(\displaystyle{ i-1}\) kul.

kalol · Post autor: **kalol** » 19 mar 2011, o 10:18

ok a mogłbyś mi powiedzieć jak będzie z 2 na 3 i z 1 na 2?

norwimaj · Post autor: **norwimaj** » 19 mar 2011, o 10:38

Tak jak tu: 244560.htm#p915759

kalol · Post autor: **kalol** » 19 mar 2011, o 18:02

ok, dzięki