Zulässige Reihenfolgen verständlich erklärt

Ein Zimmer soll renoviert werden. Manche Aufgaben müssen vor anderen kommen, die übrigen dürfen in beliebiger Folge geschehen. Wie viele Reihenfolgen sind dann möglich? Und wie lost man eine aus, bei der jede dieselbe Chance hat? Das ist schwerer, als es klingt.

Zuletzt aktualisiert: 11. November 2026

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

Ein Zimmer, drei Aufgaben

Stellen Sie sich vor, Sie renovieren ein Zimmer. Es gibt drei Aufgaben: die Wand streichen, die Möbel aufstellen und die Fenster putzen. Eine Vorgabe gilt: Die Möbel kommen erst nach dem Streichen, sonst gibt es Farbspritzer darauf. Das Fensterputzen ist frei, keine Vorgabe bindet es. Aufgaben samt Vorgaben heißen der Plan.

Welche Reihenfolgen sind erlaubt? Genau drei:

• Wand, Möbel, Fenster
• Wand, Fenster, Möbel
• Fenster, Wand, Möbel

Eine Reihenfolge, die alle Vorgaben einhält, heißt zulässig. Wie viele es gibt, zeigt den Spielraum des Plans. Gäbe es gar keine Vorgabe, wäre jede Anordnung der drei Aufgaben erlaubt.

Das Programm zum Ausprobieren

Zu dieser Seite gehört ein Programm zum Ausprobieren, die Demo. Der erste Knopf unten öffnet sie, der zweite führt zum zweiten Teil für Fachleute. Zum Verstehen brauchen Sie sie nicht. Sie erzeugt zufällige Pläne und misst, wie gut jedes Verfahren zählt, auslost und schätzt, mit einem vereinfachten Rechenbild (Fachwort: Modell). Die Aussagen in diesem Teil beschreiben diese Pläne, nicht echte Vorhaben.

Zählen, ohne alles aufzuschreiben

Bei drei Aufgaben schreibt man die Reihenfolgen einfach auf. Bei vielen Aufgaben geht das nicht mehr, denn ihre Zahl wächst rasch.

Der Trick: Man zählt nicht die Reihenfolgen, sondern die Zwischenstände. Ein Zwischenstand ist eine erlaubte Auswahl fertiger Aufgaben. Erlaubt heißt: Die Möbel dürfen nur fertig sein, wenn auch die Wand fertig ist. Im Zimmer gibt es sechs: nichts fertig, nur Wand, nur Fenster, Wand und Fenster, Wand und Möbel, alles fertig (Fachwort: Ideal). Das sind mehr als drei Reihenfolgen, aber der Vorteil zeigt sich bei vielen Aufgaben: Bei 20 Aufgaben mit im Schnitt 2 Vorgaben je Aufgabe waren es im mittleren Fall einige Hundert Zwischenstände gegen Milliarden Reihenfolgen.

Warum spart das Arbeit? Mehrere Reihenfolgen laufen durch denselben Zwischenstand, und ab dort ist der Rest gleich. Im Zimmer führen 2 Wege zum Stand „Wand und Fenster fertig“, und von dort geht es auf 1 Weise weiter: Durch diesen Stand laufen 2 mal 1, also 2 Reihenfolgen. Das rechnet man einmal, statt beide bis zum Ende zu verfolgen.

Zufällig und fair

Jetzt soll eine Reihenfolge zufällig ausgewählt werden, und jede zulässige soll dieselbe Chance haben. Naheliegend ist: In jedem Schritt zufällig eine der gerade erlaubten Aufgaben nehmen. Im Zimmer entscheidet der erste Schritt zwischen Wand und Fenster, denn die Möbel sind gesperrt.

Nehmen wir an, man spielt das 4-mal durch. Im Schnitt fällt 2-mal zuerst das Fenster, dann steht der Rest fest. Je 1-mal fällt zuerst die Wand, und ein zweiter Zufall entscheidet zwischen Möbeln und Fenster. Fenster, Wand, Möbel kommt also 2-mal vor, jede andere Reihenfolge nur 1-mal.

Der Grund: Jede Wahl zwischen zwei Aufgaben teilt die Chance auf. Der Weg über das Fenster hat nur eine solche Wahl, die beiden anderen haben zwei. Der Zufall ist in jedem Schritt fair, aber nicht über die ganze Reihenfolge. Die Demo hat das an kleinen Zufallsplänen ausgerechnet: In einem mittleren war die häufigste Reihenfolge 102-mal so wahrscheinlich wie die seltenste.

