Mathematik online lernen im Mathe-Forum. Nachhilfe online

Startseite » Forum » Abzählen geordneter Summen <= S aus n Summanden

Abzählen geordneter Summen <= S aus n Summanden

Universität / Fachhochschule

Tags: Kombinatorik

GeheimAgent001254 aktiv_icon

05:07 Uhr, 19.10.2024

Für gegebene natürliche Zahlen

n

S

Wie viele Kombinationen

(k_{0}, . . ., k_{n})

(Reihenfolge relevant)
gibt es mit

\sum_{i = 0}^{n} k_{i} < = S

,
wobei

0 < = k_{i} < = S

Beispiele für S=4:
n=0: Erg=0

n=1: Erg=5
(0),(1),(2),(3),(4)

n=2: Erg=15
(0,0),(0,1),(0,2),(0,3),(0,4),(1,0),(1,1),(1,2),(1,3),(2,0),(2,1),(2,2),(3,0),(3,1),(4,0)

Hat jemand eine Idee?

Für alle, die mir helfen möchten (automatisch von OnlineMathe generiert):
"Ich möchte die Lösung in Zusammenarbeit mit anderen erstellen."

Hierzu passend bei OnlineMathe:

Online-Übungen (Übungsaufgaben) bei unterricht.de:

Gemischte Aufgaben der Kombinatorik
Kombinatorik: Ziehen mit Reihenfolge und mit Zurücklegen
Kombinatorik: Ziehen mit Reihenfolge und ohne Zurücklegen
Kombinatorik: Ziehen ohne Reihenfolge und ohne Zurücklegen

pivot aktiv_icon

08:52 Uhr, 19.10.2024

Hallo,

folgende Formel für die Anzahl der Kombinationen könnte passen:

A (S, n) = {\begin{array}{rcl} (\binom{S + 1}{n}), & n \geq 1 \\ 0, & n = 0 \end{array}

Gruß
pivot

HJKweseleit aktiv_icon

11:48 Uhr, 19.10.2024

Um genau die Summe S zu erhalten, kannst du dir Folgendes vorstellen, das ich im Bild für S = 12 und n = 5 dargestellt habe:

Du bildest eine Kästchenschlange der Länge S + n - 1. Dann suchst du dir n - 1 Kästchen aus und färbst sie schwarz. Es verbleiben S Kästchen, die durch die n - 1 schwarzen voneinander in n Blöcke getrennt werden. Diese Blöcke bilden deine Summanden. Fehlen Blöcke z.B. am Rand oder zwischen zwei schwarzen Kästchen, stehen sie für die Zahl 0 (s.Bild).

Jede Kombination für die schwarzen Kästchen bildet eine andere Möglichkeit ab, und alle werden erfasst. Da es

(\begin{array}{rcl} S + n - 1 \\ n - 1 \end{array})

Möglichkeiten dafür gibt, gibt es auch entsprechend viele Summendarstellungen.

Für alle Summen

<

S musst du dann nur die obigen Werte für kleinere S zusammenzählen:

\sum_{i = 0}^{S} (\begin{array}{rcl} i + n - 1 \\ n - 1 \end{array}) = (\begin{array}{rcl} S + n \\ n \end{array})

HAL9000

13:41 Uhr, 19.10.2024

@GeheimAgent001254

1) Wenn ich mal deine Beispiele als Grundlage nehme, dann hast du dich in der Aufgabenstellung verschrieben und meinst nicht

\sum_{i = 0}^{n} k_{i} \leq S

(das wären

n + 1

Summanden) sondern stattdessen

\sum_{i = 1}^{n} k_{i} \leq S

. Achte das nächste mal also besser genau auf die Indizes.

2) Statt eine Summation durchzuführen (wie bei HJKweseleit) kann man das auch lösen durch Einführung einer nichtnegativen "Schlupfvariablen"

k_{n + 1}

:

Die Anzahl der Lösungstupel

(k_{1}, \dots, k_{n})

nichtnegativer ganzer Zahlen mit

\sum_{k = 1}^{n} k_{i} \leq S

ist gleich der Anzahl der Lösungstupel

(k_{1}, \dots, k_{n}, k_{n + 1})

nichtnegativer ganzer Zahlen mit

\sum_{k = 1}^{n + 1} k_{i} = S

.

Letztere ergibt sich gemäß Anzahlformel "Kombinationen mit Wiederholung" als

(\begin{array}{c} n + 1 + S - 1 \\ S \end{array}) = (\begin{array}{c} n + S \\ S \end{array}) = (\begin{array}{c} n + S \\ n \end{array})

.

Oder um im (leicht modifizierten) Bild von HJKweseleit zu bleiben: Man nimmt

S

weiße und

n

schwarze Kästchen und ordnet die auf alle mögliche Weisen an.

k_{1}

ist die Anzahl der weißen Kästchen bis zum ersten schwarzen Kästchen,

k_{2}

die Anzahl der weißen Kästchen vom ersten bis zum zweiten schwarzen Kästchen, usw.

k_{n}

die Anzahl der weißen Kästchen vom

(n - 1)

-ten bis zum

n

-ten schwarzen Kästchen. Die weißen Kästchen nach dem letzten,

n

-ten schwarzen Kästchen zählen dabei dann nicht mehr zur Summe.

GeheimAgent001254 aktiv_icon

20:17 Uhr, 19.10.2024

@HAL9000
Du hast recht ich meine n Summanden und damit Indizes 1 bis n.

\sum_{i = 1}^{n} k_{i} < = S \Leftrightarrow 0 < = S - \sum_{i = 1}^{n} k_{i} < = S

\Rightarrow S - \sum_{i = 1}^{n} k_{i} = k_{0}

\Rightarrow S = k_{0} + \sum_{i = 1}^{n} k_{i} = \sum_{i = 0}^{n} k_{i}

Das Beispiel mit dem Kästchen schwarz färben ist für mich Kombination ohne Wiederholung.
Ich kann ja kein Kästchen zweimal schwarz machen. Da verstehe ich also den Zusammenhang.

(\binom{m}{k})

mit

m = n + S

(weiße Kästchen) und

k = n

(färben), und so bleiben immer S weiße Kästchen in n+1 Gruppen (Summanden) über.

Aber bei Kombination mit Wiederholung hab

(\binom{m + k - 1}{k})

mit

m = n + 1

und

k = S

m ist also die Menge der k_i. Dann kann ich aber doch bei S = 4, n=2
Sowas ziehen (k_4, k_4, k_4, k_4)
Irgendwie fehlt mir da der Zusammenhang zur Fragestellung, obwohl das Ergebnis ja dasselbe ist.

HJKweseleit aktiv_icon

22:51 Uhr, 19.10.2024

"Aber bei Kombination mit Wiederholung hab
...
m ist also die Menge der k_i. Dann kann ich aber doch bei S = 4, n=2
Sowas ziehen (k_4, k_4, k_4, k_4)
Irgendwie fehlt mir da der Zusammenhang zur Fragestellung, obwohl das Ergebnis ja dasselbe ist."

Deine Frage ist unverständlich. Insbesondere: Wenn n=2 ist, ziehst du ja nicht 4 Zahlen.
--------------------------------------------------------------------------------------------

Als Ergänzung zu meinem ersten Beitrag:

\sum_{i = 0}^{S} (\begin{array}{rcl} i + n - 1 \\ n - 1 \end{array}) = (\begin{array}{rcl} S + n \\ n \end{array})

zeigt, dass die Summe durch einen einzigen Binominalkoeffizienten ausgedrückt werden kann. Setzt man dieses wieder in eine entsprechende Grafik um, so ist die Lösung durch ein einziges Bild darstellbar. Nehmen wir wieder S = 12 und n = 5. Jetzt betrachten wir n + S = 17 (statt 16) Felder, von denen n = 5 (statt 4) schwarz gefärbt werden. Dann erhalten wir wie im ersten Beispiel jetzt 6 statt 5 verschiedene Zahlen, deren Summe S = 12 gibt. Dabei kann die letzte Zahl von 0 (das letzte schwarze Feld ist ganz rechts) bis S = 12 (alle schwarzen Felder sind ganz links) gehen.

Damit bleiben für die ersten n=5 Zahlen als mögliche Summen die Werte von S = 12 bis 0 übrig. Wenn wir also die letzte Zahl immer streichen, bekommen wir für die ersten n = 5 Zahlen alle möglichen Summen von 0 bis S in allen möglichen Anordnungen.

GeheimAgent001254 aktiv_icon

09:46 Uhr, 20.10.2024

@HJKweseleit ich sagte ja deine Lösung verstehe ich.

Aber das Färben der Kästchen, da stimmts du sicher zu ist Kombination ohne Wiederholung.

Bei Kombination mit Wiederholung wie von HAL9000 gezeigt kommt diesselbe Lösung raus.
Da in diesem Fall m = n + 1 und k = S ist,
muss der Fall von S = 4 und n = 2 durch k (also 4 Ziehungen) dargestellt sein.
Also irgendworan muss HAL9000 ja die Kombination mit Wiederholung erkannt haben, da das ja sein letzter Lösungschritt ist; das wollt ich gern wissen.

HAL9000

10:41 Uhr, 20.10.2024

@GeheimAgent001254

Betreffs des Zusammenhangs Tupelanzahl - Kombinationen mit Wiederholung siehe

de.wikipedia.org/wiki/Kombination_(Kombinatorik)#Mengendarstellung_2 .

Genauer erklärt: Jedes Tupel

(k_{1}, \dots, k_{n + 1})

mit

\sum_{i = 1}^{n + 1} k_{i} = S

entspricht einer Auswahl von

S

Elementen aus der Menge

{1, \dots, n + 1}

mit Zurücklegen aber ohne Berücksichtigung der Auswahlreihenfolge, wobei

k_{i}

die Anzahl ist, wie oft dabei Zahl

i

ausgewählt wurde.

1588322

1588296

	Status: nicht eingeloggt	Noch nicht registriert?