Partitionen - kombinatorische Begründung dafür, dass für alle n ≥ 2 die Gleichung Sn2 = 2^{n-1} - 1 gilt

Question

a) Geben Sie eine kombinatorische Begründung dafür, dass für alle \( n \geq 2 \) die Gleichung \( S_{n, 2}=2^{n-1}-1 \) gilt.
b) Bestimmen Sie die Anzahl (die Zahl, keine Formel) der geordneten Partitionen der Zahl \( n=100 \) in 8 Summanden \( a_{i} \geq 12 \)

Partitionen - kombinatorische Begründung dafür, dass für alle n ≥ 2 die Gleichung Sn2 = 2^{n-1} - 1 gilt.

Answer 1

Das ist nur Aufgabe a)

S_n,2 ist eine Stirlingzahl 2. Art.

Bezeichnung für Anzahl der 2-elementigen Partitionen einer n-elementigen Menge =

Anzahl Möglichkeiten, eine n-elementige Menge in genau 2 nichtleere disjunkte (elementfremde) Teilmengen aufzuteilen.

Kombinatorische Berechnung von S_n,2:

Jedes der n Elemente kann zur einen oder andern Menge der Partition gehören: Prinzipiell mal 2ⁿ Möglichkeiten. Nun sind aber alle Aufteilungen doppelt gezählt. Also Division durch 2. Nachträglich noch die mitgezählte Möglichkeit, dass eine Teilmenge alle Elemente und die andere keine enthält subtrahieren.

Als Rechnung S_n,2 =  2ⁿ / 2 – 1 = 2^n-1 – 1

 

Definition etc. vgl.

https://de.wikipedia.org/wiki/Stirling-Zahl

Answer 2

b) Bestimmen Sie die Anzahl (die Zahl, keine Formel) der geordneten Partitionen der Zahl n = 100 in 8 Summanden ai >= 12.

Zunächst mal haben wir 8 Summanden die 11 sind. Damit haben wir als Grundsumme 8 * 11 = 88.

Nun müssen wir die Restsumme 100 - 88 = 12 auf 8 Summanden >= 1 verteilen. Dafür gilt jetzt der Ausdruck.

(12-1 über 8-1) = (11 über 7) = 330

Damit gibt es 330 Möglichkeiten,  die Zahl 100 in 8 Summanden >= 12 aufzuteilen.

Siehe auch "Geordnete Zahlpartitionen" bei https://de.wikipedia.org/wiki/Partitionsfunktion

Comments

Wieso 8 Summanden die 11 sind? Ich verstehe den ansatz nicht

Wie wird dieses "ai >= 12" miteinbezogen? Soll das der rest sein der 'bleibt'?
(wodurch glaube ich die frage warum du mit 8 summanden die 11 statt 12 sind 'anfängst' beantwortet werden könnte)

Wie rechnet man X über Y aus?

Wenn ich das hier benutze:

\( \left(\begin{array}{l}{n} \\ {k}\end{array}\right)=\frac{n}{1} \cdot \frac{n-1}{2} \cdots \frac{n-(k-1)}{k} \)

scheitere ich bei (11 über 7) letztendlich bei 11/1*10/2*9/3*8/4*7/5*6/6*5/k* 4/?

---

Jeder Summand soll größer gleich 12 sein. Wenn ich von jedem Summand 11 subtrahiere muss jeder Summand größer gleich 1 sein. Das ist leichter zu berechnen. Daher nehme ich von jedem Summanden zunächst 11 weg.

(n über k) ist der Binomialkoeffizient und berechnet sich nach folgender Formel:

(n über k) = n! / (k! * (n - k)!)

---

(11 über 7) =  11*10*9*8*7*6*5   =   11*10*9*8    = 320
                   7  * 6 *5*4* 3*2*1          4*3*2*1

---

Bitte rechne noch mal nach

(11 über 7) = 11! / (7! / 4!) = 11*10*9*8 / 4*3*2*1 = 330

---

Mein (Tipp)Fehler!