A244531 -id:A244531 - cp's OEIS frontend

A244530 Number T(n,k) of ordered unlabeled rooted trees with n nodes such that the minimal outdegree of inner nodes equals k; triangle T(n,k), n>=1, 0<=k<=n-1, read by rows.

1, 0, 1, 0, 1, 1, 0, 4, 0, 1, 0, 11, 2, 0, 1, 0, 36, 5, 0, 0, 1, 0, 117, 11, 3, 0, 0, 1, 0, 393, 28, 7, 0, 0, 0, 1, 0, 1339, 78, 8, 4, 0, 0, 0, 1, 0, 4630, 201, 21, 9, 0, 0, 0, 0, 1, 0, 16193, 532, 55, 10, 5, 0, 0, 0, 0, 1, 0, 57201, 1441, 121, 11, 11, 0, 0, 0, 0, 0, 1

Offset: 1

Joerg Arndt and Alois P. Heinz, Jun 29 2014

T(1,0) = 1 by convention.

			T(5,1) = 11:
  o   o     o     o     o     o     o     o     o     o     o
  |   |     |     |    / \   / \   / \    |    /|\   /|\   /|\
  o   o     o     o   o   o o   o o   o   o   o o o o o o o o o
  |   |    / \   / \  |         | |   |  /|\  |       |       |
  o   o   o   o o   o o         o o   o o o o o       o       o
  |  / \  |         | |         |
  o o   o o         o o         o
  |
  o
Triangle T(n,k) begins:
  1;
  0,     1;
  0,     1,   1;
  0,     4,   0,  1;
  0,    11,   2,  0,  1;
  0,    36,   5,  0,  0, 1;
  0,   117,  11,  3,  0, 0, 1;
  0,   393,  28,  7,  0, 0, 0, 1;
  0,  1339,  78,  8,  4, 0, 0, 0, 1;
  0,  4630, 201, 21,  9, 0, 0, 0, 0, 1;
  0, 16193, 532, 55, 10, 5, 0, 0, 0, 0, 1;

Alois P. Heinz, Rows n = 1..141, flattened

Columns k=0-10 give: A063524, A106640(n-2), A244531, A244532, A244533, A244534, A244535, A244536, A244537, A244538, A244539.
Row sums give A000108(n-1).
Cf. A244454 (unordered unlabeled rooted trees).

b:= proc(n, t, k) option remember; `if`(n=0,
      `if`(t in [0, k], 1, 0), `if`(t>n, 0, add(b(j-1, k$2)*
       b(n-j, max(0, t-1), k), j=1..n)))
    end:
T:= (n, k)-> b(n-1, k$2) -`if`(n=1 and k=0, 0, b(n-1, k+1$2)):
seq(seq(T(n, k), k=0..n-1), n=1..14);

b[n_, t_, k_] := b[n, t, k] = If[n == 0, If[t == 0 || t == k, 1, 0], If[t>n, 0, Sum[b[j-1, k, k]*b[n-j, Max[0, t-1], k], {j, 1, n}]]]; T[n_, k_] := b[n-1, k, k] - If[n == 1 && k == 0, 0, b[n-1, k+1, k+1]]; Table[Table[T[n, k], {k, 0, n-1}], {n, 1, 14}] // Flatten (* Jean-François Alcover, Jan 13 2015, translated from Maple *)

A244456 Number of unlabeled rooted trees with n nodes such that the minimal outdegree of inner nodes equals 2.

Original entry on oeis.org

1, 0, 1, 2, 4, 7, 15, 28, 56, 110, 220, 436, 878, 1762, 3560, 7205, 14650, 29838, 60991, 124938, 256628, 528238, 1089834, 2252860, 4666304, 9682422, 20125777, 41900433, 87369029, 182441944, 381499040, 798782945, 1674575394, 3514733683, 7385298837, 15534856067

Offset: 3

Joerg Arndt and Alois P. Heinz, Jun 29 2014

nonn

			a(5) = 1:
      o
     / \
    o   o
   / \
  o   o

Alois P. Heinz, Table of n, a(n) for n = 3..900

Column k=2 of A244454.

Cf. A244531, A246403.

b:= proc(n, i, t, k) option remember; `if`(n=0, `if`(t in [0, k],
      1, 0), `if`(i<1 or t>n, 0, add(binomial(b((i-1)$2, k$2)+j-1, j)*
      b(n-i*j, i-1, max(0,t-j), k), j=0..n/i)))
    end:
a:= n-> b(n-1$2, 2$2) -b(n-1$2, 3$2):
seq(a(n), n=3..40);

b[n_, i_, t_, k_] := b[n, i, t, k] = If[n == 0, If[t == 0 || t == k, 1, 0], If[i < 1, 0, Sum[Binomial[b[i - 1, i - 1, k, k] + j - 1, j]*b[n - i*j, i - 1, Max[0, t - j], k], {j, 0, n/i}]]]; a[n_] := b[n - 1, n - 1, 2, 2] - b[n - 1, n - 1, 3, 3] // FullSimplify; Table[a[n], {n, 3, 40}] (* Jean-François Alcover, Feb 06 2015, after Maple *)

a(n) ~ c * d^n / n^(3/2), where d = A246403 = 2.18946198566085056388702757711..., c = 0.4213018528699249210965028... (constants are same as for A001679). - Vaclav Kotesovec, Jul 02 2014

cp's OEIS Frontend

A244530 Number T(n,k) of ordered unlabeled rooted trees with n nodes such that the minimal outdegree of inner nodes equals k; triangle T(n,k), n>=1, 0<=k<=n-1, read by rows.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica