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 ----- \ j 1 ) Z[j] t = ----------- / 2 ----- -t - t + 1 j = 0 Let n - 1 --------' ' | | Z[i + 1] (Z[i] + Z[i + 1]) F[n](x) = | | (1 + x + x ) | | | | i = 0 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 = - ------- / 3 t - 1 ----- n = 0 and in Maple notation -1/(3*t-1) For the sake of the OEIS, here are the first 30 terms, starting at n=0 1, 3, 9, 27, 81, 243, 729, 2187, 6561, 19683, 59049, 177147, 531441, 1594323, 4782969, 14348907, 43046721, 129140163, 387420489, 1162261467, 3486784401, 10460353203, 31381059609, 94143178827, 282429536481, 847288609443, 2541865828329, 7625597484987, 22876792454961, 68630377364883, 205891132094649 ----------------------------- This took, 0.099, seconds. Theorem Number, 2 --------------------------------- Let Z[n] be the integer sequence whose generating function is infinity ----- \ j 1 ) Z[j] t = ----------- / 2 ----- -t - t + 1 j = 0 Let n - 1 --------' ' | | Z[i + 1] (Z[i] + Z[i + 1]) F[n](x) = | | (1 + x + x ) | | | | i = 0 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 ) H(n) t = / ----- n = 0 6 5 4 3 2 (1 + t) (5 t - 13 t + 5 t + 20 t - 12 t - 3 t + 2) t - ------------------------------------------------------------ 8 7 6 5 4 3 2 18 t - 34 t - 50 t + 84 t + 32 t - 47 t - t + 7 t - 1 and in Maple notation -(1+t)*(5*t^6-13*t^5+5*t^4+20*t^3-12*t^2-3*t+2)*t/(18*t^8-34*t^7-50*t^6+84*t^5+ 32*t^4-47*t^3-t^2+7*t-1) For the sake of the OEIS, here are the first 30 terms, starting at n=0 0, 2, 13, 74, 419, 2337, 13038, 72588, 404150, 2249550, 12521356, 69693136, 387908122, 2159063560, 12017164190, 66886466276, 372284117950, 2072100067608, 11533123445138, 64192331639800, 357288765773126, 1988637251169672, 11068576724472002, 61606706103664880, 342897405098258334, 1908536226918423704, 10622741599397417730, 59125227750793029552, 329085718961860538974, 1831661619656901130568, 10194864424709642917970 ----------------------------- This took, 0.319, seconds. Theorem Number, 3 --------------------------------- Let Z[n] be the integer sequence whose generating function is infinity ----- \ j 1 ) Z[j] t = ----------- / 2 ----- -t - t + 1 j = 0 Let n - 1 --------' ' | | Z[i + 1] (Z[i] + Z[i + 1]) F[n](x) = | | (1 + x + x ) | | | | i = 0 Write: infinity ----- \ i F[n](x) = ) a(n, i) x / ----- i = 0 Let : infinity ----- \ H(n) = ) a(n, k) a(n, k + 1) a(n, k + 2) / ----- k = 0 Then infinity ----- \ n 33 32 31 30 29 28 ) H(n) t = (68 t - 90 t + 86 t + 1460 t - 1732 t + 8380 t / ----- n = 0 27 26 25 24 23 - 6395 t - 144779 t + 267472 t + 236434 t - 478528 t 22 21 20 19 18 - 733772 t + 559915 t + 2271915 t - 1679335 t - 2772890 t 17 16 15 14 13 + 2504166 t + 1900258 t - 2116061 t - 847133 t + 1137852 t 12 11 10 9 8 7 + 246892 t - 406159 t - 44247 t + 95846 t + 6862 t - 14571 t 6 5 4 3 2 / 35 - 1964 t + 1457 t + 424 t - 101 t - 39 t + 4 t + 1) t / (48 t / 34 33 32 31 30 29 - 38 t - 84 t - 534 t - 8082 t + 31262 t + 47442 t 28 27 26 25 24 - 256850 t + 189166 t + 222332 t + 349584 t - 1169200 t 23 22 21 20 19 - 2182331 t + 5725263 t + 2364221 t - 11442244 t - 178343 t 18 17 16 15 14 + 14968569 t - 3503371 t - 12105383 t + 4281821 t + 6391186 t 13 12 11 10 9 - 2591348 t - 2421504 t + 1036857 t + 679065 t - 300086 t 8 7 6 5 4 3 2 - 130951 t + 60151 t + 15148 t - 7540 t - 815 t + 513 t + t - 14 t + 1) and in Maple notation (68*t^33-90*t^32+86*t^31+1460*t^30-1732*t^29+8380*t^28-6395*t^27-144779*t^26+ 267472*t^25+236434*t^24-478528*t^23-733772*t^22+559915*t^21+2271915*t^20-\ 1679335*t^19-2772890*t^18+2504166*t^17+1900258*t^16-2116061*t^15-847133*t^14+ 1137852*t^13+246892*t^12-406159*t^11-44247*t^10+95846*t^9+6862*t^8-14571*t^7-\ 1964*t^6+1457*t^5+424*t^4-101*t^3-39*t^2+4*t+1)*t/(48*t^35-38*t^34-84*t^33-534* t^32-8082*t^31+31262*t^30+47442*t^29-256850*t^28+189166*t^27+222332*t^26+349584 *t^25-1169200*t^24-2182331*t^23+5725263*t^22+2364221*t^21-11442244*t^20-178343* t^19+14968569*t^18-3503371*t^17-12105383*t^16+4281821*t^15+6391186*t^14-2591348 *t^13-2421504*t^12+1036857*t^11+679065*t^10-300086*t^9-130951*t^8+60151*t^7+ 15148*t^6-7540*t^5-815*t^4+513*t^3+t^2-14*t+1) For the sake of the OEIS, here are the first 30 terms, starting at n=0 0, 1, 18, 212, 2336, 24497, 255533, 2645985, 27376230, 282955020, 2924185830, 30215683761, 312213336565, 3225985817329, 33332835578496, 344414175662604, 3558685558812494, 36770376789464982, 379932569013565197, 3925680510217335169, 40562375124908040388, 419113645164314189727, 4330521744097472559659, 44745425931934897995112, 462335316636309211612253, 4777112756145040578778315, 49359859530042197506197891, 510014282095784833743972496, 5269759079918839249651002704, 54450162937140281712979783503, 562610206447549947510243061177 ----------------------------- This took, 10.106, seconds. Theorem Number, 4 --------------------------------- Let Z[n] be the integer sequence whose generating function is infinity ----- \ j 1 ) Z[j] t = ----------- / 2 ----- -t - t + 1 j = 0 Let n - 1 --------' ' | | Z[i + 1] (Z[i] + Z[i + 1]) F[n](x) = | | (1 + x + x ) | | | | i = 0 Write: infinity ----- \ i F[n](x) = ) a(n, i) x / ----- i = 0 Let : infinity ----- \ H(n) = ) a(n, k) a(n, k + 1) a(n, k + 2) a(n, k + 3) / ----- k = 0 Then infinity ----- \ n 108 107 106 105 ) H(n) t = (132 t + 1308 t - 56328 t + 4644 t / ----- n = 0 104 103 102 101 + 1788092 t + 11647748 t + 257587022 t - 2292412106 t 100 99 98 - 9983399075 t + 108995379205 t - 117690446171 t 97 96 95 - 1167716826400 t + 9622044477889 t - 21792194538706 t 94 93 92 - 100977545391833 t + 498063015336364 t + 185763103931707 t 91 90 89 - 2087577434457037 t - 3871625807311931 t - 30516927411573042 t 88 87 + 133620756835836770 t + 486902256691942682 t 86 85 - 1670347726485867300 t - 3162910466920286018 t 84 83 + 11754582920280314963 t + 11076065803670805283 t 82 81 - 54763862331944829464 t - 17181172203725435016 t 80 79 + 185100009666761992660 t - 32902547653137373756 t 78 77 - 483062622289311097040 t + 284920500857028879079 t 76 75 + 1147199285401861175184 t - 1150311919579162851533 t 74 73 - 3035706327815741953351 t + 4775311804818034382830 t 72 71 + 7110012299500002817234 t - 18126361220334499044095 t 70 69 - 7801427661744312452906 t + 49043379691052090844850 t 68 67 - 12823193208479493665821 t - 89718001077302093385400 t 66 65 + 66828437259856518257944 t + 114501457619265523638161 t 64 63 - 131025976494089086835099 t - 109946781450543348410725 t 62 61 + 159468189402679103093358 t + 88562033501712317679861 t 60 59 - 127165526308066643432930 t - 58308744506297301369951 t 58 57 + 38032063832286770413870 t + 10800448119219932715434 t 56 55 + 93205661393853283351789 t + 47228722240673051673446 t 54 53 - 235614160903262460516299 t - 85878534203646726698024 t 52 51 + 339588897913661018601481 t + 84198816895648535384019 t 50 49 - 366789775131663460523786 t - 50243789922797972585541 t 48 47 + 317215381512124879524517 t + 9963600718647689745092 t 46 45 - 224665038445559960156951 t + 15037434439107052507696 t 44 43 + 131301477450637948273427 t - 20368191243137457459086 t 42 41 - 63683341092110615421050 t + 14662220581347602141476 t 40 39 + 25945944265752908167398 t - 7511395283866195899881 t 38 37 - 9090652172880576934099 t + 3007614509552099625524 t 36 35 + 2828851098446695601196 t - 1007663032421843169354 t 34 33 - 800944703143096424678 t + 301395927089605723415 t 32 31 + 204807483858165571804 t - 83701340606589884564 t 30 29 - 45281813006727534685 t + 21308176512951738236 t 28 27 + 8107129235340792674 t - 4739164842927208365 t 26 25 24 - 1071765778247208233 t + 879527276295528163 t + 82840048953940858 t 23 22 21 - 132475217832650667 t + 2078607969600700 t + 16009309714152679 t 20 19 18 - 1770589909047466 t - 1552099250149436 t + 308289781070918 t 17 16 15 + 121531061922734 t - 34899445042801 t - 7715362027116 t 14 13 12 + 2965365908061 t + 388872571017 t - 197508123660 t 11 10 9 8 - 14307373159 t + 10302252819 t + 298069991 t - 407210562 t 7 6 5 4 3 2 + 748965 t + 11576577 t - 193611 t - 224333 t + 2787 t + 2828 t 2 / 3 2 3 2 + 12 t - 20) t / ((t - 2 t - t + 1) (t - 6 t + 5 t - 1) / 3 2 3 2 95 94 (t + t - 2 t - 1) (t + 2 t - t - 1) (1 + t) (t - 1) (180 t + 4680 t 93 92 91 90 89 + 49488 t - 468612 t - 1635846 t + 47473026 t - 37904442 t 88 87 86 85 - 731661104 t + 5948372358 t - 28208274782 t + 64579372381 t 84 83 82 + 1651737172978 t - 8605328214897 t - 24212216561840 t 81 80 79 + 213602955349436 t - 19610135273134 t - 2497871758214910 t 78 77 76 + 3709818281073261 t + 16169650748634842 t - 40829062723500568 t 75 74 73 - 52959504126327225 t + 234382555793689335 t - 31719310277323196 t 72 71 - 788191274919375939 t + 1026777110955544218 t 70 69 + 1312409677483744932 t - 4610911834867559035 t 68 67 + 655283194210712269 t + 13602708236044256315 t 66 65 - 11597212088515204996 t - 32338412740184885372 t 64 63 + 49125559582599746782 t + 53466328000124911244 t 62 61 - 148870238248500486789 t - 27921797202033383362 t 60 59 + 320119114989084216332 t - 121416618022672300524 t 58 57 - 417406828263674985766 t + 341493473908910643165 t 56 55 + 177463015675169852275 t - 323191778776747816099 t 54 53 + 392675928866035875577 t - 179416162608191216914 t 52 51 - 893335187503336852701 t + 970250479645214523298 t 50 49 + 970873252296198754585 t - 1584088684527900195729 t 48 47 - 655097906012668358467 t + 1707674527010205459751 t 46 45 + 256737569497334803443 t - 1400488067415014737525 t 44 43 - 23048241756871499383 t + 947923884350449143798 t 42 41 - 39353136819203394289 t - 566056063746542865768 t 40 39 + 35495024948628093843 t + 307894405744434450199 t 38 37 - 26680105394034431733 t - 150009450720956587725 t 36 35 + 20176714042133525017 t + 62825098251919037997 t 34 33 - 12920730171955835950 t - 21813124395228324635 t 32 31 + 6450206039332723198 t + 6134331804093683174 t 30 29 - 2509143740928757819 t - 1373901863596474521 t 28 27 26 + 776354315187159050 t + 238876173393005020 t - 194478546395598032 t 25 24 23 - 30053163293475448 t + 39700525974962393 t + 2039841689891880 t 22 21 20 - 6570693971436333 t + 137417153977493 t + 871564148700711 t 19 18 17 - 63933193196452 t - 91665569116653 t + 10326268727340 t 16 15 14 + 7623534934271 t - 1088874474306 t - 506968912990 t 13 12 11 10 + 84163335991 t + 27555296788 t - 5050029185 t - 1231584712 t 9 8 7 6 5 + 241891494 t + 42975705 t - 9021617 t - 1026391 t + 239267 t 4 3 2 + 12797 t - 3847 t - 8 t + 27 t - 1)) and in Maple notation (132*t^108+1308*t^107-56328*t^106+4644*t^105+1788092*t^104+11647748*t^103+ 257587022*t^102-2292412106*t^101-9983399075*t^100+108995379205*t^99-\ 117690446171*t^98-1167716826400*t^97+9622044477889*t^96-21792194538706*t^95-\ 100977545391833*t^94+498063015336364*t^93+185763103931707*t^92-2087577434457037 *t^91-3871625807311931*t^90-30516927411573042*t^89+133620756835836770*t^88+ 486902256691942682*t^87-1670347726485867300*t^86-3162910466920286018*t^85+ 11754582920280314963*t^84+11076065803670805283*t^83-54763862331944829464*t^82-\ 17181172203725435016*t^81+185100009666761992660*t^80-32902547653137373756*t^79-\ 483062622289311097040*t^78+284920500857028879079*t^77+1147199285401861175184*t^ 76-1150311919579162851533*t^75-3035706327815741953351*t^74+ 4775311804818034382830*t^73+7110012299500002817234*t^72-18126361220334499044095 *t^71-7801427661744312452906*t^70+49043379691052090844850*t^69-\ 12823193208479493665821*t^68-89718001077302093385400*t^67+ 66828437259856518257944*t^66+114501457619265523638161*t^65-\ 131025976494089086835099*t^64-109946781450543348410725*t^63+ 159468189402679103093358*t^62+88562033501712317679861*t^61-\ 127165526308066643432930*t^60-58308744506297301369951*t^59+ 38032063832286770413870*t^58+10800448119219932715434*t^57+ 93205661393853283351789*t^56+47228722240673051673446*t^55-\ 235614160903262460516299*t^54-85878534203646726698024*t^53+ 339588897913661018601481*t^52+84198816895648535384019*t^51-\ 366789775131663460523786*t^50-50243789922797972585541*t^49+ 317215381512124879524517*t^48+9963600718647689745092*t^47-\ 224665038445559960156951*t^46+15037434439107052507696*t^45+ 131301477450637948273427*t^44-20368191243137457459086*t^43-\ 63683341092110615421050*t^42+14662220581347602141476*t^41+ 25945944265752908167398*t^40-7511395283866195899881*t^39-9090652172880576934099 *t^38+3007614509552099625524*t^37+2828851098446695601196*t^36-\ 1007663032421843169354*t^35-800944703143096424678*t^34+301395927089605723415*t^ 33+204807483858165571804*t^32-83701340606589884564*t^31-45281813006727534685*t^ 30+21308176512951738236*t^29+8107129235340792674*t^28-4739164842927208365*t^27-\ 1071765778247208233*t^26+879527276295528163*t^25+82840048953940858*t^24-\ 132475217832650667*t^23+2078607969600700*t^22+16009309714152679*t^21-\ 1770589909047466*t^20-1552099250149436*t^19+308289781070918*t^18+ 121531061922734*t^17-34899445042801*t^16-7715362027116*t^15+2965365908061*t^14+ 388872571017*t^13-197508123660*t^12-14307373159*t^11+10302252819*t^10+298069991 *t^9-407210562*t^8+748965*t^7+11576577*t^6-193611*t^5-224333*t^4+2787*t^3+2828* t^2+12*t-20)*t^2/(t^3-2*t^2-t+1)/(t^3-6*t^2+5*t-1)/(t^3+t^2-2*t-1)/(t^3+2*t^2-t -1)/(1+t)/(t-1)/(180*t^95+4680*t^94+49488*t^93-468612*t^92-1635846*t^91+ 47473026*t^90-37904442*t^89-731661104*t^88+5948372358*t^87-28208274782*t^86+ 64579372381*t^85+1651737172978*t^84-8605328214897*t^83-24212216561840*t^82+ 213602955349436*t^81-19610135273134*t^80-2497871758214910*t^79+3709818281073261 *t^78+16169650748634842*t^77-40829062723500568*t^76-52959504126327225*t^75+ 234382555793689335*t^74-31719310277323196*t^73-788191274919375939*t^72+ 1026777110955544218*t^71+1312409677483744932*t^70-4610911834867559035*t^69+ 655283194210712269*t^68+13602708236044256315*t^67-11597212088515204996*t^66-\ 32338412740184885372*t^65+49125559582599746782*t^64+53466328000124911244*t^63-\ 148870238248500486789*t^62-27921797202033383362*t^61+320119114989084216332*t^60 -121416618022672300524*t^59-417406828263674985766*t^58+341493473908910643165*t^ 57+177463015675169852275*t^56-323191778776747816099*t^55+392675928866035875577* t^54-179416162608191216914*t^53-893335187503336852701*t^52+ 970250479645214523298*t^51+970873252296198754585*t^50-1584088684527900195729*t^ 49-655097906012668358467*t^48+1707674527010205459751*t^47+256737569497334803443 *t^46-1400488067415014737525*t^45-23048241756871499383*t^44+ 947923884350449143798*t^43-39353136819203394289*t^42-566056063746542865768*t^41 +35495024948628093843*t^40+307894405744434450199*t^39-26680105394034431733*t^38 -150009450720956587725*t^37+20176714042133525017*t^36+62825098251919037997*t^35 -12920730171955835950*t^34-21813124395228324635*t^33+6450206039332723198*t^32+ 6134331804093683174*t^31-2509143740928757819*t^30-1373901863596474521*t^29+ 776354315187159050*t^28+238876173393005020*t^27-194478546395598032*t^26-\ 30053163293475448*t^25+39700525974962393*t^24+2039841689891880*t^23-\ 6570693971436333*t^22+137417153977493*t^21+871564148700711*t^20-63933193196452* t^19-91665569116653*t^18+10326268727340*t^17+7623534934271*t^16-1088874474306*t ^15-506968912990*t^14+84163335991*t^13+27555296788*t^12-5050029185*t^11-\ 1231584712*t^10+241891494*t^9+42975705*t^8-9021617*t^7-1026391*t^6+239267*t^5+ 12797*t^4-3847*t^3-8*t^2+27*t-1) For the sake of the OEIS, here are the first 30 terms, starting at n=0 0, 0, 20, 588, 13252, 265849, 5229763, 101060435, 1946449634, 37394644117, 718025430413, 13782217902826, 264523144785617, 5076775429023344, 97433304301807750, 1869925419947982942, 35887277870506178778, 688741774314747395339, 13218198159465653883379, 253681065900280678327359, 4868597160089158423450280, 93437159003154657230689454, 1793227572952759123248287220, 34415270756635207082666262163, 660491105008436517535299488589, 12676015332359255753118242502146, 243275592192994613524191983095453, 4668897299776099033177828766685771, 89604558350846562033695752701764135, 1719673053775189511036192158671250839, 33003626894799846771256509394138856117 ----------------------------- This took, 145163.312, seconds. ----------------------------------------- This concludes this article that took, 145163.260, seconds to produce.