Frage von tuyjoe, 76

Kombinatorik Wieviele Tupel (x1, .. , xn) = 8?

Hi,

Angenommen wir haben die Menge M = {1,2,...,10} Nun habe ich die Aufgabe: "Wieviele 4-Tupel (x1,x2,x3,x4) Element M^4 gibt es mit x1+x2+x3+x4 = 8?"

Die Lösung geht mit ((n+k-1) über k). Mit n=4 und k =8.

Jedoch versteh ich nicht warum das mit dieser Formel geht. Es kommt ja auch auf die Elemente meiner Menge M an. Würde dort die 2 Fehlen, könnte ich die Formel ja nichtmehr anwenden. Doch wo wird dies in der Formel berücksichtigt? Dessweiteren könnte ich ja die Elemente ab der >= 6 weglassen, da diese als Element eines 4er Tupels addiert immer > 8 ergeben.

LG

Antwort
von ralphdieter, 23

Du hast einen Stock der Länge k=8. Der wird an den möglichen Stellen 1, 2, 3, ..., 7 genau dreimal (n=4) zersägt ("3 aus 7 ohne Zurücklegen").

Die Längen der n=4 Teilstücke (von links nach rechts) bilden genau deine 4-Tupel. Dafür gibt es 7·6·5/3! = 35 Möglichkeiten. Die allgemeine Formel lautet "(k-1) über (n-1)".

Man kann dieses anschauliche Problem für beliebige Mindestlängen m∈ℤ verallgemeinern, indem man bei jedem Teil das Anfangsstück (m-1) ignoriert und den Stock um n·(m-1) verkürzt.

Ich glaube, es gibt auch einen Trick, um die Maximallänge M zu begrenzen: Dazu berechnet man Teile mit Längen k-x_i, die auf die Minimallänge M begrenzt sind und in Summe (n-1)·k ergeben (oder so ähnlich).

Formeln für beliebige Einschränkungen auf bestimmte Längen sind mir nicht bekannt.

Expertenantwort
von Willy1729, Community-Experte für Mathe & Mathematik, 42

Hallo,

die Formel kann eigentlich nicht stimmen. Bei n=4 und k=8 wären das 11 über 4 gleich 165 mögliche Tupel.

Ich komme aber nur auf 35, nämlich die Tupel (1,1,1,5);(1,1,2,4);(1,1,3,3);(1,2,2,3) und (2,2,2,2) mit ihren jeweiligen Permutationen.

Herzliche Grüße,

Willy

Kommentar von tuyjoe ,

Hallo Willy,

Danke für deine Antwort.

Meine "Lösung" hatte ich von einer Freundin abgeschrieben, dann ist diese wohl falsch, was mir auch durch die Tupel einleuchtet.

Eine Frage hätte ich noch, wie errechne ich die Anzahl der Permutationen z.B. für das Tupel (1,1,2,4), (da ich ja z.B. die 1 nicht untereinander vertauschen darf)

Kombinatorik ist bis jetzt leider noch nicht ganz meine Stärke ;)

Kommentar von Willy1729 ,

Hallo,

Du rechnest 4!, also 1*2*3*4=24 und teilst dies durch die Fakultäten der gleichen Zahlen. Bei (5,1,1,1) rechnest Du 4!/3! denn hier sind drei Zahlen ununterscheidbar

bei (1,1,2,4) rechnest Du 4!/2! weil hier zwei Zahlen gleich sind,

bei (1,1,3,3) rechnest Du 4!/(2!*2!), weil hier zwei Gruppen von je zwei Zahlen nicht zu unterscheiden sind.

Herzliche Grüße,

Willy

Kommentar von tuyjoe ,

vielen Dank!

Keine passende Antwort gefunden?

Fragen Sie die Community