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
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