Ilość przedstawień liczby naturalnej w postaci sumy

Permutacje. Kombinacje. Wariacje. Rozmieszczanie kul w urnach. Silnie i symbole Newtona. Przeliczanie zbiorów. Funkcje tworzące. Teoria grafów.
Jakub Gurak
Użytkownik
Użytkownik
Posty: 1392
Rejestracja: 20 lip 2012, o 21:19
Płeć: Mężczyzna
Lokalizacja: Rzeszów
Podziękował: 60 razy
Pomógł: 83 razy

Ilość przedstawień liczby naturalnej w postaci sumy

Post autor: Jakub Gurak »

Mam pytanie, chyba wcale nie takie proste.

Ustalmy liczbę naturalną \(\displaystyle{ a\in\NN=\left\{ 0,1,2, \ldots \right\}}\), oraz liczbę naturalną \(\displaystyle{ n \ge 2}\). Na ile sposobów liczbę naturalną \(\displaystyle{ a}\) można przedstawić w postaci w postaci sumy \(\displaystyle{ n}\) liczb naturalnych \(\displaystyle{ x_1, x_2, \ldots, x_n}\) ?? :o Z uwzględnieniem kolejności składników.

Dla \(\displaystyle{ n=2}\), mamy oczywiście \(\displaystyle{ a+1}\) sposobów.
Dla \(\displaystyle{ n=3}\) mamy (biorąc jako trzecią liczbę kolejno \(\displaystyle{ 0 ,1, 2,\ldots, a}\)), mamy: \(\displaystyle{ (a+1)+a+(a-1)+\ldots+1= \frac{(a+1) \cdot \left( a+2\right) }{2} }\)- sposobów.
Potem sprawa zaczyna się troszkę komplikować. A mi grzęznąć we wzorach mi się nie chcę, to nie moja specjalność, a jest mi to potrzebne do innego problemu teorio-mnogościowego. Pomoże ktoś :?:
Tmkk
Użytkownik
Użytkownik
Posty: 1718
Rejestracja: 15 wrz 2010, o 15:36
Płeć: Mężczyzna
Lokalizacja: Ostrołęka
Podziękował: 59 razy
Pomógł: 501 razy

Re: Ilość przedstawień liczby naturalnej w postaci sumy

Post autor: Tmkk »

\(\displaystyle{ {n+a-1 \choose n-1}}\)

To pytanie jest równoważne pytaniu: na ile sposobów można rozmieścić \(\displaystyle{ a}\) nierozróżnialnych kul w \(\displaystyle{ n}\) rozróżnialnych urnach i jest bardzo elementarne.
Jakub Gurak
Użytkownik
Użytkownik
Posty: 1392
Rejestracja: 20 lip 2012, o 21:19
Płeć: Mężczyzna
Lokalizacja: Rzeszów
Podziękował: 60 razy
Pomógł: 83 razy

Re: Ilość przedstawień liczby naturalnej w postaci sumy

Post autor: Jakub Gurak »

Dziękuje, a jeszcze jedno, podobne pytanie (przy tych samych oznaczeniach):

Ile jest wszystkich układów \(\displaystyle{ \left( x_1, x_2,\ldots, x_n\right)}\) których suma jest mniejsza lub równa od liczby naturalnej \(\displaystyle{ a}\) ??
Jednak odpowiedź na to pytanie jest mi jednak bardziej potrzebna. :)
Tmkk
Użytkownik
Użytkownik
Posty: 1718
Rejestracja: 15 wrz 2010, o 15:36
Płeć: Mężczyzna
Lokalizacja: Ostrołęka
Podziękował: 59 razy
Pomógł: 501 razy

Re: Ilość przedstawień liczby naturalnej w postaci sumy

Post autor: Tmkk »

