Ilość przedstawień liczby naturalnej w postaci sumy
-
- Użytkownik
- Posty: 1407
- Rejestracja: 20 lip 2012, o 21:19
- Płeć: Mężczyzna
- Lokalizacja: Rzeszów
- Podziękował: 66 razy
- Pomógł: 83 razy
Ilość przedstawień liczby naturalnej w postaci sumy
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}\) ?? 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ś
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}\) ?? 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ś
-
- 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
\(\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.
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.
-
- Użytkownik
- Posty: 1407
- Rejestracja: 20 lip 2012, o 21:19
- Płeć: Mężczyzna
- Lokalizacja: Rzeszów
- Podziękował: 66 razy
- Pomógł: 83 razy
Re: Ilość przedstawień liczby naturalnej w postaci sumy
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.
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.
-
- 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
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?
\(\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?
-
- Użytkownik
- Posty: 1407
- Rejestracja: 20 lip 2012, o 21:19
- Płeć: Mężczyzna
- Lokalizacja: Rzeszów
- Podziękował: 66 razy
- Pomógł: 83 razy
Re: Ilość przedstawień liczby naturalnej w postaci sumy
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ć??
-
- 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
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.
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.
-
- Użytkownik
- Posty: 1407
- Rejestracja: 20 lip 2012, o 21:19
- Płeć: Mężczyzna
- Lokalizacja: Rzeszów
- Podziękował: 66 razy
- Pomógł: 83 razy
Re: Ilość przedstawień liczby naturalnej w postaci sumy
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}\)
Ile wynosi suma:
\(\displaystyle{ \sum_{k=2}^{n }{n-1 \choose k-1}}\), gdzie \(\displaystyle{ n\in\NN}\) i \(\displaystyle{ n \ge 2}\)
-
- 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
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}\).
-
- Użytkownik
- Posty: 1407
- Rejestracja: 20 lip 2012, o 21:19
- Płeć: Mężczyzna
- Lokalizacja: Rzeszów
- Podziękował: 66 razy
- Pomógł: 83 razy
Re: Ilość przedstawień liczby naturalnej w postaci sumy
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] }\)??
\(\displaystyle{ \sum_{k=0}^{n} \left[ {n \choose k} \cdot 2 ^{n-k} \right] }\)??
- Dasio11
- Moderator
- Posty: 10226
- Rejestracja: 21 kwie 2009, o 19:04
- Płeć: Mężczyzna
- Lokalizacja: Wrocław
- Podziękował: 40 razy
- Pomógł: 2362 razy
Re: Ilość przedstawień liczby naturalnej w postaci sumy
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 pisze: ↑5 mar 2022, o 21:02A dla zbioru skończonego, \(\displaystyle{ n}\)-elementowego, ile jest par podzbiorów rozłącznych
-
- Użytkownik
- Posty: 1407
- Rejestracja: 20 lip 2012, o 21:19
- Płeć: Mężczyzna
- Lokalizacja: Rzeszów
- Podziękował: 66 razy
- Pomógł: 83 razy
Re: Ilość przedstawień liczby naturalnej w postaci sumy
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.}\)
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.}\)
- Janusz Tracz
- Użytkownik
- Posty: 4075
- Rejestracja: 13 sie 2016, o 15:01
- Płeć: Mężczyzna
- Lokalizacja: hrubielowo
- Podziękował: 80 razy
- Pomógł: 1395 razy
Re: Ilość przedstawień liczby naturalnej w postaci sumy
- 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}\).
\(\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
\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}}\)
Kod: Zaznacz cały
mathworld.wolfram.com/Chu-VandermondeIdentity.html