Die Siebformel verständlich erklärt

Vier Gäste geben ihre Hüte ab, die Garderobe reicht sie blind zurück. Auf wie viele Arten bekommt keiner den eigenen Hut? Man zählt erst alle Möglichkeiten und zieht dann das Verbotene ab. Diese Seite zeigt, wie das geht und wo es nicht hilft.

Zuletzt aktualisiert: 11. November 2026

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

Vier Hüte, und keiner den eigenen

Stellen Sie sich eine Garderobe vor: Vier Gäste geben ihre Hüte ab. Beim Gehen reicht die Garderobiere die Hüte blind zurück, jeder Gast bekommt genau einen.

Wir fragen: Auf wie viele Arten geht das aus, ohne dass ein Gast seinen eigenen Hut erhält?

Diese Arten Stück für Stück aufzubauen ist mühsam. Wie viele Hüte für den zweiten Gast noch falsch sind, hängt davon ab, welchen Hut der erste genommen hat. Man müsste sich in jedem Schritt merken, welche Hüte vergeben sind und wer noch seinen eigenen bekommen könnte.

Einfacher geht es andersherum: erst alles zählen, dann das Verbotene abziehen. Verboten heißt hier: Mindestens ein Gast hat seinen eigenen Hut. Man nennt das die Siebformel. So rechnen wir:

• Alles zählen: Für den ersten Gast gibt es vier Hüte, für den zweiten drei, dann zwei, dann einen. Das sind 24 Verteilungen.
• Abziehen: Hat ein bestimmter Gast seinen Hut, verteilen sich die übrigen Hüte beliebig auf die übrigen Gäste. Das sind sechs Möglichkeiten, bei vier Gästen also 4 · 6 = 24. Die ziehen wir ab.
• Zurückgeben: Haben zwei bestimmte Gäste ihren Hut, wurde die Verteilung zwei Mal abgezogen, einmal je Gast. Je Gästepaar gibt es zwei solche Verteilungen, bei sechs Paaren zusammen 12. Die geben wir zurück.
• Wieder abziehen: Haben drei bestimmte Gäste ihren Hut, hat auch der vierte seinen. Je Dreiergruppe gibt es eine Verteilung, bei vier Gruppen zusammen 4. Die ziehen wir erneut ab.
• Wieder zurückgeben: Haben alle vier ihren Hut, ist das eine Verteilung. Die geben wir zurück.

Ergebnis: 24 − 24 + 12 − 4 + 1 = 9. Es gibt also neun Arten ohne eigenen Hut.

Warum der Wechsel zwischen Abziehen und Zurückgeben? Nehmen Sie die Verteilung, in der alle vier ihren Hut haben. Sie wird vier Mal abgezogen, sechs Mal zurückgegeben, vier Mal abgezogen und ein Mal zurückgegeben. Unterm Strich wird sie genau einmal abgezogen, wie es sein soll.

Das Programm zum Ausprobieren

Zu dieser Seite gehört ein Programm zum Ausprobieren im Browser, die Demo. Sie erreichen es über den ersten Knopf unten, der zweite führt zum Teil für Fachleute. Zum Verstehen brauchen Sie die Demo nicht.

Sie rechnet mit erfundenen Beispielen. Die Aussagen in diesem Teil beschreiben diese vereinfachten Rechenbilder (Fachwort: Modell), nicht die Wirklichkeit.

Wenn viele Paare verboten sind

Dasselbe Verfahren passt, wenn mehr verboten ist als der eigene Hut. Nehmen wir acht Aufgaben und acht Maschinen. Jede Aufgabe geht an eine Maschine, jede Maschine bekommt eine Aufgabe. Manche Paare aus Aufgabe und Maschine sind verboten, weil die Maschine die Aufgabe nicht kann. Zeichnen Sie eine Tabelle: Jede Zeile ist eine Aufgabe, jede Spalte eine Maschine. Ein verbotenes Paar ist ein Kreuz im Feld. Gezählt werden die Zuordnungen ohne ein Kreuz.

Beim Abziehen betrachtet man jede Auswahl von Kreuzen, die zugleich vorkommen sollen. Jedes weitere Kreuz verdoppelt die Zahl der Auswahlen. Das Beispiel der Demo hat vierzehn Kreuze, also 16.384 Auswahlen.

