# [seqfan] Re: A001250, A001251, A001252, A001253 counting permutations

Max Alekseyev maxale at gmail.com
Fri May 4 03:02:54 CEST 2012

```I confirm that the terms starting with a(13) are incorrect in these sequences.
Please find my calculations for the first 100 terms of each sequence
in attached b-files.
Regards,
Max

On Wed, May 2, 2012 at 4:37 PM, Sean A. Irvine <sairvin at xtra.co.nz> wrote:
> The sequences A001250, A001251, A001252, A001253 (and possibly a few others)
> count runs in permutations. Their current values appear to be taken from
> Table 7.4.2 in "Symmetric Function and Allied Tables" by David, Kendall, and
> Barton. For example, A001251, gives the number of permutations of 1,2,...,n
> such that the longest run (either ascending or descending) is precisely 3.
>
> I would like to give these sequences more precise titles and extend them in
> the OEIS. But, I have run into a problem. My computed values for these
> sequences differ from those in the original reference for n>=13. I computed
> my values by brute force so I am inclined to believe them, but it is always
> possible I have overlooked something. Given the book was published in 1966,
> it seems unlikely that the entire original table (which goes up to n=14) was
> computed by brute force, but I could find no obvious generating function or
> recurrence in the book or other explanation as to how they produced their
> table. It seems likely that such a recurrence should exist, but it eludes
> me.
>
> Here are my brute force numbers for permutations of length n. Each row sums
> to n! as expected. For the case l=2 (A001250) my numbers agree with the
> formula and entries in the OEIS, but for A001251, A001252, A001253 they do
> not.
>
> n l=0, l=1, l=2, l=3, etc...
> 1 [0, 1]
> 2 [0, 0, 2]
> 3 [0, 0, 4, 2]
> 4 [0, 0, 10, 12, 2]
> 5 [0, 0, 32, 70, 16, 2]
> 6 [0, 0, 122, 442, 134, 20, 2]
> 7 [0, 0, 544, 3108, 1164, 198, 24, 2]
> 8 [0, 0, 2770, 24216, 10982, 2048, 274, 28, 2]
> 9 [0, 0, 15872, 208586, 112354, 22468, 3204, 362, 32, 2]
> 10 [0, 0, 101042, 1972904, 1245676, 264538, 39420, 4720, 462, 36, 2]
> 11 [0, 0, 707584, 20373338, 14909340, 3340962, 514296, 64020, 6644, 574, 40,
> 2]
> 12 [0, 0, 5405530, 228346522, 191916532, 45173518, 7137818, 913440, 98472,
> 9024, 698, 44, 2]
> 13 [0, 0, 44736512, 2763212980, 2646100822, 652209564, 105318770, 13760472,
> 1523808, 145080, 11908, 834, 48, 2]
> 14 [0, 0, 398721962, 35926266244, 38932850396, 10024669626, 1649355338,
> 219040274, 24744720, 2419872, 206388, 15344, 982, 52, 2]
> 15 [0, 0, 3807514624, 499676669254, 609137502242, 163546399460, 27356466626,
> 3681354658, 422335056, 42129360, 3690960, 285180, 19380, 1142, 56, 2]
>
> I would appreciate either an independent verification of my numbers or some
> insight into a way of computing these numbers without recourse to brute
> force.
>
> Sean.
>
> _______________________________________________
>
> Seqfan Mailing list - http://list.seqfan.eu/
-------------- next part --------------
1 0
2 0
3 2
4 12
5 70
6 442
7 3108
8 24216
9 208586
10 1972904
11 20373338
12 228346522
13 2763212980
14 35926266244
15 499676669254
16 7405014187564
17 116511984902094
18 1940073930857802
19 34087525861589564
20 630296344519286304
21 12235215845125112122
22 248789737587365945992
23 5288401559545098158274
24 117294152832167774140794
25 2709823034116344223826156
26 65107005330724501180563644
27 1624416035986375508414316374
28 42029653338368894057003757724
29 1126291171592996900709809238550
30 31222401549267466199541956919802
31 894377044579361446889859136622164
32 26446126991309707231741487188872328
33 806429965396136427038647355336004426
34 25335859847597440415336234517564647112
35 819395128469697575791860793508068391498
36 27257454510400423669252224456130632689946
37 931914894867860274305042554213649360878372
38 32722686815447436441557280565682029692927124
39 1179241029614753093446017335092721579540394438
40 43586453254803828850732822442805810808210874796
41 1651293624261998979456748033792086830984747135294
42 64085899209461943394155545413459519329073058338154
43 2546360016162807406049203660950075073112113099099628
44 103528837473973003797877644003229141333856353203134416
45 4304896321090420556124594454582201095360019490915527930
46 182982419963049253760386631861570414013899477366868541672
47 7946869095947563093331037723980940175149886578379467699058
48 352473221522299080207429933773517631824858049947665873884666
49 15959197052831909109421583685268984443797465151517175212657116
50 737343522237839268945563364908702780356585850485216636760858124
51 34747924727503354073213543762320591664696080173202744997757352598
52 1669633084009057706025905474354950724490404933284690302587612229852
53 81768444647845388364912608144473586391549174081917382831844264310470
54 4080076650086147518820281237168768852466154911177965513571088351607834
55 207357542194269541455737389477499976867052555730027902685931622095190404
56 10729925051146901670160602933435721807635449069265444913965630900922702584
57 565145623620624600781017347085667680572262282193529342064482108701131194954
58 30288459629131912731515095201666786108911920374153543438746159389146314951272
59 1651269743800030060017749922810580361608444520253589933827534614567807270682554
60 91549947247569606697805301871929107243999737208562449581197333139817029487232154
61 5160321475783779691977638456348843878309525829657295091565836661346168977815367572
62 295635969010263210702355830284156521214485604668073721257655080680860058491141830692
63 17210228879339327025428952333599699541321455117531411142178183761421710717939064627654
64 1017783590578063453027298668201074881501013541415390676215873676803653014332118439303084
65 61130454645308876255194068559416980644451614701605905226686712361357863563772275655145006
66 3728124317622904322058509740033695949350757182445818438105931274281649049402257839029275274
67 230809676926884175755189763539382105814830477873776316293165336717171815325548937774520656284
68 14502796408032610710544975238064515644997462337257241020728287011188193005456575966795860100864
69 924676170251445719792289598669085937926273213476790111838161002773889845208680375838579723836730
70 59810375659385679666912747034411732778037585098877050866280322785683194467605955414291364223212232
71 3923952155415339221268510157224912426259887495559718573254126574349574672653786721141422388487534754
72 261062819650624361156554632342349633835088451551251784138686234180177274600984214739410710926484818298
73 17609892670532142617169570913500060917865127193368175032713862177791797213512586122044910618442396114636
74 1204140748439363584426242662373688590997336990123527632576071462843206358291720102489439251565900091434972
75 83450192187381856012566191946245573742629956960449378251157942779645350136941757757736631566049235659565398
76 5860433712811663190175000119423276546369791212438348444409615189237891637498284309147781280472929900193419676
77 416974318666425620927776100307498254727276996680358751495606688173569140941035835111552616194401510698767676662
78 30053339327647971692146008542945097723075536488494216748694811605428682075250150886181594653911633586076950461754
79 2193858691188216451098055337182918118490847246269546759022955663427637194253800630581155916098620606200160445101748
80 162176327774564904849756794541031038223460037648764417759125502493873220237914629327450975697863498983993944921445096
81 12138396111624559690109402018752992562018086920896853211802026231782082934995958831749917492429733755641255148804955594
82 919737687400814124771510440091850801808313139935881199928513651764366777610806995373049005221169615676413107755084468104
83 70539260028367228683963515222991364634004070439987744714232846819388073713426690104318569271821673127050412388138975901098
84 5475187673366447625238977225948417178040428244072287562785702427328151934621950799205457309382373329450275830669938495545626
85 430037927672324028942322797768362940073175733877107238641096373803474674092123820166615162024162516459269439460847716257931780
86 34173860015840255147800793633972537301193625783297341473774982988551690670981117558440496975798552300888972893215478301187978292
87 2747274868132246960837268687878472089827702164799002413614849764745649079916374325238659973622908655169555388271039769844927900998
88 223395083019523876227092322082162296565904055819652517023004907033223187367110202954790865707882714408024415371521626041511583327276
89 18371830973969543965990494246837325979329058974299564852532827368018144474311044337726998771521942317653246201703652449180099193430686
90 1527860753086742291794856352834011917427745585234036874772787409473145389473054990566125441833830289335437486276108741685906015239450794
91 128473629036790025942609324028988847526393956756218609351746809646229284618722257040545520525855095451686445785365208658173618593098060108
92 10921710078800587988965175362846946549394935415706559182137466529841241542948746200333816572773045685667786456701102685055113052373226509232
93 938560811746100746021569479890314865428828707211016330497419801936540312527033734383072374651766955222476531089355457183633435635873276156410
94 81522801392271622942465809088068130394479957132881991449887634805596147502422963854892264095697448626848372409603358128231142286577647901226024
95 7156349211412277671125769528164156639854029253174977374781180582575186804734897357165290394562507966056724626879468539692228697506756366307894354
96 634821434967010860907451237279235457128454730654782356329263993001136390580698054223088353605403201090006653815568257099057503957404374160503080954
97 56899983601476726580299349925082025168079708401426840191528109675240417161520100148444517249066709795061627982419532657178573104742927398836302431164
98 5152607264214440945394535984360056441835002121091472960766238623351631644298737542771483164889549035230381840013615438332489541535687937992713057832492
99 471358193358018151596128482879153526525071585565273479604206396021987361411373142027772580690867177897507086143343415033992077051519518823622241827251094
100 43555187243991533304626192619312146966982157162829228799012213480006181628723781761688569084800708716000659470873352830929243965124924780113557084650243804
-------------- next part --------------
1 0
2 0
3 0
4 2
5 16
6 134
7 1164
8 10982
9 112354
10 1245676
11 14909340
12 191916532
13 2646100822
14 38932850396
15 609137502242
16 10101955358506
17 177053463254274
18 3270694371428814
19 63524155236581118
20 1294248082658393546
21 27604013493657933856
22 615135860462018980316
23 14297040348356531600802
24 346008803353280124666176
25 8706332798002339827319444
26 227445888154568562388849576
27 6160912927580553985615050408
28 172823773114845585082623511810
29 5014814692414807953089571365356
30 150359895665968145544177041782694
31 4653674116787199925120079986363988
32 148536699790033900461356466353659270
33 4884905557891236678795009551152299414
34 165384833774195539168005959089044881448
35 5759765678905166220082337440457787267240
36 206183793223702366982855023889404130187128
37 7581109613401766484291824249335674775080790
38 286116743774508636183534922265432792848727816
39 11076544827553244396158690256908495174678658358
40 439589908651041069919095382843083875449604625494
41 17873841814269137556132941611706523602422409710834
42 744168097976320913409368546691534395603693190771442
43 31708392176228467710737941416820319401195059433159434
44 1381989504799524631358891785424152123893119830526573974
45 61581392158748778976738003246141602163204792441274111848
46 2804170017651451405810582723053750718382218860280462054736
47 130428806346750770195579433197821197284811834142850348261198
48 6193971440389432951957144809732302227896011345758730556855004
49 300200197229068875999602482380240814564392528590514478926905364
50 14843128286036609049771526710557695876139226187348732797374405916
51 748420718193421560311003209335477422620148023997571398873897539764
52 38469052234241313856906543947755898030929527014048562290605558903102
53 2014966449543474559394397854973058145651664281562668818975131734339956
54 107514166781351406427483799560620408027423360064669761094580854700912282
55 5841996340663146571637504639394658473387815569077068192754930802615577328
56 323158626145684586931146206196133965163710995320329778464886510624728180114
57 18192610831328317393618173651833595606730281415086671443964526216049367657686
58 1042004355088708086252717726251249059793317569337849623807543070331542277162668
59 60703534044514255434420911654050825894308290145473725174883388971974071969694644
60 3595896118363769255329339505138076038191285791082558397186375283062919187755854740
61 216536783184767682680746648502594632810390546063852928528349455715396846041376266350
62 13251772338900013491709257582437529961165335733017191391378534346452635658599609512748
63 823993674436760507304666727895893568706662408486138516909680745397381361192881322687442
64 52044478777984897816649705717173357921922888147493232733039411168302841026237373409421426
65 3338280180536394453542578860066043772773158222220395871721726628296930160813470352035816082
66 217404120056837999526336293214530986000970248812372554460740561341687706225066080759743145302
67 14371830569413343159463080690540504622304217843995350773486957986487070406439438661185702444358
68 964186431352964079931863223488626402300100344791694535093411946694000262467955002100101725484066
69 65633039539758946678463226890464001151907023800651485445319806891130332500217372428747228632312448
70 4532179880456004987079587829828115796346999397643000176399606908179292520652236606464127950795583876
71 317415327681755200329109194556185783233984112959938903014255640938160607126320819961048901467760303882
72 22542401058030694564335345027606117219324372227854482734278229943536473105409473358912022880660201019672
73 1623086380264754232217170886501920946386068000710620671171140360133124555700668181425497724955851254219524
74 118460108573967768069135105771229902024882809638224072901536668137687177579194675740341392436547027933419888
75 8762208813770518119555783007625488204469535146149611294302995507661856815871610141716051630507463087012795344
76 656734781443896671927955463085321362027140664749976570752385861647960177649097470482571898139447830948108411098
77 49868613358428665475302130014525033072936338698773709115624359476816760928643631927146557271852941681554490149484
78 3835775683003320964007323566231032291250791791274758117216307129534221345115878989673380361450826000373681183147182
79 298811510864611243842566517514553445979145578663333027949186266204844179830227087873074064487635234742984694960080764
80 23571703518030354894246869471243961323672690483883756310562422285346841224150191262558659266264137168848614390180731902
81 1882639316769228312194744062856434776910014223169740925740526339760878899282928798187346173537822549834088540845095610246
82 152216026316898382401591067996930851099567545340831168601853792329419786935886380297655330557722574916346246950913782089616
83 12456811321457065379656201921783852607579134427361366339217048038689237850436885240279809028106610913733111371562750476434960
84 1031678287769002058849261378006468320536875783178449588838013570704721712403439193741463443910099470872119367775414448677279888
85 86459294825402599893314657721082807870479801806120651510247861345586808116481545347035946172254298461996094875141457922649389302
86 7330769697215133881671221116049146396474754650010791994215438888293385168566444623396241181014627630712671868610563276961568332848
87 628781560370239470213779292806581827581830188392565162869034401034673044977666127986756179389433822421488631725030779880757958658398
88 54551350193154348453912542971247017327148708663230134483518830475097186991001487030738005896670727974625187308524233415810203212649454
89 4786423388086796250778377406081752775889596290107098683946471952516295339747760403672309043876568609848832008803614968789211895945286562
90 424680437968689414950587630784853741619821182848131549642370035119584050596696450851230336757019079937819476636403719373328418174788188762
91 38098313965851321349615714960393660661985350528449240670505080533262974822312211911439631750111096870939624884299240822068682779089989807314
92 3455330346348357776794916231296991739307853075355059885893632097633223629426052173524465359320576325279169577617671999466578620818486898308238
93 316783666402365089260839768162783954362242094023475286770778193792135515989825549635886616096988525082557061736622977781941986641757466155845768
94 29354556302442246261458893037851103972543652900268510123198202752087123213385155576599864106061494040018887808436821924719367572554985509109991384
95 2749026818435872590435020245049048288884108423790715548678297325981808453521476356990358253716940277891628134174364627707570069296368373636711031862
96 260150905665535818771355291851650039602799699568052773088689512878617825059587422452316881755204234838724617953662985242499038425371881909488334660916
97 24875269033802519246373693834295061678492795906100755055235813903773126089700348826976411723930282976695266576339844607034835907425726431512520342549476
98 2403036831910300784049483451826160798174597338963253993237219691682711261724769983994857843596846311746574246333631454195094651015207029337822277460865188
99 234508345369960790524631964610019067835471372247925388067717375465953902350635512531808354940479487265315284020843970802791512502910029126699818385270112828
100 23116247820609072557356216229533780510139127274816196446356338123986012938700343969552231452309235731441864093969506487106947630178285551898325708116677567190
-------------- next part --------------
1 0
2 0
3 0
4 0
5 2
6 20
7 198
8 2048
9 22468
10 264538
11 3340962
12 45173518
13 652209564
14 10024669626
15 163546399460
16 2823941647390
17 51468705947590
18 987671243816650
19 19909066390361346
20 420650676776338140
21 9297308938203169622
22 214562999510569012168
23 5161426727339223536666
24 129214351064504504526264
25 3361512948990282233431684
26 90749187827293213080657368
27 2539073897721489820772140984
28 73537612792458688834732042452
29 2202192493823117211799765449914
30 68116557012664956321761350060566
31 2174049325553496913056022367357008
32 71531651506044472775242736794422810
33 2424126450791838458348736050660344970
34 84543015895111728579260547808233910082
35 3031953542029748653442562109217371337130
36 111728681526144735086559398704659917277442
37 4227619020928829603389796310684060987805524
38 164143336044123218777522077524842723116834210
39 6535344564685819232246682947146390137262834804
40 266665284369229856053234786592291146359737159548
41 11144602849086693597958429393001721058317216456064
42 476784131827222523944779945462382163937276623597124
43 20869298286501054075306026323208220204841702440661508
44 934119953234962862016211321491648600002115751726707600
45 42736166446483525885527791533374300500731193086516431998
46 1997490977843468293363540581483258842902015409912728370380
47 95340410076659181640120361821381136525897766676971147156446
48 4645008746021578753719366574097741790162978203117390376197692
49 230905971436065940118140687483266584710856125993875906920594372
50 11707161780713939338763858252660329508526097994689682568363366990
51 605161332526729392600951332467261091403984676583808071584217236526
52 31881244512011474054785843578976590324458011736690769613815484960998
53 1711162285645309778617882630470941841195903494238370945610829475794784
54 93538799593740739738684525050238713291464101568662020382569254469585674
55 5205891342008568852898046732081056324511489657557795088744185439097471660
56 294892779232048419810280282156167994683491852047673858533642199154604971106
57 16996779311153299749952521286513956188251245761261300408521989818237000452574
58 996494224557321716579435080597728856659813119484858170361615662642133131952750
59 59410749919790050476910562209153523082095068487783903317266136460091915032043102
60 3600956426825338174320194290302183475897060878027259721749242015553779934396720352
61 221828638829773368377321117717326238726411542390811916233379146238238072585240599478
62 13885204367814795761867073871548993344052964153252253086273285226727929863381007423844
63 882903714447595109345625176971675865127598181681272779808045175218133114175762666300694
64 57015855245391546038776610073745620277617753430090626470050595510842451294312441930026280
65 3738498260574717714422897513538082278202584679282360448562659876507371197083430934614007816
66 248839324286993532778727365685828643185882247597353152412187795151396482988149985023229370212
67 16809898552162268691840917416864738977925167593299518750518327423135598947487941601585995027100
68 1152237910333980348189581579120280839191150015350477982426275922288961100608406613419406299107996
69 80123445917459359241157367398656385381787295607086502220237000577900265192416563770872074825851550
70 5651053555098867938204962892769114653020141511444506995536999346941120188818584474262348373684013946
71 404171765456862421430340133110528891189457689695651878256504425325302322212520668215445418735956021628
72 29307988168658088133269418522675786718958966152994191901631590857204738295750237363150363122020625215330
73 2154311627500497510300738197101471066026477550944422702684830035893186984389231311761738186057342433684374
74 160492476813645133121307896783866030862624825741907091726497794266550350210767938277524327191191801219627830
75 12115677337282229365373877942238778725958427318900766573901780818924023422747201261542250640565475417979240102
76 926643764464095902021186103747021642830972937475844069271331337364986770219356915637226442995970462963204483390
77 71792181175710950157289426585673489033360469045898205605317347315199696288690118536873662612641088705338766054604
78 5633388564120388099051679689851212415325289112354731872227689350552930398556288357328025464816330396463712568875210
79 447632128619036661615411232771114596201564871278564702427831444409291529710655683711645263948511298109622931604251316
80 36013410379295933760804123936605263788493206039191493575454299114311460545698338934825497940986680466605551572555074024
81 2933140246972485237574676820552653244718156039799447578848657501615086338885287018245352576888079687039570159327883518112
82 241803564628612583822557052278683296167260396299872115751696967939686073070936706746210825404529420111443939461866823774380
83 20173957527799693336611235541666487957675622830208447188246055263990726172501587155642100884265141816389697576379534855211988
84 1703165141598225310758247246058577613864480299245139241617407913308176107136915205451116489910130883187475461360192796330518480
85 145478836592275134596822890116295430176197930234078127725404410781597930595511557135085617845861250381692891300649796269779105306
86 12570767816176515767194652743604916766689808690556780274287366123918427257181562891377255436678263877648589690305307384052982723896
87 1098716310897105860086858592240236465756259766783602998254875023891280973959595061000668270123451400741932991034919838297042118710314
88 97121472953124968212139943982808176009961530956458034054851217013688631836505991009319812894662674837878612007513697295851635870043688
89 8681529665349985934991380626682282745605578383493337561228446336781396799758932401703929597082614127034657005638607280840642414972880148
90 784648477777212675069288844655048175267603013980905199137610659161806933304588815161380170350954596192760732094313479435640336406171663722
91 71696780879225858541084366402689105511559714472634701777853388667839749541273900077687331867435386162396787444181088721721404294798688590602
92 6622449977394832794419847603842677901509460205883299600163747049204123217582327166101624860006795142973792094403135157602601121072393045156738
93 618275714358669894506470775023476809607961403364416555994626889874230650435403863102033304407382211915543989951464938109732075673066971504453944
94 58336608534526503260777965163324307220227066067114045026942501225288471493948154461889436439246521186113519246540871101361961901772084488448789914
95 5562213990863864918244445598020426496038185471737679738998766062247136520479233361098278912772492573241313244780982229855462890965525874764436830932
96 535864225030776230842878867132868583659920643610443561283325291624684922191270323730302622333786820926062752231773707354839774347862533320933767660070
97 52157453352279536325282965644968086956733036341213852087000027249254327009529814515843576874986522601583492748754577107753010137309071021650307382289910
98 5128465703080771571165945537346646355111215692978877264719598844035717642617293752578071636856327065786941566631886733865148376620518180753603763777121262
99 509358804687584958287943394936048975275585204577287340800466298083244100984619992480487040168168214956200905683192380120441352135628503006663621130274244310
100 51095442332194273900723557765202090466612429557513974123915014046899194090873692349758114103059579054767624496957720266881864799344881256761551194206954963060
```