Enumerating Generalized Dyck paths with alphabets consisting of integers from -3 to 3 By Shalosh B. Ekhad ------------------------------------------------------------- Theorem 1 : Let a(n) be number of words of length n in the alphabet, {-3, 1}, that sum-u\ p to 0 and whose partial sums are never negative, in other words general\ ized Dyck words with alphabet, {-3, 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 4 4 X(t) t - X(t) + 1 = 0 and in Maple notation X(t)^4*t^4-X(t)+1 = 0 For the sake of the OEIS here are the first 40 terms, starting with n=0 [1, 0, 0, 0, 1, 0, 0, 0, 4, 0, 0, 0, 22, 0, 0, 0, 140, 0, 0, 0, 969, 0, 0, 0, 7084, 0, 0, 0, 53820, 0, 0, 0, 420732, 0, 0, 0, 3362260, 0, 0, 0, 27343888] ------------------------------------------------------------- Theorem 2 : Let a(n) be number of words of length n in the alphabet, {-3, 0, 1}, that su\ m-up to 0 and whose partial sums are never negative, in other words gene\ ralized Dyck words with alphabet, {-3, 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 4 4 t X(t) + (t - 1) X(t) + 1 = 0 and in Maple notation t^4*X(t)^4+(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, 1, 2, 6, 16, 36, 75, 163, 391, 991, 2498, 6150, 15016, 37116, 93481, 238137, 607921, 1550401, 3959335, 10155615, 26182267, 67753907, 175713561, 456422121, 1187771521, 3097869841, 8097629671, 21207212047, 55628797891, 146129168651, 384401493333, 1012608918421, 2671045963125, 7054394743221, 18652371085976, 49371261259652, 130815961651922, 346957535076270, 921088107741179] Furthermore a(n) satisfies the following linear recurrence equation with pol\ ynomial coefficients 2 (2 n - 1) (18 n - 18 n - 7) a(n - 1) a(n) = ------------------------------------- n (3 n + 4) (3 n - 4) 2 (n - 1) (54 n - 108 n + 47) a(n - 2) - ------------------------------------- n (3 n + 4) (3 n - 4) 18 (n - 1) (n - 2) (2 n - 3) a(n - 3) + ------------------------------------- n (3 n + 4) (3 n - 4) (n - 1) (n - 2) (n - 3) a(n - 4) + 229/3 -------------------------------- n (3 n + 4) (3 n - 4) subject to the initial conditions a(1) = 1, a(2) = 1, a(3) = 1, a(4) = 2 and in Maple notation a(n) = (2*n-1)*(18*n^2-18*n-7)/n/(3*n+4)/(3*n-4)*a(n-1)-(n-1)*(54*n^2-108*n+47) /n/(3*n+4)/(3*n-4)*a(n-2)+18*(n-1)*(n-2)*(2*n-3)/n/(3*n+4)/(3*n-4)*a(n-3)+229/3 *(n-1)*(n-2)*(n-3)/n/(3*n+4)/(3*n-4)*a(n-4) a(1) = 1, a(2) = 1, a(3) = 1, a(4) = 2 Just for fun, using this recurrence we get that a(1000) = 231743437992686632226300726080995339062376202529945048733917363746\ 965082528237050546385515299339950845798586133134313734666364972092866060\ 847752936894302987691711038981119670131857987885505601288224193477874781\ 933791109170951999663092637018027842494894457053604936905794438444682716\ 143802042730214003851405549485414901179374534999320253139044232786016866\ 443101531075188866417706185034277654078514740827949795656641580431626392\ 6261088499 Theorem 3 : Let a(n) be number of words of length n in the alphabet, {-3, 2}, that sum-u\ p to 0 and whose partial sums are never negative, in other words general\ ized Dyck words with alphabet, {-3, 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 10 10 7 5 6 5 5 5 X(t) t + X(t) t - X(t) t + 2 X(t) t - X(t) + 1 = 0 and in Maple notation X(t)^10*t^10+X(t)^7*t^5-X(t)^6*t^5+2*X(t)^5*t^5-X(t)+1 = 0 For the sake of the OEIS here are the first 40 terms, starting with n=0 [1, 0, 0, 0, 0, 2, 0, 0, 0, 0, 23, 0, 0, 0, 0, 377, 0, 0, 0, 0, 7229, 0, 0, 0, 0, 151491, 0, 0, 0, 0, 3361598, 0, 0, 0, 0, 77635093, 0, 0, 0, 0, 1846620581] ------------------------------------------------------------- Theorem 4 : Let a(n) be number of words of length n in the alphabet, {-3, 0, 2}, that su\ m-up to 0 and whose partial sums are never negative, in other words gene\ ralized Dyck words with alphabet, {-3, 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 10 10 7 6 5 7 6 5 6 5 5 X(t) t + (t - 2 t + t ) X(t) + (t - t ) X(t) + 2 t X(t) + (t - 1) X(t) + 1 = 0 and in Maple notation X(t)^10*t^10+(t^7-2*t^6+t^5)*X(t)^7+(t^6-t^5)*X(t)^6+2*t^5*X(t)^5+(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, 1, 1, 3, 13, 43, 113, 253, 528, 1178, 3103, 9153, 27028, 75453, 198953, 510953, 1331203, 3609203, 10132634, 28762504, 80890514, 224031754, 614938259, 1691838522, 4703335222, 13220653447, 37382497972, 105697114147, 297957776877, 838064412777, 2358582333977, 6658223815277, 18867098851877, 53610064846798, 152500637451283, 433813670782263, 1233943961159183, 3511664702034048, 10006035051811618] Theorem 5 : Let a(n) be number of words of length n in the alphabet, {-3, 1, 2}, that su\ m-up to 0 and whose partial sums are never negative, in other words gene\ ralized Dyck words with alphabet, {-3, 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 10 10 8 8 5 7 6 5 6 5 5 t X(t) - t X(t) + t X(t) + (-t - t ) X(t) + 2 t X(t) 4 3 4 3 3 + (t + 3 t ) X(t) - t X(t) - X(t) + 1 = 0 and in Maple notation t^10*X(t)^10-t^8*X(t)^8+t^5*X(t)^7+(-t^6-t^5)*X(t)^6+2*t^5*X(t)^5+(t^4+3*t^3)*X (t)^4-t^3*X(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, 2, 1, 2, 17, 17, 43, 220, 322, 877, 3495, 6513, 18246, 63069, 137364, 389520, 1240075, 2986569, 8518188, 25878573, 66493272, 190276431, 563345305, 1509236554, 4329167366, 12645267502, 34810974533, 100065738510, 290410780163, 813932210810, 2344530239608, 6787557305833, 19254309739598, 55576193661986, 160849076903780, 460095808260232, 1330726621028529, 3854609838686679, 11091289883698738] ------------------------------------------------------------- Theorem 6 : Let a(n) be number of words of length n in the alphabet, {-3, 0, 1, 2}, that\ sum-up to 0 and whose partial sums are never negative, in other words g\ eneralized Dyck words with alphabet, {-3, 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 10 10 8 8 7 6 5 7 5 6 5 5 t X(t) - t X(t) + (t - 2 t + t ) X(t) - t X(t) + 2 t X(t) 4 3 4 3 3 + (-2 t + 3 t ) X(t) - t X(t) + (t - 1) X(t) + 1 = 0 and in Maple notation t^10*X(t)^10-t^8*X(t)^8+(t^7-2*t^6+t^5)*X(t)^7-t^5*X(t)^6+2*t^5*X(t)^5+(-2*t^4+ 3*t^3)*X(t)^4-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, 3, 10, 28, 85, 284, 950, 3194, 11022, 38663, 136648, 487293, 1753721, 6355487, 23165983, 84904035, 312705898, 1156649565, 4294810000, 16003643559, 59825332308, 224294452660, 843171200441, 3177498031365, 12001748172016, 45427657059164, 172285169942194, 654589135217652, 2491324791058185, 9496969190260568, 36256823075139673, 138613424885860426, 530635011047750827, 2033896545856682338, 7805022714021742130, 29985014430235892751, 115317102985146210440, 443934701340502461213, 1710640168411094685146] Theorem 7 : Let a(n) be number of words of length n in the alphabet, {-3, 1, 3}, that su\ m-up to 0 and whose partial sums are never negative, in other words gene\ ralized Dyck words with alphabet, {-3, 1, 3}, 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 20 20 18 19 18 18 16 17 16 14 16 t X(t) - t X(t) + t X(t) - 3 t X(t) + (t + 3 t ) X(t) 14 15 14 12 14 12 10 13 - 3 t X(t) + (5 t + 3 t ) X(t) + (-3 t - 3 t ) X(t) 12 10 12 10 8 11 + (2 t + 3 t ) X(t) + (-6 t - t ) X(t) 10 8 6 10 8 6 9 8 6 8 + (-4 t + 6 t + t ) X(t) + (-6 t - t ) X(t) + (2 t + 3 t ) X(t) 6 4 7 6 4 6 4 5 + (-3 t - 3 t ) X(t) + (5 t + 3 t ) X(t) - 3 t X(t) 4 2 4 2 3 2 2 + (t + 3 t ) X(t) - 3 t X(t) + t X(t) - X(t) + 1 = 0 and in Maple notation t^20*X(t)^20-t^18*X(t)^19+t^18*X(t)^18-3*t^16*X(t)^17+(t^16+3*t^14)*X(t)^16-3*t ^14*X(t)^15+(5*t^14+3*t^12)*X(t)^14+(-3*t^12-3*t^10)*X(t)^13+(2*t^12+3*t^10)*X( t)^12+(-6*t^10-t^8)*X(t)^11+(-4*t^10+6*t^8+t^6)*X(t)^10+(-6*t^8-t^6)*X(t)^9+(2* t^8+3*t^6)*X(t)^8+(-3*t^6-3*t^4)*X(t)^7+(5*t^6+3*t^4)*X(t)^6-3*t^4*X(t)^5+(t^4+ 3*t^2)*X(t)^4-3*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, 0, 3, 0, 16, 0, 100, 0, 655, 0, 4465, 0, 31599, 0, 230390, 0, 1717910 , 0, 13034753, 0, 100308732, 0, 781057488, 0, 6142515700, 0, 48719605150, 0, 389274014325, 0, 3130375135624, 0, 25315962247754, 0, 205765906922296, 0, 1679968849194124, 0, 13771490153093158] ------------------------------------------------------------- Theorem 8 : Let a(n) be number of words of length n in the alphabet, {-3, 0, 1, 3}, that\ sum-up to 0 and whose partial sums are never negative, in other words g\ eneralized Dyck words with alphabet, {-3, 0, 1, 3}, 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 20 20 19 18 19 18 18 17 16 17 t X(t) + (t - t ) X(t) + t X(t) + (3 t - 3 t ) X(t) 16 15 14 16 15 14 15 + (4 t - 6 t + 3 t ) X(t) + (3 t - 3 t ) X(t) 14 13 12 14 13 12 11 10 13 + (8 t - 6 t + 3 t ) X(t) + (6 t - 12 t + 9 t - 3 t ) X(t) 12 11 10 12 11 10 9 8 11 + (5 t - 6 t + 3 t ) X(t) + (7 t - 9 t + 3 t - t ) X(t) 10 9 8 7 6 10 + (3 t - 16 t + 12 t - 4 t + t ) X(t) 9 8 7 6 9 8 7 6 8 + (7 t - 9 t + 3 t - t ) X(t) + (5 t - 6 t + 3 t ) X(t) 7 6 5 4 7 6 5 4 6 + (6 t - 12 t + 9 t - 3 t ) X(t) + (8 t - 6 t + 3 t ) X(t) 5 4 5 4 3 2 4 3 2 3 + (3 t - 3 t ) X(t) + (4 t - 6 t + 3 t ) X(t) + (3 t - 3 t ) X(t) 2 2 + t X(t) + (t - 1) X(t) + 1 = 0 and in Maple notation t^20*X(t)^20+(t^19-t^18)*X(t)^19+t^18*X(t)^18+(3*t^17-3*t^16)*X(t)^17+(4*t^16-6 *t^15+3*t^14)*X(t)^16+(3*t^15-3*t^14)*X(t)^15+(8*t^14-6*t^13+3*t^12)*X(t)^14+(6 *t^13-12*t^12+9*t^11-3*t^10)*X(t)^13+(5*t^12-6*t^11+3*t^10)*X(t)^12+(7*t^11-9*t ^10+3*t^9-t^8)*X(t)^11+(3*t^10-16*t^9+12*t^8-4*t^7+t^6)*X(t)^10+(7*t^9-9*t^8+3* t^7-t^6)*X(t)^9+(5*t^8-6*t^7+3*t^6)*X(t)^8+(6*t^7-12*t^6+9*t^5-3*t^4)*X(t)^7+(8 *t^6-6*t^5+3*t^4)*X(t)^6+(3*t^5-3*t^4)*X(t)^5+(4*t^4-6*t^3+3*t^2)*X(t)^4+(3*t^3 -3*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, 4, 10, 26, 77, 239, 787, 2659, 9191, 32143, 113531, 403755, 1445012, 5200306, 18814519, 68408103, 249892428, 916815494, 3377157559, 12485749763, 46316370130, 172338774900, 643050671303, 2405574084191, 9020145833371, 33896154601987, 127632015424514, 481481331095110, 1819512373567996, 6887111753708552, 26108472965285573, 99116931981049829, 376790260011450152, 1434179336243916366, 5465482900924222364, 20851950412261916476, 79640115514045689401, 304480940692857483063, 1165223280108220473369] Theorem 9 : Let a(n) be number of words of length n in the alphabet, {-3, 2, 3}, that su\ m-up to 0 and whose partial sums are never negative, in other words gene\ ralized Dyck words with alphabet, {-3, 2, 3}, 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 20 20 18 19 18 18 16 17 14 16 t X(t) - t X(t) + t X(t) - 3 t X(t) + 3 t X(t) 15 14 15 14 13 12 14 + (2 t - 3 t ) X(t) + (3 t - t + 3 t ) X(t) 13 12 11 10 13 12 10 12 + (t - 3 t + t - 3 t ) X(t) + (3 t + 3 t ) X(t) 11 10 8 11 10 9 8 6 10 + (t - 6 t - t ) X(t) + (t - 6 t + 6 t + t ) X(t) 9 8 6 9 8 6 8 + (t - 6 t - t ) X(t) + (3 t + 3 t ) X(t) 7 6 5 4 7 6 5 4 6 + (t - 3 t + t - 3 t ) X(t) + (3 t - t + 3 t ) X(t) 5 4 5 2 4 2 3 2 2 + (2 t - 3 t ) X(t) + 3 t X(t) - 3 t X(t) + t X(t) - X(t) + 1 = 0 and in Maple notation t^20*X(t)^20-t^18*X(t)^19+t^18*X(t)^18-3*t^16*X(t)^17+3*t^14*X(t)^16+(2*t^15-3* t^14)*X(t)^15+(3*t^14-t^13+3*t^12)*X(t)^14+(t^13-3*t^12+t^11-3*t^10)*X(t)^13+(3 *t^12+3*t^10)*X(t)^12+(t^11-6*t^10-t^8)*X(t)^11+(t^10-6*t^9+6*t^8+t^6)*X(t)^10+ (t^9-6*t^8-t^6)*X(t)^9+(3*t^8+3*t^6)*X(t)^8+(t^7-3*t^6+t^5-3*t^4)*X(t)^7+(3*t^6 -t^5+3*t^4)*X(t)^6+(2*t^5-3*t^4)*X(t)^5+3*t^2*X(t)^4-3*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, 0, 2, 2, 5, 22, 14, 164, 65, 1030, 657, 5868, 7463, 31765, 73575, 173849, 631556, 1053086, 4877803, 7526655, 34948691, 61382672, 239407864, 524309309, 1621763388, 4415274965, 11255289437, 35813332389, 82153463817, 279458110861, 633479334487, 2118070224696, 5075741777630, 15824514104397, 41275863623366, 118428013850973, 334523141763061, 899513350738990, 2678023253678681] ------------------------------------------------------------- Theorem 10 : Let a(n) be number of words of length n in the alphabet, {-3, 0, 2, 3}, that\ sum-up to 0 and whose partial sums are never negative, in other words g\ eneralized Dyck words with alphabet, {-3, 0, 2, 3}, 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 20 20 19 18 19 18 18 17 16 17 t X(t) + (t - t ) X(t) + t X(t) + (3 t - 3 t ) X(t) 16 15 14 16 15 14 15 + (3 t - 6 t + 3 t ) X(t) + (5 t - 3 t ) X(t) 14 13 12 14 + (7 t - 7 t + 3 t ) X(t) 13 12 11 10 13 + (8 t - 14 t + 10 t - 3 t ) X(t) 12 11 10 12 11 10 9 8 11 + (6 t - 6 t + 3 t ) X(t) + (8 t - 9 t + 3 t - t ) X(t) 10 9 8 7 6 10 + (14 t - 22 t + 12 t - 4 t + t ) X(t) 9 8 7 6 9 8 7 6 8 + (8 t - 9 t + 3 t - t ) X(t) + (6 t - 6 t + 3 t ) X(t) 7 6 5 4 7 6 5 4 6 + (8 t - 14 t + 10 t - 3 t ) X(t) + (7 t - 7 t + 3 t ) X(t) 5 4 5 4 3 2 4 3 2 3 + (5 t - 3 t ) X(t) + (3 t - 6 t + 3 t ) X(t) + (3 t - 3 t ) X(t) 2 2 + t X(t) + (t - 1) X(t) + 1 = 0 and in Maple notation t^20*X(t)^20+(t^19-t^18)*X(t)^19+t^18*X(t)^18+(3*t^17-3*t^16)*X(t)^17+(3*t^16-6 *t^15+3*t^14)*X(t)^16+(5*t^15-3*t^14)*X(t)^15+(7*t^14-7*t^13+3*t^12)*X(t)^14+(8 *t^13-14*t^12+10*t^11-3*t^10)*X(t)^13+(6*t^12-6*t^11+3*t^10)*X(t)^12+(8*t^11-9* t^10+3*t^9-t^8)*X(t)^11+(14*t^10-22*t^9+12*t^8-4*t^7+t^6)*X(t)^10+(8*t^9-9*t^8+ 3*t^7-t^6)*X(t)^9+(6*t^8-6*t^7+3*t^6)*X(t)^8+(8*t^7-14*t^6+10*t^5-3*t^4)*X(t)^7 +(7*t^6-7*t^5+3*t^4)*X(t)^6+(5*t^5-3*t^4)*X(t)^5+(3*t^4-6*t^3+3*t^2)*X(t)^4+(3* t^3-3*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, 4, 9, 23, 63, 191, 611, 2043, 6995, 24285, 85002, 299032, 1056374, 3746277, 13339312, 47696449, 171274045, 617628946, 2236251077, 8127586687, 29643037040, 108460380396, 397996659534, 1464304342760, 5400380113098, 19960417936077, 73924963996529, 274298489892107, 1019553263777529, 3795780168219128, 14153139985026002, 52847639793506348, 197598425723999833, 739764573954668670, 2772843982944385426, 10405218264935053091, 39088130249804436831, 146988218686614545549, 553275975616690538969] Theorem 11 : Let a(n) be number of words of length n in the alphabet, {-3, 1, 2, 3}, that\ sum-up to 0 and whose partial sums are never negative, in other words g\ eneralized Dyck words with alphabet, {-3, 1, 2, 3}, 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 20 20 18 19 18 18 17 16 17 t X(t) - t X(t) + t X(t) + (-t - 3 t ) X(t) 16 15 14 16 15 14 15 + (t + 3 t + 3 t ) X(t) + (-2 t - 3 t ) X(t) 14 13 12 14 13 12 11 10 13 + (4 t + t + 3 t ) X(t) + (-5 t - 3 t - 2 t - 3 t ) X(t) 12 11 10 12 11 10 9 8 11 + (5 t + 5 t + 3 t ) X(t) + (-4 t - 6 t - t - t ) X(t) 10 9 8 6 10 9 8 7 6 9 + (t + 6 t + 6 t + t ) X(t) + (-4 t - 6 t - t - t ) X(t) 8 7 6 8 7 6 5 4 7 + (5 t + 5 t + 3 t ) X(t) + (-5 t - 3 t - 2 t - 3 t ) X(t) 6 5 4 6 5 4 5 + (4 t + t + 3 t ) X(t) + (-2 t - 3 t ) X(t) 4 3 2 4 3 2 3 2 2 + (t + 3 t + 3 t ) X(t) + (-t - 3 t ) X(t) + t X(t) - X(t) + 1 = 0 and in Maple notation t^20*X(t)^20-t^18*X(t)^19+t^18*X(t)^18+(-t^17-3*t^16)*X(t)^17+(t^16+3*t^15+3*t^ 14)*X(t)^16+(-2*t^15-3*t^14)*X(t)^15+(4*t^14+t^13+3*t^12)*X(t)^14+(-5*t^13-3*t^ 12-2*t^11-3*t^10)*X(t)^13+(5*t^12+5*t^11+3*t^10)*X(t)^12+(-4*t^11-6*t^10-t^9-t^ 8)*X(t)^11+(t^10+6*t^9+6*t^8+t^6)*X(t)^10+(-4*t^9-6*t^8-t^7-t^6)*X(t)^9+(5*t^8+ 5*t^7+3*t^6)*X(t)^8+(-5*t^7-3*t^6-2*t^5-3*t^4)*X(t)^7+(4*t^6+t^5+3*t^4)*X(t)^6+ (-2*t^5-3*t^4)*X(t)^5+(t^4+3*t^3+3*t^2)*X(t)^4+(-t^3-3*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, 2, 3, 16, 33, 115, 390, 1087, 4060, 12555, 42953, 148067, 492739, 1735298, 5944320, 20744252, 72905575, 254998049, 903660769, 3195209422, 11355589072, 40507136044, 144620988953, 518478617875, 1861257943227, 6697455408050, 24152234870325, 87226107921628, 315651869078757, 1143924927595869, 4151936835886485, 15091681888691404, 54925223488389666, 200157938880285184, 730258764785275647, 2667274260621421838, 9752675597285646950, 35695329641773808896, 130773052695581564343] ------------------------------------------------------------- Theorem 12 : Let a(n) be number of words of length n in the alphabet, {-3, 0, 1, 2, 3}, t\ hat sum-up to 0 and whose partial sums are never negative, in other word\ s generalized Dyck words with alphabet, {-3, 0, 1, 2, 3}, 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 20 20 19 18 19 18 18 17 16 17 t X(t) + (t - t ) X(t) + t X(t) + (2 t - 3 t ) X(t) 16 15 14 16 15 14 15 + (t - 3 t + 3 t ) X(t) + (t - 3 t ) X(t) 14 13 12 14 13 12 11 10 13 + (6 t - 5 t + 3 t ) X(t) + (-t - 8 t + 7 t - 3 t ) X(t) 12 11 10 12 11 10 9 8 11 + (3 t - t + 3 t ) X(t) + (2 t - 7 t + 2 t - t ) X(t) 10 9 8 7 6 10 + (2 t - 10 t + 12 t - 4 t + t ) X(t) 9 8 7 6 9 8 7 6 8 + (2 t - 7 t + 2 t - t ) X(t) + (3 t - t + 3 t ) X(t) 7 6 5 4 7 6 5 4 6 + (-t - 8 t + 7 t - 3 t ) X(t) + (6 t - 5 t + 3 t ) X(t) 5 4 5 4 3 2 4 3 2 3 + (t - 3 t ) X(t) + (t - 3 t + 3 t ) X(t) + (2 t - 3 t ) X(t) 2 2 + t X(t) + (t - 1) X(t) + 1 = 0 and in Maple notation t^20*X(t)^20+(t^19-t^18)*X(t)^19+t^18*X(t)^18+(2*t^17-3*t^16)*X(t)^17+(t^16-3*t ^15+3*t^14)*X(t)^16+(t^15-3*t^14)*X(t)^15+(6*t^14-5*t^13+3*t^12)*X(t)^14+(-t^13 -8*t^12+7*t^11-3*t^10)*X(t)^13+(3*t^12-t^11+3*t^10)*X(t)^12+(2*t^11-7*t^10+2*t^ 9-t^8)*X(t)^11+(2*t^10-10*t^9+12*t^8-4*t^7+t^6)*X(t)^10+(2*t^9-7*t^8+2*t^7-t^6) *X(t)^9+(3*t^8-t^7+3*t^6)*X(t)^8+(-t^7-8*t^6+7*t^5-3*t^4)*X(t)^7+(6*t^6-5*t^5+3 *t^4)*X(t)^6+(t^5-3*t^4)*X(t)^5+(t^4-3*t^3+3*t^2)*X(t)^4+(2*t^3-3*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, 6, 18, 62, 230, 879, 3481, 14108, 58158, 243314, 1029999, 4403397, 18985458, 82455222, 360393501, 1584051367, 6997128913, 31045539212, 138296932691, 618291385895, 2773304484578, 12476734334348, 56285216856132, 254555227938556, 1153929593249383, 5242169232823971, 23862180549759162, 108821946576020609, 497136987107388944, 2274783622443835103, 10424718711428141738, 47841928082007748190, 219855066265262106699, 1011612777729798723621, 4660274592113086968304, 21493142670920856200374, 99232429198268238875108, 458615453846739302558685, 2121597433893231246682433] Theorem 13 : 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 14 : 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 15 : Let a(n) be number of words of length n in the alphabet, {-2, 3}, that sum-u\ p to 0 and whose partial sums are never negative, in other words general\ ized Dyck words with alphabet, {-2, 3}, 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 10 10 7 5 6 5 5 5 X(t) t + X(t) t - X(t) t + 2 X(t) t - X(t) + 1 = 0 and in Maple notation X(t)^10*t^10+X(t)^7*t^5-X(t)^6*t^5+2*X(t)^5*t^5-X(t)+1 = 0 For the sake of the OEIS here are the first 40 terms, starting with n=0 [1, 0, 0, 0, 0, 2, 0, 0, 0, 0, 23, 0, 0, 0, 0, 377, 0, 0, 0, 0, 7229, 0, 0, 0, 0, 151491, 0, 0, 0, 0, 3361598, 0, 0, 0, 0, 77635093, 0, 0, 0, 0, 1846620581] ------------------------------------------------------------- Theorem 16 : Let a(n) be number of words of length n in the alphabet, {-2, 0, 3}, that su\ m-up to 0 and whose partial sums are never negative, in other words gene\ ralized Dyck words with alphabet, {-2, 0, 3}, 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 10 10 7 6 5 7 6 5 6 5 5 X(t) t + (t - 2 t + t ) X(t) + (t - t ) X(t) + 2 t X(t) + (t - 1) X(t) + 1 = 0 and in Maple notation X(t)^10*t^10+(t^7-2*t^6+t^5)*X(t)^7+(t^6-t^5)*X(t)^6+2*t^5*X(t)^5+(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, 1, 1, 3, 13, 43, 113, 253, 528, 1178, 3103, 9153, 27028, 75453, 198953, 510953, 1331203, 3609203, 10132634, 28762504, 80890514, 224031754, 614938259, 1691838522, 4703335222, 13220653447, 37382497972, 105697114147, 297957776877, 838064412777, 2358582333977, 6658223815277, 18867098851877, 53610064846798, 152500637451283, 433813670782263, 1233943961159183, 3511664702034048, 10006035051811618] Theorem 17 : 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 18 : 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 19 : Let a(n) be number of words of length n in the alphabet, {-2, 1, 3}, that su\ m-up to 0 and whose partial sums are never negative, in other words gene\ ralized Dyck words with alphabet, {-2, 1, 3}, 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 10 10 9 9 5 7 5 6 5 4 5 4 4 X(t) t + X(t) t + t X(t) - t X(t) + (2 t + 2 t ) X(t) + t X(t) 3 3 + t X(t) - X(t) + 1 = 0 and in Maple notation X(t)^10*t^10+X(t)^9*t^9+t^5*X(t)^7-t^5*X(t)^6+(2*t^5+2*t^4)*X(t)^5+t^4*X(t)^4+t ^3*X(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, 3, 2, 3, 23, 59, 74, 178, 753, 1859, 3299, 8937, 29884, 73955, 160368, 445889, 1334825, 3371535, 8167687, 22732271, 64550448, 166944853, 429281385, 1189787311, 3299504856, 8708248080, 23118437489, 63845014804, 175463878127, 470269479575, 1270311652558, 3501884445317, 9604857045847, 26027895342456, 71002490056153, 195692892371919, 537321155970160, 1467430337299719] ------------------------------------------------------------- Theorem 20 : Let a(n) be number of words of length n in the alphabet, {-2, 0, 1, 3}, that\ sum-up to 0 and whose partial sums are never negative, in other words g\ eneralized Dyck words with alphabet, {-2, 0, 1, 3}, 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 10 10 9 9 7 6 5 7 6 5 6 4 5 t X(t) + t X(t) + (t - 2 t + t ) X(t) + (t - t ) X(t) + 2 t X(t) 4 4 3 3 + t X(t) + t X(t) + (t - 1) X(t) + 1 = 0 and in Maple notation t^10*X(t)^10+t^9*X(t)^9+(t^7-2*t^6+t^5)*X(t)^7+(t^6-t^5)*X(t)^6+2*t^4*X(t)^5+t^ 4*X(t)^4+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, 8, 28, 81, 227, 706, 2400, 8218, 27572, 92406, 315573, 1097204, 3842170, 13477678, 47432830, 167903275, 597749633, 2136722448, 7660609975, 27543306011, 99328408241, 359233964164, 1302485284541, 4732909420882, 17233603840144, 62874796135573, 229816149753687, 841450305500412, 3085784363606663, 11333096919324658, 41681337991980060, 153500792575062725, 566007455062761383, 2089513818353579733, 7722398691273306152, 28570516961040998988, 105808295147677933280, 392225058781229252372] Theorem 21 : Let a(n) be number of words of length n in the alphabet, {-2, 2, 3}, that su\ m-up to 0 and whose partial sums are never negative, in other words gene\ ralized Dyck words with alphabet, {-2, 2, 3}, 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 10 10 7 8 7 5 7 6 5 6 5 4 5 X(t) t - t X(t) + (-t + t ) X(t) + (t - t ) X(t) + (2 t - t ) X(t) 4 4 2 3 2 2 - t X(t) + 2 t X(t) - t X(t) - X(t) + 1 = 0 and in Maple notation X(t)^10*t^10-t^7*X(t)^8+(-t^7+t^5)*X(t)^7+(t^6-t^5)*X(t)^6+(2*t^5-t^4)*X(t)^5-t ^4*X(t)^4+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, 0, 2, 2, 5, 17, 14, 103, 65, 544, 515, 2671, 4333, 12920, 32888, 66569, 225063, 389929, 1426875, 2581052, 8652846, 18130991, 51937472, 127733905 , 318505753, 879213643, 2034543521, 5892047281, 13539791786, 38764350879, 92547902870, 253609842517, 638716733669, 1670011621498, 4398787899731, 11151727980457, 30093346643625, 75616292374270, 204712934528781] ------------------------------------------------------------- Theorem 22 : Let a(n) be number of words of length n in the alphabet, {-2, 0, 2, 3}, that\ sum-up to 0 and whose partial sums are never negative, in other words g\ eneralized Dyck words with alphabet, {-2, 0, 2, 3}, 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 10 10 8 7 8 6 5 7 6 5 6 X(t) t + (t - t ) X(t) + (-2 t + t ) X(t) + (2 t - t ) X(t) 5 4 5 4 4 3 2 3 2 2 + (3 t - t ) X(t) - t X(t) + (-2 t + 2 t ) X(t) - t X(t) + (t - 1) X(t) + 1 = 0 and in Maple notation X(t)^10*t^10+(t^8-t^7)*X(t)^8+(-2*t^6+t^5)*X(t)^7+(2*t^6-t^5)*X(t)^6+(3*t^5-t^4 )*X(t)^5-t^4*X(t)^4+(-2*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, 4, 9, 23, 63, 186, 571, 1802, 5785, 18794, 61648, 203886, 679378, 2279317, 7694857, 26123728, 89136693, 305517029, 1051403044, 3631474197, 12584232291, 43739327631, 152443310597, 532646630266, 1865434035199, 6547198663406, 23024974603198, 81124275553139, 286323183150034, 1012202463501236, 3583762432337799, 12706670245662210, 45113691865323541, 160374580860936540, 570798147751318106, 2033860826371763212, 7254802601780451762, 25904290541981914555, 92584307842211819220] Theorem 23 : Let a(n) be number of words of length n in the alphabet, {-2, 1, 2, 3}, that\ sum-up to 0 and whose partial sums are never negative, in other words g\ eneralized Dyck words with alphabet, {-2, 1, 2, 3}, 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 10 10 9 9 7 8 7 5 7 6 5 6 t X(t) + t X(t) - t X(t) + (-t + t ) X(t) + (-2 t - t ) X(t) 5 4 5 3 2 3 2 2 + (2 t + t ) X(t) + (t + 2 t ) X(t) - t X(t) - X(t) + 1 = 0 and in Maple notation t^10*X(t)^10+t^9*X(t)^9-t^7*X(t)^8+(-t^7+t^5)*X(t)^7+(-2*t^6-t^5)*X(t)^6+(2*t^5 +t^4)*X(t)^5+(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, 5, 9, 31, 78, 248, 705, 2196, 6632, 20780, 64709, 204902, 650000, 2080483, 6683564, 21593311, 70024903, 228022074, 744976876, 2441850778, 8026618762, 26455041139, 87405982153, 289438774174, 960462359139, 3193366842536 , 10636635056279, 35489063311272, 118596791583351, 396914141297320, 1330230442462987, 4464042344334714, 14999217181926990, 50456596364848778, 169921812232536963, 572844723715864685, 1933116776188266041, 6529668152176835624] ------------------------------------------------------------- Theorem 24 : Let a(n) be number of words of length n in the alphabet, {-2, 0, 1, 2, 3}, t\ hat sum-up to 0 and whose partial sums are never negative, in other word\ s generalized Dyck words with alphabet, {-2, 0, 1, 2, 3}, 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 10 10 9 9 8 7 8 6 5 7 6 5 6 t X(t) + t X(t) + (t - t ) X(t) + (-2 t + t ) X(t) + (-t - t ) X(t) 5 4 5 3 2 3 2 2 + (t + t ) X(t) + (-t + 2 t ) X(t) - t X(t) + (t - 1) X(t) + 1 = 0 and in Maple notation t^10*X(t)^10+t^9*X(t)^9+(t^8-t^7)*X(t)^8+(-2*t^6+t^5)*X(t)^7+(-t^6-t^5)*X(t)^6+ (t^5+t^4)*X(t)^5+(-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, 16, 55, 196, 716, 2679, 10234, 39760, 156574, 623470, 2506019, 10154474, 41436046, 170126128, 702301074, 2913227672, 12136812234, 50760652587, 213050186816, 897078215872, 3788365153993, 16041350732675, 68093344462829, 289708176300213, 1235196411711532, 5276732820209448, 22583402165895227, 96817980060306005, 415735725394935606, 1787845988028491975, 7699365883451094554 , 33201372215592007538, 143350931388519425892, 619666943480177517360, 2681648237641916287037, 11617307394761213641949, 50378568161599401802592, 218675969476171281960739] Theorem 25 : 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 26 : 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 27 : 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 28 : 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 29 : Let a(n) be number of words of length n in the alphabet, {-1, 3}, that sum-u\ p to 0 and whose partial sums are never negative, in other words general\ ized Dyck words with alphabet, {-1, 3}, 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 4 4 X(t) t - X(t) + 1 = 0 and in Maple notation X(t)^4*t^4-X(t)+1 = 0 For the sake of the OEIS here are the first 40 terms, starting with n=0 [1, 0, 0, 0, 1, 0, 0, 0, 4, 0, 0, 0, 22, 0, 0, 0, 140, 0, 0, 0, 969, 0, 0, 0, 7084, 0, 0, 0, 53820, 0, 0, 0, 420732, 0, 0, 0, 3362260, 0, 0, 0, 27343888] ------------------------------------------------------------- Theorem 30 : Let a(n) be number of words of length n in the alphabet, {-1, 0, 3}, that su\ m-up to 0 and whose partial sums are never negative, in other words gene\ ralized Dyck words with alphabet, {-1, 0, 3}, 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 4 4 t X(t) + (t - 1) X(t) + 1 = 0 and in Maple notation t^4*X(t)^4+(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, 1, 2, 6, 16, 36, 75, 163, 391, 991, 2498, 6150, 15016, 37116, 93481, 238137, 607921, 1550401, 3959335, 10155615, 26182267, 67753907, 175713561, 456422121, 1187771521, 3097869841, 8097629671, 21207212047, 55628797891, 146129168651, 384401493333, 1012608918421, 2671045963125, 7054394743221, 18652371085976, 49371261259652, 130815961651922, 346957535076270, 921088107741179] Furthermore a(n) satisfies the following linear recurrence equation with pol\ ynomial coefficients 2 (2 n - 1) (18 n - 18 n - 7) a(n - 1) a(n) = ------------------------------------- n (3 n + 4) (3 n - 4) 2 (n - 1) (54 n - 108 n + 47) a(n - 2) - ------------------------------------- n (3 n + 4) (3 n - 4) 18 (n - 1) (n - 2) (2 n - 3) a(n - 3) + ------------------------------------- n (3 n + 4) (3 n - 4) (n - 1) (n - 2) (n - 3) a(n - 4) + 229/3 -------------------------------- n (3 n + 4) (3 n - 4) subject to the initial conditions a(1) = 1, a(2) = 1, a(3) = 1, a(4) = 2 and in Maple notation a(n) = (2*n-1)*(18*n^2-18*n-7)/n/(3*n+4)/(3*n-4)*a(n-1)-(n-1)*(54*n^2-108*n+47) /n/(3*n+4)/(3*n-4)*a(n-2)+18*(n-1)*(n-2)*(2*n-3)/n/(3*n+4)/(3*n-4)*a(n-3)+229/3 *(n-1)*(n-2)*(n-3)/n/(3*n+4)/(3*n-4)*a(n-4) a(1) = 1, a(2) = 1, a(3) = 1, a(4) = 2 Just for fun, using this recurrence we get that a(1000) = 231743437992686632226300726080995339062376202529945048733917363746\ 965082528237050546385515299339950845798586133134313734666364972092866060\ 847752936894302987691711038981119670131857987885505601288224193477874781\ 933791109170951999663092637018027842494894457053604936905794438444682716\ 143802042730214003851405549485414901179374534999320253139044232786016866\ 443101531075188866417706185034277654078514740827949795656641580431626392\ 6261088499 Theorem 31 : 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 32 : 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 33 : Let a(n) be number of words of length n in the alphabet, {-1, 1, 3}, that su\ m-up to 0 and whose partial sums are never negative, in other words gene\ ralized Dyck words with alphabet, {-1, 1, 3}, 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 4 4 2 2 X(t) t + X(t) t - X(t) + 1 = 0 and in Maple notation X(t)^4*t^4+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, 3, 0, 11, 0, 46, 0, 207, 0, 979, 0, 4797, 0, 24138, 0, 123998, 0, 647615, 0, 3428493, 0, 18356714, 0, 99229015, 0, 540807165, 0, 2968468275, 0, 16395456762, 0, 91053897066, 0, 508151297602, 0, 2848290555562, 0, 16028132445156] ------------------------------------------------------------- Theorem 34 : Let a(n) be number of words of length n in the alphabet, {-1, 0, 1, 3}, that\ sum-up to 0 and whose partial sums are never negative, in other words g\ eneralized Dyck words with alphabet, {-1, 0, 1, 3}, 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 4 4 2 2 t X(t) + t X(t) + (t - 1) X(t) + 1 = 0 and in Maple notation t^4*X(t)^4+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, 4, 10, 26, 72, 204, 593, 1753, 5263, 15995, 49127, 152231, 475359, 1494287, 4724903, 15017767, 47954400, 153764322, 494892393, 1598241869, 5177492708, 16820048006, 54785449703, 178873019471, 585312014446, 1919212203652 , 6305054573239, 20750506952675, 68405627426506, 225856342963732, 746807064830711, 2472761691513879, 8198212773239166, 27213692044392428, 90439467115506752, 300887392613150360, 1002076228695130756, 3340607738204162316 , 11146975093230149583] Furthermore a(n) satisfies the following linear recurrence equation with pol\ ynomial coefficients 5 4 3 2 (6084 n - 7722 n - 2894 n + 3471 n + 181 n - 240) a(n - 1) a(n) = -------------------------------------------------------------- n (3 n + 2) (3 n + 4) %1 4 3 2 (n - 1) (3718 n - 6578 n + 973 n + 3551 n - 848) a(n - 2) - 1/3 ------------------------------------------------------------ n (3 n + 2) (3 n + 4) %1 3 2 (n - 1) (n - 2) (14534 n - 18447 n - 7783 n + 6184) a(n - 3) - 2/3 -------------------------------------------------------------- n (3 n + 2) (3 n + 4) %1 2 (n - 1) (n - 2) (n - 3) (169 n + 39 n - 32) a(n - 4) + 257/3 ----------------------------------------------------- n (3 n + 2) (3 n + 4) %1 2 %1 := 169 n - 299 n + 98 subject to the initial conditions a(1) = 1, a(2) = 2, a(3) = 4, a(4) = 10 and in Maple notation a(n) = (6084*n^5-7722*n^4-2894*n^3+3471*n^2+181*n-240)/n/(3*n+2)/(3*n+4)/(169*n ^2-299*n+98)*a(n-1)-1/3*(n-1)*(3718*n^4-6578*n^3+973*n^2+3551*n-848)/n/(3*n+2)/ (3*n+4)/(169*n^2-299*n+98)*a(n-2)-2/3*(n-1)*(n-2)*(14534*n^3-18447*n^2-7783*n+ 6184)/n/(3*n+2)/(3*n+4)/(169*n^2-299*n+98)*a(n-3)+257/3*(n-1)*(n-2)*(n-3)*(169* n^2+39*n-32)/n/(3*n+2)/(3*n+4)/(169*n^2-299*n+98)*a(n-4) a(1) = 1, a(2) = 2, a(3) = 4, a(4) = 10 Just for fun, using this recurrence we get that a(1000) = 627137201682701361422584426858898117587060102006650962696837827734\ 136877524635225581241195421244904962177959831753253271108739917782565183\ 671487493297560364403128024264855123992994169014563340244830147363730961\ 504735235720347178392173233087844817491528700792583336471955085515913829\ 447165186502590283596001677192856912353383018537015835286967850692704470\ 870357878180831282635566688341539593632317448334596239780340863755726857\ 936299999287665544832163642853832229302779380838518339323368491357327472\ 9358927458214966351371496405214867403 Theorem 35 : Let a(n) be number of words of length n in the alphabet, {-1, 2, 3}, that su\ m-up to 0 and whose partial sums are never negative, in other words gene\ ralized Dyck words with alphabet, {-1, 2, 3}, 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 4 4 3 3 X(t) t + X(t) t - X(t) + 1 = 0 and in Maple notation X(t)^4*t^4+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, 1, 0, 3, 7, 4, 12, 45, 55, 77, 286, 546, 728, 1960, 4760, 7548, 15504, 39729, 75582, 140448, 336490, 723327, 1366200, 2992990, 6758895, 13522275, 28094040, 63183315, 133231800, 273896532, 600805296, 1305229332, 2720740792, 5843241088, 12797739672, 27206642716, 57941746476, 126405822608] Furthermore a(n) satisfies the following linear recurrence equation with pol\ ynomial coefficients 4 3 2 (383223 n - 1242382 n + 742077 n + 191578 n - 69216) a(n - 1) a(n) = 1/3 ---------------------------------------------------------------- (3 n + 2) (3 n + 4) (327 n - 721) (n + 1) 3 2 (n - 2) (29271 n - 78016 n + 36331 n + 1854) a(n - 2) - 2/3 ------------------------------------------------------- (3 n + 2) (3 n + 4) (327 n - 721) (n + 1) 3 2 2 (n - 2) (24609 n - 77965 n + 19183 n + 54053) a(n - 3) + ---------------------------------------------------------- (3 n + 2) (3 n + 4) (327 n - 721) (n + 1) 2 (n - 2) (n - 3) (2640957 n - 7454897 n + 2159600) a(n - 4) - 1/3 ----------------------------------------------------------- (3 n + 2) (3 n + 4) (327 n - 721) (n + 1) (2829 n - 709) (n - 2) (n - 3) (n - 4) a(n - 5) - 1145/3 ----------------------------------------------- (3 n + 2) (3 n + 4) (327 n - 721) (n + 1) subject to the initial conditions a(1) = 0, a(2) = 0, a(3) = 1, a(4) = 1, a(5) = 0 and in Maple notation a(n) = 1/3*(383223*n^4-1242382*n^3+742077*n^2+191578*n-69216)/(3*n+2)/(3*n+4)/( 327*n-721)/(n+1)*a(n-1)-2/3*(n-2)*(29271*n^3-78016*n^2+36331*n+1854)/(3*n+2)/(3 *n+4)/(327*n-721)/(n+1)*a(n-2)+2*(n-2)*(24609*n^3-77965*n^2+19183*n+54053)/(3*n +2)/(3*n+4)/(327*n-721)/(n+1)*a(n-3)-1/3*(n-2)*(n-3)*(2640957*n^2-7454897*n+ 2159600)/(3*n+2)/(3*n+4)/(327*n-721)/(n+1)*a(n-4)-1145/3*(2829*n-709)*(n-2)*(n-\ 3)*(n-4)/(3*n+2)/(3*n+4)/(327*n-721)/(n+1)*a(n-5) a(1) = 0, a(2) = 0, a(3) = 1, a(4) = 1, a(5) = 0 Just for fun, using this recurrence we get that a(1000) = 142781710629015524207637432785021308704945680033375594485837481678\ 328371857670078135480761741153013794013169714968725977111270123270602909\ 900766312469843046814338918214346172411218534535814528882610865730549473\ 241912425599088119142538347809711262414223382460829847812746130469195655\ 917521308467938300107456958458135458174855125661281877694707668 ------------------------------------------------------------- Theorem 36 : Let a(n) be number of words of length n in the alphabet, {-1, 0, 2, 3}, that\ sum-up to 0 and whose partial sums are never negative, in other words g\ eneralized Dyck words with alphabet, {-1, 0, 2, 3}, 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 4 4 3 3 t X(t) + t X(t) + (t - 1) X(t) + 1 = 0 and in Maple notation t^4*X(t)^4+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, 6, 16, 39, 99, 271, 763, 2146, 6062, 17359, 50337, 147057, 431874, 1275273, 3786649, 11298031, 33846202, 101762937, 306997821, 929038518, 2819426688, 8578433304, 26163061776, 79970186791, 244938841096, 751646959402, 2310683396056, 7115199919151, 21943632512859, 67774020321241, 209610712661673, 649119613899321, 2012637248834018, 6247508516101772, 19414317844210898, 60393022343470489, 188052033815206409, 586104316792820973] Furthermore a(n) satisfies the following linear recurrence equation with pol\ ynomial coefficients 4 3 2 (46327 n - 124888 n + 73583 n + 16702 n - 7584) a(n - 1) a(n) = 1/3 ----------------------------------------------------------- (n + 1) (3 n + 2) (3 n + 4) (73 n - 79) 4 3 2 12 (4761 n - 21773 n + 33153 n - 18673 n + 3132) a(n - 2) - ------------------------------------------------------------ (n + 1) (3 n + 2) (3 n + 4) (73 n - 79) 3 2 54 (n - 2) (1716 n - 6935 n + 7922 n - 1803) a(n - 3) + ------------------------------------------------------- (n + 1) (3 n + 2) (3 n + 4) (73 n - 79) 486 (2 n - 5) (157 n - 57) (n - 2) (n - 3) a(n - 4) - --------------------------------------------------- (n + 1) (3 n + 2) (3 n + 4) (73 n - 79) subject to the initial conditions a(1) = 1, a(2) = 1, a(3) = 2, a(4) = 6 and in Maple notation a(n) = 1/3*(46327*n^4-124888*n^3+73583*n^2+16702*n-7584)/(n+1)/(3*n+2)/(3*n+4)/ (73*n-79)*a(n-1)-12*(4761*n^4-21773*n^3+33153*n^2-18673*n+3132)/(n+1)/(3*n+2)/( 3*n+4)/(73*n-79)*a(n-2)+54*(n-2)*(1716*n^3-6935*n^2+7922*n-1803)/(n+1)/(3*n+2)/ (3*n+4)/(73*n-79)*a(n-3)-486*(2*n-5)*(157*n-57)*(n-2)*(n-3)/(n+1)/(3*n+2)/(3*n+ 4)/(73*n-79)*a(n-4) a(1) = 1, a(2) = 1, a(3) = 2, a(4) = 6 Just for fun, using this recurrence we get that a(1000) = 111676546007861618828942522116366840725976140366076436210341516041\ 266885268506528426214657961820233673278584826973308607929343758757441563\ 948347666983702778821570875700646611714217918337516723749545182128479990\ 235923023909686505832691385122577348773962391097149354387245858994960558\ 194272761554011155549104984069070408541565316376301071426602236824449663\ 851699256119932161985687905487500352939766363660082985592196632940712476\ 881388689035559798831807878997651994286357191911496314077096865878777495\ 87744133 Theorem 37 : Let a(n) be number of words of length n in the alphabet, {-1, 1, 2, 3}, that\ sum-up to 0 and whose partial sums are never negative, in other words g\ eneralized Dyck words with alphabet, {-1, 1, 2, 3}, 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 4 4 3 3 2 2 X(t) t + X(t) t + X(t) t - X(t) + 1 = 0 and in Maple notation X(t)^4*t^4+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, 3, 5, 14, 28, 74, 168, 432, 1045, 2684, 6721, 17355, 44408, 115502 , 299812, 785570, 2060094, 5434475, 14362841, 38114760, 101360402, 270373303, 722696570, 1936398635, 5198249550, 13982513625, 37674988080, 101685303765, 274867141845, 744093631842, 2017066320624, 5474900965050, 14878450339822, 40479971557162, 110253945275970, 300605644859552, 820399033872096, 2241084167717824] Furthermore a(n) satisfies the following linear recurrence equation with pol\ ynomial coefficients 4 3 2 (2177255 n - 7596148 n + 5392195 n + 643078 n - 697632) a(n - 1) a(n) = 1/3 ------------------------------------------------------------------- (3 n + 4) (n + 1) (5045 n - 7267) (3 n + 2) 4 3 2 (1846645 n - 6665962 n + 7690229 n - 2401076 n - 144828) a(n - 2) + 1/3 -------------------------------------------------------------------- (3 n + 4) (n + 1) (5045 n - 7267) (3 n + 2) 3 2 (n - 2) (9957995 n - 47994027 n + 64131424 n - 21792366) a(n - 3) - 1/3 ------------------------------------------------------------------- (3 n + 4) (n + 1) (5045 n - 7267) (3 n + 2) 2 (n - 2) (n - 3) (19850205 n - 61572608 n + 22999478) a(n - 4) - 1/3 -------------------------------------------------------------- (3 n + 4) (n + 1) (5045 n - 7267) (3 n + 2) (83255 n - 31418) (n - 2) (n - 3) (n - 4) a(n - 5) - 257/3 -------------------------------------------------- (3 n + 4) (n + 1) (5045 n - 7267) (3 n + 2) subject to the initial conditions a(1) = 0, a(2) = 1, a(3) = 1, a(4) = 3, a(5) = 5 and in Maple notation a(n) = 1/3*(2177255*n^4-7596148*n^3+5392195*n^2+643078*n-697632)/(3*n+4)/(n+1)/ (5045*n-7267)/(3*n+2)*a(n-1)+1/3*(1846645*n^4-6665962*n^3+7690229*n^2-2401076*n -144828)/(3*n+4)/(n+1)/(5045*n-7267)/(3*n+2)*a(n-2)-1/3*(n-2)*(9957995*n^3-\ 47994027*n^2+64131424*n-21792366)/(3*n+4)/(n+1)/(5045*n-7267)/(3*n+2)*a(n-3)-1/ 3*(n-2)*(n-3)*(19850205*n^2-61572608*n+22999478)/(3*n+4)/(n+1)/(5045*n-7267)/(3 *n+2)*a(n-4)-257/3*(83255*n-31418)*(n-2)*(n-3)*(n-4)/(3*n+4)/(n+1)/(5045*n-7267 )/(3*n+2)*a(n-5) a(1) = 0, a(2) = 1, a(3) = 1, a(4) = 3, a(5) = 5 Just for fun, using this recurrence we get that a(1000) = 435664937395013763787949579947984439584655565053233018263110658753\ 756208596803266887752602685360416819037939099907684543965531805330122822\ 028820144707111347228638419654525604014546772038884881826115094150090391\ 408270179162739057381181319825114086188469476854311934325015555718644409\ 136497974862056469106782342137085649208845212489297912951176488788681344\ 074162655693945522326874272619565681044420720296127403270759070332728078\ 5785975030073749500364 ------------------------------------------------------------- Theorem 38 : Let a(n) be number of words of length n in the alphabet, {-1, 0, 1, 2, 3}, t\ hat sum-up to 0 and whose partial sums are never negative, in other word\ s generalized Dyck words with alphabet, {-1, 0, 1, 2, 3}, 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 4 4 3 3 2 2 t X(t) + t X(t) + t X(t) + (t - 1) X(t) + 1 = 0 and in Maple notation t^4*X(t)^4+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, 14, 41, 125, 393, 1265, 4147, 13798, 46476, 158170, 543050, 1878670, 6542330, 22915999, 80682987, 285378270, 1013564805, 3613262795, 12924536005, 46373266470, 166856922125, 601928551824, 2176616383346, 7888184659826, 28645799759632, 104224861693855, 379885129946864, 1386926469714491, 5071414788349655, 18571114244497835, 68099230660004675, 250038808009880790, 919183172864105235, 3382962549917829020, 12464250091478255375, 45971046526098151125, 169718503374474353075, 627161711811600906925] Furthermore a(n) satisfies the following linear recurrence equation with pol\ ynomial coefficients 4 3 2 (111457 n - 364730 n + 228995 n + 19310 n - 33312) a(n - 1) a(n) = 1/3 -------------------------------------------------------------- (3 n + 2) (133 n - 347) (3 n + 4) (n + 1) 4 3 2 (68503 n - 346618 n + 590627 n - 397748 n + 90564) a(n - 2) - 5/3 -------------------------------------------------------------- (3 n + 2) (133 n - 347) (3 n + 4) (n + 1) 3 2 (n - 2) (1933 n - 9435 n + 14354 n - 7518) a(n - 3) - 25/3 ----------------------------------------------------- (3 n + 2) (133 n - 347) (3 n + 4) (n + 1) 2 (n - 2) (n - 3) (1333 n - 4384 n + 2718) a(n - 4) - 125/3 -------------------------------------------------- (3 n + 2) (133 n - 347) (3 n + 4) (n + 1) (733 n - 400) (n - 2) (n - 3) (n - 4) a(n - 5) - 625/3 ---------------------------------------------- (3 n + 2) (133 n - 347) (3 n + 4) (n + 1) subject to the initial conditions a(1) = 1, a(2) = 2, a(3) = 5, a(4) = 14, a(5) = 41 and in Maple notation a(n) = 1/3*(111457*n^4-364730*n^3+228995*n^2+19310*n-33312)/(3*n+2)/(133*n-347) /(3*n+4)/(n+1)*a(n-1)-5/3*(68503*n^4-346618*n^3+590627*n^2-397748*n+90564)/(3*n +2)/(133*n-347)/(3*n+4)/(n+1)*a(n-2)-25/3*(n-2)*(1933*n^3-9435*n^2+14354*n-7518 )/(3*n+2)/(133*n-347)/(3*n+4)/(n+1)*a(n-3)-125/3*(n-2)*(n-3)*(1333*n^2-4384*n+ 2718)/(3*n+2)/(133*n-347)/(3*n+4)/(n+1)*a(n-4)-625/3*(733*n-400)*(n-2)*(n-3)*(n -4)/(3*n+2)/(133*n-347)/(3*n+4)/(n+1)*a(n-5) a(1) = 1, a(2) = 2, a(3) = 5, a(4) = 14, a(5) = 41 Just for fun, using this recurrence we get that a(1000) = 117711848358311507260501387450472721192196780278057100773141629457\ 874549270935251680967630248998259630513560544734950180528735564258216410\ 768101409514739674823181662227396770728090832354033859082570512348398794\ 132270732161950316476493826456852828897097622431227426259093467430724875\ 518644407663649770737001565751229059320413263413446107962205949393372351\ 729403777736808047472181812619862819908851807149180742176833625681554567\ 135995935399985938640715789068549459810334387377454614535889797814949170\ 492174615667138189874262655322845442819474979342277457355041027689452773\ 3576496425 Theorem 39 : Let a(n) be number of words of length n in the alphabet, {-3, -2, 1}, that s\ um-up to 0 and whose partial sums are never negative, in other words gen\ eralized Dyck words with alphabet, {-3, -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 4 4 3 3 X(t) t + X(t) t - X(t) + 1 = 0 and in Maple notation X(t)^4*t^4+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, 1, 0, 3, 7, 4, 12, 45, 55, 77, 286, 546, 728, 1960, 4760, 7548, 15504, 39729, 75582, 140448, 336490, 723327, 1366200, 2992990, 6758895, 13522275, 28094040, 63183315, 133231800, 273896532, 600805296, 1305229332, 2720740792, 5843241088, 12797739672, 27206642716, 57941746476, 126405822608] Furthermore a(n) satisfies the following linear recurrence equation with pol\ ynomial coefficients 4 3 2 (383223 n - 1242382 n + 742077 n + 191578 n - 69216) a(n - 1) a(n) = 1/3 ---------------------------------------------------------------- (3 n + 2) (3 n + 4) (327 n - 721) (n + 1) 3 2 (n - 2) (29271 n - 78016 n + 36331 n + 1854) a(n - 2) - 2/3 ------------------------------------------------------- (3 n + 2) (3 n + 4) (327 n - 721) (n + 1) 3 2 2 (n - 2) (24609 n - 77965 n + 19183 n + 54053) a(n - 3) + ---------------------------------------------------------- (3 n + 2) (3 n + 4) (327 n - 721) (n + 1) 2 (n - 2) (n - 3) (2640957 n - 7454897 n + 2159600) a(n - 4) - 1/3 ----------------------------------------------------------- (3 n + 2) (3 n + 4) (327 n - 721) (n + 1) (2829 n - 709) (n - 2) (n - 3) (n - 4) a(n - 5) - 1145/3 ----------------------------------------------- (3 n + 2) (3 n + 4) (327 n - 721) (n + 1) subject to the initial conditions a(1) = 0, a(2) = 0, a(3) = 1, a(4) = 1, a(5) = 0 and in Maple notation a(n) = 1/3*(383223*n^4-1242382*n^3+742077*n^2+191578*n-69216)/(3*n+2)/(3*n+4)/( 327*n-721)/(n+1)*a(n-1)-2/3*(n-2)*(29271*n^3-78016*n^2+36331*n+1854)/(3*n+2)/(3 *n+4)/(327*n-721)/(n+1)*a(n-2)+2*(n-2)*(24609*n^3-77965*n^2+19183*n+54053)/(3*n +2)/(3*n+4)/(327*n-721)/(n+1)*a(n-3)-1/3*(n-2)*(n-3)*(2640957*n^2-7454897*n+ 2159600)/(3*n+2)/(3*n+4)/(327*n-721)/(n+1)*a(n-4)-1145/3*(2829*n-709)*(n-2)*(n-\ 3)*(n-4)/(3*n+2)/(3*n+4)/(327*n-721)/(n+1)*a(n-5) a(1) = 0, a(2) = 0, a(3) = 1, a(4) = 1, a(5) = 0 Just for fun, using this recurrence we get that a(1000) = 142781710629015524207637432785021308704945680033375594485837481678\ 328371857670078135480761741153013794013169714968725977111270123270602909\ 900766312469843046814338918214346172411218534535814528882610865730549473\ 241912425599088119142538347809711262414223382460829847812746130469195655\ 917521308467938300107456958458135458174855125661281877694707668 ------------------------------------------------------------- Theorem 40 : Let a(n) be number of words of length n in the alphabet, {-3, -2, 0, 1}, tha\ t sum-up to 0 and whose partial sums are never negative, in other words \ generalized Dyck words with alphabet, {-3, -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 4 4 3 3 t X(t) + t X(t) + (t - 1) X(t) + 1 = 0 and in Maple notation t^4*X(t)^4+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, 6, 16, 39, 99, 271, 763, 2146, 6062, 17359, 50337, 147057, 431874, 1275273, 3786649, 11298031, 33846202, 101762937, 306997821, 929038518, 2819426688, 8578433304, 26163061776, 79970186791, 244938841096, 751646959402, 2310683396056, 7115199919151, 21943632512859, 67774020321241, 209610712661673, 649119613899321, 2012637248834018, 6247508516101772, 19414317844210898, 60393022343470489, 188052033815206409, 586104316792820973] Furthermore a(n) satisfies the following linear recurrence equation with pol\ ynomial coefficients 4 3 2 (46327 n - 124888 n + 73583 n + 16702 n - 7584) a(n - 1) a(n) = 1/3 ----------------------------------------------------------- (n + 1) (3 n + 2) (3 n + 4) (73 n - 79) 4 3 2 12 (4761 n - 21773 n + 33153 n - 18673 n + 3132) a(n - 2) - ------------------------------------------------------------ (n + 1) (3 n + 2) (3 n + 4) (73 n - 79) 3 2 54 (n - 2) (1716 n - 6935 n + 7922 n - 1803) a(n - 3) + ------------------------------------------------------- (n + 1) (3 n + 2) (3 n + 4) (73 n - 79) 486 (2 n - 5) (157 n - 57) (n - 2) (n - 3) a(n - 4) - --------------------------------------------------- (n + 1) (3 n + 2) (3 n + 4) (73 n - 79) subject to the initial conditions a(1) = 1, a(2) = 1, a(3) = 2, a(4) = 6 and in Maple notation a(n) = 1/3*(46327*n^4-124888*n^3+73583*n^2+16702*n-7584)/(n+1)/(3*n+2)/(3*n+4)/ (73*n-79)*a(n-1)-12*(4761*n^4-21773*n^3+33153*n^2-18673*n+3132)/(n+1)/(3*n+2)/( 3*n+4)/(73*n-79)*a(n-2)+54*(n-2)*(1716*n^3-6935*n^2+7922*n-1803)/(n+1)/(3*n+2)/ (3*n+4)/(73*n-79)*a(n-3)-486*(2*n-5)*(157*n-57)*(n-2)*(n-3)/(n+1)/(3*n+2)/(3*n+ 4)/(73*n-79)*a(n-4) a(1) = 1, a(2) = 1, a(3) = 2, a(4) = 6 Just for fun, using this recurrence we get that a(1000) = 111676546007861618828942522116366840725976140366076436210341516041\ 266885268506528426214657961820233673278584826973308607929343758757441563\ 948347666983702778821570875700646611714217918337516723749545182128479990\ 235923023909686505832691385122577348773962391097149354387245858994960558\ 194272761554011155549104984069070408541565316376301071426602236824449663\ 851699256119932161985687905487500352939766363660082985592196632940712476\ 881388689035559798831807878997651994286357191911496314077096865878777495\ 87744133 Theorem 41 : Let a(n) be number of words of length n in the alphabet, {-3, -2, 2}, that s\ um-up to 0 and whose partial sums are never negative, in other words gen\ eralized Dyck words with alphabet, {-3, -2, 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 10 10 7 8 7 5 7 6 5 6 5 4 5 t X(t) - t X(t) + (-t + t ) X(t) + (t - t ) X(t) + (2 t - t ) X(t) 4 4 2 3 2 2 - t X(t) + 2 t X(t) - t X(t) - X(t) + 1 = 0 and in Maple notation t^10*X(t)^10-t^7*X(t)^8+(-t^7+t^5)*X(t)^7+(t^6-t^5)*X(t)^6+(2*t^5-t^4)*X(t)^5-t ^4*X(t)^4+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, 0, 2, 2, 5, 17, 14, 103, 65, 544, 515, 2671, 4333, 12920, 32888, 66569, 225063, 389929, 1426875, 2581052, 8652846, 18130991, 51937472, 127733905 , 318505753, 879213643, 2034543521, 5892047281, 13539791786, 38764350879, 92547902870, 253609842517, 638716733669, 1670011621498, 4398787899731, 11151727980457, 30093346643625, 75616292374270, 204712934528781] ------------------------------------------------------------- Theorem 42 : Let a(n) be number of words of length n in the alphabet, {-3, -2, 0, 2}, tha\ t sum-up to 0 and whose partial sums are never negative, in other words \ generalized Dyck words with alphabet, {-3, -2, 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 10 10 8 7 8 6 5 7 6 5 6 t X(t) + (t - t ) X(t) + (-2 t + t ) X(t) + (2 t - t ) X(t) 5 4 5 4 4 3 2 3 2 2 + (3 t - t ) X(t) - t X(t) + (-2 t + 2 t ) X(t) - X(t) t + (t - 1) X(t) + 1 = 0 and in Maple notation t^10*X(t)^10+(t^8-t^7)*X(t)^8+(-2*t^6+t^5)*X(t)^7+(2*t^6-t^5)*X(t)^6+(3*t^5-t^4 )*X(t)^5-t^4*X(t)^4+(-2*t^3+2*t^2)*X(t)^3-X(t)^2*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, 4, 9, 23, 63, 186, 571, 1802, 5785, 18794, 61648, 203886, 679378, 2279317, 7694857, 26123728, 89136693, 305517029, 1051403044, 3631474197, 12584232291, 43739327631, 152443310597, 532646630266, 1865434035199, 6547198663406, 23024974603198, 81124275553139, 286323183150034, 1012202463501236, 3583762432337799, 12706670245662210, 45113691865323541, 160374580860936540, 570798147751318106, 2033860826371763212, 7254802601780451762, 25904290541981914555, 92584307842211819220] Theorem 43 : Let a(n) be number of words of length n in the alphabet, {-3, -2, 3}, that s\ um-up to 0 and whose partial sums are never negative, in other words gen\ eralized Dyck words with alphabet, {-3, -2, 3}, 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 20 20 18 19 18 18 16 17 14 16 t X(t) - t X(t) + t X(t) - 3 t X(t) + 3 t X(t) 15 14 15 14 13 12 14 + (2 t - 3 t ) X(t) + (3 t - t + 3 t ) X(t) 13 12 11 10 13 12 10 12 + (t - 3 t + t - 3 t ) X(t) + (3 t + 3 t ) X(t) 11 10 8 11 10 9 8 6 10 + (t - 6 t - t ) X(t) + (t - 6 t + 6 t + t ) X(t) 9 8 6 9 8 6 8 + (t - 6 t - t ) X(t) + (3 t + 3 t ) X(t) 7 6 5 4 7 6 5 4 6 + (t - 3 t + t - 3 t ) X(t) + (3 t - t + 3 t ) X(t) 5 4 5 2 4 2 3 2 2 + (2 t - 3 t ) X(t) + 3 t X(t) - 3 t X(t) + t X(t) - X(t) + 1 = 0 and in Maple notation t^20*X(t)^20-t^18*X(t)^19+t^18*X(t)^18-3*t^16*X(t)^17+3*t^14*X(t)^16+(2*t^15-3* t^14)*X(t)^15+(3*t^14-t^13+3*t^12)*X(t)^14+(t^13-3*t^12+t^11-3*t^10)*X(t)^13+(3 *t^12+3*t^10)*X(t)^12+(t^11-6*t^10-t^8)*X(t)^11+(t^10-6*t^9+6*t^8+t^6)*X(t)^10+ (t^9-6*t^8-t^6)*X(t)^9+(3*t^8+3*t^6)*X(t)^8+(t^7-3*t^6+t^5-3*t^4)*X(t)^7+(3*t^6 -t^5+3*t^4)*X(t)^6+(2*t^5-3*t^4)*X(t)^5+3*t^2*X(t)^4-3*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, 0, 2, 2, 5, 22, 14, 164, 65, 1030, 657, 5868, 7463, 31765, 73575, 173849, 631556, 1053086, 4877803, 7526655, 34948691, 61382672, 239407864, 524309309, 1621763388, 4415274965, 11255289437, 35813332389, 82153463817, 279458110861, 633479334487, 2118070224696, 5075741777630, 15824514104397, 41275863623366, 118428013850973, 334523141763061, 899513350738990, 2678023253678681] ------------------------------------------------------------- Theorem 44 : Let a(n) be number of words of length n in the alphabet, {-3, -2, 0, 3}, tha\ t sum-up to 0 and whose partial sums are never negative, in other words \ generalized Dyck words with alphabet, {-3, -2, 0, 3}, 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 20 20 19 18 19 18 18 17 16 17 t X(t) + (t - t ) X(t) + t X(t) + (3 t - 3 t ) X(t) 16 15 14 16 15 14 15 + (3 t - 6 t + 3 t ) X(t) + (5 t - 3 t ) X(t) 14 13 12 14 + (7 t - 7 t + 3 t ) X(t) 13 12 11 10 13 + (8 t - 14 t + 10 t - 3 t ) X(t) 12 11 10 12 11 10 9 8 11 + (6 t - 6 t + 3 t ) X(t) + (8 t - 9 t + 3 t - t ) X(t) 10 9 8 7 6 10 + (14 t - 22 t + 12 t - 4 t + t ) X(t) 9 8 7 6 9 8 7 6 8 + (8 t - 9 t + 3 t - t ) X(t) + (6 t - 6 t + 3 t ) X(t) 7 6 5 4 7 6 5 4 6 + (8 t - 14 t + 10 t - 3 t ) X(t) + (7 t - 7 t + 3 t ) X(t) 5 4 5 4 3 2 4 3 2 3 + (5 t - 3 t ) X(t) + (3 t - 6 t + 3 t ) X(t) + (3 t - 3 t ) X(t) 2 2 + t X(t) + (t - 1) X(t) + 1 = 0 and in Maple notation t^20*X(t)^20+(t^19-t^18)*X(t)^19+t^18*X(t)^18+(3*t^17-3*t^16)*X(t)^17+(3*t^16-6 *t^15+3*t^14)*X(t)^16+(5*t^15-3*t^14)*X(t)^15+(7*t^14-7*t^13+3*t^12)*X(t)^14+(8 *t^13-14*t^12+10*t^11-3*t^10)*X(t)^13+(6*t^12-6*t^11+3*t^10)*X(t)^12+(8*t^11-9* t^10+3*t^9-t^8)*X(t)^11+(14*t^10-22*t^9+12*t^8-4*t^7+t^6)*X(t)^10+(8*t^9-9*t^8+ 3*t^7-t^6)*X(t)^9+(6*t^8-6*t^7+3*t^6)*X(t)^8+(8*t^7-14*t^6+10*t^5-3*t^4)*X(t)^7 +(7*t^6-7*t^5+3*t^4)*X(t)^6+(5*t^5-3*t^4)*X(t)^5+(3*t^4-6*t^3+3*t^2)*X(t)^4+(3* t^3-3*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, 4, 9, 23, 63, 191, 611, 2043, 6995, 24285, 85002, 299032, 1056374, 3746277, 13339312, 47696449, 171274045, 617628946, 2236251077, 8127586687, 29643037040, 108460380396, 397996659534, 1464304342760, 5400380113098, 19960417936077, 73924963996529, 274298489892107, 1019553263777529, 3795780168219128, 14153139985026002, 52847639793506348, 197598425723999833, 739764573954668670, 2772843982944385426, 10405218264935053091, 39088130249804436831, 146988218686614545549, 553275975616690538969] Theorem 45 : Let a(n) be number of words of length n in the alphabet, {-3, -2, 1, 2}, tha\ t sum-up to 0 and whose partial sums are never negative, in other words \ generalized Dyck words with alphabet, {-3, -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 10 10 8 7 8 5 7 5 6 4 5 3 4 t X(t) + (-t - t ) X(t) + t X(t) - 2 t X(t) - t X(t) + 3 t X(t) 2 3 2 2 + 2 t X(t) - t X(t) - X(t) + 1 = 0 and in Maple notation t^10*X(t)^10+(-t^8-t^7)*X(t)^8+t^5*X(t)^7-2*t^5*X(t)^6-t^4*X(t)^5+3*t^3*X(t)^4+ 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, 3, 3, 23, 48, 155, 612, 1609, 6255, 20608, 67954, 250621, 837858, 2997773, 10682234, 37447731, 135767710, 484626014, 1747304695, 6345838687, 22949010094, 83737139716, 305552771525, 1117272519230, 4101926037674, 15064915295407, 55488468018578, 204729501895013, 756350275118646, 2800027056148971, 10377918836812794, 38521413439022433, 143184883556986540, 532814894354798905, 1985211915360494824, 7404609038051674655, 27647122999848204744, 103334287176052280814, 386579072024085298844] ------------------------------------------------------------- Theorem 46 : Let a(n) be number of words of length n in the alphabet, {-3, -2, 0, 1, 2}, \ that sum-up to 0 and whose partial sums are never negative, in other wor\ ds generalized Dyck words with alphabet, {-3, -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 10 10 7 8 7 6 5 7 6 5 6 t X(t) - t X(t) + (t - 2 t + t ) X(t) + (2 t - 2 t ) X(t) 5 4 5 4 3 4 3 2 3 2 2 + (t - t ) X(t) + (-3 t + 3 t ) X(t) + (-2 t + 2 t ) X(t) - X(t) t + (t - 1) X(t) + 1 = 0 and in Maple notation t^10*X(t)^10-t^7*X(t)^8+(t^7-2*t^6+t^5)*X(t)^7+(2*t^6-2*t^5)*X(t)^6+(t^5-t^4)*X (t)^5+(-3*t^4+3*t^3)*X(t)^4+(-2*t^3+2*t^2)*X(t)^3-X(t)^2*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, 7, 22, 79, 307, 1206, 4891, 20294, 85397, 364381, 1572540, 6849487, 30078324, 133017168, 591868095, 2647908096, 11903633098, 53744460606, 243601241475, 1108042670458, 5056220920464, 23140233405411, 106188147445720, 488492678546426, 2252327637335970, 10406949400999442, 48180175017505798, 223464105239450550, 1038218812932800540, 4831300777052271853, 22515941339920038323, 105081847077888360986, 491067287805709896478, 2297720776244536503419, 10763818893782103978538, 50480165579368787346737, 236992698161835603541447, 1113744225852760409324285, 5239025683479528150174195] Theorem 47 : Let a(n) be number of words of length n in the alphabet, {-3, -2, 1, 3}, tha\ t sum-up to 0 and whose partial sums are never negative, in other words \ generalized Dyck words with alphabet, {-3, -2, 1, 3}, 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 20 20 18 19 18 18 17 16 17 t X(t) - t X(t) + t X(t) + (t - 3 t ) X(t) 16 14 16 15 14 15 + (2 t + 3 t ) X(t) + (5 t - t ) X(t) 14 13 12 14 13 12 11 10 13 + (9 t + t + 3 t ) X(t) + (2 t - 4 t + t - 3 t ) X(t) 12 10 12 11 10 8 11 + (3 t + 4 t ) X(t) + (-3 t - 11 t - t ) X(t) 10 9 8 6 10 9 8 6 9 + (-6 t - 10 t + 6 t + t ) X(t) + (-3 t - 11 t - t ) X(t) 8 6 8 7 6 5 4 7 + (3 t + 4 t ) X(t) + (2 t - 4 t + t - 3 t ) X(t) 6 5 4 6 5 4 5 4 2 4 + (9 t + t + 3 t ) X(t) + (5 t - t ) X(t) + (2 t + 3 t ) X(t) 3 2 3 2 2 + (t - 3 t ) X(t) + t X(t) - X(t) + 1 = 0 and in Maple notation t^20*X(t)^20-t^18*X(t)^19+t^18*X(t)^18+(t^17-3*t^16)*X(t)^17+(2*t^16+3*t^14)*X( t)^16+(5*t^15-t^14)*X(t)^15+(9*t^14+t^13+3*t^12)*X(t)^14+(2*t^13-4*t^12+t^11-3* t^10)*X(t)^13+(3*t^12+4*t^10)*X(t)^12+(-3*t^11-11*t^10-t^8)*X(t)^11+(-6*t^10-10 *t^9+6*t^8+t^6)*X(t)^10+(-3*t^9-11*t^8-t^6)*X(t)^9+(3*t^8+4*t^6)*X(t)^8+(2*t^7-\ 4*t^6+t^5-3*t^4)*X(t)^7+(9*t^6+t^5+3*t^4)*X(t)^6+(5*t^5-t^4)*X(t)^5+(2*t^4+3*t^ 2)*X(t)^4+(t^3-3*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, 6, 15, 52, 156, 528, 1765, 6114, 21236, 74776, 265291, 949595, 3422399, 12410903, 45247919, 165752707, 609808036, 2252176796, 8347161607, 31035445149, 115729542652, 432703786186, 1621835578983, 6092706372588, 22936590083350, 86516207497332, 326932457744595, 1237536547815069, 4691914691117079, 17815222622885223, 67739562218872488, 257909787594052190, 983184309422800372, 3752440379470237568, 14337614322431343300, 54840178875567735030, 209969537892201797328, 804687981679200752808] ------------------------------------------------------------- Theorem 48 : Let a(n) be number of words of length n in the alphabet, {-3, -2, 0, 1, 3}, \ that sum-up to 0 and whose partial sums are never negative, in other wor\ ds generalized Dyck words with alphabet, {-3, -2, 0, 1, 3}, 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 20 20 19 18 19 18 18 17 16 17 t X(t) + (t - t ) X(t) + t X(t) + (4 t - 3 t ) X(t) 16 15 14 16 15 14 15 + (5 t - 6 t + 3 t ) X(t) + (6 t - t ) X(t) 14 13 12 14 + (11 t - 5 t + 3 t ) X(t) 13 12 11 10 13 + (10 t - 15 t + 10 t - 3 t ) X(t) 12 11 10 12 11 10 9 8 11 + (7 t - 8 t + 4 t ) X(t) + (9 t - 14 t + 3 t - t ) X(t) 10 9 8 7 6 10 + (11 t - 26 t + 12 t - 4 t + t ) X(t) 9 8 7 6 9 8 7 6 8 + (9 t - 14 t + 3 t - t ) X(t) + (7 t - 8 t + 4 t ) X(t) 7 6 5 4 7 6 5 4 6 + (10 t - 15 t + 10 t - 3 t ) X(t) + (11 t - 5 t + 3 t ) X(t) 5 4 5 4 3 2 4 3 2 3 + (6 t - t ) X(t) + (5 t - 6 t + 3 t ) X(t) + (4 t - 3 t ) X(t) 2 2 + t X(t) + (t - 1) X(t) + 1 = 0 and in Maple notation t^20*X(t)^20+(t^19-t^18)*X(t)^19+t^18*X(t)^18+(4*t^17-3*t^16)*X(t)^17+(5*t^16-6 *t^15+3*t^14)*X(t)^16+(6*t^15-t^14)*X(t)^15+(11*t^14-5*t^13+3*t^12)*X(t)^14+(10 *t^13-15*t^12+10*t^11-3*t^10)*X(t)^13+(7*t^12-8*t^11+4*t^10)*X(t)^12+(9*t^11-14 *t^10+3*t^9-t^8)*X(t)^11+(11*t^10-26*t^9+12*t^8-4*t^7+t^6)*X(t)^10+(9*t^9-14*t^ 8+3*t^7-t^6)*X(t)^9+(7*t^8-8*t^7+4*t^6)*X(t)^8+(10*t^7-15*t^6+10*t^5-3*t^4)*X(t )^7+(11*t^6-5*t^5+3*t^4)*X(t)^6+(6*t^5-t^4)*X(t)^5+(5*t^4-6*t^3+3*t^2)*X(t)^4+( 4*t^3-3*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, 17, 66, 268, 1102, 4577, 19268, 82370, 357320, 1569529, 6964790, 31165457, 140441862, 636760864, 2902760597, 13297023766, 61177749428, 282580601782, 1309901179625, 6091732788599, 28413622102823, 132888925290852, 623065157021019, 2928043941328992, 13789462250164166, 65069387619745754, 307614340493252535, 1456745281999048323, 6909708195123342537, 32823977378364103786, 156148724640645802604, 743815529947146269791, 3547631693267841463928, 16940568021477717256442, 80985207117091652473571, 387566329201173141465641, 1856629704121694090459827, 8902695847590803598905366] Theorem 49 : Let a(n) be number of words of length n in the alphabet, {-3, -2, 2, 3}, tha\ t sum-up to 0 and whose partial sums are never negative, in other words \ generalized Dyck words with alphabet, {-3, -2, 2, 3}, 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 14 14 13 12 13 12 11 12 11 10 11 t X(t) + (-t - t ) X(t) + (t + t ) X(t) + (-t - t ) X(t) 10 8 10 9 8 7 9 + (t + 2 t ) X(t) + (2 t - 5 t - t ) X(t) 8 7 6 8 7 6 4 7 + (-2 t + 3 t + 2 t ) X(t) + (2 t - 3 t - t ) X(t) 6 5 4 6 5 4 3 5 + (-2 t + 3 t + 2 t ) X(t) + (2 t - 5 t - t ) X(t) 4 2 4 3 2 3 2 2 + (t + 2 t ) X(t) + (-t - t ) X(t) + (t + t) X(t) + (-t - 1) X(t) + 1 = 0 and in Maple notation t^14*X(t)^14+(-t^13-t^12)*X(t)^13+(t^12+t^11)*X(t)^12+(-t^11-t^10)*X(t)^11+(t^ 10+2*t^8)*X(t)^10+(2*t^9-5*t^8-t^7)*X(t)^9+(-2*t^8+3*t^7+2*t^6)*X(t)^8+(2*t^7-3 *t^6-t^4)*X(t)^7+(-2*t^6+3*t^5+2*t^4)*X(t)^6+(2*t^5-5*t^4-t^3)*X(t)^5+(t^4+2*t^ 2)*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, 0, 11, 4, 86, 78, 805, 1192, 8452, 16990, 96270, 236808, 1164643, 3284046, 14743066, 45644056, 193172365, 637821100, 2598848478, 8972601330, 35688679563, 127118293564, 498084862421, 1813552391314, 7042085802066, 26046219527470, 100619518600486, 376413085980710, 1450310346991644, 5471244629599182, 21059012766071621, 79947499571174084, 307715177621912926, 1173886029775191684, 4520932319331403266, 17312819399699279000, 66739472841683131101, 256368332246429186536, 989408338157591223177] ------------------------------------------------------------- Theorem 50 : Let a(n) be number of words of length n in the alphabet, {-3, -2, 0, 2, 3}, \ that sum-up to 0 and whose partial sums are never negative, in other wor\ ds generalized Dyck words with alphabet, {-3, -2, 0, 2, 3}, 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 14 14 12 13 11 12 10 11 t X(t) - t X(t) + t X(t) - t X(t) 10 9 8 10 9 8 7 9 + (3 t - 4 t + 2 t ) X(t) + (6 t - 3 t - t ) X(t) 8 7 6 8 7 6 5 4 7 + (-3 t - t + 2 t ) X(t) + (6 t - 6 t + 3 t - t ) X(t) 6 5 4 6 5 4 3 5 + (-3 t - t + 2 t ) X(t) + (6 t - 3 t - t ) X(t) 4 3 2 4 2 3 2 + (3 t - 4 t + 2 t ) X(t) - t X(t) + t X(t) - X(t) + 1 = 0 and in Maple notation t^14*X(t)^14-t^12*X(t)^13+t^11*X(t)^12-t^10*X(t)^11+(3*t^10-4*t^9+2*t^8)*X(t)^ 10+(6*t^9-3*t^8-t^7)*X(t)^9+(-3*t^8-t^7+2*t^6)*X(t)^8+(6*t^7-6*t^6+3*t^5-t^4)*X (t)^7+(-3*t^6-t^5+2*t^4)*X(t)^6+(6*t^5-3*t^4-t^3)*X(t)^5+(3*t^4-4*t^3+2*t^2)*X( t)^4-t^2*X(t)^3+t*X(t)^2-X(t)+1 = 0 For the sake of the OEIS here are the first 40 terms, starting with n=0 [1, 1, 3, 7, 24, 80, 306, 1192, 4888, 20432, 87426, 379408, 1668683, 7413719, 33234292, 150099820, 682380349, 3120007765, 14338030432, 66188847310, 306790606256, 1427213140894, 6661594070868, 31187620971820, 146416449811625, 689133470463255, 3251146168020586, 15371380445633954, 72822291736606620, 345644712675660086, 1643443540157779463, 7826895059295423197, 37332693828278213442, 178325559963529619118, 852953373245791424784, 4084986184256624893172, 19587478018162089371055, 94028744350829775212863, 451867133992806155647324, 2173725620449002472445992, 10466951651602198775656540 ] Theorem 51 : Let a(n) be number of words of length n in the alphabet, {-3, -2, 1, 2, 3}, \ that sum-up to 0 and whose partial sums are never negative, in other wor\ ds generalized Dyck words with alphabet, {-3, -2, 1, 2, 3}, 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 20 20 18 19 16 17 16 15 14 16 t X(t) - t X(t) - t X(t) + (2 t + 3 t + 3 t ) X(t) 15 14 15 14 13 12 14 + (t - 4 t ) X(t) + (2 t + t + 2 t ) X(t) 13 12 11 10 13 12 11 10 12 + (-3 t - 2 t - t - 3 t ) X(t) + (t + 7 t + 8 t ) X(t) 11 10 9 8 11 10 9 8 6 10 + (-4 t - 7 t - t - 2 t ) X(t) + (t - 2 t + 5 t + t ) X(t) 9 8 7 6 9 8 7 6 8 + (-4 t - 7 t - t - 2 t ) X(t) + (t + 7 t + 8 t ) X(t) 7 6 5 4 7 6 5 4 6 + (-3 t - 2 t - t - 3 t ) X(t) + (2 t + t + 2 t ) X(t) 5 4 5 4 3 2 4 3 2 + (t - 4 t ) X(t) + (2 t + 3 t + 3 t ) X(t) - X(t) t - X(t) + 1 = 0 and in Maple notation t^20*X(t)^20-t^18*X(t)^19-t^16*X(t)^17+(2*t^16+3*t^15+3*t^14)*X(t)^16+(t^15-4*t ^14)*X(t)^15+(2*t^14+t^13+2*t^12)*X(t)^14+(-3*t^13-2*t^12-t^11-3*t^10)*X(t)^13+ (t^12+7*t^11+8*t^10)*X(t)^12+(-4*t^11-7*t^10-t^9-2*t^8)*X(t)^11+(t^10-2*t^9+5*t ^8+t^6)*X(t)^10+(-4*t^9-7*t^8-t^7-2*t^6)*X(t)^9+(t^8+7*t^7+8*t^6)*X(t)^8+(-3*t^ 7-2*t^6-t^5-3*t^4)*X(t)^7+(2*t^6+t^5+2*t^4)*X(t)^6+(t^5-4*t^4)*X(t)^5+(2*t^4+3* t^3+3*t^2)*X(t)^4-X(t)^3*t^2-X(t)+1 = 0 For the sake of the OEIS here are the first 40 terms, starting with n=0 [1, 0, 2, 3, 15, 52, 196, 848, 3285, 14647, 60702, 270321, 1175419, 5255914, 23491263, 106039951, 481526629, 2196502989, 10079226967, 46405794075, 214644323424, 995842152796, 4636334700470, 21645379432275, 101333050920532, 475554054349281, 2236867470931726, 10543910516031653, 49798007373922185, 235624174511043642, 1116777689178292522, 5301626970881411615, 25205850251590771049, 120006708503224545684, 572117331555550458916, 2730911696937623440681, 13050977933834611429924, 62440110843797303986797, 299050203169880371941497, 1433708348090695408846840, 6880058216300684749855770] ------------------------------------------------------------- Theorem 52 : Let a(n) be number of words of length n in the alphabet, {-3, -2, 0, 1, 2, 3}, that sum-up to 0 and whose partial sums are never negative, in other wo\ rds generalized Dyck words with alphabet, {-3, -2, 0, 1, 2, 3}, 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 20 20 19 18 19 17 16 17 t X(t) + (t - t ) X(t) + (t - t ) X(t) 16 15 14 16 15 14 15 + (2 t - 3 t + 3 t ) X(t) + (5 t - 4 t ) X(t) 14 13 12 14 13 12 11 10 13 + (3 t - 3 t + 2 t ) X(t) + (t - 9 t + 8 t - 3 t ) X(t) 12 11 10 12 11 10 9 8 11 + (2 t - 9 t + 8 t ) X(t) + (4 t - 11 t + 5 t - 2 t ) X(t) 10 9 8 7 6 10 + (9 t - 16 t + 11 t - 4 t + t ) X(t) 9 8 7 6 9 8 7 6 8 + (4 t - 11 t + 5 t - 2 t ) X(t) + (2 t - 9 t + 8 t ) X(t) 7 6 5 4 7 6 5 4 6 + (t - 9 t + 8 t - 3 t ) X(t) + (3 t - 3 t + 2 t ) X(t) 5 4 5 4 3 2 4 3 2 3 + (5 t - 4 t ) X(t) + (2 t - 3 t + 3 t ) X(t) + (t - t ) X(t) + (t - 1) X(t) + 1 = 0 and in Maple notation t^20*X(t)^20+(t^19-t^18)*X(t)^19+(t^17-t^16)*X(t)^17+(2*t^16-3*t^15+3*t^14)*X(t )^16+(5*t^15-4*t^14)*X(t)^15+(3*t^14-3*t^13+2*t^12)*X(t)^14+(t^13-9*t^12+8*t^11 -3*t^10)*X(t)^13+(2*t^12-9*t^11+8*t^10)*X(t)^12+(4*t^11-11*t^10+5*t^9-2*t^8)*X( t)^11+(9*t^10-16*t^9+11*t^8-4*t^7+t^6)*X(t)^10+(4*t^9-11*t^8+5*t^7-2*t^6)*X(t)^ 9+(2*t^8-9*t^7+8*t^6)*X(t)^8+(t^7-9*t^6+8*t^5-3*t^4)*X(t)^7+(3*t^6-3*t^5+2*t^4) *X(t)^6+(5*t^5-4*t^4)*X(t)^5+(2*t^4-3*t^3+3*t^2)*X(t)^4+(t^3-t^2)*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, 3, 10, 40, 178, 824, 3985, 19744, 99971, 514622, 2685625, 14176140, 75552739, 406004201, 2197435059, 11967922244, 65541745451, 360700764547, 1993799140084, 11064460304559, 61621191297826, 344302222977332, 1929464284971942, 10842102255389729, 61076711461196642, 344857477219235278, 1951332407647841139, 11063287357056217098, 62840413117965029735, 357554540536489974226, 2037725561786030373678, 11630689244938304167132, 66478588142168708946990, 380485775178651410710264, 2180430261152798312070968, 12510155725442309587379111, 71857488874878429977624954, 413184893247251385429807144, 2378242645226788683602509799, 13702040691074329300256215649] Theorem 53 : Let a(n) be number of words of length n in the alphabet, {-3, -1, 1}, that s\ um-up to 0 and whose partial sums are never negative, in other words gen\ eralized Dyck words with alphabet, {-3, -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 4 4 2 2 X(t) t + X(t) t - X(t) + 1 = 0 and in Maple notation X(t)^4*t^4+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, 3, 0, 11, 0, 46, 0, 207, 0, 979, 0, 4797, 0, 24138, 0, 123998, 0, 647615, 0, 3428493, 0, 18356714, 0, 99229015, 0, 540807165, 0, 2968468275, 0, 16395456762, 0, 91053897066, 0, 508151297602, 0, 2848290555562, 0, 16028132445156] ------------------------------------------------------------- Theorem 54 : Let a(n) be number of words of length n in the alphabet, {-3, -1, 0, 1}, tha\ t sum-up to 0 and whose partial sums are never negative, in other words \ generalized Dyck words with alphabet, {-3, -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 4 4 2 2 t X(t) + t X(t) + (t - 1) X(t) + 1 = 0 and in Maple notation t^4*X(t)^4+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, 4, 10, 26, 72, 204, 593, 1753, 5263, 15995, 49127, 152231, 475359, 1494287, 4724903, 15017767, 47954400, 153764322, 494892393, 1598241869, 5177492708, 16820048006, 54785449703, 178873019471, 585312014446, 1919212203652 , 6305054573239, 20750506952675, 68405627426506, 225856342963732, 746807064830711, 2472761691513879, 8198212773239166, 27213692044392428, 90439467115506752, 300887392613150360, 1002076228695130756, 3340607738204162316 , 11146975093230149583] Furthermore a(n) satisfies the following linear recurrence equation with pol\ ynomial coefficients 5 4 3 2 (6084 n - 7722 n - 2894 n + 3471 n + 181 n - 240) a(n - 1) a(n) = -------------------------------------------------------------- n (3 n + 2) (3 n + 4) %1 4 3 2 (n - 1) (3718 n - 6578 n + 973 n + 3551 n - 848) a(n - 2) - 1/3 ------------------------------------------------------------ n (3 n + 2) (3 n + 4) %1 3 2 (n - 1) (n - 2) (14534 n - 18447 n - 7783 n + 6184) a(n - 3) - 2/3 -------------------------------------------------------------- n (3 n + 2) (3 n + 4) %1 2 (n - 1) (n - 2) (n - 3) (169 n + 39 n - 32) a(n - 4) + 257/3 ----------------------------------------------------- n (3 n + 2) (3 n + 4) %1 2 %1 := 169 n - 299 n + 98 subject to the initial conditions a(1) = 1, a(2) = 2, a(3) = 4, a(4) = 10 and in Maple notation a(n) = (6084*n^5-7722*n^4-2894*n^3+3471*n^2+181*n-240)/n/(3*n+2)/(3*n+4)/(169*n ^2-299*n+98)*a(n-1)-1/3*(n-1)*(3718*n^4-6578*n^3+973*n^2+3551*n-848)/n/(3*n+2)/ (3*n+4)/(169*n^2-299*n+98)*a(n-2)-2/3*(n-1)*(n-2)*(14534*n^3-18447*n^2-7783*n+ 6184)/n/(3*n+2)/(3*n+4)/(169*n^2-299*n+98)*a(n-3)+257/3*(n-1)*(n-2)*(n-3)*(169* n^2+39*n-32)/n/(3*n+2)/(3*n+4)/(169*n^2-299*n+98)*a(n-4) a(1) = 1, a(2) = 2, a(3) = 4, a(4) = 10 Just for fun, using this recurrence we get that a(1000) = 627137201682701361422584426858898117587060102006650962696837827734\ 136877524635225581241195421244904962177959831753253271108739917782565183\ 671487493297560364403128024264855123992994169014563340244830147363730961\ 504735235720347178392173233087844817491528700792583336471955085515913829\ 447165186502590283596001677192856912353383018537015835286967850692704470\ 870357878180831282635566688341539593632317448334596239780340863755726857\ 936299999287665544832163642853832229302779380838518339323368491357327472\ 9358927458214966351371496405214867403 Theorem 55 : Let a(n) be number of words of length n in the alphabet, {-3, -1, 2}, that s\ um-up to 0 and whose partial sums are never negative, in other words gen\ eralized Dyck words with alphabet, {-3, -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 10 10 9 9 5 7 5 6 5 4 5 4 4 X(t) t + X(t) t + t X(t) - t X(t) + (2 t + 2 t ) X(t) + t X(t) 3 3 + t X(t) - X(t) + 1 = 0 and in Maple notation X(t)^10*t^10+X(t)^9*t^9+t^5*X(t)^7-t^5*X(t)^6+(2*t^5+2*t^4)*X(t)^5+t^4*X(t)^4+t ^3*X(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, 3, 2, 3, 23, 59, 74, 178, 753, 1859, 3299, 8937, 29884, 73955, 160368, 445889, 1334825, 3371535, 8167687, 22732271, 64550448, 166944853, 429281385, 1189787311, 3299504856, 8708248080, 23118437489, 63845014804, 175463878127, 470269479575, 1270311652558, 3501884445317, 9604857045847, 26027895342456, 71002490056153, 195692892371919, 537321155970160, 1467430337299719] ------------------------------------------------------------- Theorem 56 : Let a(n) be number of words of length n in the alphabet, {-3, -1, 0, 2}, tha\ t sum-up to 0 and whose partial sums are never negative, in other words \ generalized Dyck words with alphabet, {-3, -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 10 10 9 9 7 6 5 7 6 5 6 4 5 t X(t) + t X(t) + (t - 2 t + t ) X(t) + (t - t ) X(t) + 2 t X(t) 4 4 3 3 + t X(t) + t X(t) + (t - 1) X(t) + 1 = 0 and in Maple notation t^10*X(t)^10+t^9*X(t)^9+(t^7-2*t^6+t^5)*X(t)^7+(t^6-t^5)*X(t)^6+2*t^4*X(t)^5+t^ 4*X(t)^4+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, 8, 28, 81, 227, 706, 2400, 8218, 27572, 92406, 315573, 1097204, 3842170, 13477678, 47432830, 167903275, 597749633, 2136722448, 7660609975, 27543306011, 99328408241, 359233964164, 1302485284541, 4732909420882, 17233603840144, 62874796135573, 229816149753687, 841450305500412, 3085784363606663, 11333096919324658, 41681337991980060, 153500792575062725, 566007455062761383, 2089513818353579733, 7722398691273306152, 28570516961040998988, 105808295147677933280, 392225058781229252372] Theorem 57 : Let a(n) be number of words of length n in the alphabet, {-3, -1, 3}, that s\ um-up to 0 and whose partial sums are never negative, in other words gen\ eralized Dyck words with alphabet, {-3, -1, 3}, 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 20 20 18 19 18 18 16 17 16 14 16 t X(t) - t X(t) + t X(t) - 3 t X(t) + (t + 3 t ) X(t) 14 15 14 12 14 12 10 13 - 3 t X(t) + (5 t + 3 t ) X(t) + (-3 t - 3 t ) X(t) 12 10 12 10 8 11 + (2 t + 3 t ) X(t) + (-6 t - t ) X(t) 10 8 6 10 8 6 9 8 6 8 + (-4 t + 6 t + t ) X(t) + (-6 t - t ) X(t) + (2 t + 3 t ) X(t) 6 4 7 6 4 6 4 5 + (-3 t - 3 t ) X(t) + (5 t + 3 t ) X(t) - 3 t X(t) 4 2 4 2 3 2 2 + (t + 3 t ) X(t) - 3 t X(t) + X(t) t - X(t) + 1 = 0 and in Maple notation t^20*X(t)^20-t^18*X(t)^19+t^18*X(t)^18-3*t^16*X(t)^17+(t^16+3*t^14)*X(t)^16-3*t ^14*X(t)^15+(5*t^14+3*t^12)*X(t)^14+(-3*t^12-3*t^10)*X(t)^13+(2*t^12+3*t^10)*X( t)^12+(-6*t^10-t^8)*X(t)^11+(-4*t^10+6*t^8+t^6)*X(t)^10+(-6*t^8-t^6)*X(t)^9+(2* t^8+3*t^6)*X(t)^8+(-3*t^6-3*t^4)*X(t)^7+(5*t^6+3*t^4)*X(t)^6-3*t^4*X(t)^5+(t^4+ 3*t^2)*X(t)^4-3*t^2*X(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, 0, 3, 0, 16, 0, 100, 0, 655, 0, 4465, 0, 31599, 0, 230390, 0, 1717910 , 0, 13034753, 0, 100308732, 0, 781057488, 0, 6142515700, 0, 48719605150, 0, 389274014325, 0, 3130375135624, 0, 25315962247754, 0, 205765906922296, 0, 1679968849194124, 0, 13771490153093158] ------------------------------------------------------------- Theorem 58 : Let a(n) be number of words of length n in the alphabet, {-3, -1, 0, 3}, tha\ t sum-up to 0 and whose partial sums are never negative, in other words \ generalized Dyck words with alphabet, {-3, -1, 0, 3}, 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 20 20 19 18 19 18 18 17 16 17 t X(t) + (t - t ) X(t) + t X(t) + (3 t - 3 t ) X(t) 16 15 14 16 15 14 15 + (4 t - 6 t + 3 t ) X(t) + (3 t - 3 t ) X(t) 14 13 12 14 13 12 11 10 13 + (8 t - 6 t + 3 t ) X(t) + (6 t - 12 t + 9 t - 3 t ) X(t) 12 11 10 12 11 10 9 8 11 + (5 t - 6 t + 3 t ) X(t) + (7 t - 9 t + 3 t - t ) X(t) 10 9 8 7 6 10 + (3 t - 16 t + 12 t - 4 t + t ) X(t) 9 8 7 6 9 8 7 6 8 + (7 t - 9 t + 3 t - t ) X(t) + (5 t - 6 t + 3 t ) X(t) 7 6 5 4 7 6 5 4 6 + (6 t - 12 t + 9 t - 3 t ) X(t) + (8 t - 6 t + 3 t ) X(t) 5 4 5 4 3 2 4 3 2 3 + (3 t - 3 t ) X(t) + (4 t - 6 t + 3 t ) X(t) + (3 t - 3 t ) X(t) 2 2 + X(t) t + (t - 1) X(t) + 1 = 0 and in Maple notation t^20*X(t)^20+(t^19-t^18)*X(t)^19+t^18*X(t)^18+(3*t^17-3*t^16)*X(t)^17+(4*t^16-6 *t^15+3*t^14)*X(t)^16+(3*t^15-3*t^14)*X(t)^15+(8*t^14-6*t^13+3*t^12)*X(t)^14+(6 *t^13-12*t^12+9*t^11-3*t^10)*X(t)^13+(5*t^12-6*t^11+3*t^10)*X(t)^12+(7*t^11-9*t ^10+3*t^9-t^8)*X(t)^11+(3*t^10-16*t^9+12*t^8-4*t^7+t^6)*X(t)^10+(7*t^9-9*t^8+3* t^7-t^6)*X(t)^9+(5*t^8-6*t^7+3*t^6)*X(t)^8+(6*t^7-12*t^6+9*t^5-3*t^4)*X(t)^7+(8 *t^6-6*t^5+3*t^4)*X(t)^6+(3*t^5-3*t^4)*X(t)^5+(4*t^4-6*t^3+3*t^2)*X(t)^4+(3*t^3 -3*t^2)*X(t)^3+X(t)^2*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, 4, 10, 26, 77, 239, 787, 2659, 9191, 32143, 113531, 403755, 1445012, 5200306, 18814519, 68408103, 249892428, 916815494, 3377157559, 12485749763, 46316370130, 172338774900, 643050671303, 2405574084191, 9020145833371, 33896154601987, 127632015424514, 481481331095110, 1819512373567996, 6887111753708552, 26108472965285573, 99116931981049829, 376790260011450152, 1434179336243916366, 5465482900924222364, 20851950412261916476, 79640115514045689401, 304480940692857483063, 1165223280108220473369] Theorem 59 : Let a(n) be number of words of length n in the alphabet, {-3, -1, 1, 2}, tha\ t sum-up to 0 and whose partial sums are never negative, in other words \ generalized Dyck words with alphabet, {-3, -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 10 10 9 9 8 8 7 5 7 6 5 6 t X(t) + t X(t) - t X(t) + (-2 t + t ) X(t) + (-t - t ) X(t) 5 4 5 4 3 4 2 2 + (3 t + 2 t ) X(t) + (2 t + 3 t ) X(t) + X(t) t - X(t) + 1 = 0 and in Maple notation t^10*X(t)^10+t^9*X(t)^9-t^8*X(t)^8+(-2*t^7+t^5)*X(t)^7+(-t^6-t^5)*X(t)^6+(3*t^5 +2*t^4)*X(t)^5+(2*t^4+3*t^3)*X(t)^4+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, 3, 6, 21, 66, 206, 694, 2343, 8006, 27865, 97842, 346560, 1238017, 4451859, 16104105, 58569206, 214013423, 785324563, 2892811352, 10692822131, 39649034086, 147443120646, 549749019862, 2054764213960, 7697272862049, 28894655660026, 108677590661657, 409493420065062, 1545562470596778, 5842680517890137, 22119801344728755, 83860065166879578, 318345575635570632, 1209984597470883971, 4604353717435642583, 17540344670612420506, 66890292116966006476, 255340921774236374052, 975637911204231539435] ------------------------------------------------------------- Theorem 60 : Let a(n) be number of words of length n in the alphabet, {-3, -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, {-3, -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 10 10 9 9 8 8 7 6 5 7 5 6 t X(t) + t X(t) - t X(t) + (-t - 2 t + t ) X(t) - t X(t) 5 4 5 4 3 4 2 2 + (t + 2 t ) X(t) + (-t + 3 t ) X(t) + t X(t) + (t - 1) X(t) + 1 = 0 and in Maple notation t^10*X(t)^10+t^9*X(t)^9-t^8*X(t)^8+(-t^7-2*t^6+t^5)*X(t)^7-t^5*X(t)^6+(t^5+2*t^ 4)*X(t)^5+(-t^4+3*t^3)*X(t)^4+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, 7, 25, 92, 358, 1446, 5983, 25240, 108204, 470011, 2064073, 9149121, 40879535, 183928036, 832593614, 3789259378, 17328270006, 79582794770, 366911986284, 1697559667124, 7879011111506, 36676059556332, 171180174657908, 800925420506151, 3755925917983035, 17650449866848961, 83108140886635519, 392032654365181642, 1852419911063297195, 8766935823870526347, 41553200625196027922, 197228810371226596772, 937367365159229449957, 4460569569962153974561, 21251125363950209328709, 101357805966449668487424, 483939199666396729329146, 2312913305429593079489647, 11064740221473415080489313 ] Theorem 61 : Let a(n) be number of words of length n in the alphabet, {-3, -1, 1, 3}, tha\ t sum-up to 0 and whose partial sums are never negative, in other words \ generalized Dyck words with alphabet, {-3, -1, 1, 3}, 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 14 14 12 13 12 12 10 11 10 8 10 t X(t) - t X(t) + t X(t) - t X(t) + (-t + 2 t ) X(t) 8 9 8 8 6 4 7 6 6 4 5 + t X(t) - t X(t) + (2 t - t ) X(t) - t X(t) + t X(t) 4 2 4 2 3 2 2 + (-t + 2 t ) X(t) - t X(t) + t X(t) - X(t) + 1 = 0 and in Maple notation t^14*X(t)^14-t^12*X(t)^13+t^12*X(t)^12-t^10*X(t)^11+(-t^10+2*t^8)*X(t)^10+t^8*X (t)^9-t^8*X(t)^8+(2*t^6-t^4)*X(t)^7-t^6*X(t)^6+t^4*X(t)^5+(-t^4+2*t^2)*X(t)^4-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, 2, 0, 13, 0, 120, 0, 1288, 0, 15046, 0, 185658, 0, 2380720, 0, 31411376, 0, 423660504, 0, 5814905977, 0, 80956085304, 0, 1140478875656, 0, 16227516683124, 0, 232870988052180, 0, 3366482778363616, 0, 48981220255732960, 0, 716707681487535144, 0, 10539913681632290532, 0, 155697664218428455520, 0, 2309297999296926348448] ------------------------------------------------------------- Theorem 62 : Let a(n) be number of words of length n in the alphabet, {-3, -1, 0, 1, 3}, \ that sum-up to 0 and whose partial sums are never negative, in other wor\ ds generalized Dyck words with alphabet, {-3, -1, 0, 1, 3}, 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 14 14 13 12 13 12 12 11 10 11 t X(t) + (t - t ) X(t) + t X(t) + (t - t ) X(t) 10 9 8 10 9 8 9 8 8 + (t - 4 t + 2 t ) X(t) + (-t + t ) X(t) - t X(t) 7 6 5 4 7 6 6 5 4 5 + (-t - t + 3 t - t ) X(t) - t X(t) + (-t + t ) X(t) 4 3 2 4 3 2 3 2 2 + (t - 4 t + 2 t ) X(t) + (t - t ) X(t) + t X(t) + (t - 1) X(t) + 1 = 0 and in Maple notation t^14*X(t)^14+(t^13-t^12)*X(t)^13+t^12*X(t)^12+(t^11-t^10)*X(t)^11+(t^10-4*t^9+2 *t^8)*X(t)^10+(-t^9+t^8)*X(t)^9-t^8*X(t)^8+(-t^7-t^6+3*t^5-t^4)*X(t)^7-t^6*X(t) ^6+(-t^5+t^4)*X(t)^5+(t^4-4*t^3+2*t^2)*X(t)^4+(t^3-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, 3, 7, 26, 86, 346, 1338, 5615, 23383, 101027, 437867, 1933702, 8589738, 38578064, 174275164, 793045125, 3627176917, 16678170283, 77015695959, 357109366619, 1661747813563, 7758461136301, 36331041497241, 170600436859245, 803111077679021, 3789532818043005, 17919710723045341, 84907599707104339, 403060916560202427, 1916681552672087867, 9129246551879966571, 43549339370831138257, 208041226884097914513, 995180460362305346819, 4766562179747507022759, 22857513003018738137260, 109734887366942477001296, 527383481369541772085128, 2537174761570963601873168, 12217831379430570202976435 ] Theorem 63 : Let a(n) be number of words of length n in the alphabet, {-3, -1, 2, 3}, tha\ t sum-up to 0 and whose partial sums are never negative, in other words \ generalized Dyck words with alphabet, {-3, -1, 2, 3}, 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 20 20 18 19 18 18 17 16 17 t X(t) - t X(t) + t X(t) + (t - 3 t ) X(t) 16 14 16 15 14 15 + (2 t + 3 t ) X(t) + (5 t - t ) X(t) 14 13 12 14 13 12 11 10 13 + (9 t + t + 3 t ) X(t) + (2 t - 4 t + t - 3 t ) X(t) 12 10 12 11 10 8 11 + (3 t + 4 t ) X(t) + (-3 t - 11 t - t ) X(t) 10 9 8 6 10 9 8 6 9 + (-6 t - 10 t + 6 t + t ) X(t) + (-3 t - 11 t - t ) X(t) 8 6 8 7 6 5 4 7 + (3 t + 4 t ) X(t) + (2 t - 4 t + t - 3 t ) X(t) 6 5 4 6 5 4 5 4 2 4 + (9 t + t + 3 t ) X(t) + (5 t - t ) X(t) + (2 t + 3 t ) X(t) 3 2 3 2 2 + (t - 3 t ) X(t) + t X(t) - X(t) + 1 = 0 and in Maple notation t^20*X(t)^20-t^18*X(t)^19+t^18*X(t)^18+(t^17-3*t^16)*X(t)^17+(2*t^16+3*t^14)*X( t)^16+(5*t^15-t^14)*X(t)^15+(9*t^14+t^13+3*t^12)*X(t)^14+(2*t^13-4*t^12+t^11-3* t^10)*X(t)^13+(3*t^12+4*t^10)*X(t)^12+(-3*t^11-11*t^10-t^8)*X(t)^11+(-6*t^10-10 *t^9+6*t^8+t^6)*X(t)^10+(-3*t^9-11*t^8-t^6)*X(t)^9+(3*t^8+4*t^6)*X(t)^8+(2*t^7-\ 4*t^6+t^5-3*t^4)*X(t)^7+(9*t^6+t^5+3*t^4)*X(t)^6+(5*t^5-t^4)*X(t)^5+(2*t^4+3*t^ 2)*X(t)^4+(t^3-3*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, 6, 15, 52, 156, 528, 1765, 6114, 21236, 74776, 265291, 949595, 3422399, 12410903, 45247919, 165752707, 609808036, 2252176796, 8347161607, 31035445149, 115729542652, 432703786186, 1621835578983, 6092706372588, 22936590083350, 86516207497332, 326932457744595, 1237536547815069, 4691914691117079, 17815222622885223, 67739562218872488, 257909787594052190, 983184309422800372, 3752440379470237568, 14337614322431343300, 54840178875567735030, 209969537892201797328, 804687981679200752808] ------------------------------------------------------------- Theorem 64 : Let a(n) be number of words of length n in the alphabet, {-3, -1, 0, 2, 3}, \ that sum-up to 0 and whose partial sums are never negative, in other wor\ ds generalized Dyck words with alphabet, {-3, -1, 0, 2, 3}, 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 20 20 19 18 19 18 18 17 16 17 t X(t) + (t - t ) X(t) + t X(t) + (4 t - 3 t ) X(t) 16 15 14 16 15 14 15 + (5 t - 6 t + 3 t ) X(t) + (6 t - t ) X(t) 14 13 12 14 + (11 t - 5 t + 3 t ) X(t) 13 12 11 10 13 + (10 t - 15 t + 10 t - 3 t ) X(t) 12 11 10 12 11 10 9 8 11 + (7 t - 8 t + 4 t ) X(t) + (9 t - 14 t + 3 t - t ) X(t) 10 9 8 7 6 10 + (11 t - 26 t + 12 t - 4 t + t ) X(t) 9 8 7 6 9 8 7 6 8 + (9 t - 14 t + 3 t - t ) X(t) + (7 t - 8 t + 4 t ) X(t) 7 6 5 4 7 6 5 4 6 + (10 t - 15 t + 10 t - 3 t ) X(t) + (11 t - 5 t + 3 t ) X(t) 5 4 5 4 3 2 4 3 2 3 + (6 t - t ) X(t) + (5 t - 6 t + 3 t ) X(t) + (4 t - 3 t ) X(t) 2 2 + t X(t) + (t - 1) X(t) + 1 = 0 and in Maple notation t^20*X(t)^20+(t^19-t^18)*X(t)^19+t^18*X(t)^18+(4*t^17-3*t^16)*X(t)^17+(5*t^16-6 *t^15+3*t^14)*X(t)^16+(6*t^15-t^14)*X(t)^15+(11*t^14-5*t^13+3*t^12)*X(t)^14+(10 *t^13-15*t^12+10*t^11-3*t^10)*X(t)^13+(7*t^12-8*t^11+4*t^10)*X(t)^12+(9*t^11-14 *t^10+3*t^9-t^8)*X(t)^11+(11*t^10-26*t^9+12*t^8-4*t^7+t^6)*X(t)^10+(9*t^9-14*t^ 8+3*t^7-t^6)*X(t)^9+(7*t^8-8*t^7+4*t^6)*X(t)^8+(10*t^7-15*t^6+10*t^5-3*t^4)*X(t )^7+(11*t^6-5*t^5+3*t^4)*X(t)^6+(6*t^5-t^4)*X(t)^5+(5*t^4-6*t^3+3*t^2)*X(t)^4+( 4*t^3-3*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, 17, 66, 268, 1102, 4577, 19268, 82370, 357320, 1569529, 6964790, 31165457, 140441862, 636760864, 2902760597, 13297023766, 61177749428, 282580601782, 1309901179625, 6091732788599, 28413622102823, 132888925290852, 623065157021019, 2928043941328992, 13789462250164166, 65069387619745754, 307614340493252535, 1456745281999048323, 6909708195123342537, 32823977378364103786, 156148724640645802604, 743815529947146269791, 3547631693267841463928, 16940568021477717256442, 80985207117091652473571, 387566329201173141465641, 1856629704121694090459827, 8902695847590803598905366] Theorem 65 : Let a(n) be number of words of length n in the alphabet, {-3, -1, 1, 2, 3}, \ that sum-up to 0 and whose partial sums are never negative, in other wor\ ds generalized Dyck words with alphabet, {-3, -1, 1, 2, 3}, 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 20 20 18 19 18 18 16 17 t X(t) - t X(t) + 2 t X(t) - 3 t X(t) 16 15 14 16 15 15 + (2 t + 3 t + 3 t ) X(t) + 2 t X(t) 14 13 12 14 13 12 11 10 13 + (3 t + 3 t + 3 t ) X(t) + (-t + t - 2 t - 3 t ) X(t) 11 10 12 11 10 9 8 11 + (5 t + 2 t ) X(t) + (-4 t - t - t - t ) X(t) 10 9 8 6 10 9 8 7 6 9 + (-6 t + 2 t + 2 t + t ) X(t) + (-4 t - t - t - t ) X(t) 7 6 8 7 6 5 4 7 + (5 t + 2 t ) X(t) + (-t + t - 2 t - 3 t ) X(t) 6 5 4 6 5 5 4 3 2 4 + (3 t + 3 t + 3 t ) X(t) + 2 t X(t) + (2 t + 3 t + 3 t ) X(t) 2 3 2 2 - 3 t X(t) + 2 t X(t) - X(t) + 1 = 0 and in Maple notation t^20*X(t)^20-t^18*X(t)^19+2*t^18*X(t)^18-3*t^16*X(t)^17+(2*t^16+3*t^15+3*t^14)* X(t)^16+2*t^15*X(t)^15+(3*t^14+3*t^13+3*t^12)*X(t)^14+(-t^13+t^12-2*t^11-3*t^10 )*X(t)^13+(5*t^11+2*t^10)*X(t)^12+(-4*t^11-t^10-t^9-t^8)*X(t)^11+(-6*t^10+2*t^9 +2*t^8+t^6)*X(t)^10+(-4*t^9-t^8-t^7-t^6)*X(t)^9+(5*t^7+2*t^6)*X(t)^8+(-t^7+t^6-\ 2*t^5-3*t^4)*X(t)^7+(3*t^6+3*t^5+3*t^4)*X(t)^6+2*t^5*X(t)^5+(2*t^4+3*t^3+3*t^2) *X(t)^4-3*t^2*X(t)^3+2*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, 2, 3, 16, 48, 208, 778, 3305, 13499, 57999, 247426, 1080038, 4725641, 20929207, 93118686, 417432294, 1879871543, 8510737402, 38686261748, 176564376942, 808602162394, 3715180084791, 17119059401564, 79095591109170, 366346002995878, 1700682157965819, 7911704506752742, 36878195675123781, 172211459271608956, 805555550951269942, 3774174295168643551, 17709186843741843257, 83212029736653279793, 391515337546259034843, 1844394597724020439367, 8699040178460691523419, 41074630787462631404420, 194149125687057441136325, 918614252117154387538888, 4350560194974760150572558] ------------------------------------------------------------- Theorem 66 : Let a(n) be number of words of length n in the alphabet, {-3, -1, 0, 1, 2, 3}, that sum-up to 0 and whose partial sums are never negative, in other wo\ rds generalized Dyck words with alphabet, {-3, -1, 0, 1, 2, 3}, 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 20 20 19 18 19 18 18 17 16 17 t X(t) + (t - t ) X(t) + 2 t X(t) + (3 t - 3 t ) X(t) 16 15 14 16 15 15 + (2 t - 3 t + 3 t ) X(t) + 2 t X(t) 14 13 12 14 13 12 11 10 13 + (3 t - 3 t + 3 t ) X(t) + (-t - 4 t + 7 t - 3 t ) X(t) 12 11 10 12 11 10 9 8 11 + (-3 t + t + 2 t ) X(t) + (-3 t - 2 t + 2 t - t ) X(t) 10 9 8 7 6 10 + (-5 t - 6 t + 8 t - 4 t + t ) X(t) 9 8 7 6 9 8 7 6 8 + (-3 t - 2 t + 2 t - t ) X(t) + (-3 t + t + 2 t ) X(t) 7 6 5 4 7 6 5 4 6 + (-t - 4 t + 7 t - 3 t ) X(t) + (3 t - 3 t + 3 t ) X(t) 5 5 4 3 2 4 3 2 3 + 2 t X(t) + (2 t - 3 t + 3 t ) X(t) + (3 t - 3 t ) X(t) 2 2 + 2 t X(t) + (t - 1) X(t) + 1 = 0 and in Maple notation t^20*X(t)^20+(t^19-t^18)*X(t)^19+2*t^18*X(t)^18+(3*t^17-3*t^16)*X(t)^17+(2*t^16 -3*t^15+3*t^14)*X(t)^16+2*t^15*X(t)^15+(3*t^14-3*t^13+3*t^12)*X(t)^14+(-t^13-4* t^12+7*t^11-3*t^10)*X(t)^13+(-3*t^12+t^11+2*t^10)*X(t)^12+(-3*t^11-2*t^10+2*t^9 -t^8)*X(t)^11+(-5*t^10-6*t^9+8*t^8-4*t^7+t^6)*X(t)^10+(-3*t^9-2*t^8+2*t^7-t^6)* X(t)^9+(-3*t^8+t^7+2*t^6)*X(t)^8+(-t^7-4*t^6+7*t^5-3*t^4)*X(t)^7+(3*t^6-3*t^5+3 *t^4)*X(t)^6+2*t^5*X(t)^5+(2*t^4-3*t^3+3*t^2)*X(t)^4+(3*t^3-3*t^2)*X(t)^3+2*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, 3, 10, 41, 179, 827, 3950, 19386, 97113, 494661, 2554083, 13337936, 70324604, 373849722, 2001619073, 10783847589, 58419179458, 318024935073, 1738871152829, 9545181145223, 52583398958366, 290616463331244, 1610929586225058 , 8953867855047620, 49891712510698204, 278641912099169358, 1559519170839178061, 8745710896013884847, 49136062800736764092, 276536887865054488569, 1558852667936799799142, 8800607916005609723274, 49754935396997975619417, 281669189376816114261257, 1596574168345667539893060, 9060560853415352901595687, 51476546715345771630718086, 292769869985696745221868563, 1666795403383774724971173590, 9498504052172587922865202811] Theorem 67 : 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 68 : 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 69 : 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 70 : 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 71 : Let a(n) be number of words of length n in the alphabet, {-2, -1, 3}, that s\ um-up to 0 and whose partial sums are never negative, in other words gen\ eralized Dyck words with alphabet, {-2, -1, 3}, 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 10 10 8 8 5 7 6 5 6 5 5 X(t) t - X(t) t + t X(t) + (-t - t ) X(t) + 2 t X(t) 4 3 4 3 3 + (t + 3 t ) X(t) - t X(t) - X(t) + 1 = 0 and in Maple notation X(t)^10*t^10-X(t)^8*t^8+t^5*X(t)^7+(-t^6-t^5)*X(t)^6+2*t^5*X(t)^5+(t^4+3*t^3)*X (t)^4-t^3*X(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, 2, 1, 2, 17, 17, 43, 220, 322, 877, 3495, 6513, 18246, 63069, 137364, 389520, 1240075, 2986569, 8518188, 25878573, 66493272, 190276431, 563345305, 1509236554, 4329167366, 12645267502, 34810974533, 100065738510, 290410780163, 813932210810, 2344530239608, 6787557305833, 19254309739598, 55576193661986, 160849076903780, 460095808260232, 1330726621028529, 3854609838686679, 11091289883698738] ------------------------------------------------------------- Theorem 72 : Let a(n) be number of words of length n in the alphabet, {-2, -1, 0, 3}, tha\ t sum-up to 0 and whose partial sums are never negative, in other words \ generalized Dyck words with alphabet, {-2, -1, 0, 3}, 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 10 10 8 8 7 6 5 7 5 6 5 5 t X(t) - t X(t) + (t - 2 t + t ) X(t) - t X(t) + 2 t X(t) 4 3 4 3 3 + (-2 t + 3 t ) X(t) - t X(t) + (t - 1) X(t) + 1 = 0 and in Maple notation t^10*X(t)^10-t^8*X(t)^8+(t^7-2*t^6+t^5)*X(t)^7-t^5*X(t)^6+2*t^5*X(t)^5+(-2*t^4+ 3*t^3)*X(t)^4-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, 3, 10, 28, 85, 284, 950, 3194, 11022, 38663, 136648, 487293, 1753721, 6355487, 23165983, 84904035, 312705898, 1156649565, 4294810000, 16003643559, 59825332308, 224294452660, 843171200441, 3177498031365, 12001748172016, 45427657059164, 172285169942194, 654589135217652, 2491324791058185, 9496969190260568, 36256823075139673, 138613424885860426, 530635011047750827, 2033896545856682338, 7805022714021742130, 29985014430235892751, 115317102985146210440, 443934701340502461213, 1710640168411094685146] Theorem 73 : 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 74 : 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 Theorem 75 : Let a(n) be number of words of length n in the alphabet, {-2, -1, 1, 3}, tha\ t sum-up to 0 and whose partial sums are never negative, in other words \ generalized Dyck words with alphabet, {-2, -1, 1, 3}, 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 10 10 9 9 8 8 7 5 7 6 5 6 t X(t) + t X(t) - t X(t) + (-2 t + t ) X(t) + (-t - t ) X(t) 5 4 5 4 3 4 2 2 + (3 t + 2 t ) X(t) + (2 t + 3 t ) X(t) + t X(t) - X(t) + 1 = 0 and in Maple notation t^10*X(t)^10+t^9*X(t)^9-t^8*X(t)^8+(-2*t^7+t^5)*X(t)^7+(-t^6-t^5)*X(t)^6+(3*t^5 +2*t^4)*X(t)^5+(2*t^4+3*t^3)*X(t)^4+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, 3, 6, 21, 66, 206, 694, 2343, 8006, 27865, 97842, 346560, 1238017, 4451859, 16104105, 58569206, 214013423, 785324563, 2892811352, 10692822131, 39649034086, 147443120646, 549749019862, 2054764213960, 7697272862049, 28894655660026, 108677590661657, 409493420065062, 1545562470596778, 5842680517890137, 22119801344728755, 83860065166879578, 318345575635570632, 1209984597470883971, 4604353717435642583, 17540344670612420506, 66890292116966006476, 255340921774236374052, 975637911204231539435] ------------------------------------------------------------- Theorem 76 : Let a(n) be number of words of length n in the alphabet, {-2, -1, 0, 1, 3}, \ 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, 3}, 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 10 10 9 9 8 8 7 6 5 7 5 6 t X(t) + t X(t) - t X(t) + (-t - 2 t + t ) X(t) - t X(t) 5 4 5 4 3 4 2 2 + (t + 2 t ) X(t) + (-t + 3 t ) X(t) + t X(t) + (t - 1) X(t) + 1 = 0 and in Maple notation t^10*X(t)^10+t^9*X(t)^9-t^8*X(t)^8+(-t^7-2*t^6+t^5)*X(t)^7-t^5*X(t)^6+(t^5+2*t^ 4)*X(t)^5+(-t^4+3*t^3)*X(t)^4+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, 7, 25, 92, 358, 1446, 5983, 25240, 108204, 470011, 2064073, 9149121, 40879535, 183928036, 832593614, 3789259378, 17328270006, 79582794770, 366911986284, 1697559667124, 7879011111506, 36676059556332, 171180174657908, 800925420506151, 3755925917983035, 17650449866848961, 83108140886635519, 392032654365181642, 1852419911063297195, 8766935823870526347, 41553200625196027922, 197228810371226596772, 937367365159229449957, 4460569569962153974561, 21251125363950209328709, 101357805966449668487424, 483939199666396729329146, 2312913305429593079489647, 11064740221473415080489313 ] Theorem 77 : Let a(n) be number of words of length n in the alphabet, {-2, -1, 2, 3}, tha\ t sum-up to 0 and whose partial sums are never negative, in other words \ generalized Dyck words with alphabet, {-2, -1, 2, 3}, 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 10 10 8 7 8 5 7 5 6 4 5 3 4 t X(t) + (-t - t ) X(t) + t X(t) - 2 t X(t) - t X(t) + 3 t X(t) 2 3 2 2 + 2 t X(t) - t X(t) - X(t) + 1 = 0 and in Maple notation t^10*X(t)^10+(-t^8-t^7)*X(t)^8+t^5*X(t)^7-2*t^5*X(t)^6-t^4*X(t)^5+3*t^3*X(t)^4+ 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, 3, 3, 23, 48, 155, 612, 1609, 6255, 20608, 67954, 250621, 837858, 2997773, 10682234, 37447731, 135767710, 484626014, 1747304695, 6345838687, 22949010094, 83737139716, 305552771525, 1117272519230, 4101926037674, 15064915295407, 55488468018578, 204729501895013, 756350275118646, 2800027056148971, 10377918836812794, 38521413439022433, 143184883556986540, 532814894354798905, 1985211915360494824, 7404609038051674655, 27647122999848204744, 103334287176052280814, 386579072024085298844] ------------------------------------------------------------- Theorem 78 : Let a(n) be number of words of length n in the alphabet, {-2, -1, 0, 2, 3}, \ that sum-up to 0 and whose partial sums are never negative, in other wor\ ds generalized Dyck words with alphabet, {-2, -1, 0, 2, 3}, 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 10 10 7 8 7 6 5 7 6 5 6 t X(t) - t X(t) + (t - 2 t + t ) X(t) + (2 t - 2 t ) X(t) 5 4 5 4 3 4 3 2 3 2 2 + (t - t ) X(t) + (-3 t + 3 t ) X(t) + (-2 t + 2 t ) X(t) - t X(t) + (t - 1) X(t) + 1 = 0 and in Maple notation t^10*X(t)^10-t^7*X(t)^8+(t^7-2*t^6+t^5)*X(t)^7+(2*t^6-2*t^5)*X(t)^6+(t^5-t^4)*X (t)^5+(-3*t^4+3*t^3)*X(t)^4+(-2*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, 7, 22, 79, 307, 1206, 4891, 20294, 85397, 364381, 1572540, 6849487, 30078324, 133017168, 591868095, 2647908096, 11903633098, 53744460606, 243601241475, 1108042670458, 5056220920464, 23140233405411, 106188147445720, 488492678546426, 2252327637335970, 10406949400999442, 48180175017505798, 223464105239450550, 1038218812932800540, 4831300777052271853, 22515941339920038323, 105081847077888360986, 491067287805709896478, 2297720776244536503419, 10763818893782103978538, 50480165579368787346737, 236992698161835603541447, 1113744225852760409324285, 5239025683479528150174195] Theorem 79 : Let a(n) be number of words of length n in the alphabet, {-2, -1, 1, 2, 3}, \ that sum-up to 0 and whose partial sums are never negative, in other wor\ ds generalized Dyck words with alphabet, {-2, -1, 1, 2, 3}, 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 10 10 9 9 8 7 8 7 5 7 t X(t) + t X(t) + (-t - t ) X(t) + (-2 t + t ) X(t) 6 5 6 5 4 5 4 3 4 + (-3 t - 2 t ) X(t) + (t + t ) X(t) + (2 t + 3 t ) X(t) 3 2 3 + (t + 2 t ) X(t) - X(t) + 1 = 0 and in Maple notation t^10*X(t)^10+t^9*X(t)^9+(-t^8-t^7)*X(t)^8+(-2*t^7+t^5)*X(t)^7+(-3*t^6-2*t^5)*X( t)^6+(t^5+t^4)*X(t)^5+(2*t^4+3*t^3)*X(t)^4+(t^3+2*t^2)*X(t)^3-X(t)+1 = 0 For the sake of the OEIS here are the first 40 terms, starting with n=0 [1, 0, 2, 4, 15, 54, 197, 778, 3046, 12378, 50688, 210821, 885836, 3755794, 16053550, 69077136, 299051044, 1301497997, 5691174700, 24991961429, 110168793923, 487328507125, 2162490768266, 9623634039899, 42941087514502, 192072611056724, 861064794485586, 3868232998947027, 17411324425937991, 78511976428487851, 354628109413966644, 1604341160570722942, 7268823842760461184 , 32978945219886339519, 149823281943148384308, 681490024904553949414, 3103471368624092952988, 14148708406910701942775, 64571602595986047193440, 294984276632934745080426, 1348861148942366519449640] ------------------------------------------------------------- Theorem 80 : Let a(n) be number of words of length n in the alphabet, {-2, -1, 0, 1, 2, 3}, that sum-up to 0 and whose partial sums are never negative, in other wo\ rds generalized Dyck words with alphabet, {-2, -1, 0, 1, 2, 3}, 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 10 10 9 9 7 8 7 6 5 7 6 5 6 t X(t) + t X(t) - t X(t) + (-t - 2 t + t ) X(t) + (-t - 2 t ) X(t) 4 5 4 3 4 3 2 3 + t X(t) + (-t + 3 t ) X(t) + (-t + 2 t ) X(t) + (t - 1) X(t) + 1 = 0 and in Maple notation t^10*X(t)^10+t^9*X(t)^9-t^7*X(t)^8+(-t^7-2*t^6+t^5)*X(t)^7+(-t^6-2*t^5)*X(t)^6+ t^4*X(t)^5+(-t^4+3*t^3)*X(t)^4+(-t^3+2*t^2)*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, 3, 11, 44, 190, 857, 3999, 19141, 93451, 463597, 2330192, 11841436, 60737564, 314037617, 1635010848, 8564502901, 45104412950, 238679263409, 1268447909245, 6767192648507, 36229650290177, 194581957851056, 1048104640156130 , 5660645539570325, 30647463900374600, 166306390980836921, 904350295353856771, 4927345554647204260, 26895513415572032779, 147056696229838786223, 805342490521464594828, 4416969155405856460129, 24259231650411277913126, 133414501686055990798601, 734631912712913399194858, 4049929180952759086436906, 22351593694071243004283938, 123488831783691674039588963, 682938544921178662112865749, 3780495262266361214563745021] Theorem 81 : Let a(n) be number of words of length n in the alphabet, {-3, -2, -1, 1}, th\ at sum-up to 0 and whose partial sums are never negative, in other words\ generalized Dyck words with alphabet, {-3, -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 4 4 3 3 2 2 X(t) t + X(t) t + X(t) t - X(t) + 1 = 0 and in Maple notation X(t)^4*t^4+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, 3, 5, 14, 28, 74, 168, 432, 1045, 2684, 6721, 17355, 44408, 115502 , 299812, 785570, 2060094, 5434475, 14362841, 38114760, 101360402, 270373303, 722696570, 1936398635, 5198249550, 13982513625, 37674988080, 101685303765, 274867141845, 744093631842, 2017066320624, 5474900965050, 14878450339822, 40479971557162, 110253945275970, 300605644859552, 820399033872096, 2241084167717824] Furthermore a(n) satisfies the following linear recurrence equation with pol\ ynomial coefficients 4 3 2 (2177255 n - 7596148 n + 5392195 n + 643078 n - 697632) a(n - 1) a(n) = 1/3 ------------------------------------------------------------------- (3 n + 4) (n + 1) (5045 n - 7267) (3 n + 2) 4 3 2 (1846645 n - 6665962 n + 7690229 n - 2401076 n - 144828) a(n - 2) + 1/3 -------------------------------------------------------------------- (3 n + 4) (n + 1) (5045 n - 7267) (3 n + 2) 3 2 (n - 2) (9957995 n - 47994027 n + 64131424 n - 21792366) a(n - 3) - 1/3 ------------------------------------------------------------------- (3 n + 4) (n + 1) (5045 n - 7267) (3 n + 2) 2 (n - 2) (n - 3) (19850205 n - 61572608 n + 22999478) a(n - 4) - 1/3 -------------------------------------------------------------- (3 n + 4) (n + 1) (5045 n - 7267) (3 n + 2) (83255 n - 31418) (n - 2) (n - 3) (n - 4) a(n - 5) - 257/3 -------------------------------------------------- (3 n + 4) (n + 1) (5045 n - 7267) (3 n + 2) subject to the initial conditions a(1) = 0, a(2) = 1, a(3) = 1, a(4) = 3, a(5) = 5 and in Maple notation a(n) = 1/3*(2177255*n^4-7596148*n^3+5392195*n^2+643078*n-697632)/(3*n+4)/(n+1)/ (5045*n-7267)/(3*n+2)*a(n-1)+1/3*(1846645*n^4-6665962*n^3+7690229*n^2-2401076*n -144828)/(3*n+4)/(n+1)/(5045*n-7267)/(3*n+2)*a(n-2)-1/3*(n-2)*(9957995*n^3-\ 47994027*n^2+64131424*n-21792366)/(3*n+4)/(n+1)/(5045*n-7267)/(3*n+2)*a(n-3)-1/ 3*(n-2)*(n-3)*(19850205*n^2-61572608*n+22999478)/(3*n+4)/(n+1)/(5045*n-7267)/(3 *n+2)*a(n-4)-257/3*(83255*n-31418)*(n-2)*(n-3)*(n-4)/(3*n+4)/(n+1)/(5045*n-7267 )/(3*n+2)*a(n-5) a(1) = 0, a(2) = 1, a(3) = 1, a(4) = 3, a(5) = 5 Just for fun, using this recurrence we get that a(1000) = 435664937395013763787949579947984439584655565053233018263110658753\ 756208596803266887752602685360416819037939099907684543965531805330122822\ 028820144707111347228638419654525604014546772038884881826115094150090391\ 408270179162739057381181319825114086188469476854311934325015555718644409\ 136497974862056469106782342137085649208845212489297912951176488788681344\ 074162655693945522326874272619565681044420720296127403270759070332728078\ 5785975030073749500364 ------------------------------------------------------------- Theorem 82 : Let a(n) be number of words of length n in the alphabet, {-3, -2, -1, 0, 1}, that sum-up to 0 and whose partial sums are never negative, in other wo\ rds generalized Dyck words with alphabet, {-3, -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 4 4 3 3 2 2 t X(t) + t X(t) + t X(t) + (t - 1) X(t) + 1 = 0 and in Maple notation t^4*X(t)^4+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, 14, 41, 125, 393, 1265, 4147, 13798, 46476, 158170, 543050, 1878670, 6542330, 22915999, 80682987, 285378270, 1013564805, 3613262795, 12924536005, 46373266470, 166856922125, 601928551824, 2176616383346, 7888184659826, 28645799759632, 104224861693855, 379885129946864, 1386926469714491, 5071414788349655, 18571114244497835, 68099230660004675, 250038808009880790, 919183172864105235, 3382962549917829020, 12464250091478255375, 45971046526098151125, 169718503374474353075, 627161711811600906925] Furthermore a(n) satisfies the following linear recurrence equation with pol\ ynomial coefficients 4 3 2 (111457 n - 364730 n + 228995 n + 19310 n - 33312) a(n - 1) a(n) = 1/3 -------------------------------------------------------------- (3 n + 2) (133 n - 347) (3 n + 4) (n + 1) 4 3 2 (68503 n - 346618 n + 590627 n - 397748 n + 90564) a(n - 2) - 5/3 -------------------------------------------------------------- (3 n + 2) (133 n - 347) (3 n + 4) (n + 1) 3 2 (n - 2) (1933 n - 9435 n + 14354 n - 7518) a(n - 3) - 25/3 ----------------------------------------------------- (3 n + 2) (133 n - 347) (3 n + 4) (n + 1) 2 (n - 2) (n - 3) (1333 n - 4384 n + 2718) a(n - 4) - 125/3 -------------------------------------------------- (3 n + 2) (133 n - 347) (3 n + 4) (n + 1) (733 n - 400) (n - 2) (n - 3) (n - 4) a(n - 5) - 625/3 ---------------------------------------------- (3 n + 2) (133 n - 347) (3 n + 4) (n + 1) subject to the initial conditions a(1) = 1, a(2) = 2, a(3) = 5, a(4) = 14, a(5) = 41 and in Maple notation a(n) = 1/3*(111457*n^4-364730*n^3+228995*n^2+19310*n-33312)/(3*n+2)/(133*n-347) /(3*n+4)/(n+1)*a(n-1)-5/3*(68503*n^4-346618*n^3+590627*n^2-397748*n+90564)/(3*n +2)/(133*n-347)/(3*n+4)/(n+1)*a(n-2)-25/3*(n-2)*(1933*n^3-9435*n^2+14354*n-7518 )/(3*n+2)/(133*n-347)/(3*n+4)/(n+1)*a(n-3)-125/3*(n-2)*(n-3)*(1333*n^2-4384*n+ 2718)/(3*n+2)/(133*n-347)/(3*n+4)/(n+1)*a(n-4)-625/3*(733*n-400)*(n-2)*(n-3)*(n -4)/(3*n+2)/(133*n-347)/(3*n+4)/(n+1)*a(n-5) a(1) = 1, a(2) = 2, a(3) = 5, a(4) = 14, a(5) = 41 Just for fun, using this recurrence we get that a(1000) = 117711848358311507260501387450472721192196780278057100773141629457\ 874549270935251680967630248998259630513560544734950180528735564258216410\ 768101409514739674823181662227396770728090832354033859082570512348398794\ 132270732161950316476493826456852828897097622431227426259093467430724875\ 518644407663649770737001565751229059320413263413446107962205949393372351\ 729403777736808047472181812619862819908851807149180742176833625681554567\ 135995935399985938640715789068549459810334387377454614535889797814949170\ 492174615667138189874262655322845442819474979342277457355041027689452773\ 3576496425 Theorem 83 : Let a(n) be number of words of length n in the alphabet, {-3, -2, -1, 2}, th\ at sum-up to 0 and whose partial sums are never negative, in other words\ generalized Dyck words with alphabet, {-3, -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 10 10 9 9 7 8 7 5 7 6 5 6 t X(t) + t X(t) - t X(t) + (-t + t ) X(t) + (-2 t - t ) X(t) 5 4 5 3 2 3 2 2 + (2 t + t ) X(t) + (t + 2 t ) X(t) - t X(t) - X(t) + 1 = 0 and in Maple notation t^10*X(t)^10+t^9*X(t)^9-t^7*X(t)^8+(-t^7+t^5)*X(t)^7+(-2*t^6-t^5)*X(t)^6+(2*t^5 +t^4)*X(t)^5+(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, 5, 9, 31, 78, 248, 705, 2196, 6632, 20780, 64709, 204902, 650000, 2080483, 6683564, 21593311, 70024903, 228022074, 744976876, 2441850778, 8026618762, 26455041139, 87405982153, 289438774174, 960462359139, 3193366842536 , 10636635056279, 35489063311272, 118596791583351, 396914141297320, 1330230442462987, 4464042344334714, 14999217181926990, 50456596364848778, 169921812232536963, 572844723715864685, 1933116776188266041, 6529668152176835624] ------------------------------------------------------------- Theorem 84 : Let a(n) be number of words of length n in the alphabet, {-3, -2, -1, 0, 2}, that sum-up to 0 and whose partial sums are never negative, in other wo\ rds generalized Dyck words with alphabet, {-3, -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 10 10 9 9 8 7 8 6 5 7 6 5 6 t X(t) + t X(t) + (t - t ) X(t) + (-2 t + t ) X(t) + (-t - t ) X(t) 5 4 5 3 2 3 2 2 + (t + t ) X(t) + (-t + 2 t ) X(t) - X(t) t + (t - 1) X(t) + 1 = 0 and in Maple notation t^10*X(t)^10+t^9*X(t)^9+(t^8-t^7)*X(t)^8+(-2*t^6+t^5)*X(t)^7+(-t^6-t^5)*X(t)^6+ (t^5+t^4)*X(t)^5+(-t^3+2*t^2)*X(t)^3-X(t)^2*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, 16, 55, 196, 716, 2679, 10234, 39760, 156574, 623470, 2506019, 10154474, 41436046, 170126128, 702301074, 2913227672, 12136812234, 50760652587, 213050186816, 897078215872, 3788365153993, 16041350732675, 68093344462829, 289708176300213, 1235196411711532, 5276732820209448, 22583402165895227, 96817980060306005, 415735725394935606, 1787845988028491975, 7699365883451094554 , 33201372215592007538, 143350931388519425892, 619666943480177517360, 2681648237641916287037, 11617307394761213641949, 50378568161599401802592, 218675969476171281960739] Theorem 85 : Let a(n) be number of words of length n in the alphabet, {-3, -2, -1, 3}, th\ at sum-up to 0 and whose partial sums are never negative, in other words\ generalized Dyck words with alphabet, {-3, -2, -1, 3}, 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 20 20 18 19 18 18 17 16 17 t X(t) - t X(t) + t X(t) + (-t - 3 t ) X(t) 16 15 14 16 15 14 15 + (t + 3 t + 3 t ) X(t) + (-2 t - 3 t ) X(t) 14 13 12 14 13 12 11 10 13 + (4 t + t + 3 t ) X(t) + (-5 t - 3 t - 2 t - 3 t ) X(t) 12 11 10 12 11 10 9 8 11 + (5 t + 5 t + 3 t ) X(t) + (-4 t - 6 t - t - t ) X(t) 10 9 8 6 10 9 8 7 6 9 + (t + 6 t + 6 t + t ) X(t) + (-4 t - 6 t - t - t ) X(t) 8 7 6 8 7 6 5 4 7 + (5 t + 5 t + 3 t ) X(t) + (-5 t - 3 t - 2 t - 3 t ) X(t) 6 5 4 6 5 4 5 + (4 t + t + 3 t ) X(t) + (-2 t - 3 t ) X(t) 4 3 2 4 3 2 3 2 2 + (t + 3 t + 3 t ) X(t) + (-t - 3 t ) X(t) + t X(t) - X(t) + 1 = 0 and in Maple notation t^20*X(t)^20-t^18*X(t)^19+t^18*X(t)^18+(-t^17-3*t^16)*X(t)^17+(t^16+3*t^15+3*t^ 14)*X(t)^16+(-2*t^15-3*t^14)*X(t)^15+(4*t^14+t^13+3*t^12)*X(t)^14+(-5*t^13-3*t^ 12-2*t^11-3*t^10)*X(t)^13+(5*t^12+5*t^11+3*t^10)*X(t)^12+(-4*t^11-6*t^10-t^9-t^ 8)*X(t)^11+(t^10+6*t^9+6*t^8+t^6)*X(t)^10+(-4*t^9-6*t^8-t^7-t^6)*X(t)^9+(5*t^8+ 5*t^7+3*t^6)*X(t)^8+(-5*t^7-3*t^6-2*t^5-3*t^4)*X(t)^7+(4*t^6+t^5+3*t^4)*X(t)^6+ (-2*t^5-3*t^4)*X(t)^5+(t^4+3*t^3+3*t^2)*X(t)^4+(-t^3-3*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, 2, 3, 16, 33, 115, 390, 1087, 4060, 12555, 42953, 148067, 492739, 1735298, 5944320, 20744252, 72905575, 254998049, 903660769, 3195209422, 11355589072, 40507136044, 144620988953, 518478617875, 1861257943227, 6697455408050, 24152234870325, 87226107921628, 315651869078757, 1143924927595869, 4151936835886485, 15091681888691404, 54925223488389666, 200157938880285184, 730258764785275647, 2667274260621421838, 9752675597285646950, 35695329641773808896, 130773052695581564343] ------------------------------------------------------------- Theorem 86 : Let a(n) be number of words of length n in the alphabet, {-3, -2, -1, 0, 3}, that sum-up to 0 and whose partial sums are never negative, in other wo\ rds generalized Dyck words with alphabet, {-3, -2, -1, 0, 3}, 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 20 20 19 18 19 18 18 17 16 17 t X(t) + (t - t ) X(t) + t X(t) + (2 t - 3 t ) X(t) 16 15 14 16 15 14 15 + (t - 3 t + 3 t ) X(t) + (t - 3 t ) X(t) 14 13 12 14 13 12 11 10 13 + (6 t - 5 t + 3 t ) X(t) + (-t - 8 t + 7 t - 3 t ) X(t) 12 11 10 12 11 10 9 8 11 + (3 t - t + 3 t ) X(t) + (2 t - 7 t + 2 t - t ) X(t) 10 9 8 7 6 10 + (2 t - 10 t + 12 t - 4 t + t ) X(t) 9 8 7 6 9 8 7 6 8 + (2 t - 7 t + 2 t - t ) X(t) + (3 t - t + 3 t ) X(t) 7 6 5 4 7 6 5 4 6 + (-t - 8 t + 7 t - 3 t ) X(t) + (6 t - 5 t + 3 t ) X(t) 5 4 5 4 3 2 4 3 2 3 + (t - 3 t ) X(t) + (t - 3 t + 3 t ) X(t) + (2 t - 3 t ) X(t) 2 2 + t X(t) + (t - 1) X(t) + 1 = 0 and in Maple notation t^20*X(t)^20+(t^19-t^18)*X(t)^19+t^18*X(t)^18+(2*t^17-3*t^16)*X(t)^17+(t^16-3*t ^15+3*t^14)*X(t)^16+(t^15-3*t^14)*X(t)^15+(6*t^14-5*t^13+3*t^12)*X(t)^14+(-t^13 -8*t^12+7*t^11-3*t^10)*X(t)^13+(3*t^12-t^11+3*t^10)*X(t)^12+(2*t^11-7*t^10+2*t^ 9-t^8)*X(t)^11+(2*t^10-10*t^9+12*t^8-4*t^7+t^6)*X(t)^10+(2*t^9-7*t^8+2*t^7-t^6) *X(t)^9+(3*t^8-t^7+3*t^6)*X(t)^8+(-t^7-8*t^6+7*t^5-3*t^4)*X(t)^7+(6*t^6-5*t^5+3 *t^4)*X(t)^6+(t^5-3*t^4)*X(t)^5+(t^4-3*t^3+3*t^2)*X(t)^4+(2*t^3-3*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, 6, 18, 62, 230, 879, 3481, 14108, 58158, 243314, 1029999, 4403397, 18985458, 82455222, 360393501, 1584051367, 6997128913, 31045539212, 138296932691, 618291385895, 2773304484578, 12476734334348, 56285216856132, 254555227938556, 1153929593249383, 5242169232823971, 23862180549759162, 108821946576020609, 497136987107388944, 2274783622443835103, 10424718711428141738, 47841928082007748190, 219855066265262106699, 1011612777729798723621, 4660274592113086968304, 21493142670920856200374, 99232429198268238875108, 458615453846739302558685, 2121597433893231246682433] Theorem 87 : Let a(n) be number of words of length n in the alphabet, {-3, -2, -1, 1, 2}, that sum-up to 0 and whose partial sums are never negative, in other wo\ rds generalized Dyck words with alphabet, {-3, -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 10 10 9 9 8 7 8 7 5 7 t X(t) + t X(t) + (-t - t ) X(t) + (-2 t + t ) X(t) 6 5 6 5 4 5 4 3 4 + (-3 t - 2 t ) X(t) + (t + t ) X(t) + (2 t + 3 t ) X(t) 3 2 3 + (t + 2 t ) X(t) - X(t) + 1 = 0 and in Maple notation t^10*X(t)^10+t^9*X(t)^9+(-t^8-t^7)*X(t)^8+(-2*t^7+t^5)*X(t)^7+(-3*t^6-2*t^5)*X( t)^6+(t^5+t^4)*X(t)^5+(2*t^4+3*t^3)*X(t)^4+(t^3+2*t^2)*X(t)^3-X(t)+1 = 0 For the sake of the OEIS here are the first 40 terms, starting with n=0 [1, 0, 2, 4, 15, 54, 197, 778, 3046, 12378, 50688, 210821, 885836, 3755794, 16053550, 69077136, 299051044, 1301497997, 5691174700, 24991961429, 110168793923, 487328507125, 2162490768266, 9623634039899, 42941087514502, 192072611056724, 861064794485586, 3868232998947027, 17411324425937991, 78511976428487851, 354628109413966644, 1604341160570722942, 7268823842760461184 , 32978945219886339519, 149823281943148384308, 681490024904553949414, 3103471368624092952988, 14148708406910701942775, 64571602595986047193440, 294984276632934745080426, 1348861148942366519449640] ------------------------------------------------------------- Theorem 88 : Let a(n) be number of words of length n in the alphabet, {-3, -2, -1, 0, 1, 2}, that sum-up to 0 and whose partial sums are never negative, in other wo\ rds generalized Dyck words with alphabet, {-3, -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 10 10 9 9 7 8 7 6 5 7 6 5 6 t X(t) + t X(t) - t X(t) + (-t - 2 t + t ) X(t) + (-t - 2 t ) X(t) 4 5 4 3 4 3 2 3 + t X(t) + (-t + 3 t ) X(t) + (-t + 2 t ) X(t) + (t - 1) X(t) + 1 = 0 and in Maple notation t^10*X(t)^10+t^9*X(t)^9-t^7*X(t)^8+(-t^7-2*t^6+t^5)*X(t)^7+(-t^6-2*t^5)*X(t)^6+ t^4*X(t)^5+(-t^4+3*t^3)*X(t)^4+(-t^3+2*t^2)*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, 3, 11, 44, 190, 857, 3999, 19141, 93451, 463597, 2330192, 11841436, 60737564, 314037617, 1635010848, 8564502901, 45104412950, 238679263409, 1268447909245, 6767192648507, 36229650290177, 194581957851056, 1048104640156130 , 5660645539570325, 30647463900374600, 166306390980836921, 904350295353856771, 4927345554647204260, 26895513415572032779, 147056696229838786223, 805342490521464594828, 4416969155405856460129, 24259231650411277913126, 133414501686055990798601, 734631912712913399194858, 4049929180952759086436906, 22351593694071243004283938, 123488831783691674039588963, 682938544921178662112865749, 3780495262266361214563745021] Theorem 89 : Let a(n) be number of words of length n in the alphabet, {-3, -2, -1, 1, 3}, that sum-up to 0 and whose partial sums are never negative, in other wo\ rds generalized Dyck words with alphabet, {-3, -2, -1, 1, 3}, 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 20 20 18 19 18 18 16 17 t X(t) - t X(t) + 2 t X(t) - 3 t X(t) 16 15 14 16 15 15 + (2 t + 3 t + 3 t ) X(t) + 2 t X(t) 14 13 12 14 13 12 11 10 13 + (3 t + 3 t + 3 t ) X(t) + (-t + t - 2 t - 3 t ) X(t) 11 10 12 11 10 9 8 11 + (5 t + 2 t ) X(t) + (-4 t - t - t - t ) X(t) 10 9 8 6 10 9 8 7 6 9 + (-6 t + 2 t + 2 t + t ) X(t) + (-4 t - t - t - t ) X(t) 7 6 8 7 6 5 4 7 + (5 t + 2 t ) X(t) + (-t + t - 2 t - 3 t ) X(t) 6 5 4 6 5 5 4 3 2 4 + (3 t + 3 t + 3 t ) X(t) + 2 t X(t) + (2 t + 3 t + 3 t ) X(t) 2 3 2 2 - 3 t X(t) + 2 t X(t) - X(t) + 1 = 0 and in Maple notation t^20*X(t)^20-t^18*X(t)^19+2*t^18*X(t)^18-3*t^16*X(t)^17+(2*t^16+3*t^15+3*t^14)* X(t)^16+2*t^15*X(t)^15+(3*t^14+3*t^13+3*t^12)*X(t)^14+(-t^13+t^12-2*t^11-3*t^10 )*X(t)^13+(5*t^11+2*t^10)*X(t)^12+(-4*t^11-t^10-t^9-t^8)*X(t)^11+(-6*t^10+2*t^9 +2*t^8+t^6)*X(t)^10+(-4*t^9-t^8-t^7-t^6)*X(t)^9+(5*t^7+2*t^6)*X(t)^8+(-t^7+t^6-\ 2*t^5-3*t^4)*X(t)^7+(3*t^6+3*t^5+3*t^4)*X(t)^6+2*t^5*X(t)^5+(2*t^4+3*t^3+3*t^2) *X(t)^4-3*t^2*X(t)^3+2*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, 2, 3, 16, 48, 208, 778, 3305, 13499, 57999, 247426, 1080038, 4725641, 20929207, 93118686, 417432294, 1879871543, 8510737402, 38686261748, 176564376942, 808602162394, 3715180084791, 17119059401564, 79095591109170, 366346002995878, 1700682157965819, 7911704506752742, 36878195675123781, 172211459271608956, 805555550951269942, 3774174295168643551, 17709186843741843257, 83212029736653279793, 391515337546259034843, 1844394597724020439367, 8699040178460691523419, 41074630787462631404420, 194149125687057441136325, 918614252117154387538888, 4350560194974760150572558] ------------------------------------------------------------- Theorem 90 : Let a(n) be number of words of length n in the alphabet, {-3, -2, -1, 0, 1, 3}, that sum-up to 0 and whose partial sums are never negative, in other wo\ rds generalized Dyck words with alphabet, {-3, -2, -1, 0, 1, 3}, 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 20 20 19 18 19 18 18 17 16 17 t X(t) + (t - t ) X(t) + 2 t X(t) + (3 t - 3 t ) X(t) 16 15 14 16 15 15 + (2 t - 3 t + 3 t ) X(t) + 2 t X(t) 14 13 12 14 13 12 11 10 13 + (3 t - 3 t + 3 t ) X(t) + (-t - 4 t + 7 t - 3 t ) X(t) 12 11 10 12 11 10 9 8 11 + (-3 t + t + 2 t ) X(t) + (-3 t - 2 t + 2 t - t ) X(t) 10 9 8 7 6 10 + (-5 t - 6 t + 8 t - 4 t + t ) X(t) 9 8 7 6 9 8 7 6 8 + (-3 t - 2 t + 2 t - t ) X(t) + (-3 t + t + 2 t ) X(t) 7 6 5 4 7 6 5 4 6 + (-t - 4 t + 7 t - 3 t ) X(t) + (3 t - 3 t + 3 t ) X(t) 5 5 4 3 2 4 3 2 3 + 2 t X(t) + (2 t - 3 t + 3 t ) X(t) + (3 t - 3 t ) X(t) 2 2 + 2 t X(t) + (t - 1) X(t) + 1 = 0 and in Maple notation t^20*X(t)^20+(t^19-t^18)*X(t)^19+2*t^18*X(t)^18+(3*t^17-3*t^16)*X(t)^17+(2*t^16 -3*t^15+3*t^14)*X(t)^16+2*t^15*X(t)^15+(3*t^14-3*t^13+3*t^12)*X(t)^14+(-t^13-4* t^12+7*t^11-3*t^10)*X(t)^13+(-3*t^12+t^11+2*t^10)*X(t)^12+(-3*t^11-2*t^10+2*t^9 -t^8)*X(t)^11+(-5*t^10-6*t^9+8*t^8-4*t^7+t^6)*X(t)^10+(-3*t^9-2*t^8+2*t^7-t^6)* X(t)^9+(-3*t^8+t^7+2*t^6)*X(t)^8+(-t^7-4*t^6+7*t^5-3*t^4)*X(t)^7+(3*t^6-3*t^5+3 *t^4)*X(t)^6+2*t^5*X(t)^5+(2*t^4-3*t^3+3*t^2)*X(t)^4+(3*t^3-3*t^2)*X(t)^3+2*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, 3, 10, 41, 179, 827, 3950, 19386, 97113, 494661, 2554083, 13337936, 70324604, 373849722, 2001619073, 10783847589, 58419179458, 318024935073, 1738871152829, 9545181145223, 52583398958366, 290616463331244, 1610929586225058 , 8953867855047620, 49891712510698204, 278641912099169358, 1559519170839178061, 8745710896013884847, 49136062800736764092, 276536887865054488569, 1558852667936799799142, 8800607916005609723274, 49754935396997975619417, 281669189376816114261257, 1596574168345667539893060, 9060560853415352901595687, 51476546715345771630718086, 292769869985696745221868563, 1666795403383774724971173590, 9498504052172587922865202811] Theorem 91 : Let a(n) be number of words of length n in the alphabet, {-3, -2, -1, 2, 3}, that sum-up to 0 and whose partial sums are never negative, in other wo\ rds generalized Dyck words with alphabet, {-3, -2, -1, 2, 3}, 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 20 20 18 19 16 17 16 15 14 16 t X(t) - t X(t) - t X(t) + (2 t + 3 t + 3 t ) X(t) 15 14 15 14 13 12 14 + (t - 4 t ) X(t) + (2 t + t + 2 t ) X(t) 13 12 11 10 13 12 11 10 12 + (-3 t - 2 t - t - 3 t ) X(t) + (t + 7 t + 8 t ) X(t) 11 10 9 8 11 10 9 8 6 10 + (-4 t - 7 t - t - 2 t ) X(t) + (t - 2 t + 5 t + t ) X(t) 9 8 7 6 9 8 7 6 8 + (-4 t - 7 t - t - 2 t ) X(t) + (t + 7 t + 8 t ) X(t) 7 6 5 4 7 6 5 4 6 + (-3 t - 2 t - t - 3 t ) X(t) + (2 t + t + 2 t ) X(t) 5 4 5 4 3 2 4 2 3 + (t - 4 t ) X(t) + (2 t + 3 t + 3 t ) X(t) - t X(t) - X(t) + 1 = 0 and in Maple notation t^20*X(t)^20-t^18*X(t)^19-t^16*X(t)^17+(2*t^16+3*t^15+3*t^14)*X(t)^16+(t^15-4*t ^14)*X(t)^15+(2*t^14+t^13+2*t^12)*X(t)^14+(-3*t^13-2*t^12-t^11-3*t^10)*X(t)^13+ (t^12+7*t^11+8*t^10)*X(t)^12+(-4*t^11-7*t^10-t^9-2*t^8)*X(t)^11+(t^10-2*t^9+5*t ^8+t^6)*X(t)^10+(-4*t^9-7*t^8-t^7-2*t^6)*X(t)^9+(t^8+7*t^7+8*t^6)*X(t)^8+(-3*t^ 7-2*t^6-t^5-3*t^4)*X(t)^7+(2*t^6+t^5+2*t^4)*X(t)^6+(t^5-4*t^4)*X(t)^5+(2*t^4+3* t^3+3*t^2)*X(t)^4-t^2*X(t)^3-X(t)+1 = 0 For the sake of the OEIS here are the first 40 terms, starting with n=0 [1, 0, 2, 3, 15, 52, 196, 848, 3285, 14647, 60702, 270321, 1175419, 5255914, 23491263, 106039951, 481526629, 2196502989, 10079226967, 46405794075, 214644323424, 995842152796, 4636334700470, 21645379432275, 101333050920532, 475554054349281, 2236867470931726, 10543910516031653, 49798007373922185, 235624174511043642, 1116777689178292522, 5301626970881411615, 25205850251590771049, 120006708503224545684, 572117331555550458916, 2730911696937623440681, 13050977933834611429924, 62440110843797303986797, 299050203169880371941497, 1433708348090695408846840, 6880058216300684749855770] ------------------------------------------------------------- Theorem 92 : Let a(n) be number of words of length n in the alphabet, {-3, -2, -1, 0, 2, 3}, that sum-up to 0 and whose partial sums are never negative, in other wo\ rds generalized Dyck words with alphabet, {-3, -2, -1, 0, 2, 3}, 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 20 20 19 18 19 17 16 17 t X(t) + (t - t ) X(t) + (t - t ) X(t) 16 15 14 16 15 14 15 + (2 t - 3 t + 3 t ) X(t) + (5 t - 4 t ) X(t) 14 13 12 14 13 12 11 10 13 + (3 t - 3 t + 2 t ) X(t) + (t - 9 t + 8 t - 3 t ) X(t) 12 11 10 12 11 10 9 8 11 + (2 t - 9 t + 8 t ) X(t) + (4 t - 11 t + 5 t - 2 t ) X(t) 10 9 8 7 6 10 + (9 t - 16 t + 11 t - 4 t + t ) X(t) 9 8 7 6 9 8 7 6 8 + (4 t - 11 t + 5 t - 2 t ) X(t) + (2 t - 9 t + 8 t ) X(t) 7 6 5 4 7 6 5 4 6 + (t - 9 t + 8 t - 3 t ) X(t) + (3 t - 3 t + 2 t ) X(t) 5 4 5 4 3 2 4 3 2 3 + (5 t - 4 t ) X(t) + (2 t - 3 t + 3 t ) X(t) + (t - t ) X(t) + (t - 1) X(t) + 1 = 0 and in Maple notation t^20*X(t)^20+(t^19-t^18)*X(t)^19+(t^17-t^16)*X(t)^17+(2*t^16-3*t^15+3*t^14)*X(t )^16+(5*t^15-4*t^14)*X(t)^15+(3*t^14-3*t^13+2*t^12)*X(t)^14+(t^13-9*t^12+8*t^11 -3*t^10)*X(t)^13+(2*t^12-9*t^11+8*t^10)*X(t)^12+(4*t^11-11*t^10+5*t^9-2*t^8)*X( t)^11+(9*t^10-16*t^9+11*t^8-4*t^7+t^6)*X(t)^10+(4*t^9-11*t^8+5*t^7-2*t^6)*X(t)^ 9+(2*t^8-9*t^7+8*t^6)*X(t)^8+(t^7-9*t^6+8*t^5-3*t^4)*X(t)^7+(3*t^6-3*t^5+2*t^4) *X(t)^6+(5*t^5-4*t^4)*X(t)^5+(2*t^4-3*t^3+3*t^2)*X(t)^4+(t^3-t^2)*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, 3, 10, 40, 178, 824, 3985, 19744, 99971, 514622, 2685625, 14176140, 75552739, 406004201, 2197435059, 11967922244, 65541745451, 360700764547, 1993799140084, 11064460304559, 61621191297826, 344302222977332, 1929464284971942, 10842102255389729, 61076711461196642, 344857477219235278, 1951332407647841139, 11063287357056217098, 62840413117965029735, 357554540536489974226, 2037725561786030373678, 11630689244938304167132, 66478588142168708946990, 380485775178651410710264, 2180430261152798312070968, 12510155725442309587379111, 71857488874878429977624954, 413184893247251385429807144, 2378242645226788683602509799, 13702040691074329300256215649] Theorem 93 : Let a(n) be number of words of length n in the alphabet, {-3, -2, -1, 1, 2, 3}, that sum-up to 0 and whose partial sums are never negative, in other wo\ rds generalized Dyck words with alphabet, {-3, -2, -1, 1, 2, 3}, 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 14 14 13 12 13 12 11 12 t X(t) + (-t - t ) X(t) + (t + t ) X(t) 10 9 8 10 9 8 7 9 + (2 t + 4 t + 2 t ) X(t) + (-2 t - 3 t - t ) X(t) 8 7 6 8 6 4 7 6 5 4 6 + (2 t + 3 t + t ) X(t) + (3 t - t ) X(t) + (2 t + 3 t + t ) X(t) 5 4 3 5 4 3 2 4 2 2 + (-2 t - 3 t - t ) X(t) + (2 t + 4 t + 2 t ) X(t) + (t + t) X(t) + (-1 - t) X(t) + 1 = 0 and in Maple notation t^14*X(t)^14+(-t^13-t^12)*X(t)^13+(t^12+t^11)*X(t)^12+(2*t^10+4*t^9+2*t^8)*X(t) ^10+(-2*t^9-3*t^8-t^7)*X(t)^9+(2*t^8+3*t^7+t^6)*X(t)^8+(3*t^6-t^4)*X(t)^7+(2*t^ 6+3*t^5+t^4)*X(t)^6+(-2*t^5-3*t^4-t^3)*X(t)^5+(2*t^4+4*t^3+2*t^2)*X(t)^4+(t^2+t )*X(t)^2+(-1-t)*X(t)+1 = 0 For the sake of the OEIS here are the first 40 terms, starting with n=0 [1, 0, 3, 6, 35, 138, 689, 3272, 16522, 83792, 434749, 2278888, 12093271, 64741330, 349470487, 1899418046, 10387322922, 57111322368, 315523027610, 1750681516380, 9751416039535, 54507046599094, 305650440453943, 1718956630038438 , 9693209009913658, 54794959143735984, 310457570693809237, 1762705520682665544, 10027857107877385345, 57151686288411033894, 326279642607630891545, 1865707051569388661592, 10684308742180810054918, 61271675090362129009048, 351842023188483741065950, 2022914958249315372328220, 11644465032923181133034754 , 67103614092340792585084972, 387107295639502088469299294, 2235385554839773350530747032, 12920742642773813918875894076] ------------------------------------------------------------- Theorem 94 : Let a(n) be number of words of length n in the alphabet, {-3, -2, -1, 0, 1, 2, 3}, that sum-up to 0 and whose partial sums are ne\ ver negative, in other words generalized Dyck words with alphabet, {-3, -2, -1, 0, 1, 2, 3}, 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 14 14 12 13 11 12 8 10 8 7 9 t X(t) - t X(t) + t X(t) + 2 t X(t) + (-t - t ) X(t) 7 6 8 7 5 4 7 5 4 6 + (t + t ) X(t) + (-2 t + 3 t - t ) X(t) + (t + t ) X(t) 4 3 5 2 4 2 + (-t - t ) X(t) + 2 t X(t) + t X(t) - X(t) + 1 = 0 and in Maple notation t^14*X(t)^14-t^12*X(t)^13+t^11*X(t)^12+2*t^8*X(t)^10+(-t^8-t^7)*X(t)^9+(t^7+t^6 )*X(t)^8+(-2*t^7+3*t^5-t^4)*X(t)^7+(t^5+t^4)*X(t)^6+(-t^4-t^3)*X(t)^5+2*t^2*X(t )^4+t*X(t)^2-X(t)+1 = 0 For the sake of the OEIS here are the first 40 terms, starting with n=0 [1, 1, 4, 16, 78, 404, 2208, 12492, 72589, 430569, 2596471, 15870357, 98102191, 612222083, 3852015239, 24408653703, 155629858911, 997744376239, 6427757480074, 41590254520410, 270163621543421, 1761179219680657, 11518126473536150, 75550988639026472, 496903502922814883, 3276301699785273475, 21651737365052293752, 143392010048539681216, 951512897070252198743, 6325617269000698284183, 42124670980683179853768, 280974893354888460791436, 1876948634402839647757171, 12556008011264947476910859, 84106397884562746948770712, 564094351516713363938872580, 3787821430652406078255953016, 25463287808387505161701079382, 171356702233466085159294642588, 1154318648436112813089207110716, 7783348255132935571556557513023] -------------------------------- This ends this book that took, 394.272, seconds to create