Diskussion:Kombination (Kombinatorik)

Kombination mit Wiederholung

Kann sein, dass ich da etwas übersehe, aber wird durch die Definition

${\frac {(n+k-1)!}{(n-1)!\,k!}}={n+k-1 \choose k}={n+k-1 \choose n-1}=\left(\!\!{n \choose k}\!\!\right)$

nicht $k=n-1$ vorausgesetzt? Für mich ergibt ${n+k-1 \choose n-1}$ keinen Sinn. LG --132.230.218.130 19:39, 8. Jun. 2013 (CEST)

Man wählt $k$ Elemente aus einer Menge von $n$ Elementen aus, es wird also $0\leq k\leq n$ vorausgesetzt. Zum Beispiel erhält man für die Anzahl der Möglichkeiten zur Auswahl von drei aus fünf Elementen mit Zurücklegen:

$\left(\!\!{5 \choose 3}\!\!\right)={7 \choose 3}={\frac {7!}{4!\cdot 3!}}=35$.

Siehe dazu auch die Abbildung im Artikel. Grüße, --Quartl (Diskussion) 19:53, 8. Jun. 2013 (CEST)

Hallo Quartl, das ist klar. Allerdings würde mit ${n+k-1 \choose n-1}$ etwas ganz anderes und offensichtlich falsches heraus kommen:

$\left(\!\!{5 \choose 3}\!\!\right)={7 \choose 4}={\frac {7!}{4!\cdot 4!}}=8.75$.

Übersehe ich da gerade irgendwas? VG, --132.230.218.130 22:17, 8. Jun. 2013 (CEST)

Du hast dich verrechnet: es muss ${7 \choose 4}={\frac {7!}{4!\cdot 3!}}=35$ heißen. Allgemein gilt ${n \choose k}={\frac {n!}{k!\cdot (n-k)!}}={n \choose n-k}$, siehe Binomialkoeffizient. Grüße, --Quartl (Diskussion) 22:24, 8. Jun. 2013 (CEST)

Nur so als Hinweis, die Ergebnisse müssen immer ganzzahlig sein. Außerdem sind Binomialkoeffizienten symmetrisch, d.h. ${n \choose k}={n \choose {n-k}}$ und damit auch ${7 \choose 3}={7 \choose 4}$--Kmhkmh (Diskussion) 22:30, 8. Jun. 2013 (CEST)

Ich habe das Gefühl wir reden etwas aneinander vorbei ;-) Mir geht es um den Teil ${n+k-1 \choose n-1}$ der obenstehenden Gleichung, der meines Erachtens falsch ist. VG --132.230.218.130 00:10, 9. Jun. 2013 (CEST)

Die obige Gleichung beruht auf der Symmetrieeigenschaft der Binomialkoeffizienten und benötigt deswegen die Annahme k=n-1 nicht.--Kmhkmh (Diskussion) 01:07, 9. Jun. 2013 (CEST)

Ich möchte die Diskussion nochmals beleben. Ich denke auch dass dies falsch ist. Die Symmetrie besagt nur dass ${n \choose k}={n \choose n-k}$ aber niemals dass ${n \choose k}={n \choose n-1}$ denn offensichtlich ist in der Regel k ungleich (n-1) und somit ist das nicht das gleiche. Der gleiche Fehler ist auch im Artikel über Multimengen (https://de.wikipedia.org/wiki/Multimenge#Anzahl_der_m.C3.B6glichen_Multimengen). (nicht signierter Beitrag von 146.60.54.209 (Diskussion) 23:24, 29. Mai 2016 (CEST))

Es wird nirgends behauptet, dass ${n \choose k}={n \choose n-1}$. Es wird aber benutzt, dass ${a+b \choose a}={a+b \choose b}$ --Daniel5Ko (Diskussion) 16:17, 30. Mai 2016 (CEST)

Stimmt, es wird behauptet dass ${n+k-1 \choose k}={n+k-1 \choose n-1}$. Diese Formulierung hat mich wohl ebenso wie meinen Vordiskutanten irritiert da $k\neq n-1$. Die Formulierung ist jedoch tatsächlich aufgrund der Symmetrie richtig. Sorry :) (nicht signierter Beitrag von 188.107.192.117 (Diskussion) 17:52, 30. Mai 2016 (CEST))