Jeśli ten wzór jest jasny, to teraz trzeba dodać - kiedy ta suma to \(\displaystyle{ 0}\), kiedy \(\displaystyle{ 1}\), itd aż do \(\displaystyle{ a}\). Czyli to będzie \(\displaystyle{ \sum_{k = 0}^a {n+k-1 \choose n-1}}\) i można pokazać, kombinatorycznie na przykład, że zachodzi

\(\displaystyle{ \sum_{k = 0}^a {n+k-1 \choose n-1} = {n+a \choose n}}\).

Jeśli chcesz zobaczyć dowód, to daj znać i rozpiszę, ale wieczorem.

Właściwie można tez zobaczyć, że układów o które pytasz jest tyle samo, ile układów \(\displaystyle{ (x_0,x_1,x_2, \ldots ,x_n)}\) takich, że ich suma daje \(\displaystyle{ a}\), prawda?
Jakub Gurak
Użytkownik
Użytkownik
Posty: 1392
Rejestracja: 20 lip 2012, o 21:19
Płeć: Mężczyzna
Lokalizacja: Rzeszów
Podziękował: 60 razy
Pomógł: 83 razy

Re: Ilość przedstawień liczby naturalnej w postaci sumy

Post autor: Jakub Gurak »

A to dlaczego?? Rozumiem, że można rozważać sumę liczby układów, których suma daje \(\displaystyle{ 0}\), potem \(\displaystyle{ 1}\), i tak aż do \(\displaystyle{ a}\), ale tego nie rozumiem, możesz rozjaśnić??
Tmkk
Użytkownik
Użytkownik
Posty: 1718
Rejestracja: 15 wrz 2010, o 15:36
Płeć: Mężczyzna
Lokalizacja: Ostrołęka
Podziękował: 59 razy
Pomógł: 501 razy

Re: Ilość przedstawień liczby naturalnej w postaci sumy

Post autor: Tmkk »

Napiszę to dokładnie:

Dowód kombinatoryczny poniższej tożsamości:

\(\displaystyle{ \sum_{k = 0}^a {n+k-1 \choose n-1} = {n+a \choose n}.}\)

Rozpatrzmy zbiór \(\displaystyle{ \left\{ 1,2,\ldots ,n+a\right\} }\) i chcemy z niego wybrać zbiór \(\displaystyle{ n}\) elementowy. Możemy to zrobić normalnie i wtedy mamy wzorek po prawej stronie. Ale możemy też zrobić to tak śmiesznie, że:

- najpierw wybierzemy ze zbiorów, w których \(\displaystyle{ n}\) będzie największym elementem. To bierzemy go i potrzebujemy jeszcze \(\displaystyle{ n-1}\) elementów z \(\displaystyle{ \left\{ 1,2\ldots ,n-1\right\}}\). Więc takich wyborów jest \(\displaystyle{ {n-1 \choose n-1}}\);
- wybierzemy ze zbiorów, w których \(\displaystyle{ n+1}\) będzie największym elementem. To bierzemy go i potrzebujemy jeszcze \(\displaystyle{ n-1}\) elementów z \(\displaystyle{ \left\{ 1,2\ldots ,n\right\}}\). Więc takich wyborów jest \(\displaystyle{ {n \choose n-1}}\);
- i tak dalej...
- na koniec wybierzemy ze zbiorów, w których \(\displaystyle{ n+a}\) będzie największym elementem. Takich wyborów jest \(\displaystyle{ {n+a-1 \choose n-1}}\)

Chyba widać, że to wyczerpuje wszystkie możliwości i nic się nie powtarza. Jak się to doda, to dostaniemy lewą stroną.



Drugi, krótszy sposób

Zauważ, że chcesz znaleźć łączną liczbę rozwiązań równań \(\displaystyle{ x_1+x_2+\ldots +x_n = a}\) lub \(\displaystyle{ x_1+x_2+\ldots +x_n = a-1}\) lub ... lub \(\displaystyle{ x_1+x_2+\ldots +x_n = 0}\), gdzie \(\displaystyle{ a}\) jest ustalone oraz \(\displaystyle{ x_i \in \left\{ 0,1,2,\ldots ,a\right\} }\), \(\displaystyle{ i=1,2,\ldots ,n}\).

