Aufzählen und Rekursion verständlich erklärt

Wie viele verschiedene Schichtfolgen sind erlaubt, wenn Regeln gelten wie „keine Frühschicht direkt nach einer Nachtschicht“ und „nie drei Nächte hintereinander“? Alle Folgen aufzuschreiben und einzeln zu prüfen, gibt schon bei einem Planungszeitraum von wenigen Wochen auf. Es geht anders: Man muss sich nur merken, wie die Folge gerade endet, nicht, wie sie entstanden ist. Diese Seite zeigt das erst ohne Formeln, dann für Fachleute, samt der Grenze, an der dieses Gedächtnis selbst zu groß wird.

Zuletzt aktualisiert: 3. November 2026

Ein Wort unbekannt? Das Begriffsverzeichnis erklärt es in wenigen Sätzen.

Wie viele Schichtfolgen sind erlaubt?

Sie planen Schichten für ein Team: Jeden Tag gibt es Früh, Spät oder Nacht. Zwei Regeln gelten. Auf eine Nachtschicht darf nicht direkt eine Frühschicht folgen, die Ruhezeit wäre zu kurz. Und drei Nächte hintereinander sind verboten. Eine Folge von Schichten über mehrere Tage ist gültig, wenn keine der beiden Regeln irgendwo in ihr vorkommt.

Gefragt ist nicht, welche Folge die beste ist, sondern wie viele gültige Folgen es gibt. Die Zahl zeigt, wie viel Spielraum die Regeln lassen und ob man Varianten je einzeln durchsehen kann. Die Demo zu dieser Seite läuft im Browser (Link am Ende dieses Teils); sie zählt nur und plant nicht.

Zwei Wege durch alle Folgen

Der naheliegende Weg: jede denkbare Folge hinschreiben und prüfen. Die Zahl der denkbaren Folgen wächst mit jedem zusätzlichen Tag um den Faktor drei: drei Folgen bei einem Tag, neun bei zwei Tagen, bald mehr, als ein Rechner ansehen kann.

Ein klügerer Weg: die Folgen Tag für Tag aufbauen und einen Anfang sofort fallen lassen, sobald er eine Regel verletzt. Wer mit Nacht und dann Früh beginnt, wird nie weiterverfolgt. Das spart viel, aber man fasst weiterhin jede gültige Folge einzeln an.

Wo beide Wege aufgeben, misst die Demo auf dem Rechner, auf dem sie läuft. Auf dem Entwicklungsrechner trug das Abschneiden bis zu gut zwei Wochen Planungszeitraum; je nach Rechner und Last kann die Grenze deutlich anders liegen. Hochgerechnet (keine Messung) bräuchte das Durchprobieren für einen Planungsmonat dort etwa einen Monat.

Der dritte Weg: nur das Ende der Folge merken

Ob die nächste Schicht erlaubt ist, hängt nicht von der ganzen Vorgeschichte ab, sondern nur davon, wie die Folge gerade endet. Zwei Folgen, die gleich enden, haben genau dieselben erlaubten Fortsetzungen. Bei den Regeln dieser Seite reichen drei Fälle:

• Die Folge endet nicht auf eine Nacht (oder ist noch leer): Jede der drei Schichten darf folgen.
• Die Folge endet auf genau eine Nacht: Früh ist verboten, Spät und Nacht sind erlaubt.
• Die Folge endet auf zwei Nächte hintereinander: Früh und Nacht sind verboten, nur Spät ist erlaubt.

Diese Fälle heißen Zustände. Sie sind das Gedächtnis der Regeln. Statt Folgen zu zählen, führt man für jeden Fall eine einzige Zahl, nämlich wie viele gültige Folgen in diesem Fall enden.

Ein Tag weiter geht so: Jede dieser Zahlen wird auf die Fälle verteilt, in die die nächste Schicht führt; verbotene Übergänge fallen weg. Nach zwei Tagen sind so acht der neun möglichen Folgen gültig, nur Nacht, dann Früh fällt weg. Die Summe der drei Zahlen ist die Zahl der gültigen Folgen. Dieses Tag-für-Tag-Rechnen heißt Rekursion: Jeder Schritt baut auf dem vorigen auf.

Der Gewinn: Der Aufwand wächst mit der Zahl der Tage mal der Zahl der Fälle, nicht mit der Zahl der Folgen. Die Demo zählt so sehr lange Folgen exakt (auf dem Entwicklungsrechner in einem Bruchteil einer Sekunde) und prüft jede Zählung mit einer zweiten, unabhängigen Rechnung.