Ein wenig unklar

Gleich zu Beginn des Artikels heißt es : "... Kombination... eine Auswahl von Objekten, bei der (im Gegensatz zur Permutation) die Reihenfolge unberücksichtigt bleibt". Die Auswahl wird hier mit der Permutation als ihr Gegensatz verglichen, was die Ansicht nahelegen könnte, dass die Auswahl ebenso viele Objekte enthalten muss, wie die Permutation. Da sie das nicht muss, werde ich das mal verdeutlichen.--Anjolo (Diskussion) 15:37, 11. Apr. 2017 (CEST)

Summe über alle (n über k) - als Beispiel erwähnen?

Es gibt eine recht einfache Formel um die Summe über alle Kombinationen für jede Anzahl von möglichen Zügen zu erhalten. (Je nachdem ob die leere Menge erlaubt ist oder nicht: $\sum _{n,k=0}{\binom {n}{k}}=2^{n}$ oder $\sum _{n,k=1}{\binom {n}{k}}=2^{n}-1$.) Vielleicht wäre das was, um es als Beispiel unter Kombination (Kombinatorik)#Kombination ohne Wiederholung zu erwähnen. (Quelle für das Resultat momentan nur Wolframalpha, haha :) -- Amtiss, SNAFU ? 17:58, 22. Jun. 2020 (CEST)

Obstsalat

Wenn man einen Apfel, eine Birne und eine Banane hat, welche Möglichkeiten für Obstsalat gibt es? 1.Apfel, 2.Birne, 3.Banane, 4.Apfel+Birne, 5.Apfel+Banane, 6.Birne+Banane, 7. Apfel+Birne+Banane. Wie nennt sich das in der Kombinatorik? --49.228.194.205 11:47, 9. Mai 2021 (CEST)

Das sollte der Zeilensumme des Pascalschen Dreiecks entsprechen:

Möglichkeiten "nichts" aus 3 Obstsorten auszuwählen: ${\binom {3}{0}}=1$

Möglichkeiten 1 Obst aus 3 Sorten auszuwählen: ${\binom {3}{1}}=3$

Möglichkeiten 2 Obst aus 3 Sorten auszuwählen: ${\binom {3}{2}}=3$

Möglichkeiten 3 Obst aus 3 Sorten auszuwählen: ${\binom {3}{3}}=1$

Die Summe davon ist $2^{3}=1+3+3+1=8$, was man sich auch so vorstellen kann, das es für jedes der 3 Obstsorten 2 Möglichkeiten (in den Salat tun, oder weglassen) gibt.

Für die konkrete Frage muss immer noch eins abgezogen werden, da die Möglichkeit "nichts", also kein Obst in den Salat zu tun, nicht betrachtet wird. (nicht signierter Beitrag von 2A01:C22:B018:7B00:62E9:2730:5C6F:CB7D (Diskussion) 17:08, 22. Jul. 2021 (CEST))

Mengendarstellung

Stimmt denn das so:

${\bigl \{}(x_{1},x_{2},\ldots ,x_{n})\mid x_{i}\in \{0,1,\ldots ,k\},x_{1}+\ldots +x_{n}=k{\bigr \}}$

Müsste die Auswahl nicht eigentlich $(x_{1},x_{2},\ldots ,x_{k})$ heißen? Müssten die Indizes der Grundmenge nicht dementsprechend $\{0,1,\ldots ,n\}$ heißen? Und die letzte Bedingung ist mir völlig unklar. --TiHa (Diskussion) 09:07, 6. Jan. 2024 (CET)

M.E. könnte es für Kombinationen mit Wiederholung einfach so heißen:

$\{\{x_{1},x_{2},\ldots ,x_{k}\}~|~x_{i}\in \{a_{1},a_{2},\ldots ,a_{n}\}\}$