Czyli w skrócie, chcesz znaleźć liczbę rozwiązań równania \(\displaystyle{ x_1+x_2+\ldots +x_n = a - x_0}\), gdzie \(\displaystyle{ x_0 \in \left\{ 0,1,2,\ldots ,a\right\} }\) oraz \(\displaystyle{ x_i \in \left\{ 0,1,2,\ldots ,a\right\} }\), \(\displaystyle{ i=1,2,\ldots ,n}\), prawda? No jak wstawię \(\displaystyle{ x_0=0}\) to mam pierwszą opcję, czyli w sumie te liczby dają \(\displaystyle{ a}\). Jak wstawię \(\displaystyle{ x_0=1}\) to mam drugą opcję, czyli w sumie te liczby dają \(\displaystyle{ a-1}\), itd.

Czyli przerzucając na drugą stronę, chcesz znaleźć liczbę rozwiązań równania \(\displaystyle{ x_0 + x_1+x_2+\ldots +x_n = a }\), gdzie \(\displaystyle{ x_i \in \left\{ 0,1,2,\ldots ,a\right\} }\), \(\displaystyle{ i=0,1,2,\ldots ,n}\). A to już stwierdziliśmy ile jest, czyli \(\displaystyle{ {n+a \choose n}}\).

Jeśli coś jest jeszcze niejasne, to pisz.
Jakub Gurak
Użytkownik
Użytkownik
Posty: 1392
Rejestracja: 20 lip 2012, o 21:19
Płeć: Mężczyzna
Lokalizacja: Rzeszów
Podziękował: 60 razy
Pomógł: 83 razy

Re: Ilość przedstawień liczby naturalnej w postaci sumy

Post autor: Jakub Gurak »

A mam takie pytanie, bo jest to mi potrzebne:

Ile wynosi suma:

\(\displaystyle{ \sum_{k=2}^{n }{n-1 \choose k-1}}\), gdzie \(\displaystyle{ n\in\NN}\) i \(\displaystyle{ n \ge 2}\) :?:
Tmkk
Użytkownik
Użytkownik
Posty: 1718
Rejestracja: 15 wrz 2010, o 15:36
Płeć: Mężczyzna
Lokalizacja: Ostrołęka
Podziękował: 59 razy
Pomógł: 501 razy

Re: Ilość przedstawień liczby naturalnej w postaci sumy

Post autor: Tmkk »

Tyle, ile wszystkich podzbiorów zbioru \(\displaystyle{ n-1}\) elementowego, pomijając zbiór pusty - bo w sumie nie ma \(\displaystyle{ {n-1 \choose 0}}\), czyli \(\displaystyle{ 2^{n-1}-1}\).
Jakub Gurak
Użytkownik
Użytkownik
Posty: 1392
Rejestracja: 20 lip 2012, o 21:19
Płeć: Mężczyzna
Lokalizacja: Rzeszów
Podziękował: 60 razy
Pomógł: 83 razy

Re: Ilość przedstawień liczby naturalnej w postaci sumy

Post autor: Jakub Gurak »

A dla zbioru skończonego, \(\displaystyle{ n}\)-elementowego, ile jest par podzbiorów rozłącznych, tzn. ile wynosi suma:

\(\displaystyle{ \sum_{k=0}^{n} \left[ {n \choose k} \cdot 2 ^{n-k} \right] }\)??
Tmkk
Użytkownik
Użytkownik
Posty: 1718
Rejestracja: 15 wrz 2010, o 15:36
Płeć: Mężczyzna
Lokalizacja: Ostrołęka
Podziękował: 59 razy
Pomógł: 501 razy

Re: Ilość przedstawień liczby naturalnej w postaci sumy

