Nummer des speziell bestellten Satzes

Eine geordnete Menge ist eine Menge, bei der die Reihenfolge, in der die Objekte in der Menge erscheinen, signifikant ist.

Zum Beispiel sind (1, 2, 3) und (2, 1, 3) zwei verschiedene geordnete Sätze von ganzen Zahlen.

Eine geordnete Menge ganzer Zahlen heißt eine spezielle Menge, wenn die Menge für jedes Element X der Menge nicht das Element X+1 enthält.

Bestimmen Sie die Anzahl der speziellen Mengen für die Zahl N, deren größtes Element nicht größer als N ist.

Für N = 3 gibt es 5 spezielle Sätze, nämlich (1), (2), (3), (1, 3), (3, 1).

Ich habe es selbst versucht, indem ich die gesamte geordnete Menge gezählt habe, indem ich die Differenz der Elemente größer als > = 2 genommen habe, aber schließlich beobachte ich, dass es für einige der Teilmengen mit einer Größe von mehr als > = 2 nachgezählt wird.

könnte mir bitte jemand erklären, wie man es richtig zählt.

Vielen Dank im Voraus.

Wird verlangt, dass spezielle Mengen nicht leer sind?
Ja, der gesamte spezielle Satz sollte nicht leer sein.
Sie sollten das in Ihrer Frage bearbeiten, um die Dinge klarer zu machen.
Ich denke, eine leere Menge hat hier keine Bedeutung, wie aus dem in der Frage angegebenen Beispiel hervorgeht.
Für zB den Fall N = 3 der Satz ∅ erfüllt offensichtlich (leer) die Bedingung, dass für jedes Element X in der Menge das Element X + 1 ist nicht im Set. Auch die Menge ist nach der leeren Relation geordnet.
Aber hier habe ich Zweifel, wenn wir kein Element aus der Menge auswählen, wie können wir dann annehmen, dass X + 1 nicht in der Nullmenge vorhanden ist. da wir kein Element in der Menge haben. kannst du es bitte erklären.
Jede Aussage des Formulars ∀ X ∈ ∅ [ P ] oder gleichwertig ∀ X [ X ∈ ∅ ⟹ P ] stimmt (egal was P Zustände). Um dies zu verstehen, beachten Sie, dass seine Negation, dh ∃ X [ X ∈ ∅ ∧ ¬ P ] ist falsch, weil X ∈ ∅ ist für jeden falsch X .

Antworten (2)

Angenommen, es gibt sie M Elemente in einem speziellen Set. Das scheint klar M ≤ ⌊ ( N + 1 ) / 2 ⌋ . Ein bekanntes Ergebnis in der Kombinatorik (siehe unten) ist, dass es gibt ( N − M + 1 M ) Teilmengen von 1 , 2 , 3 , … , N von Größe M ohne angrenzende Elemente. Jedes dieser Sets kann bestellt werden M ! Wege. Die Gesamtzahl der Spezialsets ist also

∑ M = 1 ⌊ ( N + 1 ) / 2 ⌋ ( N − M + 1 M ) M !
Die ersten paar Werte, z 1 ≤ N ≤ 10 , Sind 1 , 2 , 5 , 10 , 23 , 50 , 121 , 290 , 755 , 1978 . Ich habe auf OEIS gesucht, ohne diese Sequenz zu finden.

Für diejenigen, die mit der Formel für die Anzahl der Möglichkeiten, k nicht benachbarte Elemente aus n auszuwählen, nicht vertraut sind, hier eine Ableitung. Angenommen, wir möchten auswählen k nicht benachbarte ganze Zahlen A 1 , A 2 , A 3 , … , A k aus dem Satz { 1 , 2 , 3 , … , N } . Damit die Auswahlmöglichkeiten nicht benachbart sind, müssen wir haben 1 ≤ A 1 , A 1 < A 2 − 1 , A 2 < A 3 − 1 , A 3 < A 4 − 1 , ..., A k − 1 < A k − 1 , Und A k ≤ N . Eine äquivalente Menge von Ungleichungen ist

1 ≤ A 1 < A 2 − 1 < A 3 − 2 < A 4 − 3 < ⋯ < A k − k + 1 ≤ N − k + 1
Wir können also die Werte äquivalent auswählen A 1 , A 2 − 1 , A 3 − 2 , A 4 − 3 , … , A k − k + 1 aus { 1 , 2 , 3 , … , N − k + 1 } , und dies kann in getan werden ( N − k + 1 k ) Wege.

Eine iterative Methode

Die Anzahl der Spezialsets für N Ist 1 kleiner als die Summe der Elemente in der N + 1 te Spalte der Matrix M . Zum Beispiel für N = 4 die Anzahl der Spezialsets ist 4 + 6 = 10 .

M = ( 1 1 1 1 1 1 1 1 . . . 0 1 2 3 4 5 6 7 . . . 0 0 0 2 6 12 20 30 . . . 0 0 0 0 0 6 24 60 . . . 0 0 0 0 0 0 0 24 . . . . . . . . . . . . . . . . . . . . . . )

Die Matrix wird durch die Formel berechnet

M ich + 1 , J + 2 = M ich + 1 , J + 1 + ich M ich , J

und ist einfach in Excel zu implementieren. Dieser Zusammenhang wird wie folgt bewiesen.

Das Element M ich + 1 , J + 2 zählt die Anzahl der Spezialsets für J + 1 von Größe ich . Betrachten Sie diese Sets danach, ob sie enthalten oder nicht J + 1 .

Nicht enthalten J + 1 . Es gibt M ich + 1 , J + 1 von diesen.

Enthält J + 1 . Ein solches Set gehört zu den M ich , J setzt für J − 1 von Größe ich − 1 mit J + 1 in einem hinzugefügt J mögliche Positionen.

Nummer des speziell bestellten Satzes
AntwortenHierDatenschutz-Bestimmungen1y, 0v