Ordnen verschiedener Objekte in Linien und einen Kreis

Es ist gegeben, dass wir haben N verschiedene Objekte und wir wollen sie in nicht leeren Linien anordnen, danach ordnen Sie diese nicht leeren Linien um einen Kreis. Wie viele Möglichkeiten gibt es bei dieser Frage? Die gegebene Antwort ist ( 2 N − 1 ) ! ( N − 1 ) ! .Es wird ein Hinweis gegeben, wie man die Zusammensetzung von exponentiell erzeugenden Funktionen verwendet.

Was ich dachte: Ohne den Hinweis zu verwenden, dachte ich, dass, wenn es gibt k Zeilen wo k ∈ { 1 , 2 , 3... } , GF dieser Linien ist ( X / ( 1 − X ) ) , also können wir das sagen

∑ k = 1 ∞ [ X N ] ( X 1 − X ) k N !
Möglichkeiten, diese zu arrangieren N eindeutiges Objekt. Außerdem weiß ich, dass, wenn ich habe M eindeutiges Objekt, ich kann sie um einen Kreis herum anordnen ( M − 1 ) ! Wege. Ich kann es jedoch nicht in dieser Frage verwenden, weil ich denke, dass, wenn die Anzahl der Objekte in einer Linie gleich ist, diese Linien als gleich angesehen werden können und es nicht erlaubt, diese Formel zu verwenden, also werde ich es brauchen Die Aufzählung von Polyas. Die Frage wird also qualvoll sein.

Daher möchte ich hier Hilfe ... Wie kann ich den Hinweis, dh EGF, verwenden, um diese Frage zu lösen und die gegebene Antwort zu erreichen.

Danke im Voraus !!

Nachtrag: Für N = 3 ,die Antwort ist ( 2 3 − 1 ) ( 3 − 1 ) ! = 14 laut der Antwort von @ Marko Riedel. Wenn ich es jedoch mit brutaler Gewalt berechne, finde ich eine andere Antwort, so dass:

1 − ) Für nur eine Zeile: 3 ! × ( 1 − 1 ) ! = 6 Wege

2 − ) Für zwei Zeilen: 3 ! × C ( 1 + 2 − 1 , 1 ) × ( 2 − 1 ) ! = 12 Wege

3 − ) Für drei Zeilen: 3 ! × ( 3 − 1 ) ! = 12 Wege

Ergebnis= 6 + 12 + 12 = 30 , Was übersehe ich hier? Warum ist es nicht gleich 14 ?

Antworten (1)

Wir haben die Verwendung kombinatorischer Klassen wie in Analytic Combinatorics von Flajolet und Sedgewick die folgende Klasse

F = C Y C ( S E Q ≥ 1 ( Z ) ) .

Das gibt der EGF

F ( z ) = Protokoll ⁡ 1 1 − z / ( 1 − z ) = Protokoll ⁡ 1 − z 1 − 2 z = − Protokoll ⁡ 1 1 − z + Protokoll ⁡ 1 1 − 2 z .

Extrahieren von Koeffizienten, die wir finden

N ! [ z N ] F ( z ) = − N ! 1 N + N ! 2 N N = ( N − 1 ) ! ( 2 N − 1 ) .

Hier haben wir die Tatsache ausgenutzt, dass C Y C ( Q ) hat EGF Protokoll ⁡ 1 1 − Q ( z ) Und S E Q ≥ 1 ( Q ) hat EGF Q ( z ) 1 − Q ( z ) was wiederum daraus folgt, dass die zyklische Gruppe C M hat Ordnung M und die Identitätsgruppe E M hat Ordnung 1 damit der EGF von C Y C = M ( Q ) Ist Q ( z ) M / M und der EGF von S E Q = M ( Q ) Ist Q ( z ) M .

Dies ist eine gekennzeichnete Aufzählung, sodass PET nicht verwendet werden muss.

Dies ist Seite 104 der Ausgabe von 2009 (der Online-Ausgabe).
@MarkoRiedel: Sehr schöne und lehrreiche Antwort. (+1)
Vielen Dank für die Gutschrift.
Was Sie Linien nennen, wird allgemein als Block bezeichnet und enthält beschriftete Objekte (Bälle). Es gibt N solche Bälle in jeder Konfiguration und sie haben alle unterschiedliche Etiketten. Es gibt also keine Symmetrie zwischen Blöcken, sie sind paarweise verschieden. Ich denke, meine Antwort ist die richtige. Sie könnten Ihre Berechnungen im Fragetext dokumentieren. Zum Beispiel mit N = 3 und drei Blöcke müssen alle Singletons sein und wir erhalten aufgrund der zyklischen Symmetrie zwei verschiedene Konfigurationen.
Mit N = 3 Ich bekomme für drei Blocks zwei Wege, für zwei Blocks ( 3 2 ) × 2 für sechs Wege und für einen Block, 3 ! = 6 Wege, für insgesamt vierzehn gemäß der Formel, die die Gesamtsumme ergibt.
MSE sagt, diese Diskussion zu schließen. Ich glaube, Sie verwechseln drei (die Gesamtzahl der Elemente) und drei (die Anzahl der Blöcke). Mit N = 3 und drei Blöcke sind alle Blöcke Singletons und wir erhalten die zwei Möglichkeiten ( [ 1 ] , [ 2 ] , [ 3 ] ) Und ( [ 1 ] , [ 3 ] , [ 2 ] ) .
Ordnen verschiedener Objekte in Linien und einen Kreis
AntwortenHierDatenschutz-Bestimmungen1y, 0v