Fair wird es mit Losen. Zu jeder möglichen nächsten Aufgabe zählt man, auf wie viele Arten es danach zu Ende gehen kann, und legt so viele Lose in den Hut. Im Zimmer geht es nach der Wand auf 2 Arten weiter, nach dem Fenster auf 1. Also kommen 2 Lose für die Wand und 1 Los für das Fenster in den Hut; danach haben Möbel und Fenster je 1 Los. So hat jede der 3 Reihenfolgen die Chance 1 von 3. Die Zahlen dafür liefert die Tabelle der Zwischenstände, auch bei vielen Aufgaben.

Wenn selbst das Zählen zu teuer wird

Hat der Plan viele freie Aufgaben, gibt es viele erlaubte Zwischenstände, denn jede freie Aufgabe kann fertig oder noch offen sein, ohne dass eine andere wartet. Die Demo bricht das Zählen bei mehr als 50.000 Zwischenständen ab. Bei 30 Aufgaben geschah das in allen untersuchten Plänen mit im Schnitt 1 Vorgabe je Aufgabe, bei 2 oder mehr Vorgaben je Aufgabe in keinem.

Dann bleibt das Schätzen (das Verfahren heißt Schätzer). Man zieht mit dem naheliegenden Weg eine Reihenfolge, merkt sich, wie viele Aufgaben bei jedem Schritt zur Wahl standen, und multipliziert diese Zahlen. Das Produkt rechnet hoch, was dieser Versuch an Möglichkeiten nicht gezogen hat.

Im Zimmer gibt Fenster, Wand, Möbel das Produkt 2 · 1 · 1 = 2, die beiden anderen je 2 · 2 · 1 = 4. Über die 4 Versuche von oben gemittelt ergibt (2 + 2 + 4 + 4) geteilt durch 4 genau 3, die Zahl der Reihenfolgen. Das gleicht sich aus: Ein Weg mit viel Auswahl wird selten gezogen, hat aber ein großes Produkt. Ein Weg mit wenig Auswahl wird oft gezogen und hat ein kleines.

Ein einzelner Versuch liefert nie genau 3, erst der Durchschnitt stimmt. In der Messung lag der Schätzer bei Plänen mit 20 Aufgaben und im Schnitt anderthalb Vorgaben je Aufgabe im ungünstigsten Plan um bis zu 55 % daneben, trotz vieler Versuche.

Das dritte Verfahren ist das Mischen. Man beginnt mit irgendeiner zulässigen Reihenfolge und tauscht immer wieder zwei zufällig gewählte Nachbarn, wenn keiner den anderen voraussetzt. Nach genug Zügen ist die Reihenfolge nahezu fair ausgelost, denn ein Tausch ist so wahrscheinlich wie der Tausch zurück und bevorzugt keine Reihenfolge. In einem gemessenen kleinen Beispiel war sie nach wenigen Zügen noch weit von fair entfernt und nach 100 Zügen nahe daran. Wie viele Züge reichen, ist in der Demo nicht bewiesen, nur gemessen; für diese Art von Kette gibt es Beweise in der Fachliteratur.

Häufige Missverständnisse

• „Eine neue Vorgabe zwischen zwei Aufgaben, die noch nicht voneinander abhängen, streicht immer gleich viele Reihenfolgen.“ Nein. Es bleiben die Reihenfolgen, in denen die erste Aufgabe ohnehin vor der zweiten stand. Im Zimmer bleiben bei „Fenster vor Möbeln“ 2 der 3 Reihenfolgen, bei „Möbel vor Fenster“ nur 1.
• „Hängt jede Aufgabe irgendwie mit einer anderen zusammen, ist die Reihenfolge festgelegt.“ Nein. Müssen Wand und Fenster beide vor den Möbeln fertig sein, hängen beide an den Möbeln, aber ihre eigene Reihenfolge bleibt offen. Festgelegt ist sie nur, wenn jede Aufgabe direkt auf die vorige wartet.

Woran Sie das im Alltag erkennen

Anzeichen bei jedem Plan, etwa bei einem Umzug:

• Sie haben viele Aufgaben und wenige feste Vorgaben. Dann sind Sie bei der Reihenfolge frei. Fragen Sie sich, welche Vorgaben nötig sind, denn jede nimmt Spielraum.
• Ein „Zufallsprogramm“ liefert auffallend oft dieselben Reihenfolgen. Dann wählt es vermutlich Schritt für Schritt irgendeine mögliche Aufgabe.

Wie ernst ist das Rechenbild zu nehmen?

Ein einziges Team erledigt die Aufgaben nacheinander, Dauern und Kosten fehlen, und keine Reihenfolge gilt als besser. Die Zahlen betreffen Spielraum und faires Auslosen, nicht die beste Reihenfolge.

