Kombinatorik: Wieviel Möglichkeiten Elemente aus unterschiedl. Zahlenlisten zu kombinieren?

Question

ich habe ein Problem, welches in die Kombinatorik geht. Ich stelle euch das Problem so vor, wie es auch mir vorgestellt wurde, um es zu lösen.

Ausgangssituation:

Ich habe n Zahlenlisten (in diesem Fall 2). Jede dieser Liste besitzt eine EIGENE Größe k und enthält die Zahlen von 1 bis k.

Nun gibt es eine Zielzahl, die mithilfe der Kombination der einzelnen Listenelemente erreicht werden soll. (In diesem Fall 7)

Veranschaulicht dann etwa so:

Liste 1: Größe 3

Liste 2 : Größe 5

1	1
2	2
3	3
	4
	5

Wieviele Möglichkeiten gibt es nun die Zielzahl (7) zu erreichen?

In diesem Fall sind es 2:

2 + 5 = 7

3 + 4 = 7

Ich habe viel probiert aber noch keine Lösung gefunden:

Gibt es eine Funktion/Algorhithmus die Anzahl der Möglichkeiten in diesem Fall zu errechnen?

Comments

Mal ein Anfang: (Auch zur Kontrolle, ob die Frage so zu lesen ist) 

Bei deiner Frage würde ich rechnen mit 2 Spalten: 

7 - 5 = 2

7 ist die Zielzahl und 5 ist die Länge der grösseren Liste. 

Passt das so? Und wie genau willst du weitere Spalten erzeugen und einbeziehen? 

Answer 1

Hi,

bei 2 Listen würde mir jetzt so spontan folgendes einfallen: 

Liste 1: 1 bis \(k_1\)

Liste 2: 1 bis \(k_2\)

Zielzahl: \(n\)

Zur Übersichtlichkeit:

\(s := \min(n-1,k_1) - \max(n-k_2,1)+1 \)

Anzahl der Möglichkeiten: \(\max(s,0)\).

Die ganze Min und Max Geschichte ist zur Absicherung für solche Sachen wie \(k_1 \geq n \) oder \(k_1+k_2 < n \) gedacht, 

Edit: Falls  diese speziellen Fälle nicht gelten, sprich \( k_1\) und \(k_2\) echt kleiner sind als \(n\) und \(k_1+k_2 \geq n \) so kriegt man aus der obigen Vorgehensweise die Anzahl der Möglichkeiten durch die einfache Formel: \(k_1+k_2+1-n\).

Gruß

Comments

Großer Respekt Yakyu, du gibst der Mathe Welt so vieles zurück! Daumen Hoch!

und schon einmal eine gute Nacht, Flo :-)

---

Danke Florian, dass ist sehr nett von dir :).

---

wie würde das ganze bei n Listen aussehen? Der Ansatz hat mir schon echt weitergeholfen :)

---

Dafür müsstest du erst mal präziseren was wir genau bei n Listen zählen würden.