Wie groß muss das Gedächtnis sein?

Entscheidend ist, wie viele Fälle man sich merken muss. Bei Regeln der Art „diese Schichten dürfen nie direkt aufeinander folgen“ (verbotene zusammenhängende Teilfolgen) bleibt das Gedächtnis klein: Man merkt sich nur das längste Ende der Folge, das der Anfang eines Verbots ist. Die Zahl der Fälle ist dann höchstens so groß wie die Verbote zusammen lang sind. Für andere Arten von Regeln gilt das nicht ohne Weiteres.

Anders bei Regeln wie „jeder Auftrag kommt genau einmal vor, und bestimmte Aufträge dürfen nicht direkt hintereinander stehen“. Dann muss man sich merken, welche Aufträge schon vergeben sind, und das Gedächtnis wächst mit jedem zusätzlichen Auftrag um mehr als den Faktor zwei. Hier steht die zweite Wand: Auch die Rekursion kommt an ihre Grenze, bleibt aber weit unter der Zahl aller Reihenfolgen. Die Grenze ist die Größe des Gedächtnisses, nicht die Länge der Folge.

Zwei Stolpersteine beim Rechnen

Rechnet ein Programm mit gerundeten Kommazahlen statt mit ganzen Zahlen, weicht das Ergebnis bei den Regeln dieser Seite schon nach etwas mehr als einem Monat Planungszeitraum vom genauen Wert ab. Bei einem Zeitraum von mehr als zwei Jahren kann der Rechner die Zahl gar nicht mehr darstellen und meldet nur noch „unendlich“.

Der zweite Stolperstein ist das Raten: Man rechnet die ersten Zahlen aus und sucht eine Regel, die jede aus den vorigen bildet. Eine Regel, die zu den ersten Zahlen passt, kann später scheitern; die Demo zeigt, dass einfachere Regeln oft nur den Anfang treffen. Gilt die Regel erst ab einem späteren Tag (einem Anlauf), kann die wirksame Regel kürzer sein, als das Raten zeigt.

Wie ernst sind die Zahlen der Demo zu nehmen?

Alles in der Demo ist gerechnet, nichts stammt aus echten Dienstplänen. Zeiten sind Messungen eines Rechners und hängen von Rechner und Last ab; Hochrechnungen sind keine Messungen. Die Demo zeigt, was ein Gedächtnis leisten kann und wo es endet, nicht, wie viele Folgen in Ihrem Betrieb gelten.

Woran Sie es im Betrieb merken:

• Ein Planungsprogramm probiert alle Varianten durch, und die Rechenzeit steigt mit jedem zusätzlichen Planungstag um einen festen Faktor: Prüfen Sie, ob die Regeln nur Verbote aufeinanderfolgender Schichten sind; dann reicht ein kleines Gedächtnis.
• Eine neue Regel der Art „jede Aufgabe nur einmal“ macht eine bisher schnelle Zählung plötzlich unbezahlbar: Das Gedächtnis hat sich vergrößert.
• Eine aus wenigen Zahlen erratene Formel trifft die späteren Werte nicht: Sie passte nur zum Anfang.

Hinweis: Alle Demos rechnen mit synthetischen oder frei verfügbaren Beispieldaten und laufen auf einem externen Anbieter (Datenschutz). Bitte geben Sie darin keine vertraulichen oder personenbezogenen Daten ein. Die Ergebnisse gelten für die jeweilige Demo-Instanz und lassen sich nicht ungeprüft auf reale Fälle übertragen; für darauf gestützte Entscheidungen übernehme ich keine Gewähr.

Modell und Annahmen

Dieser Teil ist eigenständig lesbar. Er fasst die formale Beschreibung der Demo zusammen; die vollständige Fassung steht im Expander „📐 Mathematische Formulierung“ der Demo.