Was Sie mitnehmen:

• Fragen Sie bei jeder Zufallsauswahl: Hat jede ganze Reihenfolge dieselbe Chance oder nur jeder einzelne Schritt?
• Wer zählt, sollte zuerst fragen, wo sich Wege treffen. Was sich trifft, muss nur einmal gerechnet werden.
• Ein Schätzwert ist erst etwas wert, wenn man weiß, wie stark er schwankt: Sehen Sie nach, wie weit einzelne Versuche danebenliegen.

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. Gegenstand sind die Zahl der zulässigen Reihenfolgen (linearen Erweiterungen) einer endlichen Ordnung, das gleichverteilte Ziehen einer solchen Reihenfolge und das Verhalten von Zählen, Schätzen und Mischen, wenn der Plan wächst.

• Plan: \(n\) Aufgaben mit \(m\) Beziehungen \(a \prec b\) („a vor b“), kreisfrei, also eine endliche Ordnung \((V, \preceq)\) mit \(P\) als Name des Plans. Der Ausgangsgrad \(m/n\) ist die mittlere Zahl der Beziehungen je Aufgabe.
• Zulässige Reihenfolge: eine Anordnung \(\sigma\) aller Aufgaben mit \(a \prec b \Rightarrow \sigma(a) < \sigma(b)\). Ihre Zahl \(e(P)\) misst den Spielraum: Eine Kette erlaubt genau eine, \(n\) unabhängige Aufgaben erlauben \(n!\). Eine Reihenfolge entspricht dem Ablauf eines einzelnen Teams, das alle Aufgaben nacheinander erledigt.
• Ideal: eine Aufgabenmenge, die mit jeder Aufgabe auch alle ihre Vorgänger enthält. \(\mathcal{I}(P)\) ist die Menge aller Ideale. Jede zulässige Reihenfolge baut Schritt für Schritt ein Ideal auf, vom leeren Ideal bis zu \(V\).
• Zufallspläne: Die Aufgaben tragen zufällige Nummern. Die Beziehungen sind zufällige Paare, die entlang einer verdeckten Wunschreihenfolge von früh nach spät gerichtet sind, der Plan ist also kreisfrei; sie sind nicht transitiv reduziert (eine Abkürzungsbeziehung ändert die Zahl der Reihenfolgen nicht). Ihre Zahl ist \(n\) mal Ausgangsgrad, höchstens alle Paare. Die Demo erlaubt 6 bis 40 Aufgaben und einen Ausgangsgrad von einer halben bis zu vier Beziehungen je Aufgabe.
• Rechenbudget: Die exakte Zählung bricht ab, sobald es mehr als 50.000 Ideale gibt. Dann fehlt die Zähltabelle, und das gleichverteilte Ziehen fällt unter einer Warnung auf den naiven Zufalls-Kahn zurück.
• Drei Ziehverfahren: gleichverteilt über die Zähltabelle; der naive Zufalls-Kahn (Kahns Abbau der Ordnung, also topologisches Sortieren: Aufgaben ohne offene Vorgänger sind verfügbar, und an jeder Stelle wird gleichverteilt eine der gerade verfügbaren genommen; die Kahn-Ordnung ist die Reihenfolge des deterministischen Abbaus mit Warteschlange in der Reihenfolge der Aufgabennummern); das Kettenverfahren (von einer zulässigen Reihenfolge aus je Schritt eine Stelle wählen, mit Wahrscheinlichkeit \(\tfrac12\) pausieren, sonst die beiden Aufgaben an dieser und der nächsten Stelle vertauschen, wenn keine von der anderen abhängt). Dazu ein Schätzer mit 1.000 Proben. Gezogen werden bis zu 5.000 Reihenfolgen.
• Messreihen: Sie laufen über feste Pläne und geben Mediane oder Zählungen an, nie den Wert eines einzelnen Zufallslaufs. Der Aufwand wird in Idealen und Schritten gezählt, nicht in Sekunden (die einzige Zeitangabe, etwa eine halbe Sekunde für den Abbruch bei 40 Aufgaben, nennt die Demo ohne Angabe der Hardware). Der Zufall kommt aus random.random() des Mersenne-Twisters, plattformstabil.

Die Formeln

Sei \(f(I)\) die Zahl der Wege vom leeren Ideal zum Ideal \(I\) (je Schritt kommt eine Aufgabe hinzu) und \(g(I)\) die Zahl der Fortsetzungen von \(I\) bis zur vollen Aufgabenmenge \(V\). Mit \(f(\emptyset) = 1\) und \(g(V) = 1\):

