Inwersje
Na ile sposobów można pozmieniać układ n umiejscowionych rozpoznawalnych obiektów, tak aby żaden z nich nie był umieszczony na swoim poprzednim miejscu? Czyli ile jest takich permutacji, które nie zawierają żadnego cyklu jednoelementowego?
Wzór:
przy czym
D1 = 0
D2 = 1
Zadanie
Na ile sposobów można przesadzić 4 osoby na 4 krzesłach, tak aby żadna z nich nie pozostała na swoim miejscu.
Rozwiązanie:
Sprawdzenie:
Ustawienie wstępne: 1234
Możliwe ustawienia:
2143
2341
2423
3142
3421
3412
4123
4312
4321
Sprawdzenie
n= 4 inversion(4) = 9
A oto pierwsze 55 liczb Dn
1: 0 2: 1 3: 2 4: 9 5: 44 6: 265 7: 1854 8: 14833 9: 133496 10: 1334961 11: 14684570 12: 176214841 13: 2290792932 14: 32071101049 15: 481066515734 16: 7697064251745 17: 130850092279664 18: 2355301661033953 19: 44750731559645106 20: 895014631192902121 21: 18795307255050944540 22: 413496759611120779881 23: 9510425471055777937262 24: 228250211305338670494289 25: 5706255282633466762357224 26: 148362637348470135821287825 27: 4005791208408693667174771274 28: 112162153835443422680893595673 29: 3252702461227859257745914274516 30: 97581073836835777732377428235481 31: 3025013288941909109703700275299910 32: 96800425246141091510518408809597121 33: 3194414033122656019847107490716704992 34: 108610077126170304674801654684367969729 35: 3801352699415960663618057913952878940514 36: 136848697178974583890250084902303641858505 37: 5063401795622059603939253141385234748764684 38: 192409268233638264949691619372638920453057993 39: 7503961461111892333037973155532917897669261726 40: 300158458444475693321518926221316715906770469041 41: 12306496796223503426182275975073985352177589230680 42: 516872865441387143899655590953107384791458747688561 43: 22225533213979647187685190410983617546032726150608122 44: 977923461415104476258148378083279172025439950626757369 45: 44006555763679701431616677013747562741144797778204081604 46: 2024301565129266265854367142632387886092660697797387753785 47: 95142173561075514495155255703722230646355052796477224427894 48: 4566824330931624695767452273778667071025042534230906772538913 49: 223774392215649610092605161415154686480227084177314431854406736 50: 11188719610782480504630258070757734324011354208865721592720336801 51: 570624700149906505736143161608644450524579064652151801228737176850 52: 29672484407795138298279444403649511427278111361911893663894333196201 53: 1572641673613142329808810553393424105645739902181330364186399659398652 54: 84922650375109685809675769883244901704869954717791839666065581607527209 55: 4670745770631032719532167343578469593767847509478551181633606988413996494
Kody
Kody do obliczeń w języku JavaScript możesz znaleźć w książce Matematyka dla programistów JavaScript.
Kody do obliczeń w języku Java możesz znaleźć w książce Matematyka dla programistów Java.