Und für Kombinationen ohne Wiederholung so:

$\{\{x_{1},x_{2},\ldots ,x_{k}\}~|~x_{i}\in \{a_{1},a_{2},\ldots ,a_{n}\},i\neq j\rightarrow x_{i}\neq x_{j}\}$

TiHa (Diskussion) 12:58, 6. Jan. 2024 (CET)

Leider auch falsch ;-)

So könnte es mit "Kombinationen ohne Wiederholung" klappen:

$\{\{\cdots x_{k}\}~|~(\cdots v_{k}),v_{i}\in \{\cdots a_{n}\},i\neq j\rightarrow v_{i}\neq v_{j},x_{i}=v_{i}\}$

Der Ausdruck "erstellt" erst die geordnete Menge der Variation und "kopiert" deren Elemente in die ungeordnete Menge der Kombination, in der die Reihenfolge keine Rolle spielt. --TiHa (Diskussion) 14:02, 6. Jan. 2024 (CET)

@TiHa: Die Formulierung im aktuellen Text ist korrekt und so verstehen, dass man jedem Element einen Wert zur Seite stellt, der angibt, ob dass Element in der zu beschreibenden Teilmenge enthalten sein soll oder nicht (man beachte eine (n,k)-Kombination kann man als die Anzahl der k-elementigen Teilmengen einer Menge mit n Elementen auffassen). Deswegen muss der Tupel n-Einträge haben, da er für jedes Element der Menge festlegen muss, ob es in der Teilmenge ist oder nicht. Jeder Tupel entspricht damit genau einer Teilmenge. Wenn eine Teilmenge nun k Elemente haben, soll dann sind dass genau alle Tupel die genau k Einsen enthalten, was sich ebe auch über die Summenbedingung formulieren lässt.--Kmhkmh (Diskussion) 15:27, 6. Jan. 2024 (CET)

Das wird mir so nicht klar. Woher kommen z.B. die Einsen, sodass $x_{1}+\ldots +x_{n}=k$ ergibt? Der Formel nach kann $x_{i}$ auch eine Zahl größer 1 sein, bis zu $k$. Sollte da nicht lieber $x_{i}\in \{0,1\}$ stehen?

Außerdem kommt in der Formel die Ausgangsmenge gar nicht vor, so dass sie keine der Kombinationen generiert. Sie ist vermutlich so gemeint, dass sie eine Menge generiert, die anzahlmäßig gleich groß ist. Das könnte man dann m.E. mit ranschreiben. --TiHa (Diskussion) 16:15, 6. Jan. 2024 (CET)

Für eine Menge $\{x_{1},\ldots ,x_{n}\}$ wird kann z.B. man die Teilmenge $\{x_{1},x_{2},x_{3}\}$ durch das Tupel $(1,1,1,0,\ldots ,0)$ beschreiben oder die Teilmenge $\{x_{n-2},x_{n-1},x_{n}\}$ durch das Tupel $(0,\ldots ,0,1,1,1)$. Wenn das j-te Element der Menge in der Teilmenge enthalten sein soll steht im Tupel an der j-ten Stelle eine 1 sonst eine 0, damit entspricht jedes Tupel eine einer Teilmenge und damit auch genau einer Kombination. Möchte man eine Darstellung über (0,1)-Tupel vermeiden und die Elemente der Menge direkt im Tupel verwenden, so kann die zweite Darstellung im Artikel verwenden.

Ansonsten steht der Zusammenhang zu Mengen auch kurz unter Binomialkoeffizient#Der_Binomialkoeffizient_in_der_Kombinatorik. Allerdings gebe ich dir Recht, dass man den Zusammenhang mit den Mengen etwas expliziter und ausführlicher darstellen sollte. Falls es sonst keiner macht werde ich das bei Gelegenheit mal ergänzen.--Kmhkmh (Diskussion) 17:30, 6. Jan. 2024 (CET)

