Permutationen

Howdy,

wie viele Möglichkeiten gibt es, die Permutationen der natürlichen Zahlen von 1 bis n so anzuordnen dass zwischen zwei aufeinanderfolgenden Gliedern (und zwischen erstem und letztem) nur eine Vertauschung von zwei Elementen stattfindet?

SideWinder

Ich befürchte du musst mir die Angabe genauer spezifizieren, was heißt "vertauschen" da genau, läuft das hintereinander ab:

1 2 3
2 1 3
2 3 1 <- neue permutation

oder muss das gleihczeitg ablaufen = ich kann eine Position immer nur entweder nach links oder nach rechts tauschen? Und sperre den Block dann für weitere Vertuaschungen:

1 2 3
2 1 3 <- möglichkeit a, 3/2 nicht mehr tauschbar
1 3 2 <- möglichkeit b, 2/1 nicht mehr tauschbar

MfG SideWinder

SideWinder schrieb:

Ich befürchte du musst mir die Angabe genauer spezifizieren, was heißt "vertauschen" da genau, läuft das hintereinander ab:
1 2 3
2 1 3
2 3 1 <- neue permutation
oder muss das gleihczeitg ablaufen = ich kann eine Position immer nur entweder nach links oder nach rechts tauschen? Und sperre den Block dann für weitere Vertuaschungen:
1 2 3
2 1 3 <- möglichkeit a, 3/2 nicht mehr tauschbar
1 3 2 <- möglichkeit b, 2/1 nicht mehr tauschbar
MfG SideWinder

eine Vertauschung s(i,j) ist definiert durch (mit i != j), (obda i < j)

s(i, j)(a1, ..., ai, ..., aj, ..., an) = (a1, ..., aj, ..., ai, ..., an)

ich möchte alle permutationen P von (1, ..., n) so anordnen dass gilt:

für alle k aus 1..n existiert i != j so dass P(k + 1) = s(i, j) P(k)

mit P(n + 1) := P(1)

und dann die Anzahl der möglichen Anordnungen.

Hast du für kleine n schon ausprobiert, ob es geht?

Probier doch mal Induktion, ich glaube damit ist es leicht.

n = 1 und 2 trivial.

für n = 3

123 s(2,3)
132 s(1,2)
312 s(2,3)
321 s(1,2)
231 s(2,3)
213 s(1,2)

... und dabei habe ich nicht mal s(1,3) benutzt.

Jeder node hat n*(n - 1) Verbindungen und es gibt n! nodes, d.h. für große n könnte es sein dass es nicht geht ???

n = 4 ist schon arbeit..

hiermit kann man ein graphviz (neato) graphen generieren, aber ab n = 4 erkennt man nix..

from itertools import permutations

import sys
n = int(sys.argv[1])

print "Graph G {"
for i in permutations(range(1, n + 1)):
    for first in range(0, n - 1):
        for second in range(first + 1, n):
            if i[first] > i[second]:
                continue
            s = [str(k) for k in i]
            print "".join(s), "--",
            temp = s[first]
            s[first] = s[second]
            s[second] = temp
            print "".join(s)

print "}"

n = 4 könnte so gehen:

1234 s(2,3)
1324 s(1,2)
3124 s(2,3)
3214 s(1,2)
2314 s(2,3)
2134 s(3,4)

2143 s(2,3)
2413 s(1,2)
4213 s(2,3)
4123 s(1,2)
1423 s(2,3)
1243 s(2,4)

1342 ...

so gehts: induktiv!

Howdy,

dsfdsf schrieb:

n = 4 könnte so gehen:

1234 s(2,3)
1324 s(1,2)
3124 s(2,3)
3214 s(1,2)
2314 s(2,3)
2134 s(3,4)

2143 s(2,3)
2413 s(1,2)
4213 s(2,3)
4123 s(1,2)
1423 s(2,3)
1243 s(2,4)

1342 ...

so gehts: induktiv!

