Anzahl süßer Permutationen

Question

Anzahl süßer Permutationen

Mathematik
Wettbewerb-Mathematik
Kombinatorik
Korrekturschreiben

Ottawa

Eine Permutation der Zahlen $1,2,3,\dots,n$ heißt niedlich , wenn es genau eine Zahl gibt, die größer als ihre Position ist. Zum Beispiel, $1,4,3,2$ ist eine niedliche Permutation (when $n=4$ ) weil nur die Zahl $4$ ist größer als seine Position. Wie viele niedliche Permutationen gibt es für einen Fix $n$ ?

Das Problem stammt von einem lokalen Mathematikwettbewerb. Hier mein Versuch das Problem zu lösen:

Das ist mir aufgefallen, wenn $p_1,p_2,\dots,p_n$ ist eine niedliche Permutation wo $p_k>k$ dann für alle $i\neq k$ , wir haben $p_i\leq i$ . Aber ich denke nicht, dass dies hilfreich ist, um die Anzahl der niedlichen Permutationen zu finden.

Ich versuchte auch für kleine Werte von $n$ indem Sie alle möglichen Permutationen auflisten.

Für $n=2$ , ist es leicht zu sehen, dass es nur eine solche Permutation gibt.
Für $n=3$ , Ich fand $4$ Permutationen.
Für $n=4$ , Ich fand $10$ Permutationen.

Von hier aus scheint es mir, dass die Anzahl der niedlichen Permutationen ist $\binom 22+\binom 32+\dots+\binom n2$ . Aber ich habe keine Möglichkeit gefunden, das zu zeigen.

Also, wie kann man das Problem lösen? Und was passiert, wenn wir eine Permutation weniger süß nennen, wenn es genau zwei Zahlen gibt, die größer als ihre Position sind? Können wir allgemein lösen?

Markus S.

@Yorch Ihre Antwort bezieht sich auf Permutationen, die genau einmal abnehmen, im Gegensatz zu der niedlichen Permutation

1, 4, 3, 2

$1,4,3,2$ . Es sei denn, Sie schlagen eine Beziehung zwischen den beiden Problemen vor?

Phicar

|Niedlich|=|Eulersch|

Saksham Sethi

Von welcher Konkurrenz war das?

Darij Grinberg

Ihre niedlichen Permutationen sind genau die Permutationen, die genau haben

1

$1$ Überschreitung . Siehe Proposition 1.4.3 in Richard Stanleys EC1 für die Antwort auf die allgemeinere Frage über

k

$k$ Überschreitungen.

Antworten (2)

Anzahl süßer Permutationen

@Yorch Ihre Antwort bezieht sich auf Permutationen, die genau einmal abnehmen, im Gegensatz zu der niedlichen Permutation $1,4,3,2$ . Es sei denn, Sie schlagen eine Beziehung zwischen den beiden Problemen vor?
Ihre niedlichen Permutationen sind genau die Permutationen, die genau haben $1$ Überschreitung . Siehe Proposition 1.4.3 in Richard Stanleys EC1 für die Antwort auf die allgemeinere Frage über $k$ Überschreitungen.

Rescha Adrian Tanuharja · Answer 1

So bilden wir eine niedliche Permutation: select $m$ Zahlen; $x_{1}<x_{2}<...<x_{m}$ . Setzen $x_{m}$ In $x_{1}$ 's ursprünglichen Standort dann für alle $i\in[1,2,...,m-1]$ setzen $x_{i}$ In $x_{i+1}$ 's ursprünglicher Standort. Die Anzahl der niedlichen Permutationen wird durch den folgenden Ausdruck angegeben:

\sum_{M = 2}^{N} (\binom{N}{M}) = 2^{N} - (N + 1)

$\sum_{m=2}^{n}{\binom{n}{m}}=2^{n}-\left(n+1\right)$

Die Idee ist, dass aus $n$ Nummern, einige ändern ihre Position ( $m$ von ihnen), während der Rest an seiner ursprünglichen Position bleibt. Von allen Zahlen, die ihre Position ändern, bewegt sich nur eine nach links, während sich die anderen nach rechts bewegen.

Übrigens für $n=4$ es gibt $11$ nette Permutationen statt $10$

@MishaLavrov stimmt, das ist eher ein Hinweis. Ich habe gerade die Antwort mit einigen Teilen meiner Gedanken geschrieben, hoffentlich genug, um OP einige Ideen zu geben.
Was ist mit der zweiten Frage? Können wir allgemein lösen?

KopierenPasteIt · Answer 2

Eine süße Permutation in $S_n$ kann immer mit einem nicht-trivialen (Länge größer oder gleich) identifiziert werden $2$ ) zyklische Permutation wirkt auf $\{1,2,\dots,n\}$ einer speziellen Form , also ist die Aufgabe, die Zahl der niedlichen zyklischen Permutationen zu zählen.

Wenn Ihnen die "aktiven" Elemente einer niedlichen zyklischen Permutation der Länge zwei oder mehr präsentiert werden, werden Sie schnell feststellen, dass es nur eine Möglichkeit gibt, diese Permutation neu aufzubauen (siehe Beispiel im nächsten Abschnitt). .

Seit

$\quad \text{The number of subsets of } \{1,2,\dots,n\} = 2^n$
$\;\;\;$ und die Anzahl der Teilmengen mit $0$ Elemente ist $1$ ,
$\quad\;$ und die Anzahl der Teilmengen mit $1$ Element ist $n$ ,
schließen wir daraus, dass die Anzahl der niedlichen Permutationen gegeben ist durch

$\tag{1} 2^n-1-n$

Beispiel: Wenn $n = 4$ dann die Teilmenge $\{1,3,4\}$ entspricht der niedlichen (zyklischen) Permutation

$\quad (4\, 3\, 1)$

Eine niedliche Permutation wird enthalten $n$ Elemente. Warum fahren wir dann nicht mit der Subtraktion fort, dh $2^n-1-n-\binom n2-\dots$ ?

Anzahl süßer Permutationen

Ottawa

Markus S.

Phicar

Saksham Sethi

Darij Grinberg

Antworten (2)

Rescha Adrian Tanuharja

Mischa Lawrow

Rescha Adrian Tanuharja

Ottawa

KopierenPasteIt

Ottawa

Wie viele Krieger kann man maximal auf ein Schachbrett stellen, damit sich nicht zwei Krieger gegenseitig angreifen?

Wie viele nahezu perfekte Permutationen gibt es?

Existenz einer Teilmenge, so dass das Produkt seiner Elemente ein perfektes Quadrat ist

Wegezählung in einem Raster - wie lässt sich dieser Ansatz beweisen?

Wie viele Möglichkeiten gibt es, sich die Hand zu geben?

Wie viele Wege kann ich im folgenden Diagramm von 1 bis 10 gehen?

Leiten Sie eine kombinatorische Identität ab

Wenn 121212 verschiedene Kugeln in 333 identische Kästchen gelegt werden sollen, wie groß ist dann die Wahrscheinlichkeit, dass eines der Kästchen genau 333 Kugeln enthält?

Menschen sitzen um dreieckige Tische