Die meisten Auswahlen tragen aber nichts bei. Zwei Kreuze in derselben Zeile oder Spalte kann keine Zuordnung zugleich enthalten, denn eine Aufgabe geht nur an eine Maschine. Im Beispiel bleiben 212 Auswahlen. Auswahlen mit gleich vielen Kreuzen betreffen gleich viele Zuordnungen, denn die übrigen Aufgaben lassen sich beliebig auf die übrigen Maschinen verteilen. Es zählt also nur, wie viele passende Auswahlen jeder Größe es gibt.

Das sind fünf Zahlen: Auswahlen mit keinem, einem, zwei, drei und vier Kreuzen. Fünf Kreuze, die sich keine Zeile und keine Spalte teilen, gibt es im Beispiel nicht. Diese Zahlen heißen Turmzahlen, denn wie bei Schachtürmen darf kein Kreuz ein anderes schlagen, also in derselben Zeile oder Spalte stehen.

Die Rundreise: weniger Speicher, mehr Schritte

Eine Reisende besucht zehn Städte, jede genau einmal, und kehrt zum Start zurück. Manche Straßen sind Einbahnstraßen. Verboten ist, eine Stadt auszulassen.

Das Sieb zählt zuerst Spaziergänge. Das sind Wege über die Straßen, die Städte auch mehrfach besuchen dürfen. Das geht leicht, denn man zählt nur Schritt für Schritt, wie viele Wege in welcher Stadt enden. Dann zieht es die Spaziergänge ab, die eine Stadt auslassen, und gibt zurück, was zu oft abgezogen wurde. Ein Spaziergang mit so vielen Schritten wie Städten, der am Start endet und alle Städte besucht, besucht jede genau einmal. Das ist eine Rundreise.

Es gibt einen anderen Rechenweg (Fachname: Held–Karp). Er legt für jede Teilreise einen Eintrag an, etwa „vom Start über Stadt B und C bis Stadt D“, und nutzt solche Einträge für viele Reisen wieder. Das Sieb beginnt dagegen für jede Auswahl von Städten von vorn. Darum braucht es mehr Schritte. Bei zehn Städten und allen Straßen zählt die Demo für das Sieb mehr als das Dreizehnfache der Rechenschritte von Held–Karp.

Dafür merkt sich das Sieb nur eine Zahl je Stadt, Held–Karp dagegen jeden Eintrag. Das Sieb spart hier also Speicherplatz, aber keine Rechenschritte.

Wenn die Zahlen zu groß werden

Beim Sieb entstehen oft riesige Zahlen, die sich beim Abziehen und Zurückgeben fast aufheben. Übrig bleibt eine viel kleinere Zahl. Stellen Sie sich zwei fast gleich hohe Türme vor, jeden auf den Meter genau gemessen. Den Höhenunterschied kennen Sie dann nicht auf den Zentimeter.

Genauso geht es einem Computer, der mit Kommazahlen rechnet, denn er speichert nur eine begrenzte Zahl von Stellen. Die Demo zeigt das mit vierzig Aufgaben auf vierzig Maschinen, jede Maschine bekommt genau eine. Mit Kommazahlen war der Fehler größer als das richtige Ergebnis selbst.

Mit ganzen Zahlen stimmte das Ergebnis in allen Fällen der Messreihe.

Häufige Missverständnisse

• „Das Sieb ist ein Trick für Hüte und Rundreisen.“ Nein. Es passt auf jede Frage der Form: Wie viele Dinge haben keine der unerwünschten Eigenschaften? Beispiel: Welche Zahlen bis zu einer Grenze sind weder durch 2 noch durch 3 teilbar? Man zählt alle, zieht die geraden ab, zieht die Vielfachen von 3 ab und gibt die Vielfachen von 6 zurück, denn die wurden zwei Mal abgezogen.
• „Weniger Summanden heißt weniger Arbeit.“ Nicht ganz. Die fünf Zahlen im Beispiel mit den Kreuzen müssen erst ausgerechnet werden, und diese Arbeit steckt in keinem Summanden.

Woran Sie das im Alltag erkennen

Anzeichen, dass ein Sieb passt:

• Die Frage heißt: Auf wie viele Arten passiert etwas Bestimmtes nie? Etwa: Kein Gast sitzt neben seinem Partner. Alle guten Fälle aufzubauen wird unübersichtlich, weil jede Regel die anderen beeinflusst.
• Sie zählen mehrere Gruppen zusammen und merken, dass manche Personen in mehreren stehen, etwa auf zwei Mailinglisten. Wer auf beiden steht, wird zu oft gezählt, und Sie ziehen ihn einmal wieder ab.