Post autor: Tmkk »

A rozpisz sobie ze wzorku dwumian Newtona \(\displaystyle{ (1+2)^n}\).
Awatar użytkownika
Dasio11
Moderator
Moderator
Posty: 10211
Rejestracja: 21 kwie 2009, o 19:04
Płeć: Mężczyzna
Lokalizacja: Wrocław
Podziękował: 40 razy
Pomógł: 2359 razy

Re: Ilość przedstawień liczby naturalnej w postaci sumy

Post autor: Dasio11 »

Jakub Gurak pisze: 5 mar 2022, o 21:02A dla zbioru skończonego, \(\displaystyle{ n}\)-elementowego, ile jest par podzbiorów rozłącznych
Tyle ile sposobów przypisania każdemu z \(\displaystyle{ n}\) elementów jednej z trzech możliwości: należy do pierwszego z tych podzbiorów, do drugiego lub do żadnego - czyli \(\displaystyle{ 3^n}\).
Jakub Gurak
Użytkownik
Użytkownik
Posty: 1392
Rejestracja: 20 lip 2012, o 21:19
Płeć: Mężczyzna
Lokalizacja: Rzeszów
Podziękował: 60 razy
Pomógł: 83 razy

Re: Ilość przedstawień liczby naturalnej w postaci sumy

Post autor: Jakub Gurak »

A mam takie pytanie, gdyż jest mi to potrzebne:

Dla liczb naturalnych \(\displaystyle{ n,m \neq 0}\), ile wynosi suma:

\(\displaystyle{ \sum_{i=2}^{min\left( n,m\right) } \left[ {m \choose i} \cdot {n-1 \choose i-1} \right] }\),

gdzie \(\displaystyle{ min\left( n,m\right) }\) oznacza liczbę naturalną mniejszą z liczb \(\displaystyle{ n,m.}\)

:?:
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: Ilość przedstawień liczby naturalnej w postaci sumy

Post autor: Janusz Tracz »

  • Wyrażanie \(\displaystyle{ \sum_{i=2}^{\min\left( n,m\right) } {m \choose i} {n-1 \choose i-1}}\) jest symetryczne względem \(\displaystyle{ n,m}\). Więc można bez straty ogólności założyć, że \(\displaystyle{ m \le n}\).
  • Reprezentacja Egorychev-a dwumianu to \(\displaystyle{ \binom{n}{k}=\frac{1}{2 \pi i}\oint_{|z|=1}\frac{(1+z)^{n}}{z^{k+1}}\,\dd z}\).
Zatem
\(\displaystyle{ \begin{split}
\sum_{i=2}^{\min\left( n,m\right) } {m \choose i} {n-1 \choose i-1}&= \frac{1}{2 \pi i}\sum_{i=2}^{m} {m \choose i} \oint_{|z|=1}\frac{(1+z)^{n-1}}{z^{i}}\,\dd z \\[1ex]
&= \frac{1}{2 \pi i} \oint_{|z|=1} \sum_{i=2}^{m} {m \choose i} \frac{(1+z)^{n-1}}{z^{i}}\,\dd z \\[1ex]
&= \frac{1}{2 \pi i} \oint_{|z|=1} (1+z)^{n-1} \times \left( \left( \frac{1+z}{z} \right)^m- \frac{m}{z}-1\right) \,\dd z \\[1ex]
&= \frac{1}{2 \pi i} \oint_{|z|=1} \frac{(1+z)^{n+m-1}}{z^m} - \frac{m(1+z)^{n-1}}{z}-(1+z)^{n-1} \,\dd z \\[1ex]
&= {n+m-1 \choose m-1}-m.
\end{split}}\)
Inna metoda polega na zastosowaniu

Kod: Zaznacz cały

mathworld.wolfram.com/Chu-VandermondeIdentity.html
Chu-Vandermonde Identity
ODPOWIEDZ