• Gezählt wird die Zahl \(a(n)\) der Wörter der Länge \(n\) über einem Alphabet mit \(k\) Zeichen, die kein Verbot aus einer Menge \(P\) als zusammenhängende Teilfolge enthalten: bis zu sechs Verbote von je höchstens sechs Zeichen. Standard: Schichtfolgen aus Früh, Spät, Nacht ohne „Früh direkt nach Nacht“ und ohne drei Nächte in Folge.
• Automat: Die Zustände sind die echten Anfänge der Verbote einschließlich des leeren Wortes, nur erreichbare; ein Schritt verteilt die Zahlen der Wörter je Zustand auf die Folgezustände, verbotene Übergänge entfallen.
• Drei Wege zur selben Zahl: alle Wörter prüfen (brute_count: \(k^n\) Wörter erzeugen und einzeln prüfen), Aufzählen mit Abschneiden (dfs_count: nur gültige Anfänge erweitern) und die Rekursion über die Zustände (count_dp: Vektor über die Zustände, ein Schritt je Länge, exakte Python-Ganzzahlen).
• Unabhängiger Prüfer in der App (check_count): Matrixpotenz der Übergangsmatrix statt Vektorschritten, bis \(n = 8\) zusätzlich Aufzählen; bei Abweichung zeigt die App einen Fehler statt einer Zahl.
• Rekursion raten (solve_recurrence, smallest_recurrence): aus den ersten \(2r\) Gliedern die Rekursion der Ordnung \(r\) mit exakten Brüchen bestimmen und gegen die ersten 60 Glieder prüfen.
• Zweite Wand (Experiment 5): \(m\) Symbole, jedes genau einmal, bestimmte geordnete Nachbarpaare verboten.
• Hochrechnung (nicht gemessen): Zeit je Wort der letzten Messzeile mal Zahl der Wörter beim Ziel; die Rekursion wird am Ziel gemessen.

Die Formeln

Aufgabe. Gegeben ein Alphabet \(\Sigma\) mit \(k\) Zeichen und Verbote \(P = \{p_1, \dots, p_s\}\). Gesucht ist \(a(n)\), die Zahl der Wörter der Länge \(n\), die kein \(p_j\) als zusammenhängende Teilfolge enthalten. Es gilt \(a(n) \le k^n\).

Zustand. Für ein gelesenes Wort \(w\) sei \(\sigma(w)\) das längste Ende von \(w\), das ein echter Anfang eines Verbots ist (das leere Wort zählt). Ob \(wc\) ein Verbot beendet, hängt nur von \(\sigma(w)\) und dem nächsten Zeichen \(c\) ab, und \(\sigma(wc)\) ist ebenfalls durch \(\sigma(w)\) und \(c\) bestimmt. Die Zahl der Zustände ist höchstens

\[1 + \sum_j (|p_j| - 1)\]

(das leere Wort plus die echten Anfänge; die Vormessung nannte „höchstens die Summe der Verbotslängen“, die genaue Schranke ist diese und wird so getestet).

Rekursion. Sei \(v_n(z)\) die Zahl der gültigen Wörter der Länge \(n\) im Zustand \(z\) und \(\delta(z, c) \in Z \cup \{\bot\}\) die Übergangsfunktion (\(\bot\) = verboten). Dann ist

\[v_0 = e_{\text{Start}}\]

\[v_{n+1}(t) = \sum_{(z, c):\, \delta(z, c) = t} v_n(z)\]

und die gesuchte Zahl ist

\[a(n) = \sum_z v_n(z) = e_{\text{Start}}^{\top} M^n \mathbf{1}\]

mit der Übergangsmatrix \(M\) (\(M_{zt}\) = Zahl der Zeichen, die \(z\) nach \(t\) führen). Der Aufwand wächst mit \(n\) mal Zustandszahl, nicht mit der Zahl der Wörter.

Lineare Rekursion. Nach Cayley–Hamilton erfüllt \(M\) sein charakteristisches Polynom vom Grad \(|Z|\); deshalb erfüllt \(a(n)\) eine lineare Rekursion mit konstanten Koeffizienten, deren Ordnung höchstens \(|Z|\) ist und die ab \(n = |Z|\) gilt. Der Anlauf kann später enden, wenn die Koeffizienten eine kleinere wirksame Ordnung ergeben (Experiment 4).

Zweite Wand. Für „jedes von \(m\) Symbolen genau einmal, Paare \(B\) verboten“ ist der Zustand \((S, \ell)\) mit der Menge \(S \subseteq \{1, \dots, m\}\) der benutzten Symbole und dem letzten Symbol \(\ell \in S\). Das sind höchstens

\[2^m \cdot m\]

