Rozkład kul w szufladach

Permutacje. Kombinacje. Wariacje. Rozmieszczanie kul w urnach. Silnie i symbole Newtona. Przeliczanie zbiorów. Funkcje tworzące. Teoria grafów.
Bran
Użytkownik
Użytkownik
Posty: 421
Rejestracja: 19 lut 2019, o 19:30
Płeć: Mężczyzna
Lokalizacja: Polska
Podziękował: 163 razy
Pomógł: 16 razy

Rozkład kul w szufladach

Post autor: Bran »

Wyznacz funkcję tworzącą liczby możliwych podziałów \(\displaystyle{ n}\) nierozróżnialnych kul w pięciu szufladach, jeżeli w każdej szufladzie musi znajdować się przynajmniej jedna kula.

To moje pierwsze zadanie z funkcji tworzących i tak naprawdę nie wiem od czego mam zacząć, nie wiem jaka jest interpretacje kombinatoryczna funkcji tworzących. Jeżeli mam:
\(\displaystyle{ \sum_{n=0}^\infty a_n x^n}\)
To co będą w tym zadaniu oznaczały liczby z ciągu \(\displaystyle{ a_n,}\) a co wykładniki przy \(\displaystyle{ x}\)?
Awatar użytkownika
Janusz Tracz
Użytkownik
Użytkownik
Posty: 4060
Rejestracja: 13 sie 2016, o 15:01
Płeć: Mężczyzna
Lokalizacja: hrubielowo
Podziękował: 79 razy
Pomógł: 1391 razy

Re: Rozkład kul w szufladach

Post autor: Janusz Tracz »

