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 + t ) Z[j] t = ------------ / 3 2 ----- -t - t + 1 j = 0 Let n - 1 --------' ' | | (Z[i] + Z[i + 1]) F[n](x) = | | (1 + 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 = - ------- / 2 t - 1 ----- n = 0 and in Maple notation -1/(2*t-1) For the sake of the OEIS, here are the first 30 terms, starting at n=0 1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536, 131072, 262144, 524288, 1048576, 2097152, 4194304, 8388608, 16777216, 33554432, 67108864, 134217728, 268435456, 536870912, 1073741824 ----------------------------- This took, 0.001, seconds. Theorem Number, 2 --------------------------------- Let Z[n] be the integer sequence whose generating function is infinity ----- 2 \ j t + t ) Z[j] t = ------------ / 3 2 ----- -t - t + 1 j = 0 Let n - 1 --------' ' | | (Z[i] + Z[i + 1]) F[n](x) = | | (1 + 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 141 140 139 138 ) H(n) t = - t (1752 t - 3648 t - 42748 t + 89400 t / ----- n = 0 137 136 135 134 133 + 32188 t - 45516 t + 231000 t + 2386284 t + 49128 t 132 131 130 129 - 7961112 t + 6708914 t + 26159278 t - 41611490 t 128 127 126 125 - 94332532 t - 62117989 t + 4181004 t - 112756973 t 124 123 122 121 - 53678480 t + 50474653 t - 554235507 t + 1448156827 t 120 119 118 117 + 2287620834 t - 819164032 t - 1610082191 t - 3579120070 t 116 115 114 113 + 2526468549 t + 5241926123 t - 7787553708 t - 3530059680 t 112 111 110 109 + 5439652048 t + 22637968806 t + 21536431930 t - 2910973136 t 108 107 106 105 - 25646775982 t - 52485518967 t - 4204970618 t - 982336297 t 104 103 102 101 + 2330967389 t - 48832629531 t + 30387552260 t + 92440069350 t 100 99 98 97 + 128340910956 t + 12734613033 t - 71942913350 t - 157767659344 t 96 95 94 93 - 104203974974 t + 35889127078 t + 72649544851 t - 46305489046 t 92 91 90 89 - 152150333429 t + 60583918378 t + 137372996073 t + 101290154940 t 88 87 86 85 - 15363590805 t + 10349754406 t - 108853794553 t - 1298993403 t 84 83 82 81 + 208546792073 t + 282215228124 t - 28581317573 t - 149068786095 t 80 79 78 77 - 11720033407 t - 5049898819 t - 199662347347 t - 110511895481 t 76 75 74 73 + 148068743245 t + 90304253198 t - 130868752473 t - 116940325341 t 72 71 70 69 + 28136723867 t - 110605638028 t - 83554367166 t + 97866575294 t 68 67 66 65 + 272322993069 t - 15587163061 t - 13531384258 t - 45660883939 t 64 63 62 61 + 17440544407 t - 244255375673 t - 42812093875 t - 8922877026 t 60 59 58 57 + 141012560622 t - 2131652955 t + 143331458734 t + 12785767461 t 56 55 54 53 + 43041652391 t - 85599516081 t - 21174078645 t - 70154778248 t 52 51 50 49 + 13853939212 t - 26340232040 t + 31927135022 t + 21030464083 t 48 47 46 45 + 33842667118 t - 11749492394 t + 7119309203 t - 8860779935 t 44 43 42 41 - 8748797032 t - 14421038136 t + 3141341191 t - 718123803 t 40 39 38 37 + 2099065276 t + 1912321358 t + 4363956056 t - 374419500 t 36 35 34 33 - 270712414 t - 452668162 t - 157350596 t - 884919501 t 32 31 30 29 28 + 1241177 t + 117253493 t + 97724518 t - 7909522 t + 127038007 t 27 26 25 24 23 + 6603444 t - 22830432 t - 17556486 t + 2323400 t - 12557341 t 22 21 20 19 18 - 1278324 t + 2407249 t + 1954441 t - 104233 t + 875251 t 17 16 15 14 13 12 + 130230 t - 151424 t - 140320 t + 805 t - 38793 t - 5497 t 11 10 9 8 7 6 5 4 + 4751 t + 5708 t - 176 t + 1040 t + 152 t - 57 t - 124 t - 2 t 3 2 / 143 142 141 - 13 t - t + t + 1) / (3768 t - 71904 t + 8804 t / 140 139 138 137 136 + 324696 t - 232816 t - 639132 t - 1039340 t + 4643616 t 135 134 133 132 + 1388314 t - 9630220 t - 3549100 t + 28982132 t 131 130 129 128 + 34401236 t - 28762256 t - 200113888 t - 33723860 t 127 126 125 124 + 276057710 t + 646612026 t + 32273546 t - 708940276 t 123 122 121 120 - 1526216298 t + 1450753578 t + 216301636 t - 1108307887 t 119 118 117 116 - 1742021662 t - 1417914234 t + 10339040766 t + 3607718193 t 115 114 113 112 - 5758570640 t - 19931220789 t - 11913117676 t + 3584365941 t 111 110 109 108 + 12735905706 t + 5458892662 t + 37070305390 t + 22013960657 t 107 106 105 + 51424203132 t + 11246329095 t - 56686728310 t 104 103 102 - 156441275117 t - 39017494174 t + 7544929854 t 101 100 99 98 + 89705462968 t + 56464552945 t + 100747991670 t + 27597567623 t 97 96 95 94 - 18897155736 t - 79839575826 t - 120843321286 t - 171591207332 t 93 92 91 90 - 200196230032 t + 272553213317 t + 272586949926 t + 99574660292 t 89 88 87 86 - 264830761774 t - 55034963169 t - 199607236418 t + 55320300249 t 85 84 83 + 307494437866 t + 331634796121 t - 101043380216 t 82 81 80 - 225467972606 t + 183759205230 t + 148349057253 t 79 78 77 76 - 103497897656 t - 355976045088 t + 92535891414 t + 109186966599 t 75 74 73 72 - 27367015364 t - 41991991563 t + 228899742676 t - 55185691748 t 71 70 69 68 - 397974097705 t - 193739797398 t + 140085633574 t + 17601989326 t 67 66 65 64 + 44030995095 t + 292468724495 t + 426256560793 t - 262339959525 t 63 62 61 60 - 256464242001 t - 244736466641 t + 8439884592 t - 289885730694 t 59 58 57 56 + 259927598297 t + 135943504431 t + 276078433475 t - 35560085829 t 55 54 53 52 + 91354643203 t - 204692514012 t - 26373196058 t - 148192512992 t 51 50 49 48 + 10841723537 t + 1796920479 t + 117022286851 t - 5561876162 t 47 46 45 44 + 48441636750 t - 3103406637 t - 7409803872 t - 48869757545 t 43 42 41 40 + 2767690761 t - 8967345023 t + 2680013150 t + 1236762128 t 39 38 37 36 + 13962818229 t - 375468127 t + 139863149 t - 1098472996 t 35 34 33 32 + 443208499 t - 2836970631 t - 46611106 t + 296787193 t 31 30 29 28 + 298048165 t - 193561244 t + 425804092 t + 16221492 t 27 26 25 24 23 - 76194757 t - 50613254 t + 33174763 t - 43743153 t - 2549622 t 22 21 20 19 18 + 9425106 t + 5052198 t - 2920611 t + 3065622 t + 148563 t 17 16 15 14 13 12 - 690525 t - 333202 t + 173317 t - 135142 t + 3047 t + 24654 t 11 10 9 8 7 6 5 + 13116 t - 6741 t + 3705 t - 235 t - 441 t - 309 t + 114 t 4 3 2 - 40 t + 8 t + 5 t + 2 t - 1) and in Maple notation -t*(1752*t^141-3648*t^140-42748*t^139+89400*t^138+32188*t^137-45516*t^136+ 231000*t^135+2386284*t^134+49128*t^133-7961112*t^132+6708914*t^131+26159278*t^ 130-41611490*t^129-94332532*t^128-62117989*t^127+4181004*t^126-112756973*t^125-\ 53678480*t^124+50474653*t^123-554235507*t^122+1448156827*t^121+2287620834*t^120 -819164032*t^119-1610082191*t^118-3579120070*t^117+2526468549*t^116+5241926123* t^115-7787553708*t^114-3530059680*t^113+5439652048*t^112+22637968806*t^111+ 21536431930*t^110-2910973136*t^109-25646775982*t^108-52485518967*t^107-\ 4204970618*t^106-982336297*t^105+2330967389*t^104-48832629531*t^103+30387552260 *t^102+92440069350*t^101+128340910956*t^100+12734613033*t^99-71942913350*t^98-\ 157767659344*t^97-104203974974*t^96+35889127078*t^95+72649544851*t^94-\ 46305489046*t^93-152150333429*t^92+60583918378*t^91+137372996073*t^90+ 101290154940*t^89-15363590805*t^88+10349754406*t^87-108853794553*t^86-\ 1298993403*t^85+208546792073*t^84+282215228124*t^83-28581317573*t^82-\ 149068786095*t^81-11720033407*t^80-5049898819*t^79-199662347347*t^78-\ 110511895481*t^77+148068743245*t^76+90304253198*t^75-130868752473*t^74-\ 116940325341*t^73+28136723867*t^72-110605638028*t^71-83554367166*t^70+ 97866575294*t^69+272322993069*t^68-15587163061*t^67-13531384258*t^66-\ 45660883939*t^65+17440544407*t^64-244255375673*t^63-42812093875*t^62-8922877026 *t^61+141012560622*t^60-2131652955*t^59+143331458734*t^58+12785767461*t^57+ 43041652391*t^56-85599516081*t^55-21174078645*t^54-70154778248*t^53+13853939212 *t^52-26340232040*t^51+31927135022*t^50+21030464083*t^49+33842667118*t^48-\ 11749492394*t^47+7119309203*t^46-8860779935*t^45-8748797032*t^44-14421038136*t^ 43+3141341191*t^42-718123803*t^41+2099065276*t^40+1912321358*t^39+4363956056*t^ 38-374419500*t^37-270712414*t^36-452668162*t^35-157350596*t^34-884919501*t^33+ 1241177*t^32+117253493*t^31+97724518*t^30-7909522*t^29+127038007*t^28+6603444*t ^27-22830432*t^26-17556486*t^25+2323400*t^24-12557341*t^23-1278324*t^22+2407249 *t^21+1954441*t^20-104233*t^19+875251*t^18+130230*t^17-151424*t^16-140320*t^15+ 805*t^14-38793*t^13-5497*t^12+4751*t^11+5708*t^10-176*t^9+1040*t^8+152*t^7-57*t ^6-124*t^5-2*t^4-13*t^3-t^2+t+1)/(3768*t^143-71904*t^142+8804*t^141+324696*t^ 140-232816*t^139-639132*t^138-1039340*t^137+4643616*t^136+1388314*t^135-9630220 *t^134-3549100*t^133+28982132*t^132+34401236*t^131-28762256*t^130-200113888*t^ 129-33723860*t^128+276057710*t^127+646612026*t^126+32273546*t^125-708940276*t^ 124-1526216298*t^123+1450753578*t^122+216301636*t^121-1108307887*t^120-\ 1742021662*t^119-1417914234*t^118+10339040766*t^117+3607718193*t^116-5758570640 *t^115-19931220789*t^114-11913117676*t^113+3584365941*t^112+12735905706*t^111+ 5458892662*t^110+37070305390*t^109+22013960657*t^108+51424203132*t^107+ 11246329095*t^106-56686728310*t^105-156441275117*t^104-39017494174*t^103+ 7544929854*t^102+89705462968*t^101+56464552945*t^100+100747991670*t^99+ 27597567623*t^98-18897155736*t^97-79839575826*t^96-120843321286*t^95-\ 171591207332*t^94-200196230032*t^93+272553213317*t^92+272586949926*t^91+ 99574660292*t^90-264830761774*t^89-55034963169*t^88-199607236418*t^87+ 55320300249*t^86+307494437866*t^85+331634796121*t^84-101043380216*t^83-\ 225467972606*t^82+183759205230*t^81+148349057253*t^80-103497897656*t^79-\ 355976045088*t^78+92535891414*t^77+109186966599*t^76-27367015364*t^75-\ 41991991563*t^74+228899742676*t^73-55185691748*t^72-397974097705*t^71-\ 193739797398*t^70+140085633574*t^69+17601989326*t^68+44030995095*t^67+ 292468724495*t^66+426256560793*t^65-262339959525*t^64-256464242001*t^63-\ 244736466641*t^62+8439884592*t^61-289885730694*t^60+259927598297*t^59+ 135943504431*t^58+276078433475*t^57-35560085829*t^56+91354643203*t^55-\ 204692514012*t^54-26373196058*t^53-148192512992*t^52+10841723537*t^51+ 1796920479*t^50+117022286851*t^49-5561876162*t^48+48441636750*t^47-3103406637*t ^46-7409803872*t^45-48869757545*t^44+2767690761*t^43-8967345023*t^42+2680013150 *t^41+1236762128*t^40+13962818229*t^39-375468127*t^38+139863149*t^37-1098472996 *t^36+443208499*t^35-2836970631*t^34-46611106*t^33+296787193*t^32+298048165*t^ 31-193561244*t^30+425804092*t^29+16221492*t^28-76194757*t^27-50613254*t^26+ 33174763*t^25-43743153*t^24-2549622*t^23+9425106*t^22+5052198*t^21-2920611*t^20 +3065622*t^19+148563*t^18-690525*t^17-333202*t^16+173317*t^15-135142*t^14+3047* t^13+24654*t^12+13116*t^11-6741*t^10+3705*t^9-235*t^8-441*t^7-309*t^6+114*t^5-\ 40*t^4+8*t^3+5*t^2+2*t-1) For the sake of the OEIS, here are the first 30 terms, starting at n=0 0, 1, 3, 10, 30, 92, 284, 844, 2568, 7760, 23384, 70802, 213416, 644851, 1948028, 5879539, 17758427, 53613858, 161894476, 488874842, 1476014361, 4456849664, 13457169954, 40633088837, 122689454895, 370445768580, 1118533050268, 3377325305096, 10197526940888, 30790501940675, 92968949980563 ----------------------------- Theorem Number, 3 Exceeded the limit of number of equations ----------------------------------------- This concludes this article that took, 14765.074, seconds to produce.