Permutaties

Op hoeveel manieren kunnen 5 koppels op 1 rij staan voor de foto als de partners van de koppels niet naast elkaar mogen staan?

De uitkomst in het boek is 10!-10·1·8!
maar ik zie niet wat die 10·1·8! wil zeggen.

Is dat niet 1 paar dat naast elkaar staat dat ervan wordt afgetrokken? Volgens mij is die uitkomst niet juist maar ik kom er niet uit...

• Permutaties

Jo
3de graad ASO - vrijdag 7 november 2014

Antwoord

Dag Jo,
Ik denk dat je gelijk hebt dat het niet klopt. Het antwoord moet zijn: 39480, eventueel nog te vermenigvuldigen me 2⁵, als je van alle paren ook man en vrouw mag verwisselen.
Zie: A114938 OEIS.org

Een formule: De som van (n boven i) ·(-1)^n-i·(n+i)! /2^i voor i=0 t/m n-2.
Voor n=5 wordt dat:-120+1800-12600+50400=39480.

Een andere recursieve formule:
a(n)=n·(2n-1)·a(n-1)+(n-1)·n·a(n-2).
Als a(1)=0, a(2)=2, dan volgt
a(3)=30+0=30
a(4)=28·30+12·2=864
a(5)=45·864+20·30=39480

De preciese uitleg over deze formules moet ik je schuldig blijven. Zie voor meer informatie:
http://www-math.mit.edu/~rstan/ec/ec1.pdf, blz. 228 voorbeeld 2.2.3.

Met dank aan D.v.L: De bovenste formule , waarbij je i echter van 0 naar n laat lopen (maakt niet uit, want die laatste twee termen van de som formule vallen tegen elkaar weg) kan je schrijven als:
10!-10·9!+40·8!-80·7!+80·6!-32·5!
Uitleg:10! is alle mogelijk volgorden.

Dan verminder je dat met minstens 1 paartje naatst elkaar: Dat geeft b.v. het rijtje 11,2,3,4,5,2,3,4,5. Dat moet je zien als 9 gegevens., Dus 9! volgorden. Maar dat paartje 11 mag je verwisselen, dus ·2: EN er zijn 5 keuzemogelijkheden voor dat paartje dat naast elkaar staat. Totaal: -5·2·9!.

Maar nu heb je teveel afgetrokken: Er kunnen ook minstens 2 paartjes naastelkaar staan: 11,22,3,4,5,3,4,5: geeft 8! volgorden met keuze uit 2 van de 5 (5 boven 2)=10, waarbij die twee paartjes man en vrouw mogen verwisselen. Dat geeft nog 4 mogelijkheden: Totaal: +10·4·8!

Zo ga je door: Weer teveel bijgeteld, dus minstens 3 paartjes naastelkaar aftrekken: -(5 boven 3)·2³·7!=-80·7!. enz.

Een heel verhaal!
Succes
Lieke.

ldr
zaterdag 8 november 2014

©2001-2024 WisFaq