Enumeration of Beta(a,b) Description Trees for a and b up to, 6 By Shalosh B. Ekhad In this article, we will try to enumerate Beta(a,b) description trees for a,\ b up to , 6 by discovering (easily provable, once discovered!) algebraic equations for t\ he generating functions of the enumerating sequence, and will also present, in each case, the implie\ d linear recurrence equation with polynomial coefficients satisfied by the enumerating sequence in each case, provided its order + deg\ ree are <=, 10 We will do this by using as TRAINING DATA (so to speak!) the first , 40, terms, and admit failure otherwise For the sake of the OEIS, we will give the first, 30, terms in each case, and just for fun the, 100, -th term. Finally we will output the set of all successful pairs [a,b]. According to the article Cori, Robert, Benjamin Jacquard, and Gilles Schaeffer. "Description trees fo\ r some families of planar maps" Proceedings of the 9th Conference on Formal Power Series and Algebraic Combi\ natorics. 1997. Available from http://www-igm.univ-mlv.fr/~fpsac/FPSAC97/ARTICLES/Schaeffer\ .ps.gz [viewed Dec. 24, 2014] The generating function, f(x,y),in the two variables (y being the so-called \ catalytic variable taking care of the label of the root) satisfies the FUNCTIONAL EQUATION / a (b + 1) \ | a y f(x, 1) - y f(x, y)| f(x, y) = x (f(x, y) + 1) |y + -----------------------------| \ 1 - y / we would be interested in the straight enumeration, whose generating functio\ n is f(x,1) -------------------------------------------------------- For the Enumeration of, BETA(0, 0), trees we have the following Theorem: Let f(x,y) be (unique!) formal power series, in the variables, x,y,\ satisfying the FUNCTIONAL Equation / f(x, 1) - y f(x, y)\ f(x, y) = x (f(x, y) + 1) |1 + -------------------| \ 1 - y / Then P(x)=f(x,1) satisfies the following algebraic equation 2 x + (-1 + 2 x) P + x P = 0 and in Maple input notation x+(-1+2*x)*P+x*P^2 = 0 The first, 30, terms, for the sake of the OEIS are [1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845, 35357670, 129644790, 477638700, 1767263190, 6564120420, 24466267020, 91482563640, 343059613650, 1289904147324, 4861946401452, 18367353072152, 69533550916004, 263747951750360, 1002242216651368, 3814986502092304] Furthermore, the sequence of coefficients, let's call them , A[n], satisfy: 2 (1 + 2 n) A[n] - ---------------- + A[1 + n] = 0 2 + n and in Maple input format -2*(1+2*n)/(2+n)*A[n]+A[1+n] = 0 Just for fun, A[100], equals 896519947090131496687170070074100632420837521538745909320 -------------------------------------------------------- For the Enumeration of, BETA(0, 1), trees we have the following Theorem: Let f(x,y) be (unique!) formal power series, in the variables, x,y,\ satisfying the FUNCTIONAL Equation / 2 \ | f(x, 1) - y f(x, y)| f(x, y) = x (f(x, y) + 1) |1 + --------------------| \ 1 - y / Then P(x)=f(x,1) satisfies the following algebraic equation 2 2 2 x (-1 + 9 x) + (1 - 12 x + 24 x ) P + 16 x P = 0 and in Maple input notation x*(-1+9*x)+(1-12*x+24*x^2)*P+16*x^2*P^2 = 0 The first, 30, terms, for the sake of the OEIS are [1, 3, 12, 56, 288, 1584, 9152, 54912, 339456, 2149888, 13891584, 91287552, 608583680, 4107939840, 28030648320, 193100021760, 1341536993280, 9390758952960, 66182491668480, 469294031831040, 3346270487838720, 23981605162844160, 172667557172477952, 1248519259554840576, 9063324995286990848, 66032796394233790464, 482722511571640123392, 3539965084858694238208, 26035872237025235042304, 192014557748061108436992] Furthermore, the sequence of coefficients, let's call them , A[n], satisfy: 4 (1 + 2 n) A[n] - ---------------- + A[1 + n] = 0 3 + n and in Maple input format -4*(1+2*n)/(3+n)*A[n]+A[1+n] = 0 Just for fun, A[100], equals 1671285366243214201189155716962959204424482130253660912676433695144250662144782\ 1066240 -------------------------------------------------------- For the Enumeration of, BETA(0, 2), trees we have the following Theorem: Let f(x,y) be (unique!) formal power series, in the variables, x,y,\ satisfying the FUNCTIONAL Equation / 3 \ | f(x, 1) - y f(x, y)| f(x, y) = x (f(x, y) + 1) |1 + --------------------| \ 1 - y / Then P(x)=f(x,1) satisfies the following algebraic equation 2 4 2 3 x (x - 1) (529 x - 248 x + 16) + (3013 x + 1785 x - 4189 x - 328 x + 16) P 2 3 2 + 3 x (616 x - 2373 x + 2214 x - 16) P 2 3 3 3 4 + x (288 x - 4671 x + 7074 x - 16) P + 243 x (-4 + 15 x) P 4 5 + 729 x P = 0 and in Maple input notation x*(x-1)*(529*x^2-248*x+16)+(3013*x^4+1785*x^2-4189*x^3-328*x+16)*P+3*x*(616*x-\ 2373*x^2+2214*x^3-16)*P^2+x*(288*x-4671*x^2+7074*x^3-16)*P^3+243*x^3*(-4+15*x)* P^4+729*x^4*P^5 = 0 The first, 30, terms, for the sake of the OEIS are [1, 4, 22, 143, 1031, 7979, 65020, 551080, 4817554, 43182358, 395144362, 3679048042, 34763818704, 332694921060, 3219421336176, 31458554595319, 310059891002173, 3079593328464058, 30799207130047216, 309950032814720473, 3136882390231688797, 31911054336170264189, 326159657933986484216, 3348101360476384399871, 34506343578792233581765, 356944481261215136702464, 3704993265504313100652136, 38579365174719731306763544, 402911904025950807807249568, 4219569539869236179089161568] -------------------------------------------------------- For the Enumeration of, BETA(1, 0), trees we have the following Theorem: Let f(x,y) be (unique!) formal power series, in the variables, x,y,\ satisfying the FUNCTIONAL Equation / y f(x, 1) - y f(x, y)\ f(x, y) = x (f(x, y) + 1) |y + ---------------------| \ 1 - y / Then P(x)=f(x,1) satisfies the following algebraic equation 2 2 2 3 x (-1 + 8 x) + (1 - 10 x + 12 x ) P + 2 x (1 + 3 x) P + x P = 0 and in Maple input notation x*(-1+8*x)+(1-10*x+12*x^2)*P+2*x*(1+3*x)*P^2+x^2*P^3 = 0 The first, 30, terms, for the sake of the OEIS are [1, 2, 6, 22, 91, 408, 1938, 9614, 49335, 260130, 1402440, 7702632, 42975796, 243035536, 1390594458, 8038677054, 46892282815, 275750636070, 1633292229030, 9737153323590, 58392041019795, 352044769046880, 2132866978427640, 12980019040145352, 79319075627675556, 486556845464525528, 2995168113638767536, 18498288730876090608, 114595331036190018936, 711933341625150895008] Furthermore, the sequence of coefficients, let's call them , A[n], satisfy: (3 n + 2) (3 n + 1) A[n] -3/2 ------------------------ + A[1 + n] = 0 (2 + n) (2 n + 3) and in Maple input format -3/2*(3*n+2)*(3*n+1)/(2+n)/(2*n+3)*A[n]+A[1+n] = 0 Just for fun, A[100], equals 409659766834989876832016504243771792550166593344529698897890119433008849645240 -------------------------------------------------------- For the Enumeration of, BETA(1, 1), trees we have the following Theorem: Let f(x,y) be (unique!) formal power series, in the variables, x,y,\ satisfying the FUNCTIONAL Equation / 2 \ | y f(x, 1) - y f(x, y)| f(x, y) = x (f(x, y) + 1) |y + ----------------------| \ 1 - y / Then P(x)=f(x,1) satisfies the following algebraic equation 2 2 3 2 2 x (-1 + 11 x + x ) + (1 - 14 x + 25 x + 4 x ) P + x (3 + 17 x + 6 x ) P 2 3 3 4 + x (3 + 4 x) P + x P = 0 and in Maple input notation x*(-1+11*x+x^2)+(1-14*x+25*x^2+4*x^3)*P+x*(3+17*x+6*x^2)*P^2+x^2*(3+4*x)*P^3+x^ 3*P^4 = 0 The first, 30, terms, for the sake of the OEIS are [1, 3, 13, 68, 399, 2530, 16965, 118668, 857956, 6369883, 48336171, 373537388, 2931682810, 23317105140, 187606350645, 1524813969276, 12504654858828, 103367824774012, 860593023907540, 7211115497448720, 60776550501588855, 514956972502029690, 4384387181372914755, 37495248874510995828, 321973371914323166604, 2775265555241813680074, 24005427634602793982722, 208318056954199178840392, 1813260799116658123072932, 15827868548437082733879976 ] Furthermore, the sequence of coefficients, let's call them , A[n], satisfy: (4 n + 5) (1 + 2 n) (4 n + 3) A[n] -8/3 ---------------------------------- + A[1 + n] = 0 (3 n + 5) (3 n + 4) (2 + n) and in Maple input format -8/3*(4*n+5)*(1+2*n)*(4*n+3)/(3*n+5)/(3*n+4)/(2+n)*A[n]+A[1+n] = 0 Just for fun, A[100], equals 1958335222532740323179521075504620513949218475446617828993462540373260673891450\ 61562673626320 -------------------------------------------------------- For the Enumeration of, BETA(2, 2), trees we have the following Theorem: Let f(x,y) be (unique!) formal power series, in the variables, x,y,\ satisfying the FUNCTIONAL Equation / 2 3 \ | 2 y f(x, 1) - y f(x, y)| f(x, y) = x (f(x, y) + 1) |y + -----------------------| \ 1 - y / Then P(x)=f(x,1) satisfies the following algebraic equation 2 2 2 3 x (-1 + 16 x) + (1 - 20 x + 48 x ) P + 8 x (1 + 6 x) P + 16 x P = 0 and in Maple input notation x*(-1+16*x)+(1-20*x+48*x^2)*P+8*x*(1+6*x)*P^2+16*x^2*P^3 = 0 The first, 30, terms, for the sake of the OEIS are [1, 4, 24, 176, 1456, 13056, 124032, 1230592, 12629760, 133186560, 1436098560, 15774990336, 176028860416, 1990947110912, 22783499599872, 263411369705472, 3073132646563840, 36143187370967040, 428157758086840320, 5105072641718353920, 61228492804372561920, 738291391496202485760, 8945892499086964162560, 108884291560315620950016, 1330753264725848380932096, 16326138585273930241540096 , 201002329595320595701039104, 2482798285346192330927898624, 30761449942170620235733794816, 382216302401502323140561207296] Furthermore, the sequence of coefficients, let's call them , A[n], satisfy: 3 (3 n + 2) (3 n + 1) A[n] - -------------------------- + A[1 + n] = 0 (2 + n) (2 n + 3) and in Maple input format -3*(3*n+2)*(3*n+1)/(2+n)/(2*n+3)*A[n]+A[1+n] = 0 Just for fun, A[100], equals 2596527246588657108810302727727395068849691221535928099094417063182616799689612\ 49686023575510102574230405120 -------------------------------------------------------- For the Enumeration of, BETA(3, 3), trees we have the following Theorem: Let f(x,y) be (unique!) formal power series, in the variables, x,y,\ satisfying the FUNCTIONAL Equation / 3 4 \ | 3 y f(x, 1) - y f(x, y)| f(x, y) = x (f(x, y) + 1) |y + -----------------------| \ 1 - y / Then P(x)=f(x,1) satisfies the following algebraic equation 2 2 3 x (27 - 587 x + 729 x ) + (-27 - 3028 x + 4374 x + 722 x) P 2 2 2 3 + x (-4322 x + 10935 x - 285) P + 12 x (-141 x + 1215 x + 5) P 2 4 2 5 3 6 + x (405 x + 10935 x + 16) P + 54 x (4 + 81 x) P + 729 x P = 0 and in Maple input notation x*(27-587*x+729*x^2)+(-27-3028*x^2+4374*x^3+722*x)*P+x*(-4322*x+10935*x^2-285)* P^2+12*x*(-141*x+1215*x^2+5)*P^3+x*(405*x+10935*x^2+16)*P^4+54*x^2*(4+81*x)*P^5 +729*x^3*P^6 = 0 The first, 30, terms, for the sake of the OEIS are [1, 5, 38, 354, 3724, 42483, 513572, 6484954, 84713615, 1137132261, 15607973712 , 218251480308, 3100333814344, 44640498779174, 650340797788224, 9572195642796594, 142173647873989974, 2128768936827836934, 32105032363199005682 , 487349948887971142102, 7441566869736726978820, 114238439695733180495496, 1762314213631848500406752, 27308728426059257276945424, 424924300886295079688059469, 6637069163028794152388262163, 104033624114194490228009529320, 1636042867705224917922927567168, 25807230076726289279758372801344, 408249644884572093087347981568396] -------------------------------------------------------- For the Enumeration of, BETA(4, 4), trees we have the following Theorem: Let f(x,y) be (unique!) formal power series, in the variables, x,y,\ satisfying the FUNCTIONAL Equation / 4 5 \ | 4 y f(x, 1) - y f(x, y)| f(x, y) = x (f(x, y) + 1) |y + -----------------------| \ 1 - y / Then P(x)=f(x,1) satisfies the following algebraic equation 2 2 3 x (1024 - 27833 x + 65536 x ) + (-1024 + 33977 x - 200066 x + 458752 x ) P 2 2 + x (-13012 - 344985 x + 1376256 x ) P 2 3 2 4 + 10 x (687 - 18344 x + 229376 x ) P + 4 x (891 + 5200 x + 573440 x ) P 2 5 2 6 + 3 x (243 + 15104 x + 458752 x ) P + 512 x (27 + 896 x) P 3 7 + 65536 x P = 0 and in Maple input notation x*(1024-27833*x+65536*x^2)+(-1024+33977*x-200066*x^2+458752*x^3)*P+x*(-13012-\ 344985*x+1376256*x^2)*P^2+10*x*(687-18344*x+229376*x^2)*P^3+4*x*(891+5200*x+ 573440*x^2)*P^4+3*x*(243+15104*x+458752*x^2)*P^5+512*x^2*(27+896*x)*P^6+65536*x ^3*P^7 = 0 The first, 30, terms, for the sake of the OEIS are [1, 6, 55, 618, 7839, 107800, 1570644, 23900130, 376204111, 6084556582, 100621333263, 1695154923288, 29010555263940, 503224103352816, 8831808633051464, 156599169137453970, 2801950155747516015, 50539198351659022450, 918178935969924630085, 16789818194032219102458, 308828428376442737783079, 5710975845145223235860976, 106126607790361094575824720, 1980994535898915203505777528, 37130641070851174216154702724, 698609880524139136399486437768, 13190710941262994313864720470740, 249875681692401094371600453571600, 4747931171327205433166986704085080, 90473528049704529658981168359300064] -------------------------------------------------------- For the Enumeration of, BETA(5, 5), trees we have the following Theorem: Let f(x,y) be (unique!) formal power series, in the variables, x,y,\ satisfying the FUNCTIONAL Equation / 5 6 \ | 5 y f(x, 1) - y f(x, y)| f(x, y) = x (f(x, y) + 1) |y + -----------------------| \ 1 - y / Then P(x)=f(x,1) satisfies the following algebraic equation 2 x (84375 - 2752164 x + 9765625 x ) 3 2 + (-84375 + 78125000 x + 3342789 x - 25667428 x ) P 2 2 + x (-51007864 x - 1169595 + 273437500 x ) P 2 3 + 5 x (-7226920 x + 109375000 x + 249003) P 2 4 + 10 x (68359375 x + 95776 - 420450 x) P 2 5 + 20 x (469375 x + 27343750 x + 19456) P 2 6 2 7 + 4 x (68359375 x + 1787500 x + 16384) P + 25000 x (3125 x + 64) P 3 8 + 9765625 x P = 0 and in Maple input notation x*(84375-2752164*x+9765625*x^2)+(-84375+78125000*x^3+3342789*x-25667428*x^2)*P+ x*(-51007864*x-1169595+273437500*x^2)*P^2+5*x*(-7226920*x+109375000*x^2+249003) *P^3+10*x*(68359375*x^2+95776-420450*x)*P^4+20*x*(469375*x+27343750*x^2+19456)* P^5+4*x*(68359375*x^2+1787500*x+16384)*P^6+25000*x^2*(3125*x+64)*P^7+9765625*x^ 3*P^8 = 0 The first, 30, terms, for the sake of the OEIS are [1, 7, 75, 984, 14562, 233508, 3965818, 70327640, 1289880813, 24305498666, 468249888601, 9189259686984, 183184438268200, 3701160352508340, 75658200184388100, 1562479225841055032, 32560734806756832104, 684011251051698021015, 14472937064111560070101, 308222353614831637133240, 6602666240656252107383388, 142197556611158620074652136, 3077387457561518676069124710, 66898143244082754663180145848, 1460270494848689502683755271772, 31996551459503704044592350785768, 703561435978762328158399031149611, 15521054092225731244298034667043000, 343449794086461264798644481744803752, 7621499092032618022818666023526873336] ---------------------------------------------------- This concludes this article for enuermationg Beta(a,b) trees with a and b <=, 6 We were successful for the following pairs, {[0, 0], [0, 1], [0, 2], [1, 0], [1, 1], [2, 2], [3, 3], [4, 4], [5, 5]} but failed for the following pairs, {[0, 3], [0, 4], [0, 5], [0, 6], [1, 2], [1, 3], [1, 4], [1, 5], [1, 6], [2, 0], [2, 1], [2, 3], [2, 4], [2, 5], [2, 6], [3, 0], [3, 1], [3, 2], [3, 4], [3, 5], [3, 6], [4, 0], [4, 1], [4, 2], [4, 3], [4, 5], [4, 6], [5, 0], [5, 1], [5, 2], [5, 3], [5, 4], [5, 6], [6, 0], [6, 1], [6, 2], [6, 3], [6, 4], [6, 5], [6, 6]} This colcludes this article, that took, 1971.424, seconds to generate.