Wie ernst ist das Rechenbild zu nehmen?

Alle Beispiele sind erfunden, alle Zahlen gezählt, nicht geschätzt. Die Demo zeigt nur kleine Fälle. Ob es bei größeren Rundreisen oder Straßennetzen mit fehlenden Straßen genauso ist, zeigt sie nicht.

Was Sie mitnehmen:

• Wer Verbote zählen will, kann rückwärts rechnen: erst alles, dann abwechselnd abziehen und zurückgeben.
• Fragen Sie bei jedem Rechenweg, was er spart: Speicherplatz oder Rechenschritte.
• Trauen Sie keiner Kommarechnung, in der riesige Zahlen sich fast aufheben.

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

Gezählt werden Objekte ohne jede von \(m\) unerwünschten Eigenschaften \(A_1, \dots, A_m\). Für eine Indexmenge \(I \subseteq \{1, \dots, m\}\) sei \(N(I)\) die Zahl der Objekte, die alle \(A_i\) mit \(i \in I\) haben; \(N(\emptyset)\) ist die Zahl aller Objekte. Die Zahl der Objekte ohne jede Eigenschaft ist \(\sum_{I} (-1)^{|I|}\, N(I)\) (Siebformel, Inklusion–Exklusion) mit \(2^m\) Summanden. Dieser Teil zeigt für zwei Zählprobleme, wie sich die Summanden zusammenfassen lassen und wo das Sieb gegenüber einer Teilmengen-Rechnung nichts spart.

• Zuordnung mit verbotenen Feldern: \(n\) Aufgaben werden \(n\) Maschinen zugeordnet (eine Permutation \(\sigma\)). Ein Brett \(F\) ist die Menge verbotener Felder (Zeile, Spalte). Gezählt werden die Permutationen mit \((i, \sigma(i)) \notin F\) für alle \(i\); jedes Feld von \(F\) ist eine Eigenschaft. Die Bretter der Demo: Zufallsbrett (Anteil verbotener Felder in Prozent), Hauptdiagonale, Ménage-Brett (Diagonale plus Nebendiagonale, zyklisch: verboten sind \(\sigma(i) = i\) und \(\sigma(i) = i+1\) modulo \(n\)), leer, voll.
• Rundreise: ein gerichteter Graph auf \(n\) Städten, gezählt werden gerichtete Hamiltonkreise ab Stadt 0, jeder Kreis einmal. Mit Kosten: ganzzahlige Kosten \(c_{ij}\) von 1 bis \(c_{\max}\) (höchstens 5) je Kante, eine fehlende Kante ist keine Kante.
• Rechenwege für Zuordnungen: Sieb mit Turmzahlen; Sieb über Feldmengen (bis 16 verbotene Felder); Ryser-Sieb über Spaltenmengen (Permanente, unten definiert); Teilmengen-DP (Zustände je Menge belegter Spalten); Formeln (Derangements, also Permutationen ohne Fixpunkt; Ménage-Zahlen; \(n!\)); Aufzählen aller Permutationen (bis \(n = 8\)).
• Rechenwege für Rundreisen: Sieb über Spaziergänge; Held–Karp als Zähler (je Städtemenge und Endstadt die Zahl der Pfade von Stadt 0); Aufzählen (bis \(n = 8\)). Für die Kosten: Sieb mit Polynomgewichten, Held–Karp mit dem Paar (kleinste Kosten, Zahl der besten Kreise) und Aufzählen. Weichen Rechenwege voneinander ab, zeigt die Demo einen Fehler statt einer Zahl.
• Notation: Die Demo schreibt k und S für mehrere Dinge. Hier steht \(m\) für die Zahl der Eigenschaften, \(I\) für Indexmengen, \(t\) für die Zahl der Türme, \(k\) nur für Maschinenzahlen und \(S\) nur für Städtemengen.
• Aufwand: gezählt als Zahl der Summanden, Zustände, Übergänge und Rechenschritte (exakt, nicht gemessen). Zeiten sind nur Messungen auf Klick.
• Einstellungen: Größe \(n\) von 3 bis 12 (Rundreise höchstens 10), Anteil in Prozent, Kostenbereich \(c_{\max}\) von 1 bis 5, Zufallsstartwert. Instanzen sind aus diesen Werten deterministisch erzeugt. Voreinstellung: Zufallsbrett 8 × 8, Anteil 20 %, Startwert 35.
• Ganze Zahlen: Der Kern rechnet durchgehend mit ganzen Zahlen beliebiger Länge. Gleitkomma kommt nur im Gegenbeispiel zu den Surjektionen unten vor und bei Anteilen und Verhältnissen, die nur angezeigt werden.

