A214575 -id:A214575 - cp's OEIS frontend

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

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, 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, 161, 429, 563, 416, 185, 52, 9, 1, 0, 1, 30, 241, 804, 1344, 1268, 732, 270, 65, 10, 1, 0

Offset: 1

Christian G. Bower, May 09 2000

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

			From _Joerg Arndt_, Aug 18 2014: (Start)
Triangle starts:
01: 1
02: 1    0
03: 1    1    0
04: 1    2    1    0
05: 1    4    3    1    0
06: 1    6    8    4    1    0
07: 1    9   18   14    5    1    0
08: 1   12   35   39   21    6    1    0
09: 1   16   62   97   72   30    7    1    0
10: 1   20  103  212  214  120   40    8    1    0
11: 1   25  161  429  563  416  185   52    9    1    0
12: 1   30  241  804 1344 1268  732  270   65   10    1    0
13: 1   36  348 1427 2958 3499 2544 1203  378   80   11    1    0
...
The trees with n=5 nodes, as (preorder-) level sequences, together with their number of leaves, and an ASCII rendering, are:
:
:     1:  [ 0 1 2 3 4 ]   1
:  O--o--o--o--o
:
:     2:  [ 0 1 2 3 3 ]   2
:  O--o--o--o
:        .--o
:
:     3:  [ 0 1 2 3 2 ]   2
:  O--o--o--o
:     .--o
:
:     4:  [ 0 1 2 3 1 ]   2
:  O--o--o--o
:  .--o
:
:     5:  [ 0 1 2 2 2 ]   3
:  O--o--o
:     .--o
:     .--o
:
:     6:  [ 0 1 2 2 1 ]   3
:  O--o--o
:     .--o
:  .--o
:
:     7:  [ 0 1 2 1 2 ]   2
:  O--o--o
:  .--o--o
:
:     8:  [ 0 1 2 1 1 ]   3
:  O--o--o
:  .--o
:  .--o
:
:     9:  [ 0 1 1 1 1 ]   4
:  O--o
:  .--o
:  .--o
:  .--o
:
This gives [1, 4, 3, 1, 0], row n=5 of the triangle.
(End)
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) + ...).

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.

Andrew Howroyd, Table of n, a(n) for n = 1..1275
N. J. A. Sloane, Transforms
Peter Steinbach, Field Guide to Simple Graphs, Volume 3, Part 10 (For Volumes 1, 2, 3, 4 of this book see A000088, A008406, A000055, A000664, respectively.)
Index entries for sequences related to rooted trees

Row sums give A000081.
Columns 2 through 12: A002620(n-1), A055278-A055287.
Cf. A055288, A055289, A055290.
Cf. A001190, A003238, A004111, A055327, A214575, A290689, A298422, A298426, A301342, A301343, A301344, A301345.

