Generating functions for Enumerating Compositions of Depth Less than r, for \ r from 1 to, 10 By Shalosh B. Ekhad In the article "The Depth of Compositions" by A. Blecher, C. Brennan, A. Kn\ opfmacher and T. Mansour To appear in "Mathematics in Computer Science", it is proved (Prop. 1) that a c\ omposition is of depth STRICTLY less than r, iff, it AVOIDS the composition r(r+1) ...(2r-2)(2r-1)(2r-2)...r Using procedure GFone(C,x), in the Maple package Compositions.txt, we can co\ mpute the enumerating generating functions for for any given r. We will do it for r up to, 10 Theorem Number:, 1, The generating function enumerating compositions of depth\ STRICTLY less than, 1, is given as follows. Theorem: Let a(n) be the number of compositions of n avoiding, as a subcompo\ sition, [1] We have the following rational function for the (ordinary) generating functi\ on of a(n) infinity ----- \ n ) a(n) x = 1 / ----- n = 0 and in Maple format 1 The first, 41, terms of a(n), starting at n=0, are [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0] ---------------------------------------------------------------------------- Theorem Number:, 2, The generating function enumerating compositions of depth\ STRICTLY less than, 2, is given as follows. Theorem: Let a(n) be the number of compositions of n avoiding, as a subcompo\ sition, [2, 3, 2] We have the following rational function for the (ordinary) generating functi\ on of a(n) infinity ----- 5 4 3 2 \ n x - x + x + x - 2 x + 1 ) a(n) x = - ------------------------------------ / 6 5 4 3 2 ----- x - x + 2 x - x - 2 x + 3 x - 1 n = 0 and in Maple format -(x^5-x^4+x^3+x^2-2*x+1)/(x^6-x^5+2*x^4-x^3-2*x^2+3*x-1) The first, 41, terms of a(n), starting at n=0, are [1, 1, 2, 4, 8, 16, 32, 63, 123, 239, 464, 901, 1751, 3405, 6624, 12888, 25076, 48788, 94918, 184659, 359241, 698875, 1359608, 2645021, 5145713, 10010657, 19475106, 37887600, 73707944, 143394148, 278964224, 542707183, 1055802347, 2053996403, 3995919576, 7773807865, 15123449775, 29421711661, 57238072664, 111353037452, 216630266628] The limit of a(n+1)/a(n) as n goes to infinity is 1.94543652756 a(n) is asymptotic to .595712202984*1.94543652756^n ---------------------------------------------------------------------------- Theorem Number:, 3, The generating function enumerating compositions of depth\ STRICTLY less than, 3, is given as follows. Theorem: Let a(n) be the number of compositions of n avoiding, as a subcompo\ sition, [3, 4, 5, 4, 3] We have the following rational function for the (ordinary) generating functi\ on of a(n) infinity ----- \ n 16 14 13 11 10 9 8 7 6 ) a(n) x = - (x - x + x + x - 2 x + x - x + 3 x - 3 x / ----- n = 0 5 4 3 2 / 18 17 16 14 13 + x + x - 4 x + 6 x - 4 x + 1) / (x + x - x + 2 x - x / 11 10 9 8 7 6 5 4 3 2 - 2 x + 3 x - x + 2 x - 5 x + 4 x - x - 2 x + 7 x - 9 x + 5 x - 1) and in Maple format -(x^16-x^14+x^13+x^11-2*x^10+x^9-x^8+3*x^7-3*x^6+x^5+x^4-4*x^3+6*x^2-4*x+1)/(x^ 18+x^17-x^16+2*x^14-x^13-2*x^11+3*x^10-x^9+2*x^8-5*x^7+4*x^6-x^5-2*x^4+7*x^3-9* x^2+5*x-1) The first, 41, terms of a(n), starting at n=0, are [1, 1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536, 131072, 262143, 524281, 1048546, 2097050, 4194001, 8387784, 16775108, 33549270, 67096623, 134189393, 268371074, 536726740, 1073422713, 2146783988, 4293445260, 8586645332, 17172800640, 34344621723, 68687285003, 137370654027, 274733477320, 549451294839] The limit of a(n+1)/a(n) as n goes to infinity is 1.99994300442 a(n) is asymptotic to .500293014909*1.99994300442^n ---------------------------------------------------------------------------- Theorem Number:, 4, The generating function enumerating compositions of depth\ STRICTLY less than, 4, is given as follows. Theorem: Let a(n) be the number of compositions of n avoiding, as a subcompo\ sition, [4, 5, 6, 7, 6, 5, 4] We have the following rational function for the (ordinary) generating functi\ on of a(n) infinity ----- \ n 33 30 29 26 25 24 22 21 20 ) a(n) x = - (x - x + x + x - 2 x + x - x + 3 x - 3 x / ----- n = 0 19 17 16 15 14 13 12 11 10 9 + x + x - 4 x + 6 x - 4 x + x - x + 5 x - 10 x + 10 x 8 7 6 5 4 3 2 / 36 35 - 5 x + x + x - 6 x + 15 x - 20 x + 15 x - 6 x + 1) / (x + x / 34 33 30 29 26 25 24 22 21 20 + x - x + 2 x - x - 2 x + 3 x - x + 2 x - 5 x + 4 x 19 17 16 15 14 13 12 11 10 - x - 2 x + 7 x - 9 x + 5 x - x + 2 x - 9 x + 16 x 9 8 7 6 5 4 3 2 - 14 x + 6 x - x - 2 x + 11 x - 25 x + 30 x - 20 x + 7 x - 1) and in Maple format -(x^33-x^30+x^29+x^26-2*x^25+x^24-x^22+3*x^21-3*x^20+x^19+x^17-4*x^16+6*x^15-4* x^14+x^13-x^12+5*x^11-10*x^10+10*x^9-5*x^8+x^7+x^6-6*x^5+15*x^4-20*x^3+15*x^2-6 *x+1)/(x^36+x^35+x^34-x^33+2*x^30-x^29-2*x^26+3*x^25-x^24+2*x^22-5*x^21+4*x^20- x^19-2*x^17+7*x^16-9*x^15+5*x^14-x^13+2*x^12-9*x^11+16*x^10-14*x^9+6*x^8-x^7-2* x^6+11*x^5-25*x^4+30*x^3-20*x^2+7*x-1) The first, 41, terms of a(n), starting at n=0, are [1, 1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536, 131072, 262144, 524288, 1048576, 2097152, 4194304, 8388608, 16777216, 33554432, 67108864, 134217728, 268435456, 536870912, 1073741824, 2147483648, 4294967296, 8589934592, 17179869184, 34359738368, 68719476735, 137438953463, 274877906897, 549755813701] The limit of a(n+1)/a(n) as n goes to infinity is 1.99999999908 a(n) is asymptotic to .500000009365*1.99999999908^n ---------------------------------------------------------------------------- Theorem Number:, 5, The generating function enumerating compositions of depth\ STRICTLY less than, 5, is given as follows. Theorem: Let a(n) be the number of compositions of n avoiding, as a subcompo\ sition, [5, 6, 7, 8, 9, 8, 7, 6, 5] We have the following rational function for the (ordinary) generating functi\ on of a(n) infinity ----- \ n 56 52 51 47 46 45 42 41 40 ) a(n) x = - (x - x + x + x - 2 x + x - x + 3 x - 3 x / ----- n = 0 39 36 35 34 33 32 30 29 28 27 + x + x - 4 x + 6 x - 4 x + x - x + 5 x - 10 x + 10 x 26 25 23 22 21 20 19 18 17 16 - 5 x + x + x - 6 x + 15 x - 20 x + 15 x - 6 x + x - x 15 14 13 12 11 10 9 8 7 + 7 x - 21 x + 35 x - 35 x + 21 x - 7 x + x + x - 8 x 6 5 4 3 2 / 60 59 58 + 28 x - 56 x + 70 x - 56 x + 28 x - 8 x + 1) / (x + x + x / 57 56 52 51 47 46 45 42 41 40 + x - x + 2 x - x - 2 x + 3 x - x + 2 x - 5 x + 4 x 39 36 35 34 33 32 30 29 28 - x - 2 x + 7 x - 9 x + 5 x - x + 2 x - 9 x + 16 x 27 26 25 23 22 21 20 19 18 - 14 x + 6 x - x - 2 x + 11 x - 25 x + 30 x - 20 x + 7 x 17 16 15 14 13 12 11 10 9 - x + 2 x - 13 x + 36 x - 55 x + 50 x - 27 x + 8 x - x 8 7 6 5 4 3 2 - 2 x + 15 x - 49 x + 91 x - 105 x + 77 x - 35 x + 9 x - 1) and in Maple format -(x^56-x^52+x^51+x^47-2*x^46+x^45-x^42+3*x^41-3*x^40+x^39+x^36-4*x^35+6*x^34-4* x^33+x^32-x^30+5*x^29-10*x^28+10*x^27-5*x^26+x^25+x^23-6*x^22+15*x^21-20*x^20+ 15*x^19-6*x^18+x^17-x^16+7*x^15-21*x^14+35*x^13-35*x^12+21*x^11-7*x^10+x^9+x^8-\ 8*x^7+28*x^6-56*x^5+70*x^4-56*x^3+28*x^2-8*x+1)/(x^60+x^59+x^58+x^57-x^56+2*x^ 52-x^51-2*x^47+3*x^46-x^45+2*x^42-5*x^41+4*x^40-x^39-2*x^36+7*x^35-9*x^34+5*x^ 33-x^32+2*x^30-9*x^29+16*x^28-14*x^27+6*x^26-x^25-2*x^23+11*x^22-25*x^21+30*x^ 20-20*x^19+7*x^18-x^17+2*x^16-13*x^15+36*x^14-55*x^13+50*x^12-27*x^11+8*x^10-x^ 9-2*x^8+15*x^7-49*x^6+91*x^5-105*x^4+77*x^3-35*x^2+9*x-1) The first, 41, terms of a(n), starting at n=0, are [1, 1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536, 131072, 262144, 524288, 1048576, 2097152, 4194304, 8388608, 16777216, 33554432, 67108864, 134217728, 268435456, 536870912, 1073741824, 2147483648, 4294967296, 8589934592, 17179869184, 34359738368, 68719476736, 137438953472, 274877906944, 549755813888] The limit of a(n+1)/a(n) as n goes to infinity is 2.00000000000 a(n) is asymptotic to .500000000000*2.00000000000^n ---------------------------------------------------------------------------- Theorem Number:, 6, The generating function enumerating compositions of depth\ STRICTLY less than, 6, is given as follows. Theorem: Let a(n) be the number of compositions of n avoiding, as a subcompo\ sition, [6, 7, 8, 9, 10, 11, 10, 9, 8, 7, 6] We have the following rational function for the (ordinary) generating functi\ on of a(n) infinity ----- \ n 85 80 79 74 73 72 68 67 66 ) a(n) x = - (x - x + x + x - 2 x + x - x + 3 x - 3 x / ----- n = 0 65 61 60 59 58 57 54 53 52 51 + x + x - 4 x + 6 x - 4 x + x - x + 5 x - 10 x + 10 x 50 49 46 45 44 43 42 41 40 38 - 5 x + x + x - 6 x + 15 x - 20 x + 15 x - 6 x + x - x 37 36 35 34 33 32 31 29 28 + 7 x - 21 x + 35 x - 35 x + 21 x - 7 x + x + x - 8 x 27 26 25 24 23 22 21 20 19 + 28 x - 56 x + 70 x - 56 x + 28 x - 8 x + x - x + 9 x 18 17 16 15 14 13 12 11 - 36 x + 84 x - 126 x + 126 x - 84 x + 36 x - 9 x + x 10 9 8 7 6 5 4 3 2 + x - 10 x + 45 x - 120 x + 210 x - 252 x + 210 x - 120 x + 45 x / 90 89 88 87 86 85 80 79 74 - 10 x + 1) / (x + x + x + x + x - x + 2 x - x - 2 x / 73 72 68 67 66 65 61 60 59 + 3 x - x + 2 x - 5 x + 4 x - x - 2 x + 7 x - 9 x 58 57 54 53 52 51 50 49 46 + 5 x - x + 2 x - 9 x + 16 x - 14 x + 6 x - x - 2 x 45 44 43 42 41 40 38 37 + 11 x - 25 x + 30 x - 20 x + 7 x - x + 2 x - 13 x 36 35 34 33 32 31 29 28 + 36 x - 55 x + 50 x - 27 x + 8 x - x - 2 x + 15 x 27 26 25 24 23 22 21 20 - 49 x + 91 x - 105 x + 77 x - 35 x + 9 x - x + 2 x 19 18 17 16 15 14 13 - 17 x + 64 x - 140 x + 196 x - 182 x + 112 x - 44 x 12 11 10 9 8 7 6 5 4 + 10 x - x - 2 x + 19 x - 81 x + 204 x - 336 x + 378 x - 294 x 3 2 + 156 x - 54 x + 11 x - 1) and in Maple format -(x^85-x^80+x^79+x^74-2*x^73+x^72-x^68+3*x^67-3*x^66+x^65+x^61-4*x^60+6*x^59-4* x^58+x^57-x^54+5*x^53-10*x^52+10*x^51-5*x^50+x^49+x^46-6*x^45+15*x^44-20*x^43+ 15*x^42-6*x^41+x^40-x^38+7*x^37-21*x^36+35*x^35-35*x^34+21*x^33-7*x^32+x^31+x^ 29-8*x^28+28*x^27-56*x^26+70*x^25-56*x^24+28*x^23-8*x^22+x^21-x^20+9*x^19-36*x^ 18+84*x^17-126*x^16+126*x^15-84*x^14+36*x^13-9*x^12+x^11+x^10-10*x^9+45*x^8-120 *x^7+210*x^6-252*x^5+210*x^4-120*x^3+45*x^2-10*x+1)/(x^90+x^89+x^88+x^87+x^86-x ^85+2*x^80-x^79-2*x^74+3*x^73-x^72+2*x^68-5*x^67+4*x^66-x^65-2*x^61+7*x^60-9*x^ 59+5*x^58-x^57+2*x^54-9*x^53+16*x^52-14*x^51+6*x^50-x^49-2*x^46+11*x^45-25*x^44 +30*x^43-20*x^42+7*x^41-x^40+2*x^38-13*x^37+36*x^36-55*x^35+50*x^34-27*x^33+8*x ^32-x^31-2*x^29+15*x^28-49*x^27+91*x^26-105*x^25+77*x^24-35*x^23+9*x^22-x^21+2* x^20-17*x^19+64*x^18-140*x^17+196*x^16-182*x^15+112*x^14-44*x^13+10*x^12-x^11-2 *x^10+19*x^9-81*x^8+204*x^7-336*x^6+378*x^5-294*x^4+156*x^3-54*x^2+11*x-1) The first, 41, terms of a(n), starting at n=0, are [1, 1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536, 131072, 262144, 524288, 1048576, 2097152, 4194304, 8388608, 16777216, 33554432, 67108864, 134217728, 268435456, 536870912, 1073741824, 2147483648, 4294967296, 8589934592, 17179869184, 34359738368, 68719476736, 137438953472, 274877906944, 549755813888] The limit of a(n+1)/a(n) as n goes to infinity is 2.00000000000 a(n) is asymptotic to .500000000000*2.00000000000^n ---------------------------------------------------------------------------- Theorem Number:, 7, The generating function enumerating compositions of depth\ STRICTLY less than, 7, is given as follows. Theorem: Let a(n) be the number of compositions of n avoiding, as a subcompo\ sition, [7, 8, 9, 10, 11, 12, 13, 12, 11, 10, 9, 8, 7] We have the following rational function for the (ordinary) generating functi\ on of a(n) infinity ----- \ n 120 114 113 107 106 105 100 99 ) a(n) x = - (x - x + x + x - 2 x + x - x + 3 x / ----- n = 0 98 97 92 91 90 89 88 84 83 82 - 3 x + x + x - 4 x + 6 x - 4 x + x - x + 5 x - 10 x 81 80 79 75 74 73 72 71 70 + 10 x - 5 x + x + x - 6 x + 15 x - 20 x + 15 x - 6 x 69 66 65 64 63 62 61 60 59 + x - x + 7 x - 21 x + 35 x - 35 x + 21 x - 7 x + x 56 55 54 53 52 51 50 49 48 + x - 8 x + 28 x - 56 x + 70 x - 56 x + 28 x - 8 x + x 46 45 44 43 42 41 40 39 - x + 9 x - 36 x + 84 x - 126 x + 126 x - 84 x + 36 x 38 37 35 34 33 32 31 30 - 9 x + x + x - 10 x + 45 x - 120 x + 210 x - 252 x 29 28 27 26 25 24 23 22 + 210 x - 120 x + 45 x - 10 x + x - x + 11 x - 55 x 21 20 19 18 17 16 15 + 165 x - 330 x + 462 x - 462 x + 330 x - 165 x + 55 x 14 13 12 11 10 9 8 7 6 - 11 x + x + x - 12 x + 66 x - 220 x + 495 x - 792 x + 924 x 5 4 3 2 / 126 125 124 - 792 x + 495 x - 220 x + 66 x - 12 x + 1) / (x + x + x / 123 122 121 120 114 113 107 106 105 + x + x + x - x + 2 x - x - 2 x + 3 x - x 100 99 98 97 92 91 90 89 88 + 2 x - 5 x + 4 x - x - 2 x + 7 x - 9 x + 5 x - x 84 83 82 81 80 79 75 74 73 + 2 x - 9 x + 16 x - 14 x + 6 x - x - 2 x + 11 x - 25 x 72 71 70 69 66 65 64 63 + 30 x - 20 x + 7 x - x + 2 x - 13 x + 36 x - 55 x 62 61 60 59 56 55 54 53 + 50 x - 27 x + 8 x - x - 2 x + 15 x - 49 x + 91 x 52 51 50 49 48 46 45 44 - 105 x + 77 x - 35 x + 9 x - x + 2 x - 17 x + 64 x 43 42 41 40 39 38 37 35 - 140 x + 196 x - 182 x + 112 x - 44 x + 10 x - x - 2 x 34 33 32 31 30 29 28 + 19 x - 81 x + 204 x - 336 x + 378 x - 294 x + 156 x 27 26 25 24 23 22 21 20 - 54 x + 11 x - x + 2 x - 21 x + 100 x - 285 x + 540 x 19 18 17 16 15 14 13 12 - 714 x + 672 x - 450 x + 210 x - 65 x + 12 x - x - 2 x 11 10 9 8 7 6 5 + 23 x - 121 x + 385 x - 825 x + 1254 x - 1386 x + 1122 x 4 3 2 - 660 x + 275 x - 77 x + 13 x - 1) and in Maple format -(x^120-x^114+x^113+x^107-2*x^106+x^105-x^100+3*x^99-3*x^98+x^97+x^92-4*x^91+6* x^90-4*x^89+x^88-x^84+5*x^83-10*x^82+10*x^81-5*x^80+x^79+x^75-6*x^74+15*x^73-20 *x^72+15*x^71-6*x^70+x^69-x^66+7*x^65-21*x^64+35*x^63-35*x^62+21*x^61-7*x^60+x^ 59+x^56-8*x^55+28*x^54-56*x^53+70*x^52-56*x^51+28*x^50-8*x^49+x^48-x^46+9*x^45-\ 36*x^44+84*x^43-126*x^42+126*x^41-84*x^40+36*x^39-9*x^38+x^37+x^35-10*x^34+45*x ^33-120*x^32+210*x^31-252*x^30+210*x^29-120*x^28+45*x^27-10*x^26+x^25-x^24+11*x ^23-55*x^22+165*x^21-330*x^20+462*x^19-462*x^18+330*x^17-165*x^16+55*x^15-11*x^ 14+x^13+x^12-12*x^11+66*x^10-220*x^9+495*x^8-792*x^7+924*x^6-792*x^5+495*x^4-\ 220*x^3+66*x^2-12*x+1)/(x^126+x^125+x^124+x^123+x^122+x^121-x^120+2*x^114-x^113 -2*x^107+3*x^106-x^105+2*x^100-5*x^99+4*x^98-x^97-2*x^92+7*x^91-9*x^90+5*x^89-x ^88+2*x^84-9*x^83+16*x^82-14*x^81+6*x^80-x^79-2*x^75+11*x^74-25*x^73+30*x^72-20 *x^71+7*x^70-x^69+2*x^66-13*x^65+36*x^64-55*x^63+50*x^62-27*x^61+8*x^60-x^59-2* x^56+15*x^55-49*x^54+91*x^53-105*x^52+77*x^51-35*x^50+9*x^49-x^48+2*x^46-17*x^ 45+64*x^44-140*x^43+196*x^42-182*x^41+112*x^40-44*x^39+10*x^38-x^37-2*x^35+19*x ^34-81*x^33+204*x^32-336*x^31+378*x^30-294*x^29+156*x^28-54*x^27+11*x^26-x^25+2 *x^24-21*x^23+100*x^22-285*x^21+540*x^20-714*x^19+672*x^18-450*x^17+210*x^16-65 *x^15+12*x^14-x^13-2*x^12+23*x^11-121*x^10+385*x^9-825*x^8+1254*x^7-1386*x^6+ 1122*x^5-660*x^4+275*x^3-77*x^2+13*x-1) The first, 41, terms of a(n), starting at n=0, are [1, 1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536, 131072, 262144, 524288, 1048576, 2097152, 4194304, 8388608, 16777216, 33554432, 67108864, 134217728, 268435456, 536870912, 1073741824, 2147483648, 4294967296, 8589934592, 17179869184, 34359738368, 68719476736, 137438953472, 274877906944, 549755813888] The limit of a(n+1)/a(n) as n goes to infinity is 2.00000000000 a(n) is asymptotic to .500000000000*2.00000000000^n ---------------------------------------------------------------------------- Theorem Number:, 8, The generating function enumerating compositions of depth\ STRICTLY less than, 8, is given as follows. Theorem: Let a(n) be the number of compositions of n avoiding, as a subcompo\ sition, [8, 9, 10, 11, 12, 13, 14, 15, 14, 13, 12, 11, 10, 9, 8] We have the following rational function for the (ordinary) generating functi\ on of a(n) infinity ----- \ n 161 154 153 146 145 144 138 137 ) a(n) x = - (x - x + x + x - 2 x + x - x + 3 x / ----- n = 0 136 135 129 128 127 126 125 120 119 - 3 x + x + x - 4 x + 6 x - 4 x + x - x + 5 x 118 117 116 115 110 109 108 107 - 10 x + 10 x - 5 x + x + x - 6 x + 15 x - 20 x 106 105 104 100 99 98 97 96 + 15 x - 6 x + x - x + 7 x - 21 x + 35 x - 35 x 95 94 93 89 88 87 86 85 84 + 21 x - 7 x + x + x - 8 x + 28 x - 56 x + 70 x - 56 x 83 82 81 78 77 76 75 74 73 + 28 x - 8 x + x - x + 9 x - 36 x + 84 x - 126 x + 126 x 72 71 70 69 66 65 64 63 - 84 x + 36 x - 9 x + x + x - 10 x + 45 x - 120 x 62 61 60 59 58 57 56 54 + 210 x - 252 x + 210 x - 120 x + 45 x - 10 x + x - x 53 52 51 50 49 48 47 + 11 x - 55 x + 165 x - 330 x + 462 x - 462 x + 330 x 46 45 44 43 41 40 39 38 - 165 x + 55 x - 11 x + x + x - 12 x + 66 x - 220 x 37 36 35 34 33 32 31 + 495 x - 792 x + 924 x - 792 x + 495 x - 220 x + 66 x 30 29 28 27 26 25 24 23 - 12 x + x - x + 13 x - 78 x + 286 x - 715 x + 1287 x 22 21 20 19 18 17 16 - 1716 x + 1716 x - 1287 x + 715 x - 286 x + 78 x - 13 x 15 14 13 12 11 10 9 8 + x + x - 14 x + 91 x - 364 x + 1001 x - 2002 x + 3003 x 7 6 5 4 3 2 / - 3432 x + 3003 x - 2002 x + 1001 x - 364 x + 91 x - 14 x + 1) / ( / 168 167 166 165 164 163 162 161 154 153 x + x + x + x + x + x + x - x + 2 x - x 146 145 144 138 137 136 135 129 - 2 x + 3 x - x + 2 x - 5 x + 4 x - x - 2 x 128 127 126 125 120 119 118 117 + 7 x - 9 x + 5 x - x + 2 x - 9 x + 16 x - 14 x 116 115 110 109 108 107 106 105 + 6 x - x - 2 x + 11 x - 25 x + 30 x - 20 x + 7 x 104 100 99 98 97 96 95 94 93 - x + 2 x - 13 x + 36 x - 55 x + 50 x - 27 x + 8 x - x 89 88 87 86 85 84 83 82 - 2 x + 15 x - 49 x + 91 x - 105 x + 77 x - 35 x + 9 x 81 78 77 76 75 74 73 72 - x + 2 x - 17 x + 64 x - 140 x + 196 x - 182 x + 112 x 71 70 69 66 65 64 63 62 - 44 x + 10 x - x - 2 x + 19 x - 81 x + 204 x - 336 x 61 60 59 58 57 56 54 53 + 378 x - 294 x + 156 x - 54 x + 11 x - x + 2 x - 21 x 52 51 50 49 48 47 46 + 100 x - 285 x + 540 x - 714 x + 672 x - 450 x + 210 x 45 44 43 41 40 39 38 37 - 65 x + 12 x - x - 2 x + 23 x - 121 x + 385 x - 825 x 36 35 34 33 32 31 30 + 1254 x - 1386 x + 1122 x - 660 x + 275 x - 77 x + 13 x 29 28 27 26 25 24 23 - x + 2 x - 25 x + 144 x - 506 x + 1210 x - 2079 x 22 21 20 19 18 17 16 + 2640 x - 2508 x + 1782 x - 935 x + 352 x - 90 x + 14 x 15 14 13 12 11 10 9 8 - x - 2 x + 27 x - 169 x + 650 x - 1716 x + 3289 x - 4719 x 7 6 5 4 3 2 + 5148 x - 4290 x + 2717 x - 1287 x + 442 x - 104 x + 15 x - 1) and in Maple format -(x^161-x^154+x^153+x^146-2*x^145+x^144-x^138+3*x^137-3*x^136+x^135+x^129-4*x^ 128+6*x^127-4*x^126+x^125-x^120+5*x^119-10*x^118+10*x^117-5*x^116+x^115+x^110-6 *x^109+15*x^108-20*x^107+15*x^106-6*x^105+x^104-x^100+7*x^99-21*x^98+35*x^97-35 *x^96+21*x^95-7*x^94+x^93+x^89-8*x^88+28*x^87-56*x^86+70*x^85-56*x^84+28*x^83-8 *x^82+x^81-x^78+9*x^77-36*x^76+84*x^75-126*x^74+126*x^73-84*x^72+36*x^71-9*x^70 +x^69+x^66-10*x^65+45*x^64-120*x^63+210*x^62-252*x^61+210*x^60-120*x^59+45*x^58 -10*x^57+x^56-x^54+11*x^53-55*x^52+165*x^51-330*x^50+462*x^49-462*x^48+330*x^47 -165*x^46+55*x^45-11*x^44+x^43+x^41-12*x^40+66*x^39-220*x^38+495*x^37-792*x^36+ 924*x^35-792*x^34+495*x^33-220*x^32+66*x^31-12*x^30+x^29-x^28+13*x^27-78*x^26+ 286*x^25-715*x^24+1287*x^23-1716*x^22+1716*x^21-1287*x^20+715*x^19-286*x^18+78* x^17-13*x^16+x^15+x^14-14*x^13+91*x^12-364*x^11+1001*x^10-2002*x^9+3003*x^8-\ 3432*x^7+3003*x^6-2002*x^5+1001*x^4-364*x^3+91*x^2-14*x+1)/(x^168+x^167+x^166+x ^165+x^164+x^163+x^162-x^161+2*x^154-x^153-2*x^146+3*x^145-x^144+2*x^138-5*x^ 137+4*x^136-x^135-2*x^129+7*x^128-9*x^127+5*x^126-x^125+2*x^120-9*x^119+16*x^ 118-14*x^117+6*x^116-x^115-2*x^110+11*x^109-25*x^108+30*x^107-20*x^106+7*x^105- x^104+2*x^100-13*x^99+36*x^98-55*x^97+50*x^96-27*x^95+8*x^94-x^93-2*x^89+15*x^ 88-49*x^87+91*x^86-105*x^85+77*x^84-35*x^83+9*x^82-x^81+2*x^78-17*x^77+64*x^76-\ 140*x^75+196*x^74-182*x^73+112*x^72-44*x^71+10*x^70-x^69-2*x^66+19*x^65-81*x^64 +204*x^63-336*x^62+378*x^61-294*x^60+156*x^59-54*x^58+11*x^57-x^56+2*x^54-21*x^ 53+100*x^52-285*x^51+540*x^50-714*x^49+672*x^48-450*x^47+210*x^46-65*x^45+12*x^ 44-x^43-2*x^41+23*x^40-121*x^39+385*x^38-825*x^37+1254*x^36-1386*x^35+1122*x^34 -660*x^33+275*x^32-77*x^31+13*x^30-x^29+2*x^28-25*x^27+144*x^26-506*x^25+1210*x ^24-2079*x^23+2640*x^22-2508*x^21+1782*x^20-935*x^19+352*x^18-90*x^17+14*x^16-x ^15-2*x^14+27*x^13-169*x^12+650*x^11-1716*x^10+3289*x^9-4719*x^8+5148*x^7-4290* x^6+2717*x^5-1287*x^4+442*x^3-104*x^2+15*x-1) The first, 41, terms of a(n), starting at n=0, are [1, 1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536, 131072, 262144, 524288, 1048576, 2097152, 4194304, 8388608, 16777216, 33554432, 67108864, 134217728, 268435456, 536870912, 1073741824, 2147483648, 4294967296, 8589934592, 17179869184, 34359738368, 68719476736, 137438953472, 274877906944, 549755813888] The limit of a(n+1)/a(n) as n goes to infinity is 2.00000000000 a(n) is asymptotic to .500000000000*2.00000000000^n ---------------------------------------------------------------------------- Theorem Number:, 9, The generating function enumerating compositions of depth\ STRICTLY less than, 9, is given as follows. Theorem: Let a(n) be the number of compositions of n avoiding, as a subcompo\ sition, [9, 10, 11, 12, 13, 14, 15, 16, 17, 16, 15, 14, 13, 12, 11, 10, 9] We have the following rational function for the (ordinary) generating functi\ on of a(n) infinity ----- \ n 208 200 199 191 190 189 182 181 ) a(n) x = - (x - x + x + x - 2 x + x - x + 3 x / ----- n = 0 180 179 172 171 170 169 168 162 161 - 3 x + x + x - 4 x + 6 x - 4 x + x - x + 5 x 160 159 158 157 151 150 149 148 - 10 x + 10 x - 5 x + x + x - 6 x + 15 x - 20 x 147 146 145 140 139 138 137 136 + 15 x - 6 x + x - x + 7 x - 21 x + 35 x - 35 x 135 134 133 128 127 126 125 124 + 21 x - 7 x + x + x - 8 x + 28 x - 56 x + 70 x 123 122 121 120 116 115 114 113 - 56 x + 28 x - 8 x + x - x + 9 x - 36 x + 84 x 112 111 110 109 108 107 103 102 - 126 x + 126 x - 84 x + 36 x - 9 x + x + x - 10 x 101 100 99 98 97 96 95 + 45 x - 120 x + 210 x - 252 x + 210 x - 120 x + 45 x 94 93 90 89 88 87 86 85 - 10 x + x - x + 11 x - 55 x + 165 x - 330 x + 462 x 84 83 82 81 80 79 76 75 - 462 x + 330 x - 165 x + 55 x - 11 x + x + x - 12 x 74 73 72 71 70 69 68 + 66 x - 220 x + 495 x - 792 x + 924 x - 792 x + 495 x 67 66 65 64 62 61 60 59 - 220 x + 66 x - 12 x + x - x + 13 x - 78 x + 286 x 58 57 56 55 54 53 52 - 715 x + 1287 x - 1716 x + 1716 x - 1287 x + 715 x - 286 x 51 50 49 47 46 45 44 43 + 78 x - 13 x + x + x - 14 x + 91 x - 364 x + 1001 x 42 41 40 39 38 37 - 2002 x + 3003 x - 3432 x + 3003 x - 2002 x + 1001 x 36 35 34 33 32 31 30 29 - 364 x + 91 x - 14 x + x - x + 15 x - 105 x + 455 x 28 27 26 25 24 23 - 1365 x + 3003 x - 5005 x + 6435 x - 6435 x + 5005 x 22 21 20 19 18 17 16 15 - 3003 x + 1365 x - 455 x + 105 x - 15 x + x + x - 16 x 14 13 12 11 10 9 8 + 120 x - 560 x + 1820 x - 4368 x + 8008 x - 11440 x + 12870 x 7 6 5 4 3 2 - 11440 x + 8008 x - 4368 x + 1820 x - 560 x + 120 x - 16 x + 1) / 216 215 214 213 212 211 210 209 208 200 / (x + x + x + x + x + x + x + x - x + 2 x / 199 191 190 189 182 181 180 179 172 - x - 2 x + 3 x - x + 2 x - 5 x + 4 x - x - 2 x 171 170 169 168 162 161 160 159 + 7 x - 9 x + 5 x - x + 2 x - 9 x + 16 x - 14 x 158 157 151 150 149 148 147 146 + 6 x - x - 2 x + 11 x - 25 x + 30 x - 20 x + 7 x 145 140 139 138 137 136 135 134 - x + 2 x - 13 x + 36 x - 55 x + 50 x - 27 x + 8 x 133 128 127 126 125 124 123 - x - 2 x + 15 x - 49 x + 91 x - 105 x + 77 x 122 121 120 116 115 114 113 - 35 x + 9 x - x + 2 x - 17 x + 64 x - 140 x 112 111 110 109 108 107 103 + 196 x - 182 x + 112 x - 44 x + 10 x - x - 2 x 102 101 100 99 98 97 96 + 19 x - 81 x + 204 x - 336 x + 378 x - 294 x + 156 x 95 94 93 90 89 88 87 86 - 54 x + 11 x - x + 2 x - 21 x + 100 x - 285 x + 540 x 85 84 83 82 81 80 79 76 - 714 x + 672 x - 450 x + 210 x - 65 x + 12 x - x - 2 x 75 74 73 72 71 70 69 + 23 x - 121 x + 385 x - 825 x + 1254 x - 1386 x + 1122 x 68 67 66 65 64 62 61 60 - 660 x + 275 x - 77 x + 13 x - x + 2 x - 25 x + 144 x 59 58 57 56 55 54 53 - 506 x + 1210 x - 2079 x + 2640 x - 2508 x + 1782 x - 935 x 52 51 50 49 47 46 45 44 + 352 x - 90 x + 14 x - x - 2 x + 27 x - 169 x + 650 x 43 42 41 40 39 38 - 1716 x + 3289 x - 4719 x + 5148 x - 4290 x + 2717 x 37 36 35 34 33 32 31 30 - 1287 x + 442 x - 104 x + 15 x - x + 2 x - 29 x + 196 x 29 28 27 26 25 24 - 819 x + 2366 x - 5005 x + 8008 x - 9867 x + 9438 x 23 22 21 20 19 18 17 - 7007 x + 4004 x - 1729 x + 546 x - 119 x + 16 x - x 16 15 14 13 12 11 10 - 2 x + 31 x - 225 x + 1015 x - 3185 x + 7371 x - 13013 x 9 8 7 6 5 4 3 + 17875 x - 19305 x + 16445 x - 11011 x + 5733 x - 2275 x + 665 x 2 - 135 x + 17 x - 1) and in Maple format -(x^208-x^200+x^199+x^191-2*x^190+x^189-x^182+3*x^181-3*x^180+x^179+x^172-4*x^ 171+6*x^170-4*x^169+x^168-x^162+5*x^161-10*x^160+10*x^159-5*x^158+x^157+x^151-6 *x^150+15*x^149-20*x^148+15*x^147-6*x^146+x^145-x^140+7*x^139-21*x^138+35*x^137 -35*x^136+21*x^135-7*x^134+x^133+x^128-8*x^127+28*x^126-56*x^125+70*x^124-56*x^ 123+28*x^122-8*x^121+x^120-x^116+9*x^115-36*x^114+84*x^113-126*x^112+126*x^111-\ 84*x^110+36*x^109-9*x^108+x^107+x^103-10*x^102+45*x^101-120*x^100+210*x^99-252* x^98+210*x^97-120*x^96+45*x^95-10*x^94+x^93-x^90+11*x^89-55*x^88+165*x^87-330*x ^86+462*x^85-462*x^84+330*x^83-165*x^82+55*x^81-11*x^80+x^79+x^76-12*x^75+66*x^ 74-220*x^73+495*x^72-792*x^71+924*x^70-792*x^69+495*x^68-220*x^67+66*x^66-12*x^ 65+x^64-x^62+13*x^61-78*x^60+286*x^59-715*x^58+1287*x^57-1716*x^56+1716*x^55-\ 1287*x^54+715*x^53-286*x^52+78*x^51-13*x^50+x^49+x^47-14*x^46+91*x^45-364*x^44+ 1001*x^43-2002*x^42+3003*x^41-3432*x^40+3003*x^39-2002*x^38+1001*x^37-364*x^36+ 91*x^35-14*x^34+x^33-x^32+15*x^31-105*x^30+455*x^29-1365*x^28+3003*x^27-5005*x^ 26+6435*x^25-6435*x^24+5005*x^23-3003*x^22+1365*x^21-455*x^20+105*x^19-15*x^18+ x^17+x^16-16*x^15+120*x^14-560*x^13+1820*x^12-4368*x^11+8008*x^10-11440*x^9+ 12870*x^8-11440*x^7+8008*x^6-4368*x^5+1820*x^4-560*x^3+120*x^2-16*x+1)/(x^216+x ^215+x^214+x^213+x^212+x^211+x^210+x^209-x^208+2*x^200-x^199-2*x^191+3*x^190-x^ 189+2*x^182-5*x^181+4*x^180-x^179-2*x^172+7*x^171-9*x^170+5*x^169-x^168+2*x^162 -9*x^161+16*x^160-14*x^159+6*x^158-x^157-2*x^151+11*x^150-25*x^149+30*x^148-20* x^147+7*x^146-x^145+2*x^140-13*x^139+36*x^138-55*x^137+50*x^136-27*x^135+8*x^ 134-x^133-2*x^128+15*x^127-49*x^126+91*x^125-105*x^124+77*x^123-35*x^122+9*x^ 121-x^120+2*x^116-17*x^115+64*x^114-140*x^113+196*x^112-182*x^111+112*x^110-44* x^109+10*x^108-x^107-2*x^103+19*x^102-81*x^101+204*x^100-336*x^99+378*x^98-294* x^97+156*x^96-54*x^95+11*x^94-x^93+2*x^90-21*x^89+100*x^88-285*x^87+540*x^86-\ 714*x^85+672*x^84-450*x^83+210*x^82-65*x^81+12*x^80-x^79-2*x^76+23*x^75-121*x^ 74+385*x^73-825*x^72+1254*x^71-1386*x^70+1122*x^69-660*x^68+275*x^67-77*x^66+13 *x^65-x^64+2*x^62-25*x^61+144*x^60-506*x^59+1210*x^58-2079*x^57+2640*x^56-2508* x^55+1782*x^54-935*x^53+352*x^52-90*x^51+14*x^50-x^49-2*x^47+27*x^46-169*x^45+ 650*x^44-1716*x^43+3289*x^42-4719*x^41+5148*x^40-4290*x^39+2717*x^38-1287*x^37+ 442*x^36-104*x^35+15*x^34-x^33+2*x^32-29*x^31+196*x^30-819*x^29+2366*x^28-5005* x^27+8008*x^26-9867*x^25+9438*x^24-7007*x^23+4004*x^22-1729*x^21+546*x^20-119*x ^19+16*x^18-x^17-2*x^16+31*x^15-225*x^14+1015*x^13-3185*x^12+7371*x^11-13013*x^ 10+17875*x^9-19305*x^8+16445*x^7-11011*x^6+5733*x^5-2275*x^4+665*x^3-135*x^2+17 *x-1) The first, 41, terms of a(n), starting at n=0, are [1, 1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536, 131072, 262144, 524288, 1048576, 2097152, 4194304, 8388608, 16777216, 33554432, 67108864, 134217728, 268435456, 536870912, 1073741824, 2147483648, 4294967296, 8589934592, 17179869184, 34359738368, 68719476736, 137438953472, 274877906944, 549755813888] The limit of a(n+1)/a(n) as n goes to infinity is 2.00000000000 a(n) is asymptotic to .500000000000*2.00000000000^n ---------------------------------------------------------------------------- Theorem Number:, 10, The generating function enumerating compositions of dept\ h STRICTLY less than, 10, is given as follows. Theorem: Let a(n) be the number of compositions of n avoiding, as a subcompo\ sition, [ 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 18, 17, 16, 15, 14, 13, 12, 11, 10] We have the following rational function for the (ordinary) generating functi\ on of a(n) infinity ----- \ n 261 252 251 242 241 240 232 231 ) a(n) x = - (x - x + x + x - 2 x + x - x + 3 x / ----- n = 0 230 229 221 220 219 218 217 210 209 - 3 x + x + x - 4 x + 6 x - 4 x + x - x + 5 x 208 207 206 205 198 197 196 195 - 10 x + 10 x - 5 x + x + x - 6 x + 15 x - 20 x 194 193 192 186 185 184 183 182 + 15 x - 6 x + x - x + 7 x - 21 x + 35 x - 35 x 181 180 179 173 172 171 170 169 + 21 x - 7 x + x + x - 8 x + 28 x - 56 x + 70 x 168 167 166 165 160 159 158 157 - 56 x + 28 x - 8 x + x - x + 9 x - 36 x + 84 x 156 155 154 153 152 151 146 145 - 126 x + 126 x - 84 x + 36 x - 9 x + x + x - 10 x 144 143 142 141 140 139 138 + 45 x - 120 x + 210 x - 252 x + 210 x - 120 x + 45 x 137 136 132 131 130 129 128 - 10 x + x - x + 11 x - 55 x + 165 x - 330 x 127 126 125 124 123 122 121 + 462 x - 462 x + 330 x - 165 x + 55 x - 11 x + x 117 116 115 114 113 112 111 + x - 12 x + 66 x - 220 x + 495 x - 792 x + 924 x 110 109 108 107 106 105 102 - 792 x + 495 x - 220 x + 66 x - 12 x + x - x 101 100 99 98 97 96 95 + 13 x - 78 x + 286 x - 715 x + 1287 x - 1716 x + 1716 x 94 93 92 91 90 89 86 85 - 1287 x + 715 x - 286 x + 78 x - 13 x + x + x - 14 x 84 83 82 81 80 79 78 + 91 x - 364 x + 1001 x - 2002 x + 3003 x - 3432 x + 3003 x 77 76 75 74 73 72 70 69 - 2002 x + 1001 x - 364 x + 91 x - 14 x + x - x + 15 x 68 67 66 65 64 63 62 - 105 x + 455 x - 1365 x + 3003 x - 5005 x + 6435 x - 6435 x 61 60 59 58 57 56 55 53 + 5005 x - 3003 x + 1365 x - 455 x + 105 x - 15 x + x + x 52 51 50 49 48 47 46 - 16 x + 120 x - 560 x + 1820 x - 4368 x + 8008 x - 11440 x 45 44 43 42 41 40 + 12870 x - 11440 x + 8008 x - 4368 x + 1820 x - 560 x 39 38 37 36 35 34 33 32 + 120 x - 16 x + x - x + 17 x - 136 x + 680 x - 2380 x 31 30 29 28 27 26 + 6188 x - 12376 x + 19448 x - 24310 x + 24310 x - 19448 x 25 24 23 22 21 20 19 18 + 12376 x - 6188 x + 2380 x - 680 x + 136 x - 17 x + x + x 17 16 15 14 13 12 11 - 18 x + 153 x - 816 x + 3060 x - 8568 x + 18564 x - 31824 x 10 9 8 7 6 5 + 43758 x - 48620 x + 43758 x - 31824 x + 18564 x - 8568 x 4 3 2 / 270 269 268 267 + 3060 x - 816 x + 153 x - 18 x + 1) / (x + x + x + x / 266 265 264 263 262 261 252 251 242 + x + x + x + x + x - x + 2 x - x - 2 x 241 240 232 231 230 229 221 220 + 3 x - x + 2 x - 5 x + 4 x - x - 2 x + 7 x 219 218 217 210 209 208 207 206 - 9 x + 5 x - x + 2 x - 9 x + 16 x - 14 x + 6 x 205 198 197 196 195 194 193 192 - x - 2 x + 11 x - 25 x + 30 x - 20 x + 7 x - x 186 185 184 183 182 181 180 179 + 2 x - 13 x + 36 x - 55 x + 50 x - 27 x + 8 x - x 173 172 171 170 169 168 167 - 2 x + 15 x - 49 x + 91 x - 105 x + 77 x - 35 x 166 165 160 159 158 157 156 + 9 x - x + 2 x - 17 x + 64 x - 140 x + 196 x 155 154 153 152 151 146 145 - 182 x + 112 x - 44 x + 10 x - x - 2 x + 19 x 144 143 142 141 140 139 138 - 81 x + 204 x - 336 x + 378 x - 294 x + 156 x - 54 x 137 136 132 131 130 129 128 + 11 x - x + 2 x - 21 x + 100 x - 285 x + 540 x 127 126 125 124 123 122 121 - 714 x + 672 x - 450 x + 210 x - 65 x + 12 x - x 117 116 115 114 113 112 - 2 x + 23 x - 121 x + 385 x - 825 x + 1254 x 111 110 109 108 107 106 105 - 1386 x + 1122 x - 660 x + 275 x - 77 x + 13 x - x 102 101 100 99 98 97 96 + 2 x - 25 x + 144 x - 506 x + 1210 x - 2079 x + 2640 x 95 94 93 92 91 90 89 86 - 2508 x + 1782 x - 935 x + 352 x - 90 x + 14 x - x - 2 x 85 84 83 82 81 80 79 + 27 x - 169 x + 650 x - 1716 x + 3289 x - 4719 x + 5148 x 78 77 76 75 74 73 72 - 4290 x + 2717 x - 1287 x + 442 x - 104 x + 15 x - x 70 69 68 67 66 65 64 + 2 x - 29 x + 196 x - 819 x + 2366 x - 5005 x + 8008 x 63 62 61 60 59 58 57 - 9867 x + 9438 x - 7007 x + 4004 x - 1729 x + 546 x - 119 x 56 55 53 52 51 50 49 48 + 16 x - x - 2 x + 31 x - 225 x + 1015 x - 3185 x + 7371 x 47 46 45 44 43 42 - 13013 x + 17875 x - 19305 x + 16445 x - 11011 x + 5733 x 41 40 39 38 37 36 35 34 - 2275 x + 665 x - 135 x + 17 x - x + 2 x - 33 x + 256 x 33 32 31 30 29 28 - 1240 x + 4200 x - 10556 x + 20384 x - 30888 x + 37180 x 27 26 25 24 23 22 - 35750 x + 27456 x - 16744 x + 8008 x - 2940 x + 800 x 21 20 19 18 17 16 15 14 - 152 x + 18 x - x - 2 x + 35 x - 289 x + 1496 x - 5440 x 13 12 11 10 9 8 + 14756 x - 30940 x + 51272 x - 68068 x + 72930 x - 63206 x 7 6 5 4 3 2 + 44200 x - 24752 x + 10948 x - 3740 x + 952 x - 170 x + 19 x - 1) and in Maple format -(x^261-x^252+x^251+x^242-2*x^241+x^240-x^232+3*x^231-3*x^230+x^229+x^221-4*x^ 220+6*x^219-4*x^218+x^217-x^210+5*x^209-10*x^208+10*x^207-5*x^206+x^205+x^198-6 *x^197+15*x^196-20*x^195+15*x^194-6*x^193+x^192-x^186+7*x^185-21*x^184+35*x^183 -35*x^182+21*x^181-7*x^180+x^179+x^173-8*x^172+28*x^171-56*x^170+70*x^169-56*x^ 168+28*x^167-8*x^166+x^165-x^160+9*x^159-36*x^158+84*x^157-126*x^156+126*x^155-\ 84*x^154+36*x^153-9*x^152+x^151+x^146-10*x^145+45*x^144-120*x^143+210*x^142-252 *x^141+210*x^140-120*x^139+45*x^138-10*x^137+x^136-x^132+11*x^131-55*x^130+165* x^129-330*x^128+462*x^127-462*x^126+330*x^125-165*x^124+55*x^123-11*x^122+x^121 +x^117-12*x^116+66*x^115-220*x^114+495*x^113-792*x^112+924*x^111-792*x^110+495* x^109-220*x^108+66*x^107-12*x^106+x^105-x^102+13*x^101-78*x^100+286*x^99-715*x^ 98+1287*x^97-1716*x^96+1716*x^95-1287*x^94+715*x^93-286*x^92+78*x^91-13*x^90+x^ 89+x^86-14*x^85+91*x^84-364*x^83+1001*x^82-2002*x^81+3003*x^80-3432*x^79+3003*x ^78-2002*x^77+1001*x^76-364*x^75+91*x^74-14*x^73+x^72-x^70+15*x^69-105*x^68+455 *x^67-1365*x^66+3003*x^65-5005*x^64+6435*x^63-6435*x^62+5005*x^61-3003*x^60+ 1365*x^59-455*x^58+105*x^57-15*x^56+x^55+x^53-16*x^52+120*x^51-560*x^50+1820*x^ 49-4368*x^48+8008*x^47-11440*x^46+12870*x^45-11440*x^44+8008*x^43-4368*x^42+ 1820*x^41-560*x^40+120*x^39-16*x^38+x^37-x^36+17*x^35-136*x^34+680*x^33-2380*x^ 32+6188*x^31-12376*x^30+19448*x^29-24310*x^28+24310*x^27-19448*x^26+12376*x^25-\ 6188*x^24+2380*x^23-680*x^22+136*x^21-17*x^20+x^19+x^18-18*x^17+153*x^16-816*x^ 15+3060*x^14-8568*x^13+18564*x^12-31824*x^11+43758*x^10-48620*x^9+43758*x^8-\ 31824*x^7+18564*x^6-8568*x^5+3060*x^4-816*x^3+153*x^2-18*x+1)/(x^270+x^269+x^ 268+x^267+x^266+x^265+x^264+x^263+x^262-x^261+2*x^252-x^251-2*x^242+3*x^241-x^ 240+2*x^232-5*x^231+4*x^230-x^229-2*x^221+7*x^220-9*x^219+5*x^218-x^217+2*x^210 -9*x^209+16*x^208-14*x^207+6*x^206-x^205-2*x^198+11*x^197-25*x^196+30*x^195-20* x^194+7*x^193-x^192+2*x^186-13*x^185+36*x^184-55*x^183+50*x^182-27*x^181+8*x^ 180-x^179-2*x^173+15*x^172-49*x^171+91*x^170-105*x^169+77*x^168-35*x^167+9*x^ 166-x^165+2*x^160-17*x^159+64*x^158-140*x^157+196*x^156-182*x^155+112*x^154-44* x^153+10*x^152-x^151-2*x^146+19*x^145-81*x^144+204*x^143-336*x^142+378*x^141-\ 294*x^140+156*x^139-54*x^138+11*x^137-x^136+2*x^132-21*x^131+100*x^130-285*x^ 129+540*x^128-714*x^127+672*x^126-450*x^125+210*x^124-65*x^123+12*x^122-x^121-2 *x^117+23*x^116-121*x^115+385*x^114-825*x^113+1254*x^112-1386*x^111+1122*x^110-\ 660*x^109+275*x^108-77*x^107+13*x^106-x^105+2*x^102-25*x^101+144*x^100-506*x^99 +1210*x^98-2079*x^97+2640*x^96-2508*x^95+1782*x^94-935*x^93+352*x^92-90*x^91+14 *x^90-x^89-2*x^86+27*x^85-169*x^84+650*x^83-1716*x^82+3289*x^81-4719*x^80+5148* x^79-4290*x^78+2717*x^77-1287*x^76+442*x^75-104*x^74+15*x^73-x^72+2*x^70-29*x^ 69+196*x^68-819*x^67+2366*x^66-5005*x^65+8008*x^64-9867*x^63+9438*x^62-7007*x^ 61+4004*x^60-1729*x^59+546*x^58-119*x^57+16*x^56-x^55-2*x^53+31*x^52-225*x^51+ 1015*x^50-3185*x^49+7371*x^48-13013*x^47+17875*x^46-19305*x^45+16445*x^44-11011 *x^43+5733*x^42-2275*x^41+665*x^40-135*x^39+17*x^38-x^37+2*x^36-33*x^35+256*x^ 34-1240*x^33+4200*x^32-10556*x^31+20384*x^30-30888*x^29+37180*x^28-35750*x^27+ 27456*x^26-16744*x^25+8008*x^24-2940*x^23+800*x^22-152*x^21+18*x^20-x^19-2*x^18 +35*x^17-289*x^16+1496*x^15-5440*x^14+14756*x^13-30940*x^12+51272*x^11-68068*x^ 10+72930*x^9-63206*x^8+44200*x^7-24752*x^6+10948*x^5-3740*x^4+952*x^3-170*x^2+ 19*x-1) The first, 41, terms of a(n), starting at n=0, are [1, 1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536, 131072, 262144, 524288, 1048576, 2097152, 4194304, 8388608, 16777216, 33554432, 67108864, 134217728, 268435456, 536870912, 1073741824, 2147483648, 4294967296, 8589934592, 17179869184, 34359738368, 68719476736, 137438953472, 274877906944, 549755813888] The limit of a(n+1)/a(n) as n goes to infinity is 2.00000000000 a(n) is asymptotic to .500000000000*2.00000000000^n ---------------------------------------------------------------------------- --------------------------------- This took, 28.993, seconds.