Siebenstellige Zahlen

[Neuling]

Aus den Ziffern 1, 2, 3, 4, 5, 6, 7 kann man verschiedene 7stelliger Zahlen bilden.
Jede dieser Zahlen soll die Ziffern 1 bis 7 genau 1 mal enthalten.

Wie viele dieser Zahlen haben folgende Struktur:

Von je drei nebeneinanderstehenden Ziffern ist die mittelste entweder kleiner oder größer als ihre beiden Nachbarn.
(Oder anders gesagt, beide Nachbarn müssen das gleiche Merkmal - entweder größer oder kleiner - aufweisen.)

Beispiel: 1537462 zählt zu dieser Gruppe, denn, die 5 hat zwei kleinere Nachbarn, die 3 hat zwei größere, die 7 hat zwei kleinere, usw.

1357462 zählt nicht zu dieser Gruppe, denn die 3 hat links einen kleineren und rechts einen größeren Nachbarn.

[Otmar]

Bin gespannt, ob du eine schöne Lösung hast. Ich kann leider nur einen "mühevollen" Weg zur Lösung liefern:

Mehr ->

Die Zahl habe die Ziffern a,b,c,d,e,f,g in der Anordnung: abcdefg. Es ist dann entweder:

a<b>c<d>e<f>g oder
a>b<c>d<e>f<g

Beide Fälle sind gleich häufig, da die umkehrbare Abbildung von einer Ziffer z auf 8-z zwischen obere und unterer Ungleichungskette hin und her schaltet. Es reicht also Möglichkeiten des oberen Falls zu zählen und dann das Doppelte zu nehmen. Die Stellen mit großen Ziffern sind dann b, d und f und für die Belegung dieser Stellen habe ich die Fälle A,B,C,D,E:

A: Für b,d,f nehmen wir 7,6,5 in beliebiger Reihenfolge.

3! Möglichkeiten für b,d,f und 4! für den Rest.
Macht A=3!4!=144

B: Für b,d,f nehmen wir 7,6,4 in beliebiger Reihenfolge.

3! Möglichkeiten für b,d,f und 4!/2 (da die 5 nur an 2 von früher 4 Positionen stehen darf) für den Rest. Macht B=3!4!/2=72

C: Für b,d,f nehmen wir 7,6,3 in beliebiger Reihenfolge.

3! Möglichkeiten für b,d,f und 2!2! (jeweils 1,2 und 4,5 an 2 Positionen) für den Rest. Macht C=24

D: Für b,d,f nehmen wir 7,5,4 in beliebiger Reihenfolge aber die 7 ist nicht in der Mitte.

(3!-2) Möglichkeiten für b,d,f und 3! für den Rest (1,2,3 an drei Positionen). Macht D=4*3!=24

E: Für b,d,f nehmen wir 7,5,3 in beliebiger Reihenfolge aber die 7 ist nicht in der Mitte.

(3!-2) Möglichkeiten für b,d,f und 2! für den Rest (1,2 an zwei Positionen). Macht E=4*2!=8

Andere Möglichkeiten für b,d,f gibt es nicht.

Also gibt es insgesamt 2(A+B+C+D+E) = 2(144+72+24+24+8)=544 Möglichkeiten.

[Marc]

Mehr ->

1527463 ?

[Neuling]

@ Marc - Deine genannte Zahl gehört zur Gruppe der gesuchten, aber als Antwort auf die gestellte Frage ist diese Zahl falsch!

Hallo Otmar!
Du hast diese Aufgabe richtig gelöst. Und auch ein für Deinen Lösungsweg.

Wollte mich diesmal eigentlich, bzgl. des Lösungsweges, aus der Verantwortung stehlen, aber es wäre Dir gegenüber nicht fair. Habe einen allgemeinen Lösungsweg und Ergebnisse für Ziffernvorgaben bis einschließlich 8. Irgendwie stecken Deine Überlegungen aber hier auch schon drin.

Und gleich noch eine Bitte:
Falls Du meine "Übersetzungen" verstehst und Fehler entdeckst, so korrigiere bitte im Anschluss, damit User, die das später mal lesen, dann nicht ins Grübeln kommen.

Werde die Beschreibung vierteilen, dann kannst Du die Spoiler nach Belieben öffnen, falls Du zwischendurch den allgemeinen Weg selbst fortsetzen möchtest.

Also, los geht's:

Mehr ->