Die Formeln

Zuordnungen. Eine Menge \(I\) verbotener Felder heißt nichtangreifend, wenn ihre Felder in verschiedenen Zeilen und Spalten liegen. Dann enthalten genau \((n - |I|)!\) Permutationen alle Felder aus \(I\), sonst keine. Mit der Turmzahl \(r_t\) (Zahl der nichtangreifenden Teilmengen von \(F\) mit \(t\) Feldern) ist die Zahl der Zuordnungen ohne verbotenes Feld \(\sum_{t=0}^{n} (-1)^t\, r_t\, (n-t)!\), also höchstens \(n+1\) Summanden statt \(2^{|F|}\). Hauptdiagonale: \(r_t = \binom{n}{t}\), also \(D_n = \sum_t (-1)^t \binom{n}{t} (n-t)!\) (Derangements). Ménage-Brett (\(n \ge 3\)): \(r_t = \frac{2n}{2n-t}\binom{2n-t}{t}\).

Ryser. Für eine 0/1-Matrix \(E = (e_{ij})\) (1 = erlaubt) ist die Zahl der Zuordnungen die Permanente \(\operatorname{perm}(E) = \sum_{J \subseteq \{1, \dots, n\}} (-1)^{n-|J|} \prod_{i=1}^{n} \sum_{j \in J} e_{ij}\). Das sind \(2^n - 1\) nichtleere Spaltenmengen \(J\) statt \(n!\) Permutationen; die leere Menge trägt für \(n \ge 1\) nichts bei.

Hamiltonkreise. Sei \(V\) die Städtemenge. Für \(S \subseteq V \setminus \{0\}\) sei \(W(S)\) die Zahl der geschlossenen Spaziergänge der Länge \(n\) von Stadt 0, die nur Städte aus \(S \cup \{0\}\) benutzen, also das Element \((0,0)\) von \(G_S^n\) mit der Nachbarschaftsmatrix \(G_S\) auf \(S \cup \{0\}\). Die Zahl der Hamiltonkreise ist

\[\sum_{S \subseteq V \setminus \{0\}} (-1)^{n-1-|S|}\, W(S).\]

Gerechnet wird mit einem Vektor aus \(n\) Zahlen (Zahl der Spaziergänge nach Stadt, Schritt für Schritt), nicht mit der Matrixpotenz. Es gibt \(2^{n-1}\) Mengen \(S\).

Kostenpolynom. Erhält jede Kante \((i, j)\) das Gewicht \(z^{c_{ij}}\), liefert dasselbe Sieb ein Polynom \(\sum_w h_w z^w\) mit \(h_w\) als Zahl der Hamiltonkreise mit Gesamtkosten \(w\). Die kleinsten Kosten sind der kleinste Exponent mit \(h_w > 0\), die Zahl der besten Kreise ist \(h_w\) dort. Der Grad ist höchstens \(n \cdot c_{\max}\). Das Polynom wird als eine große ganze Zahl mit \(B\) Bit je Koeffizient gepackt; eine Verschiebung um \(B c\) Bit ersetzt dann die Multiplikation mit \(z^c\).

Surjektionen und Legendre. Die Zahl der Abbildungen von \(n\) Aufgaben auf \(k\) Maschinen, bei denen jede Maschine mindestens eine Aufgabe bekommt, ist \(\sum_{j=0}^{k} (-1)^{k-j} \binom{k}{j}\, j^n\) mit \(k+1\) Summanden; das Ergebnis ist \(k!\) mal die Stirling-Zahl zweiter Art. Zahlen von 1 bis \(L\) ohne die Teiler \(d_1, \dots, d_p\): \(\sum_{I \subseteq \{1, \dots, p\}} (-1)^{|I|} \lfloor L / \operatorname{kgV}(d_i : i \in I) \rfloor\), mit kgV der leeren Menge gleich 1.

Herleitungen Schritt für Schritt

Die Herleitungen sind Rechnungen dieser Seite, keine Messungen der Demo.

Die Siebformel.