\[f(I) = \sum_{v \in I,\; I \setminus \{v\} \in \mathcal{I}} f(I \setminus \{v\}), \qquad g(I) = \sum_{v \notin I,\; I \cup \{v\} \in \mathcal{I}} g(I \cup \{v\}), \qquad e(P) = g(\emptyset) = f(V).\]

Gezählt wird nur über die Ideale, nicht über alle \(n!\) Anordnungen. Gleichverteilt zieht man, indem man aus dem Ideal \(I\) die nächste Aufgabe \(v\) mit der Wahrscheinlichkeit der Fortsetzungen dahinter wählt; dann hat jede Reihenfolge die Wahrscheinlichkeit \(1 / e(P)\):

\[\Pr[v \mid I] = \frac{g(I \cup \{v\})}{g(I)}\]

Wählt man dagegen bei jedem Schritt gleichverteilt aus den \(d_t\) verfügbaren Aufgaben, hat eine Reihenfolge die Wahrscheinlichkeit \(\prod_t 1/d_t\). Die Probe \(X = \prod_t d_t\) ist deshalb erwartungstreu für die Zahl der Reihenfolgen:

\[\mathbb{E}[X] = \sum_{\sigma} \Pr[\sigma] \prod_t d_t(\sigma) = e(P).\]

Zerlegt man den Plan in \(w\) Ketten der Längen \(\ell_1, \dots, \ell_w\) (die Demo nimmt eine kleinste Zerlegung, berechnet als \(n\) minus größtes Matching auf der transitiven Hülle), wählt ein Ideal aus jeder Kette einen Anfang, und die Zahl der Ideale ist beschränkt:

\[|\mathcal{I}(P)| \le \prod_{k=1}^{w} (\ell_k + 1).\]

Als Maß für den Abstand zweier Verteilungen \(\mu, \nu\) auf den Reihenfolgen dient die Totalvariation \(\mathrm{TV}(\mu, \nu) = \tfrac12 \sum_\sigma |\mu(\sigma) - \nu(\sigma)|\): 0 heißt gleich, 1 völlig verschieden.

Herleitungen Schritt für Schritt

Die folgenden Herleitungen sind Rechnungen dieser Seite, keine Messungen der Demo. Wo die Demo dieselbe Aussage an Gegenproben prüft, steht es dabei.

Die Zähltabelle zählt richtig.

• Schritt 1: Eine zulässige Reihenfolge ist dasselbe wie eine Kette von Idealen \(\emptyset = I_0 \subset I_1 \subset \dots \subset I_n = V\) mit \(|I_k| = k\): \(I_k\) besteht aus den ersten \(k\) Aufgaben. Umgekehrt legt jede solche Kette die Reihenfolge fest, denn die Aufgabe in \(I_k \setminus I_{k-1}\) steht an Stelle \(k\).
• Schritt 2: \(f(I)\) zählt die Ketten von \(\emptyset\) bis \(I\). Die zuletzt ergänzte Aufgabe ist ein \(v \in I\) mit \(I \setminus \{v\} \in \mathcal{I}\); das ist die Summe in der Formel für \(f\). Spiegelbildlich zählt \(g(I)\) die Ketten von \(I\) bis \(V\).
• Schritt 3: Jede Reihenfolge, die durch \(I\) läuft, besteht aus einem Weg bis \(I\) und einer Fortsetzung. Durch \(I\) laufen also \(f(I)\,g(I)\) Reihenfolgen, und die Summe über alle Ideale gleicher Größe ist \(e(P)\). Die Demo prüft das an Gegenproben (Aufzählung mit networkx, siehe Befunde).
• Aufwand: Die Tabelle hat \(|\mathcal{I}(P)|\) Zeilen mit höchstens \(n\) Übergängen je Zeile. Der Aufwand hängt also an der Zahl der Ideale, nicht an \(e(P)\).

Das Ziehen über die Tabelle ist gleichverteilt. Die Wahrscheinlichkeiten \(g(I \cup \{v\}) / g(I)\) über die wählbaren \(v\) addieren sich nach der Rekursion für \(g\) zu 1. Die Wahrscheinlichkeit einer ganzen Reihenfolge ist das Produkt über ihre Schritte, \(\prod_{t} g(I_t)/g(I_{t-1}) = g(V)/g(\emptyset) = 1/e(P)\), ein Teleskopprodukt. Sie hängt nicht von der Reihenfolge ab.