Hm... nehmen wir als Beispiel n=5 und k=3. Dann wäre der Ausdruck $x_{i}\in \{0,1,\ldots ,k\}$ konkret $x_{i}\in \{0,1,2,3\}$ und es gäbe Tupel wie $(0,0,0,0,3)$ - etwa nicht? --TiHa (Diskussion) 18:30, 6. Jan. 2024 (CET)

Ja, solche Tupel gäbe es nicht bzw. es sind nur Tupel der Länge 5 zugelassen deren Einträge ausschlie0lich Nullen und Einsen sind. Für n=5 und k=3 haben wir als Grundmenge $M:=\{x_{1},x_{2},x_{3},x_{4},x_{5}\}$, die 3-elementigen Teilmengen entsprechen nun den 5-Tupeln mit genau 3 Einsen (und sonst nur Nullen). Die Teilmenge $\{x_{2},x_{4},x_{5}\}$ entspricht z. B. dem 5-Tupel $(0,1,0,1,1)$. Es gibt dann ${\binom {5}{3}}$ solche Tupel mit 3 Einsen (und 2 Nullen).--Kmhkmh (Diskussion) 22:34, 6. Jan. 2024 (CET)

Dieser Ausdruck lässt aber auch Tupel zu, wie (1,2,0,0,0), (3,0,0,0,0), da deren Summe 3 gemäß der letzten Bedingung k= 3 ist:

${\bigl \{}(x_{1},x_{2},\ldots ,x_{n})\mid x_{i}\in \{0,1,\ldots ,k\},x_{1}+\ldots +x_{n}=k{\bigr \}}$

Es würde mit den Nullen und Einsen funktionieren, wenn da $x_{i}\in \{0,1\}$ stünde. --TiHa (Diskussion) 03:02, 7. Jan. 2024 (CET)

Das steht ja auch im Artikel (Zitat: ${\bigl \{}(x_{1},x_{2},\ldots ,x_{n})\mid x_{i}\in \{0,1\},x_{1}+\ldots +x_{n}=k{\bigr \}}$). Vielleicht muss man noch einmal darauf hinweisen dass die $x_{i}$ im Tupel nicht die $x_{i}$ aus der Menge oben sind und man beiden notiert sollte man der Klarheit zu Liebe unterschiedliche $x_{i}$ Variablennamen benutzen. Also für eine Menge $M:=\{m_{1},\ldots ,m_{n}\}$ entspricht jeder Tupel der Form ${\bigl \{}(x_{1},x_{2},\ldots ,x_{n})\mid x_{i}\in \{0,1\},x_{1}+\ldots +x_{n}=k{\bigr \}}$ einer k-elementigen Teilmenge von M.--Kmhkmh (Diskussion) 03:22, 7. Jan. 2024 (CET)

Ich hab es jetzt aber, glaube ich verstanden. Meine Eingangsfrage bezog sich auf die Kombination mit Wiederholung. Da steht $x_{i}\in \{0,1,\ldots ,k\}$. Der Ausdruck $(x_{1},x_{2},\ldots ,x_{n})$ enthält dann für jedes Element der Ausgangsmenge $(a_{1},a_{2},\ldots ,a_{n})$ die Anzahl, wie oft es vorkommt. Jedenfalls ist es nicht die Menge der Kombinationen. --TiHa (Diskussion) 05:44, 7. Jan. 2024 (CET)

