Lotto Permutationen

[Flex]

Hallo zusammen,


nachdem ich mir ein wenig den Kopf zerbrochen und Google mehr als
bemüht habe sehe ich meine letzte Chance hier in der Newsgroup der
Experten.


Ich habe mir ein kleines Progamm geschrieben, das mir die Permutationen
der Lottozahlen ausgibt.
Die Ausgabe sieht wie folgt aus:

1;1;2;3;4;5;6
2;1;2;3;4;5;7
3;1;2;3;4;5;8
4;1;2;3;4;5;9
5;1;2;3;4;5;10
6;1;2;3;4;5;11
7;1;2;3;4;5;12
8;1;2;3;4;5;13
9;1;2;3;4;5;14
[...]
13983807;42;44;45;47;48;49
13983808;42;44;46;47;48;49
13983809;42;45;46;47;48;49
13983810;43;44;45;46;47;48
13983811;43;44;45;46;47;49
13983812;43;44;45;46;48;49
13983813;43;44;45;47;48;49
13983814;43;44;46;47;48;49
13983815;43;45;46;47;48;49
13983816;44;45;46;47;48;49


Die 1. Zahl ist die n-te Permutation und ich stehe vor der Aufgabe
herazszufinden welche Permutation die Zahlen 27, 31, 36, 37, 43, 44
haben ohne mein Programm alle Permutationen ausrechnen zu lassen. Das
kann man doch sicher elegant in einer Formel werfen und ein Ergebnis
erhalten.


Gebt mir Euren Hirnschmalz! :-)



Viele Grüße,
*Flex*

[Thomas Heye]

Hallo,

Post by Flex
Hallo zusammen,
nachdem ich mir ein wenig den Kopf zerbrochen und Google mehr als
bemüht habe sehe ich meine letzte Chance hier in der Newsgroup der
Experten.
Ich habe mir ein kleines Progamm geschrieben, das mir die Permutationen
der Lottozahlen ausgibt.

Nein, das sind keine "Permutationen", sondern Kombinationen ohne
Zurücklegen *mit Berücksichtigung der Reihenfolge*.
Wenn ichs recht versteh, möchtest Du wissen, nach wie vielen
"Schleifendurchläufen" Dir dein Programm eine gegebene aufsteigend
sortierte 6er-Reihe der Zahlen 1...49 ausgibt. Dürfte schwierig sein,
das in eine geschlossene Formel "zu packen"; aber ein paar Ideen:
Als Beispiel die Reihe 27, 31, 32, 34, 36, 41.
- es gibt 48*47... *(48-5+1) aufsteigend geordnete Reihen mit
Anfangszahl 1;
- 47*46...(47-5+1) reihen mit Anfangszahl 2 (da 2 die kleinste Zahl
ist, kommen für die 2. bis 6. Zahl nur die Zahlen 3...49 in Frage)
usw. bis hin zu Reihen mit Anfangszahl 26.
Wie viele aufsteigend geordnete 6er-Reihen mit den Anfangszahlen
27,28; 27,29; 27,30 gibt es?
Wie viele 6er-Reihen, beginnend mit 27,31,32,33 gibt es?
...

Gruß
Thomas

[Gerd Thieme]

Post by Thomas Heye
Nein, das sind keine "Permutationen", sondern Kombinationen ohne
Zurücklegen *mit Berücksichtigung der Reihenfolge*.

^^^
ohne

Die Zählung der Kombinationen scheint auch zu stimmen, (49 über 6) ist
tatsächlich 13983816.

Eine »einfache« Formel zur Ermittlung der lexikographischen Ordnungszahl
einer gegebenen Kombination kann ich nicht angeben, aber eine
Rekursionsvorschrift ist leicht zu finden.

Sei (a1,a2,a3,...,ak) eine Kombination von k aus n natürlichen Zahlen
mit 0<a1<a2<a3<...<ak<=n, dann gilt für die Ordnungszahl

m=1, falls k=0, und sonst
m=m(a1,a2,a3,...,ak,n)=m(a2-a1,a3-a1,...,ak-a1,n-a1)+Binomial(n,k)-Binomial(n+1-a1,k)

Begründung: Die Anzahl der Kombinationen, deren kleinstes Element größer
oder gleich a1 ist, ist (n+1-a1 über k). Das Komplement zu (n über k)
ist dann die Anzahl der Kombinationen, deren kleinstes Element kleiner
als a1 ist. Diese Kombinationen liegen alle lexikographisch vor der
gegebenen Kombination.

Noch zu zählen bleiben diejenigen Kombinationen, die mit a1 beginnen und
vor der gegebenen Kombination liegen. Weil bei diesen das kleinste
Element konstant ist, kann es entfernt werden, wobei sich die übrigen
Elemente sowie das n um seinen Wert verringern. Damit ist die Aufgabe
von k aus n Elementen auf k-1 aus n-a1 Elementen zurückgeführt.

Für das angegebene Beispiel erhält man:

m(27,31,32,34,36,41,49)
= m(4,5,7,9,14,22) + Binomial(49,6)-Binomial(23,6)
= m(1,3,5,10,18) + Binomial(22,5)-Binomial(19,5) + 13983816-100947
= m(2,4,9,17) + Binomial(18,4)-Binomial(18,4) + 26334-11628 + 13882869
= m(2,7,15) + Binomial(17,3)-Binomial(16,3) [phone] + 13897475
= m(5,13) + Binomial(15,2)-Binomial(14,2) + 680-560 + 13897475
= m(8) + Binomial(13,1)-Binomial(9,1) + 105-91 + 13897595
= 1 + 13-9 + 13897609
= 13897714

Beim Programmieren läßt sich die Rekursion leicht per Iteration
erledigen.

Gerd

[Gerd Thieme]

Post by Gerd Thieme
Eine »einfache« Formel zur Ermittlung der lexikographischen Ordnungszahl
einer gegebenen Kombination kann ich nicht angeben,

Nun kann ich's doch:

m = {n \choose k} - \sum_{i = 1}^{k} {{n - a_i} \choose {k + 1 - i}}

Für das angegebene Beispiel ist das

m = (49 über 6) - (49-27 über 6) - (49-31 über 5) - (49-32 über 4)
- (49-34 über 3) - (49-36 über 2) - (49-41 über 1)
= 13897714

Eine verblüffend einfach aussehende Lösung.

Gerd