Der naive Zufalls-Kahn ist verzerrt. Ein Plan mit drei Aufgaben \(W, M, F\) und der einen Beziehung \(W \prec M\) hat drei Reihenfolgen. Im ersten Schritt stehen \(W\) und \(F\) zur Wahl. Der Weg \(F, W, M\) hat die Auswahlgrößen \(2, 1, 1\) und die Wahrscheinlichkeit \(\tfrac12\); die Wege \(W, M, F\) und \(W, F, M\) haben die Auswahlgrößen \(2, 2, 1\) und je \(\tfrac14\). Gleichverteilt wäre jede mit \(\tfrac13\). Allgemein bevorzugt \(\prod_t 1/d_t\) die Reihenfolgen, die an wenigen Stellen eine Auswahl haben. Das Verhältnis von häufigster zu seltenster Reihenfolge ist hier 2; die Messung unten zeigt es an Plänen mit 9 Aufgaben.

Der Schätzer ist erwartungstreu, aber einzelne Proben liegen daneben.

• Schritt 1: Jede Reihenfolge \(\sigma\) tritt mit \(\Pr[\sigma] = 1 / \prod_t d_t(\sigma)\) auf und liefert die Probe \(\prod_t d_t(\sigma)\). Ihr Beitrag \(\Pr[\sigma] \prod_t d_t(\sigma)\) ist also genau 1, und die Summe über alle \(\sigma\) ist \(e(P)\).
• Schritt 2 (Beispiel): Im Plan mit \(W, M, F\) liefert \(F, W, M\) die Probe 2 mit Wahrscheinlichkeit \(\tfrac12\), die beiden anderen die Probe 4 mit zusammen \(\tfrac12\). Der Erwartungswert ist 3.
• Schritt 3: \(\mathbb{E}[X^2] = \sum_\sigma \Pr[\sigma] \prod_t d_t(\sigma)^2 = \sum_\sigma \prod_t d_t(\sigma)\), die Summe der Produkte über alle Reihenfolgen. Im Beispiel ist das 10, die Varianz also 1 und die relative Standardabweichung \(\tfrac13\). Keine einzelne Probe trifft die Zahl 3. Wie stark die Produkte schwanken, hängt davon ab, wie ungleich die Auswahlgrößen der Reihenfolgen sind.

Die Schranke und das Wachstum der Ideale. Die Schnittmenge eines Ideals mit einer Kette ist ein Anfang der Kette: Gehört eine Aufgabe dazu, auch alle Aufgaben der Kette vor ihr, weil sie Vorgänger sind. Ein Ideal ist durch diese \(w\) Anfänge festgelegt, jeder hat \(\ell_k + 1\) mögliche Längen, das gibt die Schranke. Umgekehrt erzwingt eine Antikette (paarweise unvergleichbare Aufgaben) aus \(a\) Aufgaben mindestens \(2^a\) Ideale: Zu jeder Teilmenge \(S\) der Antikette gehört das von \(S\) erzeugte Ideal (\(S\) und alle Vorgänger), und verschiedene Teilmengen ergeben verschiedene Ideale, weil die maximalen Aufgaben des Ideals gerade \(S\) sind. Schon bei \(a = 16\) ist \(2^{16}\) größer als das Budget von 50.000. Ob die gemessenen Pläne eine so große Antikette haben, hat die Demo nicht gemessen.

Eindeutig genau dann, wenn Hamilton-Pfad. Sei \(u_1, \dots, u_n\) eine zulässige Reihenfolge. Ist jedes Paar \(u_i, u_{i+1}\) unmittelbar durch eine Beziehung verbunden, steht \(u_i\) vor \(u_{i+1}\) in jeder zulässigen Reihenfolge, also ist sie eindeutig. Fehlt für ein \(i\) die unmittelbare Beziehung, sind \(u_i\) und \(u_{i+1}\) unvergleichbar, denn ein Weg von \(u_i\) nach \(u_{i+1}\) bräuchte eine Aufgabe dazwischen. Dann ergibt ihr Vertauschen eine zweite zulässige Reihenfolge. Die Demo bestätigt die Äquivalenz in 400 von 400 Fällen.

Spielraum und eine neue Beziehung. Die früheste Stelle einer Aufgabe ist die Zahl ihrer Vorgänger plus eins, die späteste \(n\) minus die Zahl ihrer Nachfolger. Verlangt man für zwei unvergleichbare Aufgaben zusätzlich \(a \prec b\), bleiben genau die Reihenfolgen, in denen \(a\) ohnehin vor \(b\) steht: \(e(P + (a \prec b)) = e(P) \cdot \Pr[a \text{ vor } b]\) unter der Gleichverteilung. Im Plan mit \(W, M, F\) bleiben bei \(F \prec M\) zwei von drei Reihenfolgen, bei \(M \prec F\) eine. Die Anteile ergeben zusammen 1.