Ah sorry, die Mengendarstellungen für die Wiederholung hatte ich nicht beachtet bzw. nicht gesehen, dass du dich auf diese beziehst. Diese ist aber auch richtig soweit ich dass sehe und verallgemeinert in gewisser Weise die Tupeldarstellung für Kombinationen ohne Wiederholung. Jetzt steht an der j-ten Stelle des Tupels, wie oft das j-te Elemente der (Multi-)Menge bzw. die Kugel mit Nr. j aus der Urne gezogen wurde. Der n-Tupel enthält enthält also für jeder der n-Kugeln in der Urne die Angabe, ie oft sie gezogen wurde (im Falle ohne Wiederholung kann eine bestimmte Kugel ja nur 0 oder 1-mal gezogen werden). Die Summe all dieser Angaben muss immer noch k ergeben, da insgesamt ja nur k-Kugeln gezogen werden. Diese Fälle entsprechen jetzt aber nicht mehr der Anzahl der Teilmengen,von denen ich oben geredet habe, da in Mengen jedes Element ja nur einmal vorkommen darf. Man könnte aber einen Bezug zu bestimmen Multimengen (Verallgemeinerung von Mengen, die das mehrfache Auftreten desselben Elements zulässt konstruieren). Also im Beispiel n=5 und k=3 steht (1,2,0,0,0) für 1-mal Kugel Nr.1 und 2-mal Kugel Nr. 2 gezogen (und keine der anderen). Entsprechend ist bei (3,0,0,0,0) 3-mal die Kugel Nr. 1 gezogen wurden und sonst keine. Jeder zulässige Tupel entspricht hier wie im Falle ohne Wiederholung genau einer Ziehung bzw. beschreibt genau eine mögliche Ziehung. Unzulässig sind Tupel deren Summe s > k ist, da diese eine Ziehung mit Wiederholung von s Kugeln beschreiben (aber nur k Kugeln gezogen wurden).--Kmhkmh (Diskussion) 10:25, 7. Jan. 2024 (CET)

Vielen Dank für die Erläuterung. Das Urnenmodell finde ich oft nicht hilfreich, daher fand ich die Idee mit der Mengen-Repräsentation so gut. Für Kombinationen ohne Wiederholung müsste es m.E. so gehen, was meinst du?

$\{\{\cdots x_{k}\}~|~(\cdots v_{k}),v_{i}\in \{\cdots a_{n}\},i\neq j\rightarrow v_{i}\neq v_{j},x_{i}=v_{i}\}$

Für Kombinationen mit Wiederholung ist es etwas schwieriger. --TiHa (Diskussion) 13:35, 7. Jan. 2024 (CET)

Nachtrag a ist die Ausgangsmenge und das Tupel v entspricht der Variation. --TiHa (Diskussion) 13:39, 7. Jan. 2024 (CET)

Ich verstehe jetzt worauf du hinaus willst, beide Notationen im Artikel (für mit und ohne Wiederholung) sind doch korrekt. Ob man sich anhand des Urnenmodells oder (Multimengen) oder anderen Deutung klar macht, ändert ja nichts an iher Korrektheit. Insofern verstehe ich nicht ganz wieso eine andere Notation suchst bzw. haben willst. Die von dir vorgeschlagene wirkt auf mich deutlich komplizierter und ich bin nicht einmal sicher, ob ich sie auf Anhieb verstehe.--Kmhkmh (Diskussion) 16:35, 7. Jan. 2024 (CET)

Im Artikel steht nicht wirklich die Mengen-Repräsentation der Kombination, wie behauptet. Das ist lediglich eine Menge, deren Kardinalität äquivalent dazu ist. Im Artikel Variation ist sie das:

$\{(x_{1},x_{2},\dotsc ,x_{k})\mid x_{i}\in \{1,2,\dotsc ,n\},x_{i}\neq x_{j}~{\text{für}}~i\neq j\}$

Dieser Ausdruck generiert wirklich die Menge aller Variationen (n,k). Der Ausdruck soll ja beschreiben, was eine Variation ist. --TiHa (Diskussion) 18:13, 7. Jan. 2024 (CET)

Ich weiß was eine "wirkliche" Repräsentation sein soll. Zum einen sind bijektive Darstellungen im Prinzip austauschbar und man hat man immer verschiedene Möglichkeiten einen Gegenstand zu beschreiben und solch ein n-Tupel beschreibt eine Variation genau. Zum anderen wenn du eine Beschreibung anhand der Mengenelemente (mit einem k-Tupel) suchst, so liefert das die zweite Darstellung im Artikel (sofern es sich um Zahlenmengen handelt).--Kmhkmh (Diskussion) 18:29, 7. Jan. 2024 (CET)