Die Vorüberlegungen sind die gleichen, die Du geführt hast. Es gibt Ziffernanordnungen, die mit einem "hohen" Wert beginnen und es gibt solche, die mit einem "tiefen" Wert beginnen. Zu jeder H-Anordnung gibt es genau eine T-Anordnung. (Dazu tausche man bei einer 7stelligen Zahl die 1 mit der 7, die 2 mit der 6, die 3 mit der 5 - die Zahlen vor und nach dem Tausch sind einander zugehörig) Man betrachtet daher im folgenden nur eine Variante und multipliziert am Ende mit 2.
Die Idee bei diesem Weg ---> wenn man die Lösung für n Ziffern kennt, kann man dann darauf aufbauend die Lösung für n+1 errechnen. (Da wir hier nur bis n=7 untersuchen, können wir bei Ziffern bleiben, ansonsten müssten wir ab n=10 eine andere Form wählen. a(Index i) definieren mit a(Index i) < a(Index i+1))
Ich lasse mal das Wort Index weg und schreibe H(1) = T(1) = 1; H(2) = T(2) = 1 (einmal die 21 und einmal die 12);
H(3) = T(3) = 2 (312, 213 und 132, 231)
Bei H(4) beginnen die eigentlichen Überlegungen. Die Ziffer 4 ist die größte Ziffer und kann bei einer H-Anordnung nur an 1. oder 3. Stelle stehen.
Bei H(n) dann allgemein steht die größte Ziffer n an einer ungeraden Position. Die restlichen Ziffern teilt man in zwei Gruppen, eine die rechts und eine die links von dieser größten Ziffer stehen. Zunächst werden nur die möglichen Gruppenbildungen untersucht, noch nicht die Reihenfolge innerhalb der Gruppen. Dabei kommen Binomialkoeffizienten ins Spiel.
Für die Gruppe von (n-1) Restzahlen kann man k Ziffern als rechtsstehend auszeichnen. Für die erste Auszeichnung hat man (n-1), für die zweite (n-2) Möglichkeiten usw. Das ergibt (n-1)*(n-2)* ... *(n-k) Varianten.

Mehr ->

Da aber die Reihenfolge der Auszeichnungen hier ohne Bedeutung ist, muss man noch herausdividieren, wie viele Möglichkeiten es für eine bestimmte Gruppe gibt, ausgezeichnet worden zu sein (bzgl. der Reihenfolge). In einer Gruppe von k Ziffern gibt es (gleiches Verfahren) k Möglichkeiten für das Glied, das als erstes ausgezeichnet wurde, (k-1) für das zweite usw. Das heißt also, dass immer k*(k-1)* ... *1 Auszeichnungsreihenfolgen genau zur gleichen Gruppenbildung führen.
Insgesamt gibt es also
(n-1)*(n-2)* ... *(n-k) / k*(k-1)* ... *1
Möglichkeiten, eine Teilmenge von k Ziffern aus (n-1) Ziffern zu bilden.

Mehr ->

Damit die gesamte Ziffernfolge eine H-Reihe wird, müssen die k Ziffern, die vor der größten Ziffer stehen, selbst eine H-Reihe bilden (wofür es H(k) Varianten gibt). Die größte Ziffer muss an einer ungeraden Position stehen und die n-1-k Ziffern, die hinter der größten stehen, müssen eine T-Reihe bilden (T(n-1-k) Möglichkeiten).
Das heißt also, wenn man die H(k) und T(k) für k ≤ n kennt, kann man jetzt H(n+1) und damit auch T(n+1) berechnen.

Mehr ->

H(1), H(2) und H(3) wurden oben schon genannt.

H(4) = T(3) + 3*2/2*1 H(2) T(1) = 2 + 3*1*1 = 5

H(5) = T(4) + 4*3/2*1 H(2) T(2) + H(4) = 5 + 6*1*1 + 5 = 16

H(6) = T(5) + 5*4/2*1 H(2) T (3) + 5*4*3*2/4*3*2*1 H(4) T(1) = 16 + 10*1*2 + 5*5*1 = 61

H(7) = T(6) + 6*5/2*1 H(2) T(4) + 6*5*4*3/4*3*2*1 H(4) T(2) + H(6) = 61 + 15*1*5 + 15*5*1 + 61 = 272

H(8) = T(7) + 7*6/2*1 H(2) T(5) + 7*6*5*4/4*3*2*1 H(4) T(3) + 7*6*5*4*3*2/6*5*4*3*2*1 H(6) T(1) =
272 + 21*1*16 + 35*5*2 + 7*61*1 = 1385


Für 7 Ziffern also 2*H(7) = 2*272 = 544

LG Neuling

[Otmar]

Hallo Neuling,
mir hat deine Lösung sehr gut gefallen.

Ich hatte auch mit Induktion begonnen, aber bald festgestellt, dass man den speziellen Fall auch relativ kurz abhandeln kann und sich dadurch viel Erklärung spart. Hab dann gespart.

Eine Bemerkung, die für dich ggf. selbstverständlich ist, würde ich noch ergänzen:

Mehr ->

Für die Anzahl der Möglichkeiten der H und T Anordnungen ist es völlig egal, welche Ziffernwerte verwendet werden, solange alle Ziffern verschieden sind, was ja hier der Fall ist. Bei den hier möglichen Anordungen ist nur die Anzahl der Ziffern wichtig, die in der Reihe untergebracht werden müssen.

[Neuling]

@ Otmar

Danke für's Begutachten und für die Ergänzung.