|
%I #39 Jul 10 2021 05:07:12
%S 1,1,0,1,1,0,1,2,1,0,1,4,3,1,0,1,6,8,4,1,0,1,9,18,14,5,1,0,1,12,35,39,
%T 21,6,1,0,1,16,62,97,72,30,7,1,0,1,20,103,212,214,120,40,8,1,0,1,25,
%U 161,429,563,416,185,52,9,1,0,1,30,241,804,1344,1268,732,270,65,10,1,0
%N Triangle T(n,k) of number of rooted trees with n nodes and k leaves, 1 <= k <= n.
%C Harary denotes the g.f. as P(x, y) on page 33 "... , and let P(x,y) = Sum Sum P_{nm} x^ny^m where P_{nm} is the number of planted trees with n points and m endpoints, in which again the plant has not been counted either as a point or as an endpoint." - _Michael Somos_, Nov 02 2014
%D F. Harary, Recent results on graphical enumeration, pp. 29-36 of Graphs and Combinatorics (Washington, Jun 1973), Ed. by R. A. Bari and F. Harary. Lect. Notes Math., Vol. 406. Springer-Verlag, 1974.
%H Andrew Howroyd, <a href="/A055277/b055277.txt">Table of n, a(n) for n = 1..1275</a>
%H N. J. A. Sloane, <a href="/transforms.txt">Transforms</a>
%H Peter Steinbach, <a href="/A000055/a000055_10.pdf">Field Guide to Simple Graphs, Volume 3</a>, Part 10 (For Volumes 1, 2, 3, 4 of this book see A000088, A008406, A000055, A000664, respectively.)
%H <a href="/index/Ro#rooted">Index entries for sequences related to rooted trees</a>
%F G.f. satisfies A(x, y) = x*y + x*EULER(A(x, y)) - x. Shifts up under EULER transform.
%F G.f. satisfies A(x, y) = x*y - x + x * exp(Sum_{i>0} A(x^i, y^i) / i). [Harary, p. 34, equation (10)]. - _Michael Somos_, Nov 02 2014
%F Sum_k T(n, k) = A000081(n). - _Michael Somos_, Aug 24 2015
%e From _Joerg Arndt_, Aug 18 2014: (Start)
%e Triangle starts:
%e 01: 1
%e 02: 1 0
%e 03: 1 1 0
%e 04: 1 2 1 0
%e 05: 1 4 3 1 0
%e 06: 1 6 8 4 1 0
%e 07: 1 9 18 14 5 1 0
%e 08: 1 12 35 39 21 6 1 0
%e 09: 1 16 62 97 72 30 7 1 0
%e 10: 1 20 103 212 214 120 40 8 1 0
%e 11: 1 25 161 429 563 416 185 52 9 1 0
%e 12: 1 30 241 804 1344 1268 732 270 65 10 1 0
%e 13: 1 36 348 1427 2958 3499 2544 1203 378 80 11 1 0
%e ...
%e The trees with n=5 nodes, as (preorder-) level sequences, together with their number of leaves, and an ASCII rendering, are:
%e :
%e : 1: [ 0 1 2 3 4 ] 1
%e : O--o--o--o--o
%e :
%e : 2: [ 0 1 2 3 3 ] 2
%e : O--o--o--o
%e : .--o
%e :
%e : 3: [ 0 1 2 3 2 ] 2
%e : O--o--o--o
%e : .--o
%e :
%e : 4: [ 0 1 2 3 1 ] 2
%e : O--o--o--o
%e : .--o
%e :
%e : 5: [ 0 1 2 2 2 ] 3
%e : O--o--o
%e : .--o
%e : .--o
%e :
%e : 6: [ 0 1 2 2 1 ] 3
%e : O--o--o
%e : .--o
%e : .--o
%e :
%e : 7: [ 0 1 2 1 2 ] 2
%e : O--o--o
%e : .--o--o
%e :
%e : 8: [ 0 1 2 1 1 ] 3
%e : O--o--o
%e : .--o
%e : .--o
%e :
%e : 9: [ 0 1 1 1 1 ] 4
%e : O--o
%e : .--o
%e : .--o
%e : .--o
%e :
%e This gives [1, 4, 3, 1, 0], row n=5 of the triangle.
%e (End)
%e G.f. = x*(y + x*y + x^2*(y + y^2) + x^3*(y + 2*y^2 + y^3) + x^4*(y + 4*y^2 + 3*x^3 + y^4) + ...).
%t rut[n_]:=rut[n]=If[n===1,{{}},Join@@Function[c,Union[Sort/@Tuples[rut/@c]]]/@IntegerPartitions[n-1]];
%t Table[Length[Select[rut[n],Count[#,{},{-2}]===k&]],{n,13},{k,n}] (* _Gus Wiseman_, Mar 19 2018 *)
%o (PARI) {T(n, k) = my(A = O(x)); if(k<1 || k>n, 0, for(j=1, n, A = x*(y - 1 + exp( sum(i=1, j, 1/i * subst( subst( A + x * O(x^(j\i)), x, x^i), y, y^i) ) ))); polcoeff( polcoeff(A, n), k))}; /* _Michael Somos_, Aug 24 2015 */
%Y Row sums give A000081.
%Y Columns 2 through 12: A002620(n-1), A055278-A055287.
%Y Cf. A055288, A055289, A055290.
%Y Cf. A001190, A003238, A004111, A055327, A214575, A290689, A298422, A298426, A301342, A301343, A301344, A301345.
%K nonn,tabl,eigen
%O 1,8
%A _Christian G. Bower_, May 09 2000
|