• Schritt 1: Ein Objekt \(x\) habe genau die Eigenschaften der Menge \(T\). Es zählt in \(N(I)\) genau dann, wenn \(I \subseteq T\).
• Schritt 2: Sein Beitrag zur Summe ist \(\sum_{I \subseteq T} (-1)^{|I|} = (1-1)^{|T|}\). Das ist 1 für \(T = \emptyset\) und sonst 0.
• Schritt 3: Die Summe zählt also jedes Objekt ohne Eigenschaft einmal und jedes andere nullmal.

Zuordnungen mit verbotenen Feldern.

• Schritt 1: Jedes Feld von \(F\) ist eine Eigenschaft: \(\sigma\) enthält das Feld. Für eine Menge \(I\) mit \(|I| = t\) Feldern zählt \(N(I)\) die Permutationen, die alle Felder von \(I\) enthalten.
• Schritt 2: Liegen zwei Felder in derselben Zeile oder Spalte, enthält keine Permutation beide, also ist \(N(I) = 0\). Ist \(I\) nichtangreifend, sind \(t\) Zeilen und \(t\) Spalten festgelegt, und die übrigen \(n-t\) Zeilen gehen beliebig auf die übrigen \(n-t\) Spalten: \(N(I) = (n-t)!\).
• Schritt 3: Alle nichtangreifenden \(I\) gleicher Größe tragen denselben Betrag \((-1)^t (n-t)!\) bei. Ihre Zahl ist \(r_t\), und \(r_t = 0\) für \(t > n\). Das gibt die Formel mit höchstens \(n+1\) Summanden. Die Turmzahlen selbst muss man berechnen; die Demo tut das zeilenweise mit einer Spaltenmaske. Der Aufwand dafür steckt in keiner Summandenzahl dieser Seite und wurde nicht gezählt.

Hamiltonkreise über Spaziergänge.

• Schritt 1: Ein geschlossener Spaziergang der Länge \(n\) von Stadt 0 durchläuft \(n\) Positionen (ohne die letzte Rückkehr). Besucht er alle \(n\) Städte, sind die Positionen paarweise verschieden: jede Stadt genau einmal, also ein Hamiltonkreis, und jeder gerichtete Kreis kommt genau einmal vor.
• Schritt 2: Objekte sind alle geschlossenen Spaziergänge der Länge \(n\) von Stadt 0 im ganzen Graphen. Die Eigenschaft \(A_v\) für \(v \in V \setminus \{0\}\) heißt: der Spaziergang meidet die Stadt \(v\).
• Schritt 3: Meidet der Spaziergang alle Städte aus \(I\), bleibt \(S = V \setminus \{0\} \setminus I\), und \(N(I) = W(S)\). Wegen \(|V \setminus \{0\}| = n-1\) ist \(|I| = n-1-|S|\). Eingesetzt in die Siebformel entsteht die abgesetzte Formel oben.
• Schritt 4: \(W(S)\) entsteht durch \(n\) Vektorschritte über die Kanten innerhalb von \(S \cup \{0\}\). Gespeichert werden nur \(n\) Zahlen.

Warum das Sieb bei Rundreisen mehr Schritte braucht. Rechnung für den vollständigen gerichteten Graphen ohne Schleifen.

• Schritt 1 (Held–Karp): Zustände sind (Menge, Endstadt). Enthält die Menge die Stadt 0 und \(s\) weitere Städte, gibt es \(s\) mögliche Endstädte und je \(n-1-s\) Übergänge zu einer neuen Stadt. Dazu kommen \(n-1\) Übergänge vom Start.
• Schritt 2: Die Summe \(\sum_s \binom{n-1}{s}\, s\,(n-1-s) = (n-1)(n-2)\,2^{n-3}\) ergibt \((n-1)(n-2)\,2^{n-3} + (n-1)\) Übergänge. Probe: Für \(n = 10\) sind das die gezählten 9.225.
• Schritt 3 (Sieb): Für eine Menge \(S\) mit \(q = |S|+1\) Städten kostet jeder Schritt ab dem dritten genau \(q(q-1)\) Kantenübergänge. Mit \(\sum_S q(q-1) = (n-1)(n+2)\,2^{n-3}\) ergibt das in führender Ordnung \((n-2)(n-1)(n+2)\,2^{n-3}\) Rechenschritte. Die beiden ersten Schritte und die kleinsten Mengen kommen hinzu; die gezählten 124.344 für \(n = 10\) liegen darum etwas darüber.
• Schritt 4: Das Verhältnis der Schritte wächst in führender Ordnung wie \(n+2\), also etwa linear in \(n\). Das passt zu den gemessenen Verhältnissen, die für \(n = 6\) bis 10 steigen (Tabelle unten). Gespeichert werden dagegen \(n\) Zahlen gegen \(1 + (n-1)\,2^{n-2}\) Zustände.

