+1 Daumen
1,6k Aufrufe

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.

von

2 Antworten

0 Daumen

Das ist nur Aufgabe a)

Sn,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 Sn,2:

Jedes der n Elemente kann zur einen oder andern Menge der Partition gehören: Prinzipiell mal 2n 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 Sn,2 =  2n / 2 – 1 = 2n-1 – 1

 

Definition etc. vgl.

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

von 161 k 🚀
0 Daumen
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 http://de.wikipedia.org/wiki/Partitionsfunktion
von 378 k 🚀

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/?

Danke im Voraus

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!

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Mathelounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community