Zustände mit je \(m\) Übergängen, also \(O(2^m m^2)\) Schritte; die Aufzählung prüft \(m!\) Reihenfolgen. Es ist dieselbe Zustandsidee wie die Teilmengenrekursion von Held und Karp für die Rundreise.

Gleitkomma. Ganze Zahlen über \(2^{53}\) sind als Python-float nicht mehr alle darstellbar; ab einem Wert, den die Zahlen für große \(n\) überschreiten, gibt die Rechnung inf.

Befunde

Alle Zahlen stammen aus der README der Demo; jede steht in deren Tests (tests/test_claims.py, tests/test_verdicts.py, tests/test_oracle_aufzaehlen_rekursion.py), mit einer Ausnahme: Zeiten sind Messungen des Entwicklungsrechners (Windows, Python 3.14, Phase 0 und Browser-Durchlauf) und stehen nicht in Tests; getestet ist nur die Rangfolge mit großem Abstand. Zeiten und Hochrechnungen hängen vom Rechner ab, wie die Zeilen mit Zeitangaben zeigen.

Frage	Befund
Wie viele Folgen im Standardfall?	a(0) bis a(10): 1, 3, 8, 20, 51, 130, 331, 843, 2147, 5468, 13926; a(12) = 90 328 von 3¹² = 531 441 Folgen (17,0 %).
Welche Rekursion und welches Wachstum hat die Standardfolge?	a(n) = 2a(n−1) + a(n−2) + a(n−3); a(n)/a(n−1) → 2,5468182769 (positive Wurzel von x³ = 2x² + x + 1), bei n = 10 schon 2,5468. Die Wurzel benennt die Demo nicht; sie zeigt nur die Folge der Quotienten.
Was liefert das Fibonacci-Beispiel?	{A, B} ohne AA: 1, 2, 3, 5, 8, 13, 21, 34, 55 mit zwei Zuständen.
Wie viele Zustände haben die Beispiele der Demo?	3 (Standard), 2 (Fibonacci), 5 (Anlauf), 11 (viele Verbote), 3 (n = 40).
Wie gut hält die Zustandsschranke?	Vier zufällige Verbote der Länge 8 über F, S, N: naiv 3⁷ = 2187 Zustände, der Automat hat nie mehr als 1 + 4·7 = 29 (60 Zufallssätze, größter 28). Die Schranke ist hier eine Obergrenze für Verbote zusammenhängender Teilfolgen; der Zufallssatz ist eine Stichprobe.
Wie groß werden die Zahlen bei der Rekursion?	Standardregeln, Stellen von a(n): n = 20: 9; 100: 41; 1000: 407; 3000: 1219; 10 000: 4061.
Wo gibt das Aufzählen auf?	Phase 0 (Python, Entwicklungsrechner, Messung, nicht getestet): Aufzählen mit Abschneiden trägt bis n ≈ 16 bis 17 in etwa zehn Sekunden, alle Wörter prüfen bis n ≈ 14 bis 15; zwei Läufe unterschieden sich um bis zu Faktor 2 (bei n = 15 maß Phase 0 14,6 und 25,6 s an zwei Läufen desselben Rechners). Der Plan vermutete n ≈ 20; das ist widerlegt. Die App nennt deshalb keine feste Wandzahl, sondern misst auf dem Rechner, der sie ausführt, und rechnet hoch.
Rekursion gegen Aufzählen?	Phase 0 (nicht getestet): n = 10 000 in 0,05 bis 0,11 s; Aufzählen mit Abschneiden bei n = 16 in 6,9 bis 14,5 s; Hochrechnung (keine Messung, gleiche Zeit je Wort angenommen) für n = 30 etwa einen Monat.
Was richtet Gleitkomma an?	Standardregeln, Rekursion in Python-float statt Ganzzahl: Die Summe weicht ab n = 41 vom exakten Wert ab (a(40) liegt schon über 2⁵³ ≈ 9,0·10¹⁵, ist aber zufällig noch darstellbar), Überlauf auf inf bei n = 760 (Test: Bänder 38 bis 44 und 740 bis 780).
Welcher Fehler fiel erst im Test auf?	Python verweigert die Umwandlung ganzer Zahlen mit mehr als 4300 Stellen in Text (ValueError). 3¹⁰⁰⁰⁰ hat 4772 Stellen, also stürzte Experiment 2 bei Regeln ohne Einschränkung ab; mit den Standardregeln hat a(10 000) „nur“ 4061 Stellen und fiel nicht auf. Behoben ohne Stringumwandlung (digit_count, leading_digits); Regressionstest in tests/test_bigint.py.
Was findet das Raten der Rekursion?	Kleinste passende Ordnung 2, 3, 5 bei Zustandszahl 2, 3, 5 (Fibonacci, Standard, Anlauf-Beispiel); kleinere Ordnungen treffen nur den Anfang: Standard Ordnung 1 bis n = 1, Ordnung 2 bis n = 3; Anlauf-Beispiel Ordnung 1, 2, 3 bis n = 1, 3, 6.
Ist die Ordnung gleich der Zustandszahl?	In zwei von drei geprüften Regelsätzen ja. Im Anlauf-Beispiel ist die wirksame Ordnung kleiner: Koeffizienten 2, −1, 1, 1, 0; die wirksame Ordnung 4 gilt erst ab n = 5, nicht ab n = 4. Die Zustandszahl ist nur eine obere Schranke (Cayley–Hamilton).
Wie wächst die zweite Wand?	2ᵐ·m Zustände: m = 12: 49 152; m = 19: 9 961 472 (gegen 19! = 121 645 100 408 832 000 Reihenfolgen). Phase 0: m = 19 braucht 23 s, Aufzählen ist ab m = 11 (54 s) zu langsam; die App zählt live nur bis m = 8 nach.
Stimmt die Zählung der zweiten Wand?	Gegenprobe: Permutationen von m Symbolen ohne „i direkt vor i+1“: 1, 1, 3, 11, 53, 309, 2119, 16 687, … (OEIS A000255, verschoben um 1) für m = 1 bis 10.