Warum Gleitkomma versagt (Größenordnung). Die Summanden \(\binom{k}{j}\, j^k\) der Surjektionen von \(k\) auf \(k\) erreichen für \(k = 40\) den Betrag 1,2·10⁶⁸, das Ergebnis \(k!\) ist um etwa zwanzig Zehnerpotenzen kleiner. Eine Gleitkommazahl doppelter Genauigkeit trägt rund sechzehn Dezimalstellen, der Rundungsfehler der größten Summanden liegt also um rund sechzehn Zehnerpotenzen unter ihnen und damit weit über dem Ergebnis. Der Fehler ist damit grob zehntausendfach größer als das Ergebnis, was zur gemessenen relativen Abweichung von \(2{,}8 \cdot 10^{4}\) passt. Ganze Zahlen runden nicht.

Bit-Breite der gepackten Polynome. Jeder Koeffizient einer Teilsumme ist höchstens \(2^{n-1} \cdot n^n\), denn es gibt \(2^{n-1}\) Mengen mit je höchstens \(n^n\) Spaziergängen der Länge \(n\). Die Demo wählt \(B = n \cdot \ell + n + 2\) mit \(\ell\) als Bit-Länge von \(n\), das liegt über \(\log_2(2^{n-1} n^n)\). Positive und negative Summanden werden getrennt gesammelt und erst am Ende subtrahiert, damit kein Koeffizient negativ und kein Übertrag falsch wird.

Durchgerechnet

Die ersten drei Beispiele stammen aus der Demo (Handinstanzen und Voreinstellung), das vierte ist eine Rechnung dieser Seite.

• Derangements von 4 (Hauptdiagonale): \(r_t = \binom{4}{t}\), also \(D_4 = 4! - 4 \cdot 3! + 6 \cdot 2! - 4 \cdot 1! + 1 \cdot 0! = 9\).
• Ménage \(n = 3\): Turmzahlen 1, 6, 9, 2, also \(6 - 12 + 9 - 2 = 1\).
• Zufallsbrett 8 × 8, 14 verbotene Felder (Voreinstellung): Turmzahlen 1, 14, 60, 92, 45, höhere sind 0. Damit ist \(40.320 - 14 \cdot 5.040 + 60 \cdot 720 - 92 \cdot 120 + 45 \cdot 24 = 3.000\). Statt 16.384 Feldmengen sind es 5 Summanden.
• Hamiltonkreise, vollständiger Digraph auf 4 Städten ohne Schleifen: Die Zahl geschlossener Spaziergänge der Länge 4 von einer Stadt auf \(q\) vollständig verbundenen Städten ist \(((q-1)^4 + (q-1))/q\). Das gibt \(W = 0, 1, 6\) für \(q = 1, 2, 3\) und für \(q = 4\) die Zahl einundzwanzig (81 plus 3, geteilt durch 4). Es gibt je 1, 3, 3, 1 Mengen \(S\) mit \(|S| = 0, 1, 2, 3\) und den Vorzeichen \((-1)^{3-|S|}\). Die Summe ist einundzwanzig minus \(3 \cdot 6\) plus \(3 \cdot 1\) minus 0, also \(6 = 3!\) Hamiltonkreise.

Befunde

Alle Anzahlen sind exakt gezählt, keine Stichproben. Die Zufallsinstanzen entstehen aus festen Startwerten und sind damit wiederholbar. Die Zufallsbretter der ersten Tabelle haben den Startwert 100; sie sind nicht das Brett der Voreinstellung (Startwert 35), darum haben „Zufallsbrett 20 %, n = 8“ dort 12 und in der Voreinstellung 14 verbotene Felder. Die erste Tabelle zeigt, wie die Summanden schrumpfen, die zweite das Sieb gegen Held–Karp im vollständigen gerichteten Graphen.

Brett	\(n\)	verbotene Felder	Teilmengen \(2^{|F|}\)	nichtangreifend	Turmzahlen ungleich 0
Hauptdiagonale	10	10	1.024	1.024	11
Ménage-Brett	10	20	1.048.576	15.127	11
Zufallsbrett 20 %	8	12	4.096	235	7
Zufallsbrett 40 %	8	19	524.288	2.737	8
Zufallsbrett 15 %	12	27	134.217.728	45.652	11