Die "alternative" Darstellung ist die eigentliche Darstellung. Ich find an der ersten Darstellung darf nicht dranstehen, dass es die Mengen-Repräsentation sei, weil das nicht stimmt. (1,3,3) als Kombination ist nicht dasselbe, wie (1,0,2,0,0), das diese Kombination irgendwie beschreibt, aber eben nicht diese Kombination ist, denn diese muss z.B. k=3 Elemente haben und nicht 5. --TiHa (Diskussion) 18:54, 7. Jan. 2024 (CET)

"Mengenrepräsentation" steht hier nur für Repräsentation anhand von Mengen, was stimmt. Einträge sind nicht dasselbe wie Elemente, (1,3,3) und (1,0,2,0,0) sind beides unterschiedliche Darstellungen eines Elements bzw. einer Kombination. Wenn man will ist (1,0,2,0,0) sogar eine exaktere Beschreibung, da man ihr die Größe der Grundmenge bzw. n entnehmen kann, bei (1,3,3) kann man das nicht.--Kmhkmh (Diskussion) (ohne (gültigen) Zeitstempel signierter Beitrag von Kmhkmh (Diskussion | Beiträge) 19:09, 7. Jan. 2024 (CET))

Was ist dagegen einzuwenden?

Nebenbei, auch die "alternative Darstellung" ist nicht wirklich die gesuchte Menge, bzw. nur wenn es sich zufällig um Ziffern handelt.

Dieser Ausdruck für Kmomb. ohne Wdh. dagegen kommt auch mit der Ausgangsmenge {rot,gelb,grün,blau,schwarz} klar, und wird die Menge liefern, in der {rot,gelb,grün}, {rot,gelb,blau} usw. alle Kombinationen enthalten sind:

$\{\{\cdots x_{k}\}~|~(\cdots v_{k}),v_{i}\in \{\cdots a_{n}\},i\neq j\rightarrow v_{i}\neq v_{j},x_{i}=v_{i}\}$

Dein Argument erschließt sich mir nicht. Es ist so, als würde man beim Pytagoras sagen: "c= a²+b²", man braucht ja bloß noch die Wurzel zu ziehen..." --TiHa (Diskussion) 11:26, 8. Jan. 2024 (CET)

Keine Ahnung was du jetzt du jetzt mit einer falschen Analogie zu Pythagoras willst (wenn überhaupt wäre dass $c={\sqrt {a^{2}+b^{2}}}$ statt $c^{2}=a^{2}+b^{2}$, also eine Darstellung als Streckenlänge anstatt als Flächeninhalt).

Was gegen deinen Vorschlag spricht, ist dass die Notation mMn. unnötig kompliziert ist und jedenfalls für mich auf den ersten Blick nicht einmal lesbar (mir ist nicht klar wofür $\{\{\cdots x_{k}\}~|~(\cdots v_{k})$ genau stehen soll). Zudem ist die aktuelle Notation angemessen und sinnvoll und es gibt nicht wirklich einen Grund daran herumzubasteln. Wenn du weiteres Feedback benötigst, kannst du im Portal:Mathematik nachfragen, ansonsten gilt wie überall, dass auch die Notation in WP-Artikeln der in der Fachliteratur üblichen Notation zu folgen hat und dies im Zweifelsfall auch dementsprechend zu belegen ist.--Kmhkmh (Diskussion) 11:53, 8. Jan. 2024 (CET)

Es steht keine Quelle dran - kann das dann raus? --TiHa (Diskussion) 12:57, 8. Jan. 2024 (CET)

Du scheinst zu trollen - nicht sehr nett... --TiHa (Diskussion) 12:59, 8. Jan. 2024 (CET)

Löschung

das von mir eingetragene Beispiel zur chemischen Reaktionstechnik wurde gelöscht, ob wohl sehr interessant. Leider hab ich keine Quelle dazu. Grüße Michael --176.6.195.235 23:01, 13. Mär. 2024 (CET)

Beachte WP:Q und belege deine Ergänzungen und Änderungen immer. --Roger (Diskussion) 07:45, 14. Mär. 2024 (CET)