Anzahl ganzzahliger Kompositionen

Eine geordnete Komposition einer positiven ganzen Zahl n ist ein Tupel positiver ganzer Zahlen, die sich zu n addieren, wobei die Reihenfolge der Teile zur Identität gehört: 1+3 und 3+1 sind zwei verschiedene Kompositionen von vier. Die klassische Kombinatorik beweist, dass die Anzahl solcher geordneten Summen stets zwei hoch n minus eins ist. Diese Fähigkeit nimmt eine einzige positive ganze Zahl n entgegen und liefert genau diese Anzahl zusammen mit der geschlossenen Formel 2^(n-1), sodass Sie nicht jedes Tupel aufzählen, einen binären Trennbaum durchlaufen oder bei Hausaufgaben, Wettbewerbsfällen oder erzeugenden Funktionen einen Einserfehler riskieren müssen.

Warum die Anzahl geordneter Kompositionen zwei hoch n minus eins ist

Schreiben Sie n Einsen in eine Reihe. Zwischen diesen Einsen liegen genau n minus eins Lücken. In jeder Lücke können Sie entweder einen Strich setzen, der die Folge in einen neuen Teil spaltet, oder die Lücke leer lassen, sodass benachbarte Einsen als größerer Teil zusammenbleiben.

Jedes Muster aus Strichen und leeren Lücken erzeugt eine geordnete Komposition von n, und jede Komposition entsteht aus genau einem solchen Muster. Weil jede der n minus eins Lücken zwei unabhängige Wahlmöglichkeiten hat, ist die Gesamtzahl der Muster zwei hoch n minus eins. Diese Identität ist der gesamte Algorithmus, den diese Fähigkeit auswertet: Sie durchläuft keine Erstteil-Zweige, legt kein Array von Tupeln an und zieht keine Stichprobe.

Eine Einzeilenprüfung für n gleich vier ergibt acht und passt zu den acht Kompositionen (4), (1,3), (3,1), (2,2), (1,1,2), (1,2,1), (2,1,1) und (1,1,1,1). Für n gleich eins gibt es ein einziges Muster ohne Striche und die Anzahl ist eins, nämlich die Komposition (1) selbst. Die geschlossene Form ist für jede positive ganze Zahl exakt, sodass eine Hausarbeit, die neun Kompositionen von vier behauptet, schlicht falsch liegt, und ein Generator, der die Größe der Kompositionsfamilie braucht, Puffer aus dieser Anzahl dimensionieren kann, ohne sie je aufzulisten.

Die Reihenfolge ist wesentlich: Wenn Sie 1+3 mit 3+1 gleichsetzen, haben Sie die Kompositionen verlassen und die Welt der Partitionen betreten, deren Anzahl p(n) keine solche Zweierpotenzformel hat und eine andere Suchabsicht darstellt.

Was Sie senden, was Sie zurückerhalten und wann die Anfrage scheitert

Die Produktregel ist streng: n unter eins ist ungültig, einschließlich null und jeder negativen Zahl, weil die übliche Definition einer Komposition eine positive ganze Zahl zum Zerlegen verlangt. Bei Erfolg wiederholt die Antwort das normalisierte n, liefert count als Dezimalzeichenkette des exakten Werts 2^(n-1) und enthält formula als die Identitätszeichenkette 2^(n-1), damit Clients den Satz anzeigen können, ohne ihn fest einzuprogrammieren.

Die Anzahl ist absichtlich eine Zeichenkette: zwei hoch dreiundfünfzig verlässt bereits den sicheren Integer-Bereich von JavaScript, und diese Seite ist gerade dann nützlich, wenn n so groß ist, dass das Auflisten jeder Komposition aussichtslos wird. Fehlgeschlagene Prüfung wird nicht berechnet.

Wo eine Kompositionsanzahl hingehört und wie sie bepreist wird

Verwenden Sie diese Anzahl, wenn die Frage lautet, wie viele geordnete Summen existieren, nicht welche Tupel es sind. Wettbewerbsprogrammierer prüfen Kandidatenlösungen für Kompositionszählprobleme gegen ein deterministisches Orakel, statt in jedem Sprach-Harness eine BigInt-Potenz neu zu implementieren. Lehrkräfte geben den Lücken-und-Striche-Beweis auf und brauchen eine maschinelle Prüfung, dass 2^(n-1) wirklich die Größe der Familie ist, bevor Lernende sie aufzulisten versuchen.

Interview-Sandkästen und Demonstrationen erzeugender Funktionen brauchen jedes Mal dieselbe Zahl. Daten- und Compilerarbeit dimensioniert manchmal einen Suchraum geordneter Stufenaufteilungen eines Budgets n und muss die Kardinalität kennen, bevor Speicher angelegt wird. Wenn Sie tatsächlich jedes Tupel brauchen, halten Sie hier inne und nutzen Sie ein Auflistungswerkzeug bei kleinem n; wenn Sie Kompositionen in genau k Teile brauchen, ist das der Binomialkoeffizient C(n-1, k-1) und eine andere Seite; wenn die Reihenfolge keine Rolle spielt, wollen Sie die Partitionsfunktion p(n).

Halten Sie n in den dokumentierten Grenzen, behandeln Sie die Zeichenkette count als die exakte ganze Zahl, und Sie erhalten eine reproduzierbare Kompositionsanzahl ohne ein Computeralgebrasystem zu installieren.