cp's OEIS Frontend

A055277 Triangle T(n,k) of number of rooted trees with n nodes and k leaves, 1 <= k <= n.

%I A055277 #39 Jul 10 2021 05:07:12
%S A055277 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 A055277 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 A055277 161,429,563,416,185,52,9,1,0,1,30,241,804,1344,1268,732,270,65,10,1,0
%N A055277 Triangle T(n,k) of number of rooted trees with n nodes and k leaves, 1 <= k <= n.
%C A055277 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 A055277 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 A055277 Andrew Howroyd, <a href="/A055277/b055277.txt">Table of n, a(n) for n = 1..1275</a>
%H A055277 N. J. A. Sloane, <a href="/transforms.txt">Transforms</a>
%H A055277 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 A055277 <a href="/index/Ro#rooted">Index entries for sequences related to rooted trees</a>
%F A055277 G.f. satisfies A(x, y) = x*y + x*EULER(A(x, y)) - x. Shifts up under EULER transform.
%F A055277 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 A055277 Sum_k T(n, k) = A000081(n). - _Michael Somos_, Aug 24 2015
%e A055277 From _Joerg Arndt_, Aug 18 2014: (Start)
%e A055277 Triangle starts:
%e A055277 01: 1
%e A055277 02: 1    0
%e A055277 03: 1    1    0
%e A055277 04: 1    2    1    0
%e A055277 05: 1    4    3    1    0
%e A055277 06: 1    6    8    4    1    0
%e A055277 07: 1    9   18   14    5    1    0
%e A055277 08: 1   12   35   39   21    6    1    0
%e A055277 09: 1   16   62   97   72   30    7    1    0
%e A055277 10: 1   20  103  212  214  120   40    8    1    0
%e A055277 11: 1   25  161  429  563  416  185   52    9    1    0
%e A055277 12: 1   30  241  804 1344 1268  732  270   65   10    1    0
%e A055277 13: 1   36  348 1427 2958 3499 2544 1203  378   80   11    1    0
%e A055277 ...
%e A055277 The trees with n=5 nodes, as (preorder-) level sequences, together with their number of leaves, and an ASCII rendering, are:
%e A055277 :
%e A055277 :     1:  [ 0 1 2 3 4 ]   1
%e A055277 :  O--o--o--o--o
%e A055277 :
%e A055277 :     2:  [ 0 1 2 3 3 ]   2
%e A055277 :  O--o--o--o
%e A055277 :        .--o
%e A055277 :
%e A055277 :     3:  [ 0 1 2 3 2 ]   2
%e A055277 :  O--o--o--o
%e A055277 :     .--o
%e A055277 :
%e A055277 :     4:  [ 0 1 2 3 1 ]   2
%e A055277 :  O--o--o--o
%e A055277 :  .--o
%e A055277 :
%e A055277 :     5:  [ 0 1 2 2 2 ]   3
%e A055277 :  O--o--o
%e A055277 :     .--o
%e A055277 :     .--o
%e A055277 :
%e A055277 :     6:  [ 0 1 2 2 1 ]   3
%e A055277 :  O--o--o
%e A055277 :     .--o
%e A055277 :  .--o
%e A055277 :
%e A055277 :     7:  [ 0 1 2 1 2 ]   2
%e A055277 :  O--o--o
%e A055277 :  .--o--o
%e A055277 :
%e A055277 :     8:  [ 0 1 2 1 1 ]   3
%e A055277 :  O--o--o
%e A055277 :  .--o
%e A055277 :  .--o
%e A055277 :
%e A055277 :     9:  [ 0 1 1 1 1 ]   4
%e A055277 :  O--o
%e A055277 :  .--o
%e A055277 :  .--o
%e A055277 :  .--o
%e A055277 :
%e A055277 This gives [1, 4, 3, 1, 0], row n=5 of the triangle.
%e A055277 (End)
%e A055277 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 A055277 rut[n_]:=rut[n]=If[n===1,{{}},Join@@Function[c,Union[Sort/@Tuples[rut/@c]]]/@IntegerPartitions[n-1]];
%t A055277 Table[Length[Select[rut[n],Count[#,{},{-2}]===k&]],{n,13},{k,n}] (* _Gus Wiseman_, Mar 19 2018 *)
%o A055277 (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 A055277 Row sums give A000081.
%Y A055277 Columns 2 through 12: A002620(n-1), A055278-A055287.
%Y A055277 Cf. A055288, A055289, A055290.
%Y A055277 Cf. A001190, A003238, A004111, A055327, A214575, A290689, A298422, A298426, A301342, A301343, A301344, A301345.
%K A055277 nonn,tabl,eigen
%O A055277 1,8
%A A055277 _Christian G. Bower_, May 09 2000