Pascals Satz für nicht eindeutige Sätze?

Question

Pascals Regel der Teilmenge der aus einem Satz auf das Zählen funktioniert gut, wenn das Set enthält einzigartige Einheiten.

Gibt es eine Änderung dieser Regel für, wenn der Satz enthält doppelte Einträge?

Zum Beispiel, wenn ich versuche, die Anzahl der Kombinationen der Buchstaben A, B, C, D zu finden, es ist leicht zu sehen, dass es 1 + 4 + 6 + 4 + 1 (von Pascals Dreieck) = 16, oder 15, wenn ich entfernen Sie den Eintrag „keine der Buchstaben verwenden“.

Nun, was ist, wenn der Satz von Buchstaben A, B, B, B, C, C, D? Computing mit der Hand, kann ich feststellen, dass die Summe von Untergruppen ist. + 4 + 1 8 + 11 + 11 + 8 + 4 + 1 = 48, aber dies entspricht nicht das Dreieck Ich weiß

Frage: Wie ändern Sie Pascal Triangle berücksichtigt doppelte Einheiten in der Menge zu nehmen

Answer 1

Es sieht aus wie Sie wissen wollen, wie viele Sub-Multi-Sets haben, sagen wir, drei Elemente. Die Mathematik für diese wird sehr kompliziert, sehr schnell. Die Idee ist, dass Sie zusammen alle Kombinationen von Möglichkeiten hinzufügen möchten dorthin zu gelangen. So haben Sie C (3,4) = 4 Möglichkeiten, es ohne duplizierte Elemente zu tun. B kann zweimal wiederholt werden in C (1,3) = 3 Wege. B kann 3-mal in 1-Weg wiederholt werden. Und C kann zweimal in C wiederholt werden (1,3) = 3 Wege. Für 11 insgesamt. (Ihre 10 Sie von Hand bekam, war falsch. Tut mir Leid.)

In der Regel, dass die Logik zu tun versucht, ist zu hart. Die einfachere Möglichkeit, den Überblick zu behalten, es ein Polynom, dessen Koeffizienten haben, die Bedingungen zu schreiben, ist, dass Sie möchten, die Sie multiplizieren aus. Für Pascal'schen Dreieck ist dies einfach das Polynom ist (1 + x) ^ n. (Sie können die wiederholte Verwendung quadriert diese effizienter zu berechnen.) In Ihrem Fall, wenn ein Element wird zweimal wiederholt würden Sie haben eine (1 + x + x ^ 2) Faktor. 3 mal wäre (1 + x + x ^ 2 + x ^ 3). So Ihr spezielles Problem gelöst werden würde wie folgt:

(1 + x) (1 + x + x^2 + x^3) (1 + x + x^2) (1 + x)
  = (1 + 2x + 2x^2 + 2x^3 + x^4)(1 + 2x + 2x^2 + x^3)
  = 1    + 2x   + 2x^2 +  x^3 +
    2x   + 4x^2 + 4x^3 + 2x^4 +
    2x^2 + 4x^3 + 4x^4 + 2x^5 +
    2x^3 + 4x^4 + 4x^5 + 2x^6 +
    x^4  + 2x^5 + 2x^6 +  x^7
  = 1 + 4x + 8x^2 + 11x^3 + 11x^4 + 8x^5 + 4x^6 + x^7

Wenn Sie diese Zahlen in Code produzieren wollen, würde ich das Polynom Trick Ihr Denken und Code zu organisieren. (Sie würden mit Arrays von Koeffizienten zu arbeiten.)

Answer 2

Ein Satz enthält nur Unikate. Wenn es Duplikate sind, dann ist es nicht mehr ein Satz.

Answer 3

Ja, wenn Sie nicht wollen, Sätze zu prüfen, die Idee betrachten ‚Faktoren.‘ Wie viele Faktoren tut:

p1^a1.p2^a2....pn^an

, wenn p1 die verschiedenen Primzahlen sind. Wenn die AI alle 1 sind, dann ist die Zahl 2 ^ n. Im Allgemeinen ist die Antwort (a1 + 1) (a2 + 1) ... (an + 1) als David Nimmt bemerkt.

Oh, und beachten Sie, dass Ihre Antwort von Hand falsch war, es 48 sein sollte, oder 47, wenn Sie nicht die leere Menge zählen wollen.

Answer 4

Sie brauchen nicht Pascals Dreieck überhaupt zu ändern. Studie C (k, n) und Sie werden es herausfinden -. Sie grundsätzlich die ursprünglichen Ergebnisse teilen müssen für die Permutation von äquivalenten Buchstaben zu berücksichtigen

z.B. A B1 B2 D1 C1 == B2-B1 C1 D1, daher müssen Sie teilen C (5,5) durch C (2,2).

Answer 5

Ohne Duplikate (in einem Satz wie zuvor Plakate haben festgestellt), jedes Element ist entweder in die oder aus der Teilmenge. So haben Sie 2 ^ n Untergruppen. Mit Duplikate (in einem „Multi-Set“), müssen Sie berücksichtigen die Zahl die Anzahl der jedes Element in der „Sub-Multi-Set“. Wenn es m_1, m_2 ... M_n die Anzahl der einzelnen Elementwiederholungen darstellen, dann ist die Anzahl der Teiltaschen (1 + m_1) * (1 + m_2) * ... (1 + M_n).

Answer 6

Auch wenn mathematische Sätze einzigartige Gegenstände enthalten, können Sie in ‚Sets‘ in der realen Welt der Programmierung in das Problem der doppelten Elemente ausgeführt werden. Siehe diese fädeln auf Lisp Gewerkschaften für ein Beispiel.