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:

inwersje

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:

inwersje

Sprawdzenie:

Ustawienie wstępne: 1234

Możliwe ustawienia:

2143
2341
2423
3142
3421
3412
4123
4312
4321

Sprawdzeni (plik: Inversion1Main.java)

n= 4
inversion(4) = 9
            

A oto pierwsze 100 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
56: 261561763155337832293801371240394297250999460530798866171481991351183803665
57: 14909020499854256440746678160702474943306969250255535371774473507017476808904
58: 864723188991546873563307333320743546711804216514821051562919463407013654916433
59: 51018668150501265540235132665923869255996448774374442042212248341013805640069546
60: 3061120089030075932414107959955432155359786926462466522532734900460828338404172761
61: 186728325430834631877260585557281361476947002514210457874496828928110528642654538420
62: 11577156176711747176390156304551444411570714155881048388218803393542852775844581382041
63: 729360839132840072112579847186740997928954991820506048457784613793199724878208627068582
64: 46679093704501764615205110219951423867453119476512387101298215282764782392205352132389249
65: 3034141090792614699988332164296842551384452765973305161584383993379710855493347888605301184
66: 200253311992312570199229922843591608391373882554238140664569343563060916462560960647949878145
67: 13416971903484942203348404830520637762222050131133955424526146018725081402991584363412641835714
68: 912354089436976069827691528475403367831099408917108968867777929273305535403427736712059644828553
69: 62952432171151348818110715464802832380345859215280518851876677119858081942836513833132115493170156
70: 4406670251980594417267750082536198266624210145069636319631367398390065735998555968319248084521910921
71: 312873587890622203626010255860070076930318920299944178693827085285694667255897473750666614001055675390
72: 22526898328124798661072738421925045538982962261595980865955550140570016042424618110047996208076008628081
73: 1644463577953110302258309904800528324345756245096506603214755160261611171096997122033503723189548629849912
74: 121690304768530162367114932955239096001585962137141488637891881859359226661177787030479275516026598608893489
75: 9126772857639762177533619971642932200118947160285611647841891139451941999588334027285945663701994895667011674
76: 693634737180621925492555117844862847209039984181706485235983726598347591968713386073731870441351612070692887225
77: 53409874762907888262926744074054439235096078781991399363170746948072764581590930727677354023984074129443352316324
78: 4165970231506815284508286037776246260337494144995329150327318261949675637364092596758833613870757782096581480673273
79: 329111648289038407476154596984323454566662037454631002875858142694024375351763315143947855495789864785629936973188566
80: 26328931863123072598092367758745876365332962996370480230068651415521950028141065211515828439663189182850394957855085281
81: 2132643480912968880445481788458415985591970002706008898635560764657277952279426282132782103612718323810881991586261907760
82: 174876765434863448196529506653590110818541540221892729688115982701896792086912955134888132496242902552492323310073476436321
83: 14514771531093666200311949052247979197938947838417096564113626564257433743213775276195714997188160911856862834736098544214642
84: 1219240808611867960826203720388830252626871618427036111385544631397624434429957123200440059763805516595976478117832277714029929
85: 103635468732008776670227316233050571473284087566298069467771293668798076926546355472037405079923468910658000640015743605692543964
86: 8912650310952754793639549196042349146702431530701633974228331255516634615682986570595216836873418326316588055041353950089558780905
87: 775400577052889667046640780055684375763111543171042155757864819229947211564419831641783864807987394389543160788597793657791613938734
88: 68235250780654290700104388644900225067153815799051709706692104092235354617668945184476980103102890706279798149396605841885662026608593
89: 6072937319478231872309290589396120030976689606115602163895597264208946560972536121418451229176157272858902035296297919927823920368164776
90: 546564358753040868507836153045650802787902064550404194750603753778805190487528250927660610625854154557301183176666812793504152833134829841
91: 49737356646526719034213089927154223053699087874086781722304941593871272334365070834417115566952728064714407669076679964208877907815269515530
92: 4575836811480458151147604273298188520940316084415983918452054626636157054761586516766374632159650981953725505555054556707216767519004795428761
93: 425552823467682608056727197416731532447449395850686504416041080277162606092827546059272840790847541321696472016620073773771159379267445974874772
94: 40001965405962165157332356557172764050060243209964531415107861546053284972725789329571647034339668884239468369562286934734488981651139921638228569
95: 3800186713566405689946573872931412584755723104946630484435246846875062072408949986309306468262268544002749495108417258799776453256858292555631714054
96: 364817924502374946234871091801415608136549418074876526505783697300005958951259198685693420953177780224263951530408056844778539512658396085340644549185
97: 35387338676730369784782495904737313989245293553263023071061018638100578018272142272512261832458244681753603298449581513943518332727864420278042521270944
98: 3467959190319576238908684598664256770946038768219776260963979826533856645790669942706201659580907978811853123248058988366464796607330713187248167084552513
99: 343327959841638047651959775267761420323657838053757849835434002826851807933276324327913964298509889902373459201557839848280014864125740605537568541370698786
100: 34332795984163804765195977526776142032365783805375784983543400282685180793327632432791396429850988990237345920155783984828001486412574060553756854137069878601