\(n\)	Teilmengen im Sieb	Rechenschritte Sieb	Zustände Held–Karp	Übergänge Held–Karp	Verhältnis der Schritte	Hamiltonkreise
6	32	1.580	81	165	9,6	120
7	64	5.154	193	486	10,6	720
8	128	15.638	449	1.351	11,6	5.040
9	256	45.000	1.025	3.592	12,5	40.320
10	512	124.344	2.305	9.225	13,5	362.880

Die Zustände von Held–Karp folgen \(1 + (n-1)\,2^{n-2}\), die Zahl der Hamiltonkreise ist \((n-1)!\). Das Sieb speichert \(n\) Zahlen gegen die Zustände.

Frage	Befund
Voreinstellung: Zufallsbrett 8 × 8, Anteil 20 %, Startwert 35	14 verbotene Felder, 3.000 Zuordnungen (7,44 % von 8!), Turmzahlen 1, 14, 60, 92, 45. Aufwand je Rechenweg: 5 Summanden (Turmzahlen), 16.384 (Feldmengen), 255 (Ryser), 233 Zustände (Teilmengen-DP), 40.320 Permutationen (Aufzählen).
Kostenverteilung: 8 Städte, alle Kanten, Kosten 1 bis 5, Startwert 35	5.040 Hamiltonkreise mit Kosten von 8 bis 39. Billigste Kosten 8, einmal, gleich Held–Karp und Aufzählen. Das Sieb braucht 15.638 Rechenschritte.
Ménage-Zahlen	Für \(n = 0\) bis 2: 1, 0, 0 nach Definition (nicht gerechnet). Für \(n = 3\) bis 12: 1, 2, 13, 80, 579, 4.738, 43.387, 439.792, 4.890.741, 59.216.642, durch mehrere Rechenwege bestätigt. Aufzählen bestätigt \(n = 3\) bis 8. Turmzahlen für \(n = 6\): 1, 12, 54, 112, 105, 36, 2.
Gleitkomma bei Surjektionen von \(k\) auf \(k\)	Relative Abweichung für \(k = 10, 15, 20, 25, 30, 40\): 0, 1,5·10⁻¹⁰, 2,1·10⁻⁷, 8,8·10⁻⁵, 3,2·10⁻², 2,8·10⁴. Der größte Summand wächst von 4,8·10¹⁰ bei \(k = 10\) auf 1,2·10⁶⁸ bei \(k = 40\). Mit ganzen Zahlen stimmt das Ergebnis in allen sechs Fällen (\(= k!\)).
Surjektionen und Legendre	10 Aufgaben auf 3 Maschinen: 55.980 von 59.049 Abbildungen lassen keine Maschine leer (94,8 %; bei 4 und 5 Maschinen 0,7806 und 0,5225). 12 auf 3: 519.156 von 531.441 (97,7 %). Zahlen von 1 bis 1000 ohne die Teiler 2, 3, 5, 7: 228, mit 16 Summanden.
Weitere Einstellungen	Hauptdiagonale 10: 1.334.961 Zuordnungen. Ménage-Brett mit 9 Paaren: 43.387 (18 Felder, 262.144 Teilmengen, 5.778 nichtangreifend, 10 Turmzahlen). Leeres Brett \(n = 7\): 5.040. Volles Brett \(n = 6\): 0. Rundreise mit allen Kanten, 8 Städte, Kosten 1 bis 3: 5.040 Kreise, billigste Kosten 10, 8 Mal. Mit 60 % der Kanten und Kosten bis 5: 30 Kreise, billigste Kosten 18, einmal.
Zeit (nur einmal gemessen, kein Zählwert)	Auf dem Entwicklungsrechner des Autors, vollständiger Digraph, \(n = 10\): Sieb 0,03 s, Held–Karp-Zähler 0,01 s. \(n = 12\): 0,18 s gegen 0,04 s. Nur dieses Zeitexperiment ruft den Kern auch mit 12 Städten direkt auf; der Regler der Rundreise endet bei 10.

Grenzen und was die Messung zeigt

Was sie belegt:

