Enumerating Generalized Dyck paths with alphabets consisting of integers from -2 to 2 By Shalosh B. Ekhad ------------------------------------------------------------- Theorem 1 : Let a(n) be number of words of length n in the alphabet, {-2, 1}, that sum-u\ p to 0 and whose partial sums are never negative, in other words general\ ized Dyck words with alphabet, {-2, 1}, rather than {1,-1} Let X(t) be the ordinary genearting function of that sequence, in other word\ s infinity ----- \ n X(t) = ) a(n) t / ----- n = 0 X(t) satisifies the algebaric equation 3 3 X(t) t - X(t) + 1 = 0 and in Maple notation X(t)^3*t^3-X(t)+1 = 0 For the sake of the OEIS here are the first 40 terms, starting with n=0 [1, 0, 0, 1, 0, 0, 3, 0, 0, 12, 0, 0, 55, 0, 0, 273, 0, 0, 1428, 0, 0, 7752, 0, 0, 43263, 0, 0, 246675, 0, 0, 1430715, 0, 0, 8414640, 0, 0, 50067108, 0, 0, 300830572, 0] ------------------------------------------------------------- Theorem 2 : Let a(n) be number of words of length n in the alphabet, {-2, 0, 1}, that su\ m-up to 0 and whose partial sums are never negative, in other words gene\ ralized Dyck words with alphabet, {-2, 0, 1}, rather than {1,-1} Let X(t) be the ordinary genearting function of that sequence, in other word\ s infinity ----- \ n X(t) = ) a(n) t / ----- n = 0 X(t) satisifies the algebaric equation 3 3 t X(t) + (t - 1) X(t) + 1 = 0 and in Maple notation t^3*X(t)^3+(t-1)*X(t)+1 = 0 For the sake of the OEIS here are the first 40 terms, starting with n=0 [1, 1, 1, 2, 5, 11, 24, 57, 141, 349, 871, 2212, 5688, 14730, 38403, 100829, 266333, 706997, 1885165, 5047522, 13565203, 36578497, 98934826, 268342933, 729709432, 1989021256, 5433518806, 14873285506, 40790118487, 112064912455, 308390452661, 849969894794, 2346045295997, 6484283432301, 17945109524709, 49723012463106, 137932680852865, 383044179221839, 1064824607532304, 2963004005175517, 8252593204567339] Furthermore a(n) satisfies the following linear recurrence equation with pol\ ynomial coefficients 2 (6 n - 1) a(n - 1) 3 (2 n - 1) (n - 1) a(n - 2) a(n) = ------------------- - ---------------------------- (2 n + 3) n (2 n + 3) n (n - 1) (n - 2) a(n - 3) + 31/2 ------------------------ (2 n + 3) n subject to the initial conditions a(1) = 1, a(2) = 1, a(3) = 2 and in Maple notation a(n) = (6*n^2-1)/(2*n+3)/n*a(n-1)-3*(2*n-1)*(n-1)/(2*n+3)/n*a(n-2)+31/2*(n-1)*( n-2)/(2*n+3)/n*a(n-3) a(1) = 1, a(2) = 1, a(3) = 2 Just for fun, using this recurrence we get that a(1000) = 191620557659347802307365493621198769180147191177401848085787099097\ 814759358806854394754767474196429967124030578927338615823821891043019713\ 979679639145574457752540415614217963188170094752419053006418762214451575\ 157647201281387566898594569642270963919210899243251958348082558226674354\ 203970388408809295122593932855958735763065470744807006926662811052757547\ 960395050405023393759847883993305838283655573122763447225181426122416586\ 9250035961303568000396851007934 Theorem 3 : Let a(n) be number of words of length n in the alphabet, {-2, 1, 2}, that su\ m-up to 0 and whose partial sums are never negative, in other words gene\ ralized Dyck words with alphabet, {-2, 1, 2}, rather than {1,-1} Let X(t) be the ordinary genearting function of that sequence, in other word\ s infinity ----- \ n X(t) = ) a(n) t / ----- n = 0 X(t) satisifies the algebaric equation 6 6 4 5 4 4 3 2 3 2 2 X(t) t - t X(t) - t X(t) + (t + 2 t ) X(t) - t X(t) - X(t) + 1 = 0 and in Maple notation X(t)^6*t^6-t^4*X(t)^5-t^4*X(t)^4+(t^3+2*t^2)*X(t)^3-t^2*X(t)^2-X(t)+1 = 0 For the sake of the OEIS here are the first 40 terms, starting with n=0 [1, 0, 1, 1, 2, 7, 8, 38, 58, 199, 452, 1149, 3277, 7650, 22696, 55726, 157502, 416967, 1128026, 3122336, 8365304, 23402737, 63505268, 176860650, 487957967, 1353427722, 3774616133, 10483218667, 29371164344, 81965145468, 230030965231, 645265199252, 1813615497166, 5107394107927, 14386545035342, 40621735594210, 114720169872202, 324560293765296, 918870098708832, 2604241833793991, 7388579097551618] ------------------------------------------------------------- Theorem 4 : Let a(n) be number of words of length n in the alphabet, {-2, 0, 1, 2}, that\ sum-up to 0 and whose partial sums are never negative, in other words g\ eneralized Dyck words with alphabet, {-2, 0, 1, 2}, rather than {1,-1} Let X(t) be the ordinary genearting function of that sequence, in other word\ s infinity ----- \ n X(t) = ) a(n) t / ----- n = 0 X(t) satisifies the algebaric equation 6 6 5 4 5 4 4 3 2 3 2 2 X(t) t + (t - t ) X(t) - t X(t) + (-t + 2 t ) X(t) - t X(t) + (t - 1) X(t) + 1 = 0 and in Maple notation X(t)^6*t^6+(t^5-t^4)*X(t)^5-t^4*X(t)^4+(-t^3+2*t^2)*X(t)^3-t^2*X(t)^2+(t-1)*X(t )+1 = 0 For the sake of the OEIS here are the first 40 terms, starting with n=0 [1, 1, 2, 5, 13, 38, 116, 368, 1203, 4016, 13642, 46987, 163696, 575816, 2042175, 7294299, 26215927, 94736708, 344015468, 1254647606, 4593682529, 16878510120, 62215957762, 230007985382, 852612196852, 3168359595108, 11800740083576, 44045606325107, 164721039237571, 617148978777583, 2316181581852586, 8706610827498169, 32777540164574119, 123570545078714196, 466475769211533776, 1763136562025613086, 6671991538484571985, 25276100101802859113, 95857089488037503932, 363893671750915858188, 1382735524079117907097] Theorem 5 : Let a(n) be number of words of length n in the alphabet, {-1, 1}, that sum-u\ p to 0 and whose partial sums are never negative, in other words general\ ized Dyck words with alphabet, {-1, 1}, rather than {1,-1} Let X(t) be the ordinary genearting function of that sequence, in other word\ s infinity ----- \ n X(t) = ) a(n) t / ----- n = 0 X(t) satisifies the algebaric equation 2 2 X(t) t - X(t) + 1 = 0 and in Maple notation X(t)^2*t^2-X(t)+1 = 0 For the sake of the OEIS here are the first 40 terms, starting with n=0 [1, 0, 1, 0, 2, 0, 5, 0, 14, 0, 42, 0, 132, 0, 429, 0, 1430, 0, 4862, 0, 16796, 0, 58786, 0, 208012, 0, 742900, 0, 2674440, 0, 9694845, 0, 35357670, 0, 129644790, 0, 477638700, 0, 1767263190, 0, 6564120420] Furthermore a(n) satisfies the following linear recurrence equation with pol\ ynomial coefficients 4 (n - 1) a(n - 2) a(n) = ------------------ n + 2 subject to the initial conditions a(1) = 0, a(2) = 1 and in Maple notation a(n) = 4*(n-1)/(n+2)*a(n-2) a(1) = 0, a(2) = 1 Just for fun, using this recurrence we get that a(1000) = 539497486917039060909410566119711128734834348196703167679426896420\ 410037336371644508208550747509720888947317534973145917768881736628103627\ 844100238921194561723883202123256952806711505149177419849031086149939116\ 975191706558395784192643914160118616272189452807591091542120727401415762\ 287153293056320 ------------------------------------------------------------- Theorem 6 : Let a(n) be number of words of length n in the alphabet, {-1, 0, 1}, that su\ m-up to 0 and whose partial sums are never negative, in other words gene\ ralized Dyck words with alphabet, {-1, 0, 1}, rather than {1,-1} Let X(t) be the ordinary genearting function of that sequence, in other word\ s infinity ----- \ n X(t) = ) a(n) t / ----- n = 0 X(t) satisifies the algebaric equation 2 2 1 + t X(t) + (t - 1) X(t) = 0 and in Maple notation 1+t^2*X(t)^2+(t-1)*X(t) = 0 For the sake of the OEIS here are the first 40 terms, starting with n=0 [1, 1, 2, 4, 9, 21, 51, 127, 323, 835, 2188, 5798, 15511, 41835, 113634, 310572 , 853467, 2356779, 6536382, 18199284, 50852019, 142547559, 400763223, 1129760415, 3192727797, 9043402501, 25669818476, 73007772802, 208023278209, 593742784829, 1697385471211, 4859761676391, 13933569346707, 40002464776083, 114988706524270, 330931069469828, 953467954114363, 2750016719520991, 7939655757745265, 22944749046030949, 66368199913921497] Furthermore a(n) satisfies the following linear recurrence equation with pol\ ynomial coefficients (2 n + 1) a(n - 1) 3 (n - 1) a(n - 2) a(n) = ------------------ + ------------------ n + 2 n + 2 subject to the initial conditions a(1) = 1, a(2) = 2 and in Maple notation a(n) = (2*n+1)/(n+2)*a(n-1)+3*(n-1)/(n+2)*a(n-2) a(1) = 1, a(2) = 2 Just for fun, using this recurrence we get that a(1000) = 611327659767718550435690476634770261235457497146560850115465892361\ 554957227669699010794318302938897113484397441952669750949116129917978333\ 663534108595168670698489302428822490403348335768238742869623299883716949\ 367954302518302682768150694320201921750341167179988855563026957589621840\ 969188712209356036697695300065446256951944019246193298794931658248883571\ 097251705649752079169310346665341751552899539053260989105341286932146899\ 17140093377138459245912955193770266157466468457 Theorem 7 : Let a(n) be number of words of length n in the alphabet, {-1, 2}, that sum-u\ p to 0 and whose partial sums are never negative, in other words general\ ized Dyck words with alphabet, {-1, 2}, rather than {1,-1} Let X(t) be the ordinary genearting function of that sequence, in other word\ s infinity ----- \ n X(t) = ) a(n) t / ----- n = 0 X(t) satisifies the algebaric equation 3 3 X(t) t - X(t) + 1 = 0 and in Maple notation X(t)^3*t^3-X(t)+1 = 0 For the sake of the OEIS here are the first 40 terms, starting with n=0 [1, 0, 0, 1, 0, 0, 3, 0, 0, 12, 0, 0, 55, 0, 0, 273, 0, 0, 1428, 0, 0, 7752, 0, 0, 43263, 0, 0, 246675, 0, 0, 1430715, 0, 0, 8414640, 0, 0, 50067108, 0, 0, 300830572, 0] ------------------------------------------------------------- Theorem 8 : Let a(n) be number of words of length n in the alphabet, {-1, 0, 2}, that su\ m-up to 0 and whose partial sums are never negative, in other words gene\ ralized Dyck words with alphabet, {-1, 0, 2}, rather than {1,-1} Let X(t) be the ordinary genearting function of that sequence, in other word\ s infinity ----- \ n X(t) = ) a(n) t / ----- n = 0 X(t) satisifies the algebaric equation 3 3 t X(t) + (t - 1) X(t) + 1 = 0 and in Maple notation t^3*X(t)^3+(t-1)*X(t)+1 = 0 For the sake of the OEIS here are the first 40 terms, starting with n=0 [1, 1, 1, 2, 5, 11, 24, 57, 141, 349, 871, 2212, 5688, 14730, 38403, 100829, 266333, 706997, 1885165, 5047522, 13565203, 36578497, 98934826, 268342933, 729709432, 1989021256, 5433518806, 14873285506, 40790118487, 112064912455, 308390452661, 849969894794, 2346045295997, 6484283432301, 17945109524709, 49723012463106, 137932680852865, 383044179221839, 1064824607532304, 2963004005175517, 8252593204567339] Furthermore a(n) satisfies the following linear recurrence equation with pol\ ynomial coefficients 2 (6 n - 1) a(n - 1) 3 (2 n - 1) (n - 1) a(n - 2) a(n) = ------------------- - ---------------------------- (2 n + 3) n (2 n + 3) n (n - 1) (n - 2) a(n - 3) + 31/2 ------------------------ (2 n + 3) n subject to the initial conditions a(1) = 1, a(2) = 1, a(3) = 2 and in Maple notation a(n) = (6*n^2-1)/(2*n+3)/n*a(n-1)-3*(2*n-1)*(n-1)/(2*n+3)/n*a(n-2)+31/2*(n-1)*( n-2)/(2*n+3)/n*a(n-3) a(1) = 1, a(2) = 1, a(3) = 2 Just for fun, using this recurrence we get that a(1000) = 191620557659347802307365493621198769180147191177401848085787099097\ 814759358806854394754767474196429967124030578927338615823821891043019713\ 979679639145574457752540415614217963188170094752419053006418762214451575\ 157647201281387566898594569642270963919210899243251958348082558226674354\ 203970388408809295122593932855958735763065470744807006926662811052757547\ 960395050405023393759847883993305838283655573122763447225181426122416586\ 9250035961303568000396851007934 Theorem 9 : Let a(n) be number of words of length n in the alphabet, {-1, 1, 2}, that su\ m-up to 0 and whose partial sums are never negative, in other words gene\ ralized Dyck words with alphabet, {-1, 1, 2}, rather than {1,-1} Let X(t) be the ordinary genearting function of that sequence, in other word\ s infinity ----- \ n X(t) = ) a(n) t / ----- n = 0 X(t) satisifies the algebaric equation 3 3 2 2 X(t) t + X(t) t - X(t) + 1 = 0 and in Maple notation X(t)^3*t^3+X(t)^2*t^2-X(t)+1 = 0 For the sake of the OEIS here are the first 40 terms, starting with n=0 [1, 0, 1, 1, 2, 5, 8, 21, 42, 96, 222, 495, 1177, 2717, 6435, 15288, 36374, 87516, 210494, 509694, 1237736, 3014882, 7370860, 18059899, 44379535, 109298070 , 269766655, 667224480, 1653266565, 4103910930, 10203669285, 25408828065, 63364046190, 158229645720, 395632288590, 990419552730, 2482238709888, 6227850849066, 15641497455612, 39322596749218, 98948326105928] Furthermore a(n) satisfies the following linear recurrence equation with pol\ ynomial coefficients 2 (n - 1) (26 n + 53 n + 18) a(n - 1) a(n) = -1/2 ------------------------------------ (2 n + 3) (26 n + 1) (n + 1) 2 3 (n - 1) (78 n + 42 n - 25) a(n - 2) + -------------------------------------- (2 n + 3) (26 n + 1) (n + 1) (26 n + 27) (n - 1) (n - 2) a(n - 3) + 31/2 ------------------------------------ (2 n + 3) (26 n + 1) (n + 1) subject to the initial conditions a(1) = 0, a(2) = 1, a(3) = 1 and in Maple notation a(n) = -1/2*(n-1)*(26*n^2+53*n+18)/(2*n+3)/(26*n+1)/(n+1)*a(n-1)+3*(n-1)*(78*n^ 2+42*n-25)/(2*n+3)/(26*n+1)/(n+1)*a(n-2)+31/2*(26*n+27)*(n-1)*(n-2)/(2*n+3)/(26 *n+1)/(n+1)*a(n-3) a(1) = 0, a(2) = 1, a(3) = 1 Just for fun, using this recurrence we get that a(1000) = 101662408407445423744168103476021587141989667612997719311488754154\ 322082931082374531255357681876619523150894345242770424947845903497434685\ 924396731064659870070402780338250399488998297800218606215611952870715670\ 616316141782311803128109822931518987777690811771955061426983735477927801\ 915580645830450923702686760277799803844656511972038824742386895372533429\ 74548248938307377609986379372338206473078793303158585992628 ------------------------------------------------------------- Theorem 10 : Let a(n) be number of words of length n in the alphabet, {-1, 0, 1, 2}, that\ sum-up to 0 and whose partial sums are never negative, in other words g\ eneralized Dyck words with alphabet, {-1, 0, 1, 2}, rather than {1,-1} Let X(t) be the ordinary genearting function of that sequence, in other word\ s infinity ----- \ n X(t) = ) a(n) t / ----- n = 0 X(t) satisifies the algebaric equation 3 3 2 2 t X(t) + t X(t) + (t - 1) X(t) + 1 = 0 and in Maple notation t^3*X(t)^3+t^2*X(t)^2+(t-1)*X(t)+1 = 0 For the sake of the OEIS here are the first 40 terms, starting with n=0 [1, 1, 2, 5, 13, 36, 104, 309, 939, 2905, 9118, 28964, 92940, 300808, 980864, 3219205, 10626023, 35252867, 117485454, 393133485, 1320357501, 4449298136, 15038769672, 50973266380, 173214422068, 589998043276, 2014026871496, 6889055189032, 23608722350440, 81049178840528, 278700885572096, 959835173086309 , 3310416757032159, 11432971961630999, 39535937094067710, 136883216842976943, 474465914711874487, 1646380234881262372, 5718752217030650552, 19883643328529880013, 69197975679197263363] Furthermore a(n) satisfies the following linear recurrence equation with pol\ ynomial coefficients 3 2 (143 n + 132 n - 17 n - 18) a(n - 1) a(n) = 1/2 -------------------------------------- (n + 1) (2 n + 3) (13 n - 1) 2 2 (n - 1) (26 n + 11 n - 6) a(n - 2) + ------------------------------------- (n + 1) (2 n + 3) (13 n - 1) 8 (13 n + 12) (n - 1) (n - 2) a(n - 3) + -------------------------------------- (n + 1) (2 n + 3) (13 n - 1) subject to the initial conditions a(1) = 1, a(2) = 2, a(3) = 5 and in Maple notation a(n) = 1/2*(143*n^3+132*n^2-17*n-18)/(n+1)/(2*n+3)/(13*n-1)*a(n-1)+2*(n-1)*(26* n^2+11*n-6)/(n+1)/(2*n+3)/(13*n-1)*a(n-2)+8*(13*n+12)*(n-1)*(n-2)/(n+1)/(2*n+3) /(13*n-1)*a(n-3) a(1) = 1, a(2) = 2, a(3) = 5 Just for fun, using this recurrence we get that a(1000) = 112718049543924946497817047468239461655675583843669943901464794765\ 533792111669532690580188378900348478962396154051472154606805143665500278\ 797461528775281470741871252428065570319092688394367917191513947824648673\ 529190684941558626782227996114319459384669364898834773886792148008545340\ 301080746770242890485768159647344818889692442357112107601225250847419471\ 248207409599029897356011756168126141752355941669112918936296621060064105\ 978604625766124118384397408012687929814034106507436273897154630784049444\ 82940579334994258331254210622965157469551755402098458848 Theorem 11 : Let a(n) be number of words of length n in the alphabet, {-2, -1, 1}, that s\ um-up to 0 and whose partial sums are never negative, in other words gen\ eralized Dyck words with alphabet, {-2, -1, 1}, rather than {1,-1} Let X(t) be the ordinary genearting function of that sequence, in other word\ s infinity ----- \ n X(t) = ) a(n) t / ----- n = 0 X(t) satisifies the algebaric equation 3 3 2 2 X(t) t + X(t) t - X(t) + 1 = 0 and in Maple notation X(t)^3*t^3+X(t)^2*t^2-X(t)+1 = 0 For the sake of the OEIS here are the first 40 terms, starting with n=0 [1, 0, 1, 1, 2, 5, 8, 21, 42, 96, 222, 495, 1177, 2717, 6435, 15288, 36374, 87516, 210494, 509694, 1237736, 3014882, 7370860, 18059899, 44379535, 109298070 , 269766655, 667224480, 1653266565, 4103910930, 10203669285, 25408828065, 63364046190, 158229645720, 395632288590, 990419552730, 2482238709888, 6227850849066, 15641497455612, 39322596749218, 98948326105928] Furthermore a(n) satisfies the following linear recurrence equation with pol\ ynomial coefficients 2 (n - 1) (26 n + 53 n + 18) a(n - 1) a(n) = -1/2 ------------------------------------ (2 n + 3) (26 n + 1) (n + 1) 2 3 (n - 1) (78 n + 42 n - 25) a(n - 2) + -------------------------------------- (2 n + 3) (26 n + 1) (n + 1) (26 n + 27) (n - 1) (n - 2) a(n - 3) + 31/2 ------------------------------------ (2 n + 3) (26 n + 1) (n + 1) subject to the initial conditions a(1) = 0, a(2) = 1, a(3) = 1 and in Maple notation a(n) = -1/2*(n-1)*(26*n^2+53*n+18)/(2*n+3)/(26*n+1)/(n+1)*a(n-1)+3*(n-1)*(78*n^ 2+42*n-25)/(2*n+3)/(26*n+1)/(n+1)*a(n-2)+31/2*(26*n+27)*(n-1)*(n-2)/(2*n+3)/(26 *n+1)/(n+1)*a(n-3) a(1) = 0, a(2) = 1, a(3) = 1 Just for fun, using this recurrence we get that a(1000) = 101662408407445423744168103476021587141989667612997719311488754154\ 322082931082374531255357681876619523150894345242770424947845903497434685\ 924396731064659870070402780338250399488998297800218606215611952870715670\ 616316141782311803128109822931518987777690811771955061426983735477927801\ 915580645830450923702686760277799803844656511972038824742386895372533429\ 74548248938307377609986379372338206473078793303158585992628 ------------------------------------------------------------- Theorem 12 : Let a(n) be number of words of length n in the alphabet, {-2, -1, 0, 1}, tha\ t sum-up to 0 and whose partial sums are never negative, in other words \ generalized Dyck words with alphabet, {-2, -1, 0, 1}, rather than {1,-1} Let X(t) be the ordinary genearting function of that sequence, in other word\ s infinity ----- \ n X(t) = ) a(n) t / ----- n = 0 X(t) satisifies the algebaric equation 3 3 2 2 t X(t) + t X(t) + (t - 1) X(t) + 1 = 0 and in Maple notation t^3*X(t)^3+t^2*X(t)^2+(t-1)*X(t)+1 = 0 For the sake of the OEIS here are the first 40 terms, starting with n=0 [1, 1, 2, 5, 13, 36, 104, 309, 939, 2905, 9118, 28964, 92940, 300808, 980864, 3219205, 10626023, 35252867, 117485454, 393133485, 1320357501, 4449298136, 15038769672, 50973266380, 173214422068, 589998043276, 2014026871496, 6889055189032, 23608722350440, 81049178840528, 278700885572096, 959835173086309 , 3310416757032159, 11432971961630999, 39535937094067710, 136883216842976943, 474465914711874487, 1646380234881262372, 5718752217030650552, 19883643328529880013, 69197975679197263363] Furthermore a(n) satisfies the following linear recurrence equation with pol\ ynomial coefficients 3 2 (143 n + 132 n - 17 n - 18) a(n - 1) a(n) = 1/2 -------------------------------------- (n + 1) (2 n + 3) (13 n - 1) 2 2 (n - 1) (26 n + 11 n - 6) a(n - 2) + ------------------------------------- (n + 1) (2 n + 3) (13 n - 1) 8 (13 n + 12) (n - 1) (n - 2) a(n - 3) + -------------------------------------- (n + 1) (2 n + 3) (13 n - 1) subject to the initial conditions a(1) = 1, a(2) = 2, a(3) = 5 and in Maple notation a(n) = 1/2*(143*n^3+132*n^2-17*n-18)/(n+1)/(2*n+3)/(13*n-1)*a(n-1)+2*(n-1)*(26* n^2+11*n-6)/(n+1)/(2*n+3)/(13*n-1)*a(n-2)+8*(13*n+12)*(n-1)*(n-2)/(n+1)/(2*n+3) /(13*n-1)*a(n-3) a(1) = 1, a(2) = 2, a(3) = 5 Just for fun, using this recurrence we get that a(1000) = 112718049543924946497817047468239461655675583843669943901464794765\ 533792111669532690580188378900348478962396154051472154606805143665500278\ 797461528775281470741871252428065570319092688394367917191513947824648673\ 529190684941558626782227996114319459384669364898834773886792148008545340\ 301080746770242890485768159647344818889692442357112107601225250847419471\ 248207409599029897356011756168126141752355941669112918936296621060064105\ 978604625766124118384397408012687929814034106507436273897154630784049444\ 82940579334994258331254210622965157469551755402098458848 Theorem 13 : Let a(n) be number of words of length n in the alphabet, {-2, -1, 2}, that s\ um-up to 0 and whose partial sums are never negative, in other words gen\ eralized Dyck words with alphabet, {-2, -1, 2}, rather than {1,-1} Let X(t) be the ordinary genearting function of that sequence, in other word\ s infinity ----- \ n X(t) = ) a(n) t / ----- n = 0 X(t) satisifies the algebaric equation 6 6 4 5 4 4 3 2 3 2 2 X(t) t - t X(t) - t X(t) + (t + 2 t ) X(t) - t X(t) - X(t) + 1 = 0 and in Maple notation X(t)^6*t^6-t^4*X(t)^5-t^4*X(t)^4+(t^3+2*t^2)*X(t)^3-t^2*X(t)^2-X(t)+1 = 0 For the sake of the OEIS here are the first 40 terms, starting with n=0 [1, 0, 1, 1, 2, 7, 8, 38, 58, 199, 452, 1149, 3277, 7650, 22696, 55726, 157502, 416967, 1128026, 3122336, 8365304, 23402737, 63505268, 176860650, 487957967, 1353427722, 3774616133, 10483218667, 29371164344, 81965145468, 230030965231, 645265199252, 1813615497166, 5107394107927, 14386545035342, 40621735594210, 114720169872202, 324560293765296, 918870098708832, 2604241833793991, 7388579097551618] ------------------------------------------------------------- Theorem 14 : Let a(n) be number of words of length n in the alphabet, {-2, -1, 0, 2}, tha\ t sum-up to 0 and whose partial sums are never negative, in other words \ generalized Dyck words with alphabet, {-2, -1, 0, 2}, rather than {1,-1} Let X(t) be the ordinary genearting function of that sequence, in other word\ s infinity ----- \ n X(t) = ) a(n) t / ----- n = 0 X(t) satisifies the algebaric equation 6 6 5 4 5 4 4 3 2 3 2 2 X(t) t + (t - t ) X(t) - t X(t) + (-t + 2 t ) X(t) - t X(t) + (t - 1) X(t) + 1 = 0 and in Maple notation X(t)^6*t^6+(t^5-t^4)*X(t)^5-t^4*X(t)^4+(-t^3+2*t^2)*X(t)^3-t^2*X(t)^2+(t-1)*X(t )+1 = 0 For the sake of the OEIS here are the first 40 terms, starting with n=0 [1, 1, 2, 5, 13, 38, 116, 368, 1203, 4016, 13642, 46987, 163696, 575816, 2042175, 7294299, 26215927, 94736708, 344015468, 1254647606, 4593682529, 16878510120, 62215957762, 230007985382, 852612196852, 3168359595108, 11800740083576, 44045606325107, 164721039237571, 617148978777583, 2316181581852586, 8706610827498169, 32777540164574119, 123570545078714196, 466475769211533776, 1763136562025613086, 6671991538484571985, 25276100101802859113, 95857089488037503932, 363893671750915858188, 1382735524079117907097] Theorem 15 : Let a(n) be number of words of length n in the alphabet, {-2, -1, 1, 2}, tha\ t sum-up to 0 and whose partial sums are never negative, in other words \ generalized Dyck words with alphabet, {-2, -1, 1, 2}, rather than {1,-1} Let X(t) be the ordinary genearting function of that sequence, in other word\ s infinity ----- \ n X(t) = ) a(n) t / ----- n = 0 X(t) satisifies the algebaric equation 5 5 4 3 4 3 2 3 2 2 X(t) t + (-t - t ) X(t) + (t + t ) X(t) + (t + t) X(t) + (-t - 1) X(t) + 1 = 0 and in Maple notation X(t)^5*t^5+(-t^4-t^3)*X(t)^4+(t^3+t^2)*X(t)^3+(t^2+t)*X(t)^2+(-t-1)*X(t)+1 = 0 For the sake of the OEIS here are the first 40 terms, starting with n=0 [1, 0, 2, 2, 11, 24, 93, 272, 971, 3194, 11293, 39148, 139687, 497756, 1798002, 6517194, 23807731, 87336870, 322082967, 1192381270, 4431889344, 16527495396, 61831374003, 231973133544, 872598922407, 3290312724374, 12434632908623, 47089829065940, 178672856753641, 679155439400068, 2585880086336653, 9861191391746256, 37660870323158835, 144029959800495438, 551546279543420059, 2114684919809270434, 8117356580480783638, 31193334574672753772, 119994768635233629431, 462054434301743595662, 1780873197452044558004] Furthermore a(n) satisfies the following linear recurrence equation with pol\ ynomial coefficients 3 2 (115 n - 137 n - 10 n + 8) a(n - 1) a(n) = 1/2 ------------------------------------- (n + 2) (2 n + 1) (5 n - 4) 3 2 2 (2 n - 1) (5 n + 36 n - 26 n - 12) a(n - 2) + ----------------------------------------------- (5 n - 4) (2 n + 1) (n + 2) (n + 1) 18 (2 n - 1) (2 n - 3) (5 n + 1) (n - 2) a(n - 3) - ------------------------------------------------- (5 n - 4) (2 n + 1) (n + 2) (n + 1) subject to the initial conditions a(1) = 0, a(2) = 2, a(3) = 2 and in Maple notation a(n) = 1/2*(115*n^3-137*n^2-10*n+8)/(n+2)/(2*n+1)/(5*n-4)*a(n-1)+2*(2*n-1)*(5*n ^3+36*n^2-26*n-12)/(5*n-4)/(2*n+1)/(n+2)/(n+1)*a(n-2)-18*(2*n-1)*(2*n-3)*(5*n+1 )*(n-2)/(5*n-4)/(2*n+1)/(n+2)/(n+1)*a(n-3) a(1) = 0, a(2) = 2, a(3) = 2 Just for fun, using this recurrence we get that a(1000) = 139772614195167149041902649127766436903551925875727337638913405792\ 188427840759653596921805327647421491676488876128470491737996281772463972\ 526011756289059749308949360125087666053197361320880341170796206360620046\ 084892661518534950720292745345618996380060652800662515682634801778993204\ 428242384583705725965881307883870135265032270058692426205930775501640122\ 673739659383912138077108863173906014654454042433096240687273593690994527\ 771254352886910806244345798404209186156571792318345924066204991414041717\ 886399654032454011666192547264833009820339622891603134887421286840377773\ 6525648777085877785246488234 ------------------------------------------------------------- Theorem 16 : Let a(n) be number of words of length n in the alphabet, {-2, -1, 0, 1, 2}, \ that sum-up to 0 and whose partial sums are never negative, in other wor\ ds generalized Dyck words with alphabet, {-2, -1, 0, 1, 2}, rather than {1,-1} Let X(t) be the ordinary genearting function of that sequence, in other word\ s infinity ----- \ n X(t) = ) a(n) t / ----- n = 0 X(t) satisifies the algebaric equation 5 5 4 3 3 2 2 X(t) t - X(t) t + X(t) t + X(t) t - X(t) + 1 = 0 and in Maple notation X(t)^5*t^5-X(t)^4*t^3+X(t)^3*t^2+X(t)^2*t-X(t)+1 = 0 For the sake of the OEIS here are the first 40 terms, starting with n=0 [1, 1, 3, 9, 32, 120, 473, 1925, 8034, 34188, 147787, 647141, 2864508, 12796238 , 57615322, 261197436, 1191268350, 5462080688, 25162978925, 116414836445, 540648963645, 2519574506595, 11779011525030, 55225888341334, 259612579655392, 1223396051745310, 5778116086462293, 27347124593409513, 129681868681425643, 616072123886855885, 2931681447103047687, 13972949818523099259, 66696500485420585110, 318803423221000803432, 1525852728670173719609, 7312059310463342118721, 35081215570214126170473, 168496226788080483702535, 810142199984165279526260, 3899102778065263063546530, 18783607897859472881263225 ] Furthermore a(n) satisfies the following linear recurrence equation with pol\ ynomial coefficients 3 2 (43 n - 48 n - 7 n + 2) a(n - 1) a(n) = 1/2 ---------------------------------- (n + 2) (2 n + 1) (n - 1) 4 3 2 (124 n - 370 n + 255 n + 15 n - 14) a(n - 2) - 1/2 ----------------------------------------------- (n - 1) (2 n + 1) (n + 2) (n + 1) 3 2 (n - 2) (2 n - 52 n + 65 n - 1) a(n - 3) + 5/2 ------------------------------------------ (n - 1) (2 n + 1) (n + 2) (n + 1) 2 (n - 2) (n - 3) (8 n - 8 n - 1) a(n - 4) + 25/2 ----------------------------------------- (n - 1) (2 n + 1) (n + 2) (n + 1) n (n - 2) (n - 3) (n - 4) a(n - 5) - 125/2 ---------------------------------- (n - 1) (2 n + 1) (n + 2) (n + 1) subject to the initial conditions a(1) = 1, a(2) = 3, a(3) = 9, a(4) = 32, a(5) = 120 and in Maple notation a(n) = 1/2*(43*n^3-48*n^2-7*n+2)/(n+2)/(2*n+1)/(n-1)*a(n-1)-1/2*(124*n^4-370*n^ 3+255*n^2+15*n-14)/(n-1)/(2*n+1)/(n+2)/(n+1)*a(n-2)+5/2*(n-2)*(2*n^3-52*n^2+65* n-1)/(n-1)/(2*n+1)/(n+2)/(n+1)*a(n-3)+25/2*(n-2)*(n-3)*(8*n^2-8*n-1)/(n-1)/(2*n +1)/(n+2)/(n+1)*a(n-4)-125/2*n*(n-2)*(n-3)*(n-4)/(n-1)/(2*n+1)/(n+2)/(n+1)*a(n-\ 5) a(1) = 1, a(2) = 3, a(3) = 9, a(4) = 32, a(5) = 120 Just for fun, using this recurrence we get that a(1000) = 158801694866092615434030418903180131269991930035948322878165849770\ 124878557978959836318829798778452130513039830780925989365841559907408917\ 515918991105166670872908147396909443913573768685983766827355847704626646\ 522232400170299904759924181859191511804097089504148239897842658229189085\ 124233168730330990799149842271911795528514567960697808122560410163803679\ 269478845942854423793560877845387992578123195506690343441228797084398100\ 634631387038933291981177729989887975467448374288984979348229271283804396\ 110297092369394584379330001545653615282672281892358282148573762337010500\ 488415083895205968308007002350792662810124632736821071592379119440056291\ 95063795310711589870050805877561931156564425556246025 -------------------------------- This ends this book that took, 3.060, seconds to create