Das Kettenverfahren hat die Gleichverteilung als stationäre Verteilung. Der Übergang von \(\sigma\) zu \(\sigma'\), das durch Vertauschen benachbarter unvergleichbarer Aufgaben entsteht, hat in beiden Richtungen dieselbe Wahrscheinlichkeit (Stelle gleichverteilt, Tausch mit Wahrscheinlichkeit \(\tfrac12\)). Die Übergangsmatrix ist damit symmetrisch, die Gleichverteilung stationär. Das Pausieren macht die Kette aperiodisch. Sie ist irreduzibel: Unterscheiden sich zwei Reihenfolgen \(\sigma \ne \tau\), gibt es in \(\sigma\) ein benachbartes Paar, das in \(\tau\) umgekehrt steht. Beide Reihenfolgen sind zulässig, also sind die zwei Aufgaben unvergleichbar und der Tausch erlaubt; er verringert die Zahl der Fehlstände gegen \(\tau\). Wie schnell die Verteilung die Gleichverteilung erreicht, folgt daraus nicht; die Demo misst es nur.

Durchgerechnet: ein Plan mit drei Aufgaben

Rechnung dieser Seite, keine Messung der Demo, mit dem Kern der Demo nachgeprüft: Plan mit den Aufgaben \(W, M, F\) und der einen Beziehung \(W \prec M\). Es gibt sechs Ideale, dazu die Wege \(f\) und die Fortsetzungen \(g\):

Ideal \(I\)	\(f(I)\)	\(g(I)\)	\(f(I)\,g(I)\)
\(\emptyset\)	1	3	3
\(\{W\}\)	1	2	2
\(\{F\}\)	1	1	1
\(\{W, F\}\)	2	1	2
\(\{W, M\}\)	1	1	1
\(\{W, M, F\}\)	3	1	3

Es gibt \(e(P) = g(\emptyset) = f(V) = 3\) Reihenfolgen. Die Summe der letzten Spalte ist je Größe des Ideals gleich 3 (Größe 1: \(2 + 1\), Größe 2: \(2 + 1\)). Gezogen wird mit \(\Pr[W \mid \emptyset] = 2/3\) und \(\Pr[F \mid \emptyset] = 1/3\), danach sind die Schritte nach \(\{W\}\) mit je \(\tfrac12\) zu wählen und alle weiteren erzwungen. Jede Reihenfolge hat \(1/3\).

Reihenfolge	Auswahlgrößen \(d_t\)	Probe \(X\)	naiver Zufalls-Kahn	gleichverteilt
\(F, W, M\)	2, 1, 1	2	\(\tfrac12\)	\(\tfrac13\)
\(W, M, F\)	2, 2, 1	4	\(\tfrac14\)	\(\tfrac13\)
\(W, F, M\)	2, 2, 1	4	\(\tfrac14\)	\(\tfrac13\)

Die frühesten und spätesten Stellen sind \(W\): 1 bis 2, \(M\): 2 bis 3, \(F\): 1 bis 3. Der Spielraum je Aufgabe (späteste minus früheste Stelle) ist 1, 1 und 2.

Befunde

Alle Zahlen dieser Tabelle stammen aus den Messreihen der Demo, bis auf die eine ausdrücklich als Nachrechnung dieser Seite gekennzeichnete. Die Messreihen laufen über feste Pläne; angegeben sind Mediane und Zählungen. Ausgangsgrad 1 bis 4 heißt: mittlere Zahl der Beziehungen je Aufgabe.

Frage	Befund
Wie viel kleiner als \(n!\) ist die Zahl der Reihenfolgen? (10 Pläne je Fall, Median)	20 Aufgaben, Ausgangsgrad 1 / 2 / 3 / 4: 10.172 / 580,5 / 204,5 / 81,5 Ideale und \(10^{13{,}3}\) / \(10^{9{,}4}\) / \(10^{7{,}0}\) / \(10^{5{,}6}\) Reihenfolgen gegen \(10^{18{,}4}\) Permutationen (20!). 12 Aufgaben: 256 / 49 / 23,5 / 17 Ideale und \(10^{5{,}6}\) / \(10^{3{,}3}\) / \(10^{2{,}0}\) / \(10^{1{,}0}\) Reihenfolgen gegen \(10^{8{,}7}\).
Wann wird das Zählen unbezahlbar? (8 Pläne je Fall, Budget 50.000 Ideale)	30 Aufgaben: Bei Ausgangsgrad 1 liegen 8 von 8 Plänen über dem Budget, bei Ausgangsgrad 2 / 3 / 4 liegt der Median bei 17.346 / 1.994,5 / 547 Idealen. 40 Aufgaben: 8 / 7 / 1 / 0 von 8 Plänen über dem Budget bei Ausgangsgrad 1 / 2 / 3 / 4; im Median der Pläne unter dem Budget sind es bei Grad 4 2.326 Ideale, bei Grad 3 9.024 (sieben Pläne), bei Grad 2 33.234 (ein Plan).
Wie gut ist die Schranke aus der Kettenzerlegung? (20 Aufgaben, 30 Pläne je Grad)	Die Zahl der Ideale liegt in 120 von 120 Plänen unter dem Produkt aus Kettenlänge plus eins. Die Schranke ist im Median das 4,0- / 9,7- / 14,3- / 11,6-Fache der tatsächlichen Zahl (Ausgangsgrad 1 bis 4).
Ist der naive Zufalls-Kahn gleichverteilt? (20 Pläne, 9 Aufgaben, Ausgangsgrad 1,5, 5 bis 5.000 Reihenfolgen, exakte Wahrscheinlichkeiten)	Nein. Die wahrscheinlichste Reihenfolge ist im Median das 102-Fache der unwahrscheinlichsten, höchstens das 432-Fache. Die Totalvariation zur Gleichverteilung beträgt im Median 0,40. Das Ziehen über die Zähltabelle trifft jede Reihenfolge im Rahmen der Stichprobe gleich oft; nach der Herleitung ist es exakt gleichverteilt.
Wie genau ist der Schätzer? (20 Pläne je Größe, Ausgangsgrad 1,5, 1.000 Proben)	Relativer Fehler im Median 3 / 8 / 11 % bei 12 / 16 / 20 Aufgaben, höchstens 27 / 24 / 55 %: erwartungstreu, aber bei dünnen Plänen streuend. Der Höchstwert ist nicht monoton in der Größe; bei 20 Plänen je Größe bestimmen einzelne Pläne ihn.
Wie schnell mischt das Kettenverfahren? (ein Plan mit 7 Aufgaben und 18 Reihenfolgen, 3.000 Läufe je Schrittzahl, Start bei der Kahn-Ordnung)	Totalvariation nach 7 / 20 / 49 / 100 / 200 / 400 Schritten: 0,64 / 0,44 / 0,23 / 0,07 / 0,03 / 0,04. Unter 0,1 liegt sie erstmals nach 100 Schritten. Die letzten beiden Werte liegen im Rauschen der 3.000 Läufe: Eine perfekt gleichverteilte Ziehung dieses Umfangs zeigt bei 18 Reihenfolgen im Mittel eine Totalvariation von etwa 0,03 (Nachrechnung dieser Seite durch Simulation).
Wann ist die Ordnung eindeutig? (400 Pläne mit 4 bis 9 Aufgaben)	In 226 Plänen eindeutig; eindeutig genau dann, wenn die Kahn-Ordnung eine Kette von Beziehungen ist (Hamilton-Pfad), in 400 von 400 Fällen.
Wie viel Spielraum hat eine Aufgabe? (20 Aufgaben, 20 Pläne je Grad, über alle Aufgaben aller Pläne)	Späteste minus früheste mögliche Stelle im Median 16 / 10 / 6 / 4 Plätze bei Ausgangsgrad 1 / 2 / 3 / 4 (Mittel 15,64 / 10,35 / 6,36 / 4,24, höchstens 19 / 19 / 17 / 13).
Ist die Rechnung korrekt?	Die Zahl der Reihenfolgen ist gleich der Aufzählung mit networkx.all_topological_sorts auf 100 Plänen (5 bis 9 Aufgaben) und gleich der Zahl der Permutationen, die alle Beziehungen halten, auf 40 Plänen. Die Ideale sind gleich den unter Vorgängern abgeschlossenen Teilmengen (60 Pläne). Stelle einer Aufgabe, „a vor b“ und Positionsbereiche sind gleich der Aufzählung (40 bzw. 60 Pläne).

Grenzen und was die Messung zeigt

Was sie belegt:

• Die Zahlen der Zähltabelle und des Ziehens: Sie sind an Aufzählungen gegengeprüft, und das Ziehen ist nach der Herleitung oben gleichverteilt.
• Die Richtung der Effekte im gemessenen Raster: Mit mehr Beziehungen je Aufgabe sinken Zahl der Ideale, Zahl der Reihenfolgen und Spielraum je Aufgabe. Die Schranke hielt in allen 120 Plänen und lag im Median bei dem 4,0- bis 14,3-Fachen der Zahl der Ideale.
• Dass der naive Zufalls-Kahn verzerrt ist: am kleinen Beispiel oben vorgerechnet, gemessen an Plänen mit 9 Aufgaben.

Was sie nicht belegt:

• Zufallspläne: Die Zahlen gelten für diese Pläne mit 6 bis 40 Aufgaben. Echte Pläne sind oft stärker in Schichten gegliedert; ob die Zahlen dort ähnlich ausfallen, hat die Demo nicht gemessen.
• Kleine Stichproben: Die Mediane stehen auf 8 bis 30 Plänen je Fall, der Median für 40 Aufgaben und Ausgangsgrad 2 auf einem einzigen Plan unter dem Budget, der für Grad 3 auf sieben.
• Der Schätzer streut: Er ist nur bei Ausgangsgrad 1,5 mit 12, 16 und 20 Aufgaben gemessen; mit 1.000 Proben lag der Fehler im ungünstigsten Plan bei 55 %. Für dünnere oder größere Pläne gibt es keine Messung.
• Die Mischzeit ist in der Demo nur gemessen: Sie steht an einem einzigen Plan mit 7 Aufgaben und 18 Reihenfolgen. Daraus folgt nichts für größere Pläne, und die Regler der Demo lassen auch zu kurze Läufe zu. Das Verfahren ist im Kern die Kette von Karzanov und Khachiyan, für die in der Literatur polynomiale Schranken der Mischzeit bewiesen sind; die Demo nutzt sie nicht.
• Der naive Zufalls-Kahn ist nur klein gemessen: Die exakte Rechnung braucht die Aufzählung aller Reihenfolgen, daher nur Pläne mit 5 bis 5.000 Reihenfolgen. Die 102-fache Verzerrung gilt für diese Pläne (9 Aufgaben, Ausgangsgrad 1,5).
• Zählen ist schwer: Dass es für beliebige Pläne #P-vollständig ist, ist ein Satz der Komplexitätstheorie (Quellen), nicht etwas, das die Demo zeigt. Sie zeigt nur, wie die Zahl der Ideale und damit der Aufwand der Tabelle wächst.
• Keine Bewertung: Es gibt keine Kosten, Rüstzeiten oder Maschinen, und nur ein Team arbeitet eine Aufgabe nach der anderen. Die Zahl der Reihenfolgen sagt nichts über Dauer oder Güte einer einzelnen.
• Größe: Die Demo rechnet bis 40 Aufgaben und zieht bis zu 5.000 Reihenfolgen; der Abbruch über dem Budget kostet bei 40 Aufgaben etwa eine halbe Sekunde.

Erweiterungen und Verweise

Was die Demo auslässt oder nur streift, zeigen andere Demos dieser Website:

• Kettenzerlegung: Die Demo „Ketten und Antiketten“ zeigt, wie viele Teams ein Vorhaben mindestens braucht; dieselbe Zerlegung liefert hier die Schranke für die Zahl der Ideale.
• Gleichverteilt ziehen: Die Demo „Gleichverteilt ziehen: zählen, dann entrollen“ zeigt dasselbe Muster, die Fortsetzungszahlen als Gewichte, an Schichtfolgen.
• Schätzen aus zufälligen Pfaden: Der Knuth-Schätzer schätzt die Zahl der Möglichkeiten aus zufälligen Pfaden, wie es hier der Schätzer tut.
• Reihenfolgen mit Team oder Maschine: Teilen sich Aufgaben ein Team oder eine Maschine, übernimmt die ressourcenbeschränkte Projektplanung der Scheduling-Linie; die Demo hier bewertet keine Reihenfolge.

Quellen

• Brightwell, Winkler: Counting linear extensions. Order 8, 1991 (das Zählen linearer Erweiterungen ist #P-vollständig), wie in der README der Demo genannt.
• Knuth: Estimating the efficiency of backtrack programs. Mathematics of Computation 29, 1975 (Schätzer aus dem Produkt der Auswahlgrößen).
• Karzanov, Khachiyan: On the conductance of order Markov chains. Order 8, 1991 (polynomiale Schranken der Mischzeit für Ketten dieser Art).
• Quelltext, Messreihen und Tests der Demo: github.com/sebastian-hanisch/zulaessige-reihenfolgen-demo.

Nur Brightwell und Winkler stehen in der README der Demo. Knuth und Karzanov und Khachiyan sind aus dem Gedächtnis genannt, nicht nachgeschlagen; die README gibt die Quellen des Schätzers und des Kettenverfahrens ausdrücklich als nicht geprüft an. Das Zimmer mit drei Aufgaben ist erdacht und stammt nicht aus der Demo; die Herleitungen und das durchgerechnete Beispiel sind Rechnungen dieser Seite und keine Messungen.