• Die Anzahlen sind exakte ganze Zahlen, und jeder Rechenweg wird gegen mindestens einen anderen geprüft. Gegengeprüft wurden zusätzlich 100 Zufallsbretter (\(n = 3\) bis 7), 100 Zufallsdigraphen (\(n = 3\) bis 8) und 60 TSP-Instanzen (\(n = 3\) bis 8).
• Der Aufwand ist als Zahl der Summanden, Zustände, Übergänge und Rechenschritte gezählt. Dass die Summanden bei Zuordnungen schrumpfen, ist für die fünf Bretter der ersten Tabelle gezählt; die Schranke \(n+1\) folgt aus der Herleitung.
• Dass das Sieb im vollständigen gerichteten Graphen mehr Schritte braucht, ist für 6 bis 10 Städte gezählt und passt zur Rechnung oben.

Was sie nicht belegt:

• Zeit: Das Sieb gewinnt gegen Held–Karp nur beim Speicher. Die Zeiten sind Python-Messungen eines Rechners, zwei Läufe unterscheiden sich, und sie sagen nichts über andere Sprachen oder Rechner.
• Dünne Graphen: Das Verhältnis der Schritte ist nur für den vollständigen gerichteten Graphen gezählt, nicht für Graphen mit fehlenden Kanten.
• Gleitkomma: Das Surjektionsbeispiel zeigt, dass das Versagen vorkommt, nicht dass jede Siebformel versagt. Für Hamiltonkreise nennt die Demo eine Nachrechnung des Autors, deren Rechenweg nicht dokumentiert ist: bis 14 Städte exakt, ab 15 abweichend, relativ 1,6·10⁻⁹ bei 16. Die Schwelle hängt vom Rechenweg ab: Eine weitere Nachrechnung (doppelte Genauigkeit, Vektor-Rekursion mit Symmetriereduktion, vollständiger Digraph) fand erst ab 16 Städten eine Abweichung, und zwar eine kleinere. Die Demo prüft das nicht automatisch.
• Grenzen der Demo: Das Sieb über Feldmengen läuft bis 16 verbotene Felder, die Turmzahlen bis \(n = 12\). Rundreisen haben höchstens 10 Städte (\(2^{n-1}\) Mengen), Kosten sind ganze Zahlen von 1 bis 5 (Grad \(n \cdot c_{\max}\)). Nur das Zeitexperiment rechnet auch \(n = 12\) Städte, direkt im Kern. Aufzählen als Prüfer geht bis \(n = 8\); darüber prüfen sich Sieb, Teilmengen-DP und Formeln gegenseitig.
• Nur gerichtete Hamiltonkreise ab Stadt 0: Ein ungerichteter Kreis zählt in beide Richtungen, also zweimal. Björklunds Verfahren für ungerichtete Kreise gehört nicht zur Demo.
• Härte: Die Permanente ist #P-schwer; das Ryser-Sieb mit \(2^n - 1\) Summanden ist ein Rechenweg bis \(n = 12\), kein Härtebeweis.
• Literaturwerte: Die Ménage-Folge, die Ryser-Formel und die Spaziergangs-Variante für Hamiltonkreise wurden an keiner Quelle gelesen. Mehrere unabhängige Rechenwege stimmen überein, das ersetzt keine Quelle.
• Simuliert: Alle Instanzen sind erzeugt, keine echten Daten.

Quellen

• H. J. Ryser: Combinatorial Mathematics. Carus Mathematical Monographs 14, 1963 (Permanente als Sieb).
• J. Riordan: An Introduction to Combinatorial Analysis. Wiley, 1958 (Turmpolynome, Ménage-Zahlen).
• R. M. Karp: Dynamic programming meets the principle of inclusion and exclusion. Operations Research Letters 1 (2), 1982, S. 49–51 (Sieb statt Teilmengen-DP).
• A. Björklund: Determinant sums for undirected Hamiltonicity. FOCS 2010 (Ausblick, nicht Teil der Demo).
• Quelltext, Messreihen und Tests der Demo: github.com/sebastian-hanisch/siebformel-demo.

Die vier Literaturangaben stammen aus der Dokumentation der Demo und sind dort als aus dem Gedächtnis, nicht eingesehen vermerkt; für diese Seite wurden sie nicht nachgeschlagen. Das gilt auch für die Zuschreibung der Spaziergangs-Variante an Karp, Bax und Kohn–Gottlieb–Kohn. Die Beispiele mit Hüten, Aufgaben und Mailinglisten sind erdacht; die Herleitungen und die Rechnung mit 4 Städten sind Rechnungen dieser Seite und keine Messungen.