Grenzen

• Zeiten und Hochrechnungen hängen vom Rechner ab. Die App misst bei jedem Klick neu; die Hochrechnung ist keine Messung und nimmt an, dass die Zeit je Wort gleich bleibt. Alle Zeiten sind Python-Zeiten: In einer kompilierten Sprache lägen alle Wände weiter hinten; die Aussage „der Zustand ist die Wand“ gilt davon unabhängig, die Zahl der Tage nicht. Eine kompilierte Messung wurde nicht gebaut.
• Der kleine Automat ist für Verbote zusammenhängender Teilfolgen gezeigt (höchstens 1 plus Summe der Längen minus 1 Zustände). Andere Regeln können ebenfalls einen kleinen Automaten haben, etwa „gerade Zahl von Nachtschichten“ mit zwei Zuständen; bei „jedes Symbol höchstens einmal“ wächst der Zustand exponentiell.
• Raten findet die kleinste Ordnung ohne Anlauf, nicht die wirksame Ordnung mit Anlauf. „Ordnung gleich Zustandszahl“ gilt in zwei von drei geprüften Regelsätzen; in der dritten ist die wirksame Ordnung kleiner (Anlauf-Beispiel: 4 statt 5; Koeffizient 0).
• Experiment 4 nur bis 12 Zustände und Ordnung 12. Darüber ist die Bruchrechnung für die App zu teuer; die App sagt es.
• Zweite Wand mit einer Verbotsdichte je Messung: Die Anzahlen gültiger Reihenfolgen wachsen mit zufälligen Verboten nicht gleichmäßig (die Paare für m + 1 Symbole sind nicht die Paare für m Symbole plus eine neue); Trends daraus sind nicht abzulesen, gezeigt werden nur Zustandszahl und Zeit.
• Nur gezählt: Schichtfolgen sind nur der Rahmen. Dienstplanung ist ein Optimierungsproblem mit Kosten und Besetzung; alles ist simuliert, keine echten Dienstpläne. Zählen nach Parameter (genau j Nachtschichten) und den Teilmengen-Zustand sinnvoll zu nutzen sind andere Demos der Reihe.

Quellen

• Quelltext, Messreihen und Tests der Demo: github.com/sebastian-hanisch/aufzaehlen-rekursion-demo.

Zu Cayley–Hamilton, Held–Karp und der Folge A000255 der OEIS wurden weder für die Demo noch für diese Seite Originalarbeiten eingesehen. Die Verfahren sind nach ihrer Beschreibung umgesetzt und gegen unabhängige Rechenwege geprüft (Handrechnung, Aufzählen aller Wörter, Matrixpotenz auf 40 festen Zufallsregelsätzen, die Literaturfolgen Fibonacci, Tribonacci und A000255).