Enumerating generalized Dyck words in the alphabet, {-4, -3, -2, -1, 0, 1, 2, 3, 4} By Shalosh B. Ekhad Theorem: Let a(n) be number of words of length n in the alphabet, {-4, -3, -2, -1, 0, 1, 2, 3, 4}, that sum-up to 0 and whose partial sums\ are never negative, in other words generalized Dyck words with alphabet, {-4, -3, -2, -1, 0, 1, 2, 3, 4}, 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 25 24 23 22 21 20 19 25 1 + (-9 t - 9 t + 27 t + 26 t - 24 t - 20 t + 4 t ) X(t) 24 23 22 21 20 19 18 24 + (9 t + 6 t - 25 t - 11 t + 16 t + 8 t + 4 t ) X(t) 23 22 21 20 19 18 17 23 + (-3 t - 6 t + 2 t + 12 t + 3 t - 8 t - 4 t ) X(t) 22 21 20 19 18 17 16 22 + (3 t + 3 t - 6 t - 12 t + t + 13 t + 6 t ) X(t) 21 19 17 16 15 21 + (-3 t + 10 t - 4 t - 2 t - 6 t ) X(t) 20 18 16 15 14 20 + (-3 t + 10 t - 4 t - 2 t - 6 t ) X(t) 19 18 17 16 15 14 13 19 + (3 t + 3 t - 6 t - 12 t + t + 13 t + 6 t ) X(t) 18 17 16 15 14 13 12 18 + (-3 t - 6 t + 2 t + 12 t + 3 t - 8 t - 4 t ) X(t) 17 16 15 14 13 12 11 17 + (9 t + 6 t - 25 t - 11 t + 16 t + 8 t + 4 t ) X(t) 16 15 14 13 12 11 10 16 + (-9 t - 9 t + 27 t + 26 t - 24 t - 20 t + 4 t ) X(t) 15 14 13 12 11 10 9 15 + (9 t + 6 t - 23 t - 11 t + 16 t + 3 t - 4 t ) X(t) 14 13 12 11 10 8 14 + (-5 t - 6 t + 7 t + 10 t + t + t ) X(t) 13 12 11 10 9 8 7 13 + (5 t + 5 t - 9 t - 13 t + 2 t + 6 t - t ) X(t) 12 11 10 9 8 7 6 12 + (-5 t - 2 t + 11 t + t - 2 t + 5 t - t ) X(t) 11 10 8 7 6 5 11 + (t + 2 t - t - 5 t - 4 t + t ) X(t) 10 9 8 7 6 10 + (-t - t + 2 t + t - t ) X(t) 9 8 7 6 5 4 9 + (t - 2 t - 4 t + 4 t + 5 t - t ) X(t) 8 7 6 5 4 8 + (3 t + 2 t - 6 t - 3 t + 3 t ) X(t) 7 6 5 4 3 7 + (-3 t - 3 t + 6 t + 4 t - 2 t ) X(t) 6 5 4 3 6 5 4 3 2 5 + (3 t + 2 t - 4 t - 3 t ) X(t) + (-2 t - 2 t + t + 2 t ) X(t) 4 3 2 4 3 2 3 2 2 + (2 t + 2 t - t ) X(t) + (-2 t - t + t) X(t) + (t + t) X(t) 41 41 40 39 40 39 38 39 + (-t - 1) X(t) + t X(t) + (-t - t ) X(t) + (t + t ) X(t) 38 37 36 38 37 36 35 37 + (-2 t - t + t ) X(t) + (2 t + 2 t - t ) X(t) 36 35 34 33 36 + (-2 t - 2 t + t + 2 t ) X(t) 35 34 33 32 35 + (3 t + 2 t - 4 t - 3 t ) X(t) 34 33 32 31 30 34 + (-3 t - 3 t + 6 t + 4 t - 2 t ) X(t) 33 32 31 30 29 33 + (3 t + 2 t - 6 t - 3 t + 3 t ) X(t) 32 31 30 29 28 27 32 + (t - 2 t - 4 t + 4 t + 5 t - t ) X(t) 31 30 29 28 27 31 + (-t - t + 2 t + t - t ) X(t) 30 29 27 26 25 24 30 + (t + 2 t - t - 5 t - 4 t + t ) X(t) 29 28 27 26 25 24 23 29 + (-5 t - 2 t + 11 t + t - 2 t + 5 t - t ) X(t) 28 27 26 25 24 23 22 28 + (5 t + 5 t - 9 t - 13 t + 2 t + 6 t - t ) X(t) 27 26 25 24 23 21 27 + (-5 t - 6 t + 7 t + 10 t + t + t ) X(t) 26 25 24 23 22 21 20 26 + (9 t + 6 t - 23 t - 11 t + 16 t + 3 t - 4 t ) X(t) = 0 and in Maple notation 1+(-9*t^25-9*t^24+27*t^23+26*t^22-24*t^21-20*t^20+4*t^19)*X(t)^25+(9*t^24+6*t^ 23-25*t^22-11*t^21+16*t^20+8*t^19+4*t^18)*X(t)^24+(-3*t^23-6*t^22+2*t^21+12*t^ 20+3*t^19-8*t^18-4*t^17)*X(t)^23+(3*t^22+3*t^21-6*t^20-12*t^19+t^18+13*t^17+6*t ^16)*X(t)^22+(-3*t^21+10*t^19-4*t^17-2*t^16-6*t^15)*X(t)^21+(-3*t^20+10*t^18-4* t^16-2*t^15-6*t^14)*X(t)^20+(3*t^19+3*t^18-6*t^17-12*t^16+t^15+13*t^14+6*t^13)* X(t)^19+(-3*t^18-6*t^17+2*t^16+12*t^15+3*t^14-8*t^13-4*t^12)*X(t)^18+(9*t^17+6* t^16-25*t^15-11*t^14+16*t^13+8*t^12+4*t^11)*X(t)^17+(-9*t^16-9*t^15+27*t^14+26* t^13-24*t^12-20*t^11+4*t^10)*X(t)^16+(9*t^15+6*t^14-23*t^13-11*t^12+16*t^11+3*t ^10-4*t^9)*X(t)^15+(-5*t^14-6*t^13+7*t^12+10*t^11+t^10+t^8)*X(t)^14+(5*t^13+5*t ^12-9*t^11-13*t^10+2*t^9+6*t^8-t^7)*X(t)^13+(-5*t^12-2*t^11+11*t^10+t^9-2*t^8+5 *t^7-t^6)*X(t)^12+(t^11+2*t^10-t^8-5*t^7-4*t^6+t^5)*X(t)^11+(-t^10-t^9+2*t^8+t^ 7-t^6)*X(t)^10+(t^9-2*t^8-4*t^7+4*t^6+5*t^5-t^4)*X(t)^9+(3*t^8+2*t^7-6*t^6-3*t^ 5+3*t^4)*X(t)^8+(-3*t^7-3*t^6+6*t^5+4*t^4-2*t^3)*X(t)^7+(3*t^6+2*t^5-4*t^4-3*t^ 3)*X(t)^6+(-2*t^5-2*t^4+t^3+2*t^2)*X(t)^5+(2*t^4+2*t^3-t^2)*X(t)^4+(-2*t^3-t^2+ t)*X(t)^3+(t^2+t)*X(t)^2+(-t-1)*X(t)+t^41*X(t)^41+(-t^40-t^39)*X(t)^40+(t^39+t^ 38)*X(t)^39+(-2*t^38-t^37+t^36)*X(t)^38+(2*t^37+2*t^36-t^35)*X(t)^37+(-2*t^36-2 *t^35+t^34+2*t^33)*X(t)^36+(3*t^35+2*t^34-4*t^33-3*t^32)*X(t)^35+(-3*t^34-3*t^ 33+6*t^32+4*t^31-2*t^30)*X(t)^34+(3*t^33+2*t^32-6*t^31-3*t^30+3*t^29)*X(t)^33+( t^32-2*t^31-4*t^30+4*t^29+5*t^28-t^27)*X(t)^32+(-t^31-t^30+2*t^29+t^28-t^27)*X( t)^31+(t^30+2*t^29-t^27-5*t^26-4*t^25+t^24)*X(t)^30+(-5*t^29-2*t^28+11*t^27+t^ 26-2*t^25+5*t^24-t^23)*X(t)^29+(5*t^28+5*t^27-9*t^26-13*t^25+2*t^24+6*t^23-t^22 )*X(t)^28+(-5*t^27-6*t^26+7*t^25+10*t^24+t^23+t^21)*X(t)^27+(9*t^26+6*t^25-23*t ^24-11*t^23+16*t^22+3*t^21-4*t^20)*X(t)^26 = 0 For the sake of the OEIS here are the first 40 terms, starting with n=0 [1, 1, 5, 25, 155, 1025, 7167, 51945, 387000, 2944860, 22791189, 178840639, 1419569398, 11377983292, 91957314063, 748575327757, 6132254500856, 50514620902564, 418174191239443, 3477075679541185, 29026557341147912, 243184916545458556, 2044067557528049283, 17232478968561332861, 145675346457153615684, 1234568101042095300792, 10486984657874905245736, 89272576880952129528940, 761466251483843529980628, 6507116905350667468556444, 55702940319430794066261997, 477606921304985522098704465, 4101304983885543148226175940, 35268945386962482983601023216, 303700399493123668840921421334, 2618468744797115208433272714332, 22603100175269952053843778324192, 195334580457972486800457888272878, 1689876286740354846991992320541887, 14634284012352002185902696555377733, 126854759312718274725560046087310168] This took, 834.448, seconds.