Rational generating functions for the Certain Stanley-Stern Sums By Shalosh B. Ekhad Theorem Number, 1 --------------------------------- Let Z[n] be the integer sequence whose generating function is infinity ----- 2 \ j -t + 1 ) Z[j] t = ---------------- / 3 2 ----- -t - t - t + 1 j = 0 Let n - 1 --------' ' | | F[n](x) = | | | | | | i = 0 Z[i + 2] (Z[i + 1] + Z[i + 2]) (Z[i] + Z[i + 1] + Z[i + 2]) (1 + x + x + x ) Write: infinity ----- \ i F[n](x) = ) a(n, i) x / ----- i = 0 Let : infinity ----- \ H(n) = ) a(n, k) / ----- k = 0 Then infinity ----- \ n 1 ) H(n) t = - ------- / 4 t - 1 ----- n = 0 and in Maple notation -1/(4*t-1) For the sake of the OEIS, here are the first 30 terms, starting at n=0 1, 4, 16, 64, 256, 1024, 4096, 16384, 65536, 262144, 1048576, 4194304, 16777216, 67108864, 268435456, 1073741824, 4294967296, 17179869184, 68719476736, 274877906944, 1099511627776, 4398046511104, 17592186044416, 70368744177664, 281474976710656, 1125899906842624, 4503599627370496, 18014398509481984, 72057594037927936, 288230376151711744, 1152921504606846976 ----------------------------- This took, 0., seconds. Theorem Number, 2 --------------------------------- Let Z[n] be the integer sequence whose generating function is infinity ----- 2 \ j -t + 1 ) Z[j] t = ---------------- / 3 2 ----- -t - t - t + 1 j = 0 Let n - 1 --------' ' | | F[n](x) = | | | | | | i = 0 Z[i + 2] (Z[i + 1] + Z[i + 2]) (Z[i] + Z[i + 1] + Z[i + 2]) (1 + x + x + x ) Write: infinity ----- \ i F[n](x) = ) a(n, i) x / ----- i = 0 Let : infinity ----- \ H(n) = ) a(n, k) a(n, k + 1) / ----- k = 0 Then infinity ----- \ n 101 100 99 98 ) H(n) t = t (45872 t + 432648 t + 116154 t - 11780728 t / ----- n = 0 97 96 95 94 + 53402926 t + 96618938 t - 2111216408 t + 3517054298 t 93 92 91 90 + 21825104094 t - 60209516281 t - 242616303574 t + 557979633058 t 89 88 87 + 1839686700107 t - 4594394156811 t - 8570599922380 t 86 85 84 + 4774029975321 t + 44318049659014 t + 54755398081729 t 83 82 81 - 126601186903278 t - 37130648260472 t - 278233180879855 t 80 79 78 + 646896027884408 t + 688551426916930 t + 1189542338905068 t 77 76 75 + 515178501087664 t - 3895081317041950 t - 3069139475544046 t 74 73 72 - 10630019077264064 t - 3741718386752362 t - 19541476428914818 t 71 70 69 + 49179425624318800 t + 50258876178295866 t + 86582276720146679 t 68 67 66 - 139638256157969885 t - 200069086004440609 t - 212768653592253216 t 65 64 63 + 370914448686191822 t + 607210908126623899 t + 206832291434148327 t 62 61 - 871135322196952628 t - 1287613461525261527 t 60 59 + 310865382186458680 t + 1530376204778598955 t 58 57 + 2000293961388219119 t - 1417403740166444393 t 56 55 - 1984000592070210690 t - 2497304823672524850 t 54 53 + 2686659206778399891 t + 1952586237371337218 t 52 51 + 2598705982517486978 t - 3469185695136749456 t 50 49 - 1472284044120680422 t - 2210827526811718880 t 48 47 + 3341873335501767993 t + 839686706202845865 t 46 45 + 1496861514634835904 t - 2455980662697024707 t 44 43 - 350510030723679417 t - 795634382220477133 t 42 41 + 1386648554570338745 t + 100105140376699907 t 40 39 38 + 331100969941113194 t - 603357802894795457 t - 15812800195701286 t 37 36 35 - 107903560614365663 t + 202451315019380509 t - 596887244585692 t 34 33 32 + 27435821517615705 t - 52292442714027076 t + 1047427476816171 t 31 30 29 - 5378138974127481 t + 10357335885516345 t - 292438699566765 t 28 27 26 + 794831609604206 t - 1562910392399417 t + 47203727701038 t 25 24 23 - 85364138543752 t + 177840919779832 t - 5173228807865 t 22 21 20 + 6286815746872 t - 15010078552956 t + 429477259579 t 19 18 17 16 - 290573029955 t + 917819206645 t - 28629245815 t + 6940829223 t 15 14 13 12 - 39522483596 t + 1457680505 t + 14590053 t + 1147811681 t 11 10 9 8 7 - 48899019 t - 6205235 t - 21186811 t + 959178 t + 161417 t 6 5 4 3 2 / + 231291 t - 9109 t - 1671 t - 1334 t + 30 t + 7 t + 3) / ( / 103 102 101 100 99 6336 t + 202864 t - 492310 t - 8284200 t + 34867030 t 98 97 96 95 + 24357758 t - 1104764086 t + 2830083686 t + 13633517786 t 94 93 92 91 - 50557378626 t - 79231682626 t + 509304454066 t + 625833421644 t 90 89 88 - 2575220998349 t - 655014415812 t + 11699817192758 t 87 86 85 + 9719595347815 t - 67417236800272 t - 142216463589794 t 84 83 82 + 202613165760708 t + 289518440051422 t + 386137536552281 t 81 80 79 - 2017220495021073 t - 1160747058690321 t - 921570944722288 t 78 77 76 + 2919562211055276 t + 6102765067198774 t + 3822734498636737 t 75 74 73 + 29057098059111631 t - 9507278307590121 t + 16328051756865337 t 72 71 70 - 110854271908490049 t - 61918356504261937 t - 97273839479387929 t 69 68 67 + 284815901610683635 t + 377013352069277941 t + 341520414427806097 t 66 65 - 844478768930642295 t - 1254748349529069076 t 64 63 - 269051308259720626 t + 2156165038828354505 t 62 61 + 2635819007516570736 t - 1100781499817736112 t 60 59 - 3912931031205868779 t - 3898362076385122692 t 58 57 + 3952943065362868145 t + 5103520773410476078 t 56 55 + 4647542979302950761 t - 7305970994065446281 t 54 53 - 4919171347998746192 t - 4846579009378982938 t 52 51 + 9510999185196157340 t + 3482254395563063343 t 50 49 + 4363246733884031273 t - 9278876733997859164 t 48 47 - 1720177883468563765 t - 3218867291288111501 t 46 45 + 6888633034627728254 t + 501456431619472676 t 44 43 42 + 1879388664152077194 t - 3919382084717644283 t - 5443154638187010 t 41 40 39 - 858554433541056833 t + 1716467625837126266 t - 74778892963634679 t 38 37 36 + 306261035185749088 t - 579339449719352812 t + 41165061165454126 t 35 34 33 - 85009512077950730 t + 150445773504635679 t - 13071870057543744 t 32 31 30 + 18191289768448131 t - 29937290121970110 t + 2840481996818265 t 29 28 27 - 2954759259948743 t + 4534862564791495 t - 443711147842673 t 26 25 24 + 356289254064196 t - 517598788544119 t + 51131356947090 t 23 22 21 - 31058921441597 t + 43810353578568 t - 4429886102758 t 20 19 18 + 1917912051273 t - 2690824372277 t + 288045675352 t 17 16 15 14 - 83273474785 t + 116961484074 t - 13629680494 t + 2493487319 t 13 12 11 10 - 3458728648 t + 437244471 t - 48158378 t + 65419026 t 9 8 7 6 5 4 - 8734698 t + 547552 t - 724260 t + 97082 t - 2942 t + 4048 t 3 - 508 t - 8 t + 1) and in Maple notation t*(45872*t^101+432648*t^100+116154*t^99-11780728*t^98+53402926*t^97+96618938*t^ 96-2111216408*t^95+3517054298*t^94+21825104094*t^93-60209516281*t^92-\ 242616303574*t^91+557979633058*t^90+1839686700107*t^89-4594394156811*t^88-\ 8570599922380*t^87+4774029975321*t^86+44318049659014*t^85+54755398081729*t^84-\ 126601186903278*t^83-37130648260472*t^82-278233180879855*t^81+646896027884408*t ^80+688551426916930*t^79+1189542338905068*t^78+515178501087664*t^77-\ 3895081317041950*t^76-3069139475544046*t^75-10630019077264064*t^74-\ 3741718386752362*t^73-19541476428914818*t^72+49179425624318800*t^71+ 50258876178295866*t^70+86582276720146679*t^69-139638256157969885*t^68-\ 200069086004440609*t^67-212768653592253216*t^66+370914448686191822*t^65+ 607210908126623899*t^64+206832291434148327*t^63-871135322196952628*t^62-\ 1287613461525261527*t^61+310865382186458680*t^60+1530376204778598955*t^59+ 2000293961388219119*t^58-1417403740166444393*t^57-1984000592070210690*t^56-\ 2497304823672524850*t^55+2686659206778399891*t^54+1952586237371337218*t^53+ 2598705982517486978*t^52-3469185695136749456*t^51-1472284044120680422*t^50-\ 2210827526811718880*t^49+3341873335501767993*t^48+839686706202845865*t^47+ 1496861514634835904*t^46-2455980662697024707*t^45-350510030723679417*t^44-\ 795634382220477133*t^43+1386648554570338745*t^42+100105140376699907*t^41+ 331100969941113194*t^40-603357802894795457*t^39-15812800195701286*t^38-\ 107903560614365663*t^37+202451315019380509*t^36-596887244585692*t^35+ 27435821517615705*t^34-52292442714027076*t^33+1047427476816171*t^32-\ 5378138974127481*t^31+10357335885516345*t^30-292438699566765*t^29+ 794831609604206*t^28-1562910392399417*t^27+47203727701038*t^26-85364138543752*t ^25+177840919779832*t^24-5173228807865*t^23+6286815746872*t^22-15010078552956*t ^21+429477259579*t^20-290573029955*t^19+917819206645*t^18-28629245815*t^17+ 6940829223*t^16-39522483596*t^15+1457680505*t^14+14590053*t^13+1147811681*t^12-\ 48899019*t^11-6205235*t^10-21186811*t^9+959178*t^8+161417*t^7+231291*t^6-9109*t ^5-1671*t^4-1334*t^3+30*t^2+7*t+3)/(6336*t^103+202864*t^102-492310*t^101-\ 8284200*t^100+34867030*t^99+24357758*t^98-1104764086*t^97+2830083686*t^96+ 13633517786*t^95-50557378626*t^94-79231682626*t^93+509304454066*t^92+ 625833421644*t^91-2575220998349*t^90-655014415812*t^89+11699817192758*t^88+ 9719595347815*t^87-67417236800272*t^86-142216463589794*t^85+202613165760708*t^ 84+289518440051422*t^83+386137536552281*t^82-2017220495021073*t^81-\ 1160747058690321*t^80-921570944722288*t^79+2919562211055276*t^78+ 6102765067198774*t^77+3822734498636737*t^76+29057098059111631*t^75-\ 9507278307590121*t^74+16328051756865337*t^73-110854271908490049*t^72-\ 61918356504261937*t^71-97273839479387929*t^70+284815901610683635*t^69+ 377013352069277941*t^68+341520414427806097*t^67-844478768930642295*t^66-\ 1254748349529069076*t^65-269051308259720626*t^64+2156165038828354505*t^63+ 2635819007516570736*t^62-1100781499817736112*t^61-3912931031205868779*t^60-\ 3898362076385122692*t^59+3952943065362868145*t^58+5103520773410476078*t^57+ 4647542979302950761*t^56-7305970994065446281*t^55-4919171347998746192*t^54-\ 4846579009378982938*t^53+9510999185196157340*t^52+3482254395563063343*t^51+ 4363246733884031273*t^50-9278876733997859164*t^49-1720177883468563765*t^48-\ 3218867291288111501*t^47+6888633034627728254*t^46+501456431619472676*t^45+ 1879388664152077194*t^44-3919382084717644283*t^43-5443154638187010*t^42-\ 858554433541056833*t^41+1716467625837126266*t^40-74778892963634679*t^39+ 306261035185749088*t^38-579339449719352812*t^37+41165061165454126*t^36-\ 85009512077950730*t^35+150445773504635679*t^34-13071870057543744*t^33+ 18191289768448131*t^32-29937290121970110*t^31+2840481996818265*t^30-\ 2954759259948743*t^29+4534862564791495*t^28-443711147842673*t^27+ 356289254064196*t^26-517598788544119*t^25+51131356947090*t^24-31058921441597*t^ 23+43810353578568*t^22-4429886102758*t^21+1917912051273*t^20-2690824372277*t^19 +288045675352*t^18-83273474785*t^17+116961484074*t^16-13629680494*t^15+ 2493487319*t^14-3458728648*t^13+437244471*t^12-48158378*t^11+65419026*t^10-\ 8734698*t^9+547552*t^8-724260*t^7+97082*t^6-2942*t^5+4048*t^4-508*t^3-8*t+1) For the sake of the OEIS, here are the first 30 terms, starting at n=0 0, 3, 31, 278, 2414, 21245, 185413, 1615519, 14087271, 122769986, 1069826009, 9322756293, 81237467781, 707887924086, 6168380649380, 53749697447416, 468360696808845, 4081167732206704, 35562166836696015, 309878846990028616, 2700197777043736460, 23528767732758920650, 205023093462987604684, 1786513782536621477454, 15567180235679878542486, 135648043762700109300031, 1181999015903573748133834, 10299607951495440493452486, 89747895271658216825993108, 782037990238211875803404797, 6814459727271138775877915257 ----------------------------- This took, 4.582, seconds. Theorem Number, 3 Exceeded the limit of number of equations ----------------------------------------- This concludes this article that took, 2214.994, seconds to produce.