Permutaties van een rij mensen

[dik_lowietje]

Stel, we hebben een rij van N mensen {1,2,3,4,...,N}, en we willen deze permuteren zodat iedere persoon een nieuw iemand voor zich heeft. (d.w.z. {1,2}, {2,3}, etc. zijn niet toegestaan). Op hoeveel manieren kan dit?
Deze vraag houdt mij nu al een aantal nachten wakker.
Ik heb dit eerst proberen op te lossen met gevalsonderscheid, maar ik kan er geen logica in vinden.
Daarna heb ik geprobeerd met de inclusie-exclusiestelling te werken, d.w.z. ik bereken

Waarbij S_i de verzameling is van rijen met i van deze ontoegestane 'koppels'.
Probleem is dat ik hierbij niet echt een goede formulering kan vinden, want als meerdere 'koppels' na elkaar voorkomen in de rij, zullen deze minder plaatsen bezet houden.

Weet iemand een betere manier om dit op te lossen?

[SafeX]

Dus bij twee is (na nummering) (1,2) niet toegestaan en (2,1) wel.
Bij drie is (1,2) en (2,3) niet toegestaan en ....., ga zo eens verder.

[dik_lowietje]

Dus bij twee is (na nummering) (1,2) niet toegestaan en (2,1) wel.
Bij drie is (1,2) en (2,3) niet toegestaan en ....., ga zo eens verder.

Mja, ik dacht eerder aan



Hoe kan ik een onderscheid maken tussen bv. (1,2,3,5,4), wat 2 niet toegestane koppels heeft: (1,2) en (2,3), en (1,2,5,3,4), wat ook 2 niet toegestane koppels heeft, maar deze overlappen niet.
Als ik dit op een goede manier zou kunnen tellen, kan ik het inclusie/exclusie principe toepassen (want ik ben er redelijk van overtuigd dat dit een werkbare manier zou moeten zijn om het probleem op te lossen)

[arie]

Dit is een leuk probleem!

Een recursieve oplossing:

Voor 2 personen a en b is er 1 toegestane permutatie:
ba

Voor 3 personen a, b en c zijn er 3 toegestane permutaties:
acb
bac
cba
(eenvoudig na te gaan).

Nu gaan we aan a, b en c een vierde persoon d toevoegen:
Dit kan voor elke toegestane a,b,c permutatie op 3 plaatsen:
_a_cb_
_b_a_c
_cb_a_
(d mag immers alleen niet direct na c komen)
in totaal levert dit 3x3=9 correcte 4-permutaties.

Bovendien kan de 4e persoon precies 1 ontoegestaan koppel opheffen:
In de 3-permutaties kunnen we eerst een foutief (ab) koppel maken:
(ab)c
in feite houden we nu een 2-permutatie over.
De enige correcte 2 permutatie is hiervoor:
c(ab)
waarbij we de (ab) koppeling corrigeren door persoon d ertussen te plaatsen:
cadb
Dit geldt voor alle 2-koppels in de 3-permutatie, dus ook:
a(bc), met als juiste 2-permutatie:
(bc)a, welke gecorrigeerd wordt door d tussen de koppeling te plaatsen:
bdca.
Dit levert 2x1=2 nieuwe correcte 4-permutaties.

In totaal zijn er dus 9 + 2 = 11 toegestane 4-permutaties.

Bovenstaand schema geldt ook in het algemeen:
Noem T(n) het aantal toegestane permutaties van n personen:

[1] Als we een n-de persoon toevoegen aan (n-1) personen, kan dit op (n-1) plaatsen in elk van de T(n-1) toegestane permutaties van (n-1) personen. Persoon n mag alleen niet direct na persoon (n-1) geplaatst worden.
Dit levert dus (n-1)*T(n-1) toegestane n-permutaties

[2] Bovendien kunnen we op (n-1)-1 manieren een tweetal van die (n-1) personen ontoegestaan koppelen
(dus: (ab)cdef...., a(bc)def..., ab(cd)ef..., etc)
en die foutieve koppeling opheffen door de n-de persoon ertussen te plaatsen.
Omdat er T(n-2) correcte oplossingen zijn voor elk tweetal (los van de incorrecte koppeling), levert dit nog eens (n-2)*T(n-2) correcte n-permutaties.

Het totale aantal correcte n-permutaties is dus:
T(n) = (n-1)*T(n-1) + (n-2)*T(n-2).

Omdat ik zelf ook nieuwsgierig werd: hier een Pari/GP programma om de waarden voor dit probleem te berekenen.
(software: zie http://pari.math.u-bordeaux.fr/)

Code: Selecteer alles

{
\\beginwaarden:
Tmin1=1;
T=3;
print("T(2) = 1");
print("T(3) = 3");

\\recursie:
for(n=4,50,
  Tmin2=Tmin1;
  Tmin1=T;
  T = (n-1)*Tmin1 + (n-2)*Tmin2;
  print("T(",n,") = ",T);
  );
}

En hier de eerste 50 waarden (je kan het programma zelf aanpassen om meer waarden te vinden):

Code: Selecteer alles

T(2) = 1
T(3) = 3
T(4) = 11
T(5) = 53
T(6) = 309
T(7) = 2119
T(8) = 16687
T(9) = 148329
T(10) = 1468457
T(11) = 16019531
T(12) = 190899411
T(13) = 2467007773
T(14) = 34361893981
T(15) = 513137616783
T(16) = 8178130767479
T(17) = 138547156531409
T(18) = 2486151753313617
T(19) = 47106033220679059
T(20) = 939765362752547227
T(21) = 19690321886243846661
T(22) = 432292066866171724421
T(23) = 9923922230666898717143
T(24) = 237760636776394448431551
T(25) = 5934505493938805432851513
T(26) = 154068892631103602583645049
T(27) = 4154153845757163802996059099
T(28) = 116167945043852116348068366947
T(29) = 3364864615063302680426807870189
T(30) = 100833776298063636990123342509997
T(31) = 3122594362778744887436077703535391
T(32) = 99825438535083000620222109084897031
T(33) = 3291214458368797111357625899526302113
T(34) = 111804491159292960694648762175084674721
T(35) = 3909962776542130968292859568637246910243
T(36) = 140650049878390544553868142816256520799019
T(37) = 5200250492801034187829503226287538390623189
T(38) = 197472670029260324553630872514024155201822677
T(39) = 7696370729345530597987664774905556818122319719
T(40) = 307662419905587585654556899376849633804439730767
T(41) = 12606655254667979119503794901295302068084359699721
T(42) = 529179362237610647325837866928181370143636336919241
T(43) = 22742406079421034331584846001936724930824184898296683
T(44) = 1000148994629084123445833568494262789571472676777365491
T(45) = 44984479225094805907874825391830841913170237728830838973
T(46) = 2068308120892945967285983819646135448833805495575591835389
T(47) = 97166475126204780761009622846354618532447713494274612181679
T(48) = 4661966504492700210262607529482389301671397587027383996966807
T(49) = 228341216546581234788372613688933353551252126711545338626945649
T(50) = 11412494002998130114722863232172889010491581293043036024574743537