rut[n_]:=rut[n]=If[n===1,{{}},Join@@Function[c,Union[Sort/@Tuples[rut/@c]]]/@IntegerPartitions[n-1]];
Table[Length[Select[rut[n],Count[#,{},{-2}]===k&]],{n,13},{k,n}] (* Gus Wiseman, Mar 19 2018 *)

{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 */

G.f. satisfies A(x, y) = x*y + x*EULER(A(x, y)) - x. Shifts up under EULER transform.
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
Sum_k T(n, k) = A000081(n). - Michael Somos, Aug 24 2015

A301343 Regular triangle where T(n,k) is the number of planted achiral (or generalized Bethe) trees with n nodes and k leaves.

Original entry on oeis.org

1, 1, 0, 1, 1, 0, 1, 1, 1, 0, 1, 2, 1, 1, 0, 1, 2, 1, 1, 1, 0, 1, 3, 2, 2, 1, 1, 0, 1, 3, 2, 2, 1, 1, 1, 0, 1, 4, 2, 4, 1, 2, 1, 1, 0, 1, 4, 3, 4, 1, 3, 1, 1, 1, 0, 1, 5, 3, 6, 2, 4, 1, 2, 1, 1, 0, 1, 5, 3, 6, 2, 4, 1, 2, 1, 1, 1, 0, 1, 6, 4, 9, 2, 7, 1, 4, 2, 2, 1, 1, 0

Offset: 1

Gus Wiseman, Mar 19 2018

			Triangle begins:
1
1  0
1  1  0
1  1  1  0
1  2  1  1  0
1  2  1  1  1  0
1  3  2  2  1  1  0
1  3  2  2  1  1  1  0
1  4  2  4  1  2  1  1  0
1  4  3  4  1  3  1  1  1  0
1  5  3  6  2  4  1  2  1  1  0
The T(9,4) = 4 planted achiral trees: (((((oooo))))), ((((oo)(oo)))), (((oo))((oo))), ((o)(o)(o)(o)).

Row sums are A003238. A version without the zeroes or first row is A214575.

Cf. A000081, A003238, A004111, A032305, A055277, A214577, A273873, A289078, A289079, A290689, A291443, A298422, A298426, A301342, A301344, A301345.

tri[n_,k_]:=If[k===1,1,If[k>=n,0,Sum[tri[n-k,d],{d,Divisors[k]}]]];
Table[tri[n,k],{n,10},{k,n}]

T(n,1) = 1, T(n,k) = 0 if n <= k, otherwise T(n,k) = Sum_{d|k} T(n - k, d).

A214576 Triangle read by rows: T(n,k) is the number of partitions of n in which each part is divisible by the next and have last part equal to k (1<=k<=n).

Original entry on oeis.org

1, 1, 1, 2, 0, 1, 3, 1, 0, 1, 5, 0, 0, 0, 1, 6, 2, 1, 0, 0, 1, 10, 0, 0, 0, 0, 0, 1, 11, 3, 0, 1, 0, 0, 0, 1, 16, 0, 2, 0, 0, 0, 0, 0, 1, 19, 5, 0, 0, 1, 0, 0, 0, 0, 1, 26, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 27, 6, 3, 2, 0, 1, 0, 0, 0, 0, 0, 1, 40, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1

Offset: 1

Emeric Deutsch, Aug 18 2012

T(n,k) is also the number of generalized Bethe trees with n edges and root degree k.
A generalized Bethe tree is a rooted tree in which vertices at the same level have the same degree; they are called uniform trees in the Goldberg and Livshits reference.
There is a simple bijection between generalized Bethe trees with n edges and partitions of n in which each part is divisible by the next (the parts are given by the number of edges at the successive levels). We have the correspondences: root degree --- last part; number of leaves --- first part; height --- number of parts.
Sum of entries in row n is A003238(n+1).

			T(9,3)=2 because we have (6,3) and (3,3,3).
Triangle starts:
   1;
   1, 1;
   2, 0, 1;
   3, 1, 0, 1;
   5, 0, 0, 0, 1;
   6, 2, 1, 0, 0, 1;
  10, 0, 0, 0, 0, 0, 1;

Seiichi Manyama, Rows n = 1..140, flattened
M. K. Goldberg and E. M. Livshits, On minimal universal trees, Mathematical Notes of the Acad. of Sciences of the USSR, 4, 1968, 713-717 (translation from the Russian Mat. Zametki 4 1968 371-379).
O. Rojo, Spectra of weighted generalized Bethe trees joined at the root, Linear Algebra and its Appl., 428, 2008, 2961-2979.

Cf. A003238, A122934, A214575.

with(numtheory): a := proc (n) if n = 0 then 1 else add(a(divisors(n)[j]-1), j = 1 .. tau(n)) end if end proc: T := proc (n, k) if type(n/k, integer) = true then a(n/k-1) else 0 end if end proc: for n to 18 do seq(T(n, k), k = 1 .. n) end do; # yields sequence in triangular form

T(n,k)=a(n/k -1) if k|n and = 0 otherwise; here a(n) is defined by a(0)=1, a(n) = sum_{j|n}a(j-1). We have a(n) = A003238(n+1) = number of partitions of n in which each part is divisible by the next one.

A306489 Square array A(n,k), n >= 0, k >= 1, read by antidiagonals, where column k is the expansion of 1/(1 - Sum_{d|k} x^d).

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 3, 1, 1, 1, 2, 2, 5, 1, 1, 1, 1, 3, 3, 8, 1, 1, 1, 2, 1, 6, 4, 13, 1, 1, 1, 1, 4, 1, 10, 6, 21, 1, 1, 1, 2, 1, 7, 2, 18, 9, 34, 1, 1, 1, 1, 3, 1, 13, 3, 31, 13, 55, 1, 1, 1, 2, 2, 6, 1, 25, 4, 55, 19, 89, 1, 1, 1, 1, 3, 3, 10, 1, 46, 5, 96, 28, 144, 1

Offset: 0

Ilya Gutkovskiy, Feb 19 2019

A(n,k) is the number of compositions (ordered partitions) of n into divisors of k.

			Square array begins:
  1,  1,  1,   1,  1,   1,  ...
  1,  1,  1,   1,  1,   1,  ...
  1,  2,  1,   2,  1,   2,  ...
  1,  3,  2,   3,  1,   4,  ...
  1,  5,  3,   6,  1,   7,  ...
  1,  8,  4,  10,  2,  13,  ...

Columns k=1..7 give A000012, A000045 (for n > 0), A000930, A060945, A003520, A079958, A005709.

Cf. A100346, A214575.

Table[Function[k, SeriesCoefficient[1/(1 - Sum[x^d, {d, Divisors[k]}]), {x, 0, n}]][i - n + 1], {i, 0, 12}, {n, 0, i}] // Flatten

G.f. of column k: 1/(1 - Sum_{d|k} x^d).

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A301343 Regular triangle where T(n,k) is the number of planted achiral (or generalized Bethe) trees with n nodes and k leaves.

Views

Author

Keywords

Examples

Crossrefs

Programs

Mathematica

Formula

A214576 Triangle read by rows: T(n,k) is the number of partitions of n in which each part is divisible by the next and have last part equal to k (1<=k<=n).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Formula

A306489 Square array A(n,k), n >= 0, k >= 1, read by antidiagonals, where column k is the expansion of 1/(1 - Sum_{d|k} x^d).

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Formula