77 lines
2.2 KiB
Markdown
77 lines
2.2 KiB
Markdown
|
---
|
||
|
|
title: Zahlpartitionen
|
||
|
|
date: 2018-10-23
|
||
|
|
---
|
||
|
|
|
||
|
|
**Gegeben**: $n,k \in \mathbb{N}$, $k < n$
|
||
|
|
|
||
|
|
Auf wie viele Arten kann man $n$ als Summe von $k$ natürlichen Zahlen $\geq 1$ schreiben
|
||
|
|
|
||
|
|
**Beispiel**:
|
||
|
|
|
||
|
|
$$
|
||
|
|
n = 4, k = 2 \\
|
||
|
|
4 = 1 + 3 \\
|
||
|
|
4 = 2 + 2 \\
|
||
|
|
4 = 3 + 1
|
||
|
|
$$
|
||
|
|
|
||
|
|
# Ungeordnete Zahlpartitionen
|
||
|
|
|
||
|
|
Eine ungeordnete Zahlpartition entspricht einer Multimenge $\{s_1,...,s_n\}$, so dass $s_i \geq 1, s_i \in \mathbb{N}$
|
||
|
|
und $\sum\limits_{i=1}^k s_i = n$. Wir bezeichnen die Anzahl dieser ungeordneten Zahlpartitionen/Multimengen mit
|
||
|
|
$P_{n,k}$.
|
||
|
|
|
||
|
|
## Satz
|
||
|
|
|
||
|
|
Es gilt $P_{n,k} = P_{n-1,k-1} + P_{n-k,k}$ mit $P_{n,0} = P_{0,0} = 0$ und $P_{n,n} = P_{n,1} = 1$
|
||
|
|
|
||
|
|
## Beweis
|
||
|
|
|
||
|
|
Wir teilen die Zahlpartitionen diesmal in $(k+1)$ disjunkte Fälle auf.
|
||
|
|
|
||
|
|
* Fall $i$ ($i \in \{1,...,k\}$)
|
||
|
|
|
||
|
|
Wir betrachten die Zahlpartitionen, bei denen genau $i$ der Summanden gleich $1$ sind. Ohne Einschränkung sei
|
||
|
|
$s_1 = s_2 = ... = s_i = 1$ und damit $s_{i+1},...,s_k \geq 2$
|
||
|
|
|
||
|
|
Es gilt $\sum\limits_{j=i+1}^k s_j = (n-i)$
|
||
|
|
|
||
|
|
Betrachte wieder $s_j' = s_{j-1}$ für $j \in \{i-1,...,k\}$. Dann gilt
|
||
|
|
$\sum\limits_{j=i+1}^k s_j' = (n-i) - (k-i) = (n-k)$ und $s_j' \geq 1$. Damit gibt es im Fall $i$ genau $P_{n-k,k}$
|
||
|
|
Möglichkeiten.
|
||
|
|
|
||
|
|
Summenregel liefert
|
||
|
|
|
||
|
|
$$
|
||
|
|
P_{n,k} = \sum\limits_{i=0}^k P_{n-k,k-i} = \sum\limits_{j=0}^k P_{n-k,j}
|
||
|
|
$$
|
||
|
|
$$
|
||
|
|
\tag*{$\Box$}
|
||
|
|
$$
|
||
|
|
|
||
|
|
|
||
|
|
# Geordnete Zahlpartitionen
|
||
|
|
|
||
|
|
Eine geordnete Zahlpartition entspricht einem $k$-Tupel $(s_1, ...s_k)$ mit $\sum\limits_{i=1}^k s_i = n$ mit
|
||
|
|
$s_i \in \mathbb{N}, s_i \geq 1$. Wir zählen die Anzahl der Tupel wie folgt:
|
||
|
|
|
||
|
|
* Schreibe $n$ als Summe von $n$ Einsen
|
||
|
|
* Jede $k$-Partition entspricht der Wahl von $(k-1)$ Plus Zeichen in obiger Summe. Da es $(n-1)$ Plus Zeichen gibt,
|
||
|
|
erhalten wir $\binom{n-1}{k-1}$ geordnete $k$-Partitionen der Zahl.
|
||
|
|
|
||
|
|
## Satz
|
||
|
|
|
||
|
|
Die Anzahl der geordneten $k$-Partitionen der Zahl $n$ ist $\binom{n-1}{k-1}$
|
||
|
|
|
||
|
|
**Beispiel**:
|
||
|
|
|
||
|
|
a) Frage: Wie viele Lösungen hat die Gleichung $x_1+x_2+...+x_{10} = 100$ mit $x_i \in \mathbb{N}, x_i \geq 1$?
|
||
|
|
|
||
|
|
Antwort: $\binom{99}{9}$
|
||
|
|
|
||
|
|
b) Wie viele Lösungen hat die Gleichung $x_1+x_2+...+x_{10} = 100$ mit $x_i \in \mathbb{N} \cup \{0\}$ ($x_i \geq 0$)?
|
||
|
|
|
||
|
|
Trick: wir betrachten $y_i = x_i + 1$. Dann gilt $y_1 + y_2+...+y_{10} = 100 + 10 = 110$. Damit gibt es
|
||
|
|
$\binom{109}{9}$ Möglichkeiten.
|