Podział liczby

[pingwindyktator]

Mając liczbę \(\displaystyle{ n}\), chcę znaleźć wzór na liczbę wszystkich możliwych podziałów, które uwzględniają pozycje elementów w sumie (nie uwzględniają "różności" takich samych elementów).
Dla przykładu, \(\displaystyle{ n=4}\):

\(\displaystyle{ 4 = 1+1+1+1 \newline
4 = 2+1+1 \newline
4 = 1+2+1\newline
4 = 1+1+2\newline
4 = 2+2\newline
4 = 1+3\newline
4 = 3+1\newline
4 = 4}\)
Jak to uogólnić? Jak wyprowadzić wzór na liczbę takich podziałów?

[jutrvy]

Ustalmy \(\displaystyle{ n}\). pytamy się ile rozwiązań w liczbach całkowitychtarczy nieujemnych ma równanie

\(\displaystyle{ n = x_1+x_2+\ldots +x_n}\). Można to łatwo sprowadzić do przypadku, kiedy każdy \(\displaystyle{ x_i > 0}\). Wystarczy stronami dodać \(\displaystyle{ n}\). Otrzymamy wtedy:

\(\displaystyle{ 2n = (x_1+1) + (x_2+1) + \ldots (x_n+1) \qquad (1)}\)

Ile rozwiązań ma to równanie?

Wystarczy napisać sobie \(\displaystyle{ 2n}\) kropek w rządku i między nie wstawić \(\displaystyle{ n-1}\) kreseczek. Liczba kółeczek między lewym brzegiem, a pierwszą kreską to \(\displaystyle{ x_1+1}\), liczba kółeczek między pierwszą a drugą kreską to \(\displaystyle{ x_2}\),... itp. Zatem wszystkich rozwiązań równania \(\displaystyle{ (1)}\) jest

\(\displaystyle{ {2n \choose n-1}}\).

Pozdrawiam

[kropka+]

To nieprawda, np. \(\displaystyle{ n=2}\) można zapisać na dwa sposoby a nie na \(\displaystyle{ {4 \choose 1}=4}\)
Raczej to będzie

\(\displaystyle{ {n-1 \choose 0}+{n-1 \choose 1}+{n-1 \choose 2}+...+ {n-1 \choose n-1}}\)

bo maksymalnie pomiędzy \(\displaystyle{ n}\) kropeczkami może być \(\displaystyle{ n-1}\) kreseczek a minimalnie żadnej kreseczki, oczywiście \(\displaystyle{ n \in N}\) Nie sprawdzałam tego, więc zweryfikujcie.

[jutrvy]

Tak - moje rozwiązanie jest złe, bo za każdym razem zakładam, że składników jest tyle samo i dużo przypadków liczę po dużo razy.
Twoje rozwiązanie \(\displaystyle{ 2^{n-1}}\) jest ok - mnie się poj...rąbało.

[pingwindyktator]

@kropka+ : rzeczywiście, mi wyszło tak samo, chociaż rozumowałem nieco inaczej. Mając owe \(\displaystyle{ n}\) kropek/kulek/czegośtam, mamy \(\displaystyle{ n-1}\) "przerw", w które możemy wsadzić kreskę. To bardzo intuicyjne, bo wtedy:
\(\displaystyle{ oo|o|o|ooo}\)
oznaczałoby \(\displaystyle{ 2+1+1+3}\). Mając zatem \(\displaystyle{ n-1}\) przerw, w każdą z nich możemy wsadzic kreskę lub jej nie wsadzać, czyli \(\displaystyle{ 2^{n-1}}\)