Liczba rozmieszczeń \(\displaystyle{ n}\) nierozróżnialnych kul w \(\displaystyle{ 5}\) szufladach jest równa liczbie rozwiązań równania \(\displaystyle{ x_1+...+x_5=n}\) w liczbach całkowitych dodatnich. Możną też zliczyć liczbę rozwiązań \(\displaystyle{ x'_1+...+x'_5=n-5}\), gdzie \(\displaystyle{ x'_i \ge 0}\) i całkowite. I to można sobie wyobrazić, że mamy \(\displaystyle{ 4}\) pionowe patyki \(\displaystyle{ |}\) i \(\displaystyle{ n-5}\) kulek \(\displaystyle{ \circ}\) i każde rozwiązanie kodujemy napisem przykładowo napis \(\displaystyle{ \circ\circ||\circ\circ\circ|\circ...\circ|}\) koduje rozwiazanie \(\displaystyle{ 2+0+3+(n-10)+0}\) i tak dalej. I takich napisów złożonych z \(\displaystyle{ 4}\) patyków \(\displaystyle{ |}\) i \(\displaystyle{ n-5}\) piłek \(\displaystyle{ \circ}\) jest

\(\displaystyle{ \frac{(n-5+4)!}{(n-5)!4!} = {n-1 \choose 4} }\)

i to jest nasze \(\displaystyle{ a_n}\) (dla \(\displaystyle{ n \ge 5}\)), a dla \(\displaystyle{ n\in\left\{ 0,1,2,3,4\right\} }\) kładziemy \(\displaystyle{ a_n=0}\). Funkcja tworząca jest więc szeregiem formalnym (choć tu jest to szereg zbieżny w kole \(\displaystyle{ \left| x\right|<1 }\))

\(\displaystyle{ \mathcal{G}(x)= \sum_{n=0}^{ \infty } a_nx^n=\sum_{n=5}^{ \infty } {n-1 \choose 4} x^n}\)

i to się nawet powinno dać jawnie policzyć. Spróbuj rozpisać dwumian i różniczkować wyraz po wyrazie szereg geometryczny aż wyjdzie to co tu.
Bran
Użytkownik
Użytkownik
Posty: 421
Rejestracja: 19 lut 2019, o 19:30
Płeć: Mężczyzna
Lokalizacja: Polska
Podziękował: 163 razy
Pomógł: 16 razy

Re: Rozkład kul w szufladach

Post autor: Bran »

Nie rozumiem kilku rzeczy, będę wdzięczny za rozjaśnienie sprawy:

1. Dlaczego rozważasz ilość rozwiązań jakiegoś innego równania?
2. Dlaczego interesuje nas właśnie to drugie równanie (tak zrozumiałem, choć mogę się mylić).
3. Czy w obu równaniach nie mamy przypadku gdzie liczba kul w szufladzie jest równa zero? (co w zadaniu trzeba wykluczyć)
4. \(\displaystyle{ a_n}\) to ilość rozmieszczeń \(\displaystyle{ n}\) kul?
Awatar użytkownika
Janusz Tracz
Użytkownik
Użytkownik
Posty: 4060
Rejestracja: 13 sie 2016, o 15:01
Płeć: Mężczyzna
Lokalizacja: hrubielowo
Podziękował: 79 razy
Pomógł: 1391 razy

Re: Rozkład kul w szufladach

Post autor: Janusz Tracz »

Bran pisze: 21 maja 2021, o 17:29 1. Dlaczego rozważasz ilość rozwiązań jakiegoś innego\(\displaystyle{ \red{^*}}\) równania?
Bo zapomniałem ja się zliczało liczbę rozwiązań \(\displaystyle{ x_1+...+x_k=n}\) w liczbach całkowitych dodatnich. W sensie to była prosta rzecz pewnie można było to zrobić bezpośrednio. Ja jednak postanowiłem zamienić zmienne \(\displaystyle{ x_i\mapsto x'_i-1}\), skoro \(\displaystyle{ x_i \ge 1}\) to równoważnie wolałem rozważać równanie postaci \(\displaystyle{ (x_1-1)+(x_2-1)+...+(x_k-1)=n-k}\) czyli \(\displaystyle{ x'_1+...+x'_k=n-k}\) ale \(\displaystyle{ x'_i \ge 0}\) w liczbach całkowitych nieujemnych.

\(\displaystyle{ \red{^*}}\)Tu dodam jedynie, że tak naprawdę nie ma pierwszego czy drugiego równania (to znaczy wizualnie jest...) jest tylko liczba rozwiązań pewnego problemu kombinatorycznego. I tym problemem jest zliczenia liczby rozwiązań równania \(\displaystyle{ x_1+...+x_k=n}\) w liczbach całkowitych dodatnich lub każdego innego równoważnego problemu. W sensie to drugie równanie to tak naprawdę to samo tylko ze względów technicznych zapisane inaczej w istocie to ten sam problem.

\(\displaystyle{ \red{^{**}}}\) Oczywiście \(\displaystyle{ k=5}\) w zadanie ale pisałem ogólnie.
Bran pisze: 21 maja 2021, o 17:29 2. Dlaczego interesuje nas właśnie to drugie równanie (tak zrozumiałem, choć mogę się mylić).
Na to pytanie chyba już odpowiedziałem. Dodam może jedynie po co w ogólne rozważamy to równanie. Bo rozkład kul jednoznacznie koduje pewne rozwiązanie takiego równania. I odwrotnie mając rozwiązanie równania \(\displaystyle{ x_1+...+x_5=n}\) w liczbach całkowitych dodatnich można rozłożyć kule w szufladach według pewnego algorytmu.

Oczywiście domyślamy się o jaki algorytm chodzi... nigdzie jawnie tego nie powiedziałem ale się domyślamy? Algorytm jest taki, że rozwiązaniu równania \(\displaystyle{ x_1+...+x_k=n}\) w liczbach całkowitych dodatnich przypisuje rozkład kul w szufladach w taki sposób, że do \(\displaystyle{ i}\)-tej szuflady ma trafić \(\displaystyle{ x_i}\) kul. Przemilczałem oczywiście kwestie tego czy ten algorytm jest odwracalny... czy jest bijekcją pomiędzy rozwiązaniami \(\displaystyle{ x_1+...+x_k=n}\) w liczbach całkowitych dodatnich, a rozmieszczeniami kul. Ale w to można raczej uwierzyć bo dowód raczej zaciemnił by prostą sprawę. Chociaż można by się było bawić. Niech

\(\displaystyle{ \Theta : \left\{ \left\langle x_1,...,x_5\right \rangle\in \ZZ^5: x_1+...+x_5=n \ \& \ x_1,...,x_n \ge 1 \right\} \rightarrow \left\{ \text{napisy złożone z } 4 \text{ symboli }| \text{ oraz } n-5 \ \circ\right\} }\)

\(\displaystyle{ \Psi:\left\{ \text{napisy złożone z } 4 \text{ symboli }| \text{ oraz } n-5 \ \circ\right\} \to \left\{ \left\langle x_1,...,x_5\right \rangle\in \ZZ^5: x_1+...+x_5=n \ \& \ x_1,...,x_n \ge 1 \right\} }\)

gdzie
\(\displaystyle{ \Theta \left( \left\langle x_1,...,x_5\right \rangle \right) = \underbrace{\circ}_{x_1 \text{ razy}}| \underbrace{\circ}_{x_2 \text{ razy}}| \underbrace{\circ}_{x_3 \text{ razy}} | \underbrace{\circ}_{x_4 \text{ razy}}| \underbrace{\circ}_{x_5 \text{ razy}} }\)

\(\displaystyle{ \Psi(\text{napis złożony z } 4 \text{ symboli }| \text{ oraz } n-5 \ \circ)=\left\langle \underbrace{\sharp \circ}_{\text{ przed pierwszym wystąpieniem symbolu }|} ,\underbrace{\sharp \circ}_{\text{ pomiędzy pierwszym }| \text{ a drugim }|} , ... , \underbrace{\sharp \circ}_{\text{ za ostatnim }|} \right\rangle }\)

gdzie \(\displaystyle{ \sharp \circ}\) to liczba symboli \(\displaystyle{ \circ}\). Teraz wystarczy sprawdzić, że

\(\displaystyle{ \Theta \blue{\circ} \Psi = \text{id}_{\left\{ \text{napisy złożone z } 4 \text{ symboli }| \text{ oraz } n-5 \ \circ\right\} } \quad \& \quad \Psi \blue{\circ} \Theta= \text{id}_{\left\{ \left\langle x_1,...,x_5\right \rangle\in \ZZ^5: x_1+...+x_5=n \ \& \ x_1,...,x_n \ge 1 \right\} }}\)

gdzie \(\displaystyle{ \blue{\circ} }\) jest złożeniem funkcji. Niestety nie przewidziałem tego, że kule będę oznaczać \(\displaystyle{ \circ}\). No jak widać spisanie tego jest gorsze od uwierzenia, że rozkład kul jednoznacznie koresponduje z rozwiązaniem odpowiedniego równania. Jednak powinno się udać pokazać, że \(\displaystyle{ \Theta \blue{\circ} \Psi = \text{id}}\) oraz \(\displaystyle{ \Psi \blue{\circ} \Theta}\). Wtedy równoważnie pokaż się, że \(\displaystyle{ \Theta }\) oraz \(\displaystyle{ \Psi }\) to bijekcje.
Bran pisze: 21 maja 2021, o 17:29 3. Czy w obu równaniach nie mamy przypadku gdzie liczba kul w szufladzie jest równa zero? (co w zadaniu trzeba wykluczyć)
Nie bo \(\displaystyle{ x_i \ge 1}\).
Bran pisze: 21 maja 2021, o 17:29 4. \(\displaystyle{ a_n}\) to ilość rozmieszczeń \(\displaystyle{ n}\) kul?
Tak.
Bran
Użytkownik
Użytkownik
Posty: 421
Rejestracja: 19 lut 2019, o 19:30
Płeć: Mężczyzna
Lokalizacja: Polska
Podziękował: 163 razy
Pomógł: 16 razy

Re: Rozkład kul w szufladach

Post autor: Bran »

Dziękuję!
Janusz Tracz pisze: 17 maja 2021, o 16:54
\(\displaystyle{ \mathcal{G}(x)= \sum_{n=0}^{ \infty } a_nx^n=\sum_{n=5}^{ \infty } {n-1 \choose 4} x^n}\)
i to się nawet powinno dać jawnie policzyć. Spróbuj rozpisać dwumian i różniczkować wyraz po wyrazie szereg geometryczny aż wyjdzie to co tu.
\(\displaystyle{ n}\)-ta pochodna będzie wyrażona wzorem:

\(\displaystyle{ n! \cdot (n-4)(n-3)(n-2)(n-1) \cdot \frac{1}{4!}}\)

Ale sądząc po odpowiedzi nie o to chodziło. Co znaczy, że nie wiem nawet do czego dążymy :oops:
Przepraszam, ale uczę się tego teraz sam i to jest moje pierwsze zadanie, więc jestem jak dziecko we mgle.

Mimo, że to co piszesz wydaje mi się jasne i nawet jest już policzone ile jest rozmieszczeń \(\displaystyle{ n}\) kul w \(\displaystyle{ 5}\) szufladach \(\displaystyle{ \left( {n-1 \choose 4} \right)}\) . Narzuca mi się pytanie: Po co tutaj ta cała funkcja tworząca, skoro i tak to co mieliśmy policzyć musieliśmy policzyć inaczej?
Awatar użytkownika
Janusz Tracz
Użytkownik
Użytkownik
Posty: 4060
Rejestracja: 13 sie 2016, o 15:01
Płeć: Mężczyzna
Lokalizacja: hrubielowo
Podziękował: 79 razy
Pomógł: 1391 razy

Re: Rozkład kul w szufladach

Post autor: Janusz Tracz »

Bran pisze: 22 maja 2021, o 10:01 \(\displaystyle{ n}\)-ta pochodna będzie wyrażona wzorem:
\(\displaystyle{ n! \cdot (n-4)(n-3)(n-2)(n-1) \cdot \frac{1}{4!}}\)
Ten fragment nie ma sensu. Jak mówisz o pochodnej to z czego ta pochodna? Poza tym pochodnej \(\displaystyle{ n}\)-tego rzędu tu nie liczymy. Pisząc
Janusz Tracz pisze: 17 maja 2021, o 16:54
\(\displaystyle{ \mathcal{G}(x)= \sum_{n=0}^{ \infty } a_nx^n=\sum_{n=5}^{ \infty } {n-1 \choose 4} x^n}\)
i to się nawet powinno dać jawnie policzyć. Spróbuj rozpisać dwumian i różniczkować wyraz po wyrazie szereg geometryczny aż wyjdzie to co tu.
miałem na myśli to aby pokazać, że
\(\displaystyle{ \boxed{\mathcal{G}(x)=\sum_{n=5}^{ \infty } {n-1 \choose 4} x^{n}= \frac{x^5}{(1-x)^5}}}\)
tym samym dając jawną postać funkcji tworzącej.
Bran pisze: 22 maja 2021, o 10:01 Po co tutaj ta cała funkcja tworząca, skoro i tak to co mieliśmy policzyć musieliśmy policzyć inaczej?
To trudne pytanie (przynajmniej dla mnie). Nie uważam abym czuł idee funkcji tworzących by się tu jednoznacznie wypowiedzieć. Ze swojego doświadczenia mogę powiedzieć jedynie, że często problem kombinatoryczny rozwiązuje się najpierw przez określenie funkcji tworzącej. Teraz pytanie czy tu dało by się najpierw napisać funkcję tworzącą nawet jawnie i na tej podstawie określić ile wynosi \(\displaystyle{ a_n}\)? Tak dało by się to zrobić. Dlaczego tego nie zrobiłem? Bo uznałem, że wyciągnięcie funkcji tworzącej z kapelusza to nie jest dydaktycznie dobry pomysł. Ale skoro już wiemy czego się spodziewać można teraz to zrobić. Skoro szukamy liczby rozwiązań \(\displaystyle{ x_1+...+x_5=n}\) w liczbach całkowitych dodatnich to zauważmy, że przy \(\displaystyle{ x^n}\) w nieskończonym wielomianie
\(\displaystyle{ \mathcal{G}(x)=\left( x^1+x^2+...\right)^5}\)

jest właśnie to co potrzebujemy. Zatem znaleźliśmy funkcje tworzącą. Koniec. Skąd wiem, że to jest funkcja tworząc? Bo to widać. A dlaczego to się zgadza z tym co wyliczyliśmy? Bo
\(\displaystyle{ \mathcal{G}(x)=\left( x^1+x^2+...\right)^5=x^5 \cdot \left( 1+x^1+...\right)^5= \frac{x^5}{(1-x)^5} }\)

zatem \(\displaystyle{ a_n=\left[ x^n\right] \mathcal{G}(x) }\). Jednak już wiemy, że \(\displaystyle{ \sum_{n=5}^{ \infty } {n-1 \choose 4} x^{n}= \frac{x^5}{(1-x)^5}}\) zatem \(\displaystyle{ a_n=\left[ x^n\right] \mathcal{G}(x)= {n-1 \choose 4} }\) (dla \(\displaystyle{ n \ge 5}\)). Co jest równie dobrym rozwiązaniem tylko od innej strony.

Warto kojarzyć taką równość
\(\displaystyle{ \frac{1}{(1-x)^{\ell}}= \sum_{n=0}^{ \infty } {n+\ell-1 \choose n} x^n= \sum_{n=0}^{ \infty } {n+\ell-1 \choose \ell-1} x^n}\)
ODPOWIEDZ