ja, das ist eine Möglichkeit. Ich müsste noch überlegen wie ich am Ende den Kreis schließen kann. Außerdem wollte ich die Anzahl der möglichen Wege rausfinden...

So aus Neugierde: Wofür brauchst du das?

bzgl. der Anzahl: Rechne mal die Anzahl für n=1,2,3 aus und suche unter http://www.research.att.com/~njas/sequences/

volkard

Mein Suchprogramm habe ich erstmal wieder gelöscht. Ich habe bei n=6 ein wenig Angst. Von 6 Dingen gibt es 6! Permutationen und diese kann man auf (6!)! Weisen anordnen.
(1!)!=1
(2!)!=2
(3!)!=720
(4!)!=620448401733239439360000
(5!)!=6689502913449127057588118054090372586752746
3331380298102956713523016335572449629893668741652
7198498130815763789321409055253440858940812185989
8481114389650005964960521256960000000000000000000
000000000
(6!)!= Äh, keine Ahnung. Aber ich wüßte schon gerne, wieviele Stellen die Zahl hat.

@volkard: Du zählst aber *alle* Permutationen. Wir wollen ja nur bestimmte.

BTW: (6!)! =
26012189435657951002049032270810436111915218750169457857275418378508356311569473
82240678577958130457082619920575892247259536641565162052015873791984587740832529
10524469038881188412376434119195104550534665861624327194019711390984553672727853
70993456298555867193697740700037004307837589974206767840169672078462806292290321
07161669867260548988445514257193985499448939594496064045132362140265986193073249
36977047760606768067017649166940303481996188145562519559256691883082551494294759
65372748456246288242345265977897377408964665539924359287862125159674832209760295
05696699927284670563747137533019248313587076125412683415860129447566011455420749
58995256354306828863463108496565068277155299625679084523570255218622235813001670
08345234432368219357931847019565107297818043541738905607274280485839959197290217
26612291298420516067579036232337699453964191475175567557695392233803056825308599
97744167578435281591346134039460490126954202883834710136373382448450666009334848
44407119312925376946573543373757247722301815340326471775319845373414786743270484
57983786618703257405938924215709695994630557521063203263493209220738320923356309
92326750440170176057202601082928804233560664308988871029738079757801305604957634
28386830571906622052911748225105366977566030295740433879834715185526028053338663
57139101046336419769097397432285994219837046979109956303389604675889865795711176
56667003915674815311594398004362539939973120306649060132531130471902889849185620
37666691644687911252491937544258458950003115616829743046411425380748972817233759
55380661719801404677935614793635266265683339509760000000000000000000000000000000
00000000000000000000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000000

edit: Zeilenumbrüche nach 80 Zeichen eingefügt.

SideWinder

3 - 1 Null
4 - 4 Nullen
5 - 28 Nullen
6 - 178 Nullen

Bei OEIS gibt es noch keine Zahlenfolge, aber ob das Zufall ist?

MfG SideWinder

die stellenzahl kann man mit stirling abschätzen, die anzahl der nullen mit der üblichen formal ausrechnen.
aber das wird langsam OT!

cirion

ich hab die vage ahnung, dass diese frage eher was für ein paper wäre... gewöhnlich ist es schwierig genug, für einen gegebenen graphen zu sagen, ob er überhaupt einen hamiltonkreis enthält (darauf läuft's ja hinaus) - wie viele verschiedene ist selbst für viele recht einfache graphen noch nicht geklärt. nur eins ist sicher: es sind weniger als (n-1)! / 2

ru,
cirion

Wir können ja im Forum gemeinsam dran forschen.

cirion

interessant ist die frage allemal... wird nur nen ziemlicher datenbankfüller, wenn wir so empirisch weitermachen

ru,
cirion

OK: 1. Kann mal ein Mod die langen Zahlen durch [...] ersetzen?
2. Wie viel Möglichkeiten gibt es jetzt für n = 3?

und 3. Kann mal einer ein Bild des Graphen für n = 3,4 zeichen?