A244455 -id:A244455 - cp's OEIS frontend

A244454 Number T(n,k) of 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, 3, 0, 1, 0, 7, 1, 0, 1, 0, 17, 2, 0, 0, 1, 0, 42, 4, 1, 0, 0, 1, 0, 105, 7, 2, 0, 0, 0, 1, 0, 267, 15, 2, 1, 0, 0, 0, 1, 0, 684, 28, 4, 2, 0, 0, 0, 0, 1, 0, 1775, 56, 7, 2, 1, 0, 0, 0, 0, 1, 0, 4639, 110, 12, 2, 2, 0, 0, 0, 0, 0, 1

Offset: 1

Joerg Arndt and Alois P. Heinz, Jun 28 2014

T(1,0) = 1 by convention.

Sum_{i=2..n-1} T(n,i) = A001678(n+1) for n>1.

			The A000081(5) = 9 rooted trees with 5 nodes sorted by minimal outdegree of inner nodes are:
: 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                                     :         :         :
:                                       :         :         :
: ------------------1------------------ : ---2--- : ---4--- :
Thus row 5 = [0, 7, 1, 0, 1].
Triangle T(n,k) begins:
  1;
  0,    1;
  0,    1,   1;
  0,    3,   0,  1;
  0,    7,   1,  0, 1;
  0,   17,   2,  0, 0, 1;
  0,   42,   4,  1, 0, 0, 1;
  0,  105,   7,  2, 0, 0, 0, 1;
  0,  267,  15,  2, 1, 0, 0, 0, 1;
  0,  684,  28,  4, 2, 0, 0, 0, 0, 1;
  0, 1775,  56,  7, 2, 1, 0, 0, 0, 0, 1;
  0, 4639, 110, 12, 2, 2, 0, 0, 0, 0, 0, 1;

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

Columns k=0-10 give: A063524, A244455, A244456, A244457, A244458, A244459, A244460, A244461, A244462, A244463, A244464.
Row sums give A000081.
Cf. A001678, A244372, A244530 (ordered unlabeled rooted trees).

b:= proc(n, i, t, k) option remember; `if`(n=0, `if`(t in [0, k],
      1, 0), `if`(i<1, 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:
T:= (n, k)-> b(n-1$2, k$2) -`if`(n=1 and k=0, 0, b(n-1$2, k+1$2)):
seq(seq(T(n, k), k=0..n-1), n=1..14);

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}]]]; T[n_, k_] := b[n-1, n-1, k, k] - If[n == 1 && k == 0, 0, b[n-1, n-1, k+1, k+1]]; Table[Table[T[n, k], {k, 0, n-1}], {n, 1, 14}] // Flatten (* Jean-François Alcover, Jan 08 2015, translated from Maple *)

A106640 Row sums of A059346.

Original entry on oeis.org

1, 1, 4, 11, 36, 117, 393, 1339, 4630, 16193, 57201, 203799, 731602, 2643903, 9611748, 35130195, 129018798, 475907913, 1762457595, 6550726731, 24428808690, 91377474411, 342763939656, 1289070060903, 4859587760076, 18360668311027, 69514565858653, 263693929034909

Offset: 0

Philippe Deléham, May 26 2005

nonn

a(n) = p(n + 1) where p(x) is the unique degree-n polynomial such that p(k) = Catalan(k) for k = 0, 1, ..., n. - Michael Somos, Jan 05 2012
Number of Dyck (n+1)-paths whose minimum ascent length is 1. - David Scambler, Aug 22 2012
From Alois P. Heinz, Jun 29 2014: (Start)
a(n) is the number of ordered rooted trees with n+2 nodes such that the minimal outdegree equals 1. a(2) = 4:
   o    o      o      o
   |    |     / \    / \
   o    o    o   o  o   o
   |   / \   |          |
   o  o   o  o          o
   |
   o
(End)
Number of non-crossing partitions of {1,2,..,n+1} that contain cyclical adjacencies. a(2) = 4, [12|3, 13|2, 1|23, 123]. - Yuchun Ji, Nov 13 2020

			1 + x + 4*x^2 + 11*x^3 + 36*x^4 + 117*x^5 + 393*x^6 + 1339*x^7 + 4630*x^8 + ...
a(2) = 4 since p(x) = (x^2 - x + 2) / 2 interpolates p(0) = 1, p(1) = 1, p(2) = 2, and p(3) = 4. - _Michael Somos_, Jan 05 2012

Alois P. Heinz, Table of n, a(n) for n = 0..1000

Cf. A000108, A005043, A244455, A000296, A247494.

a:= proc(n) option remember; `if`(n<3, [1, 1, 4][n+1],
      ((30*n^3-44*n^2-22*n+24)*a(n-1)-(25*n^3-105*n^2+140*n-48)*a(n-2)
       -6*(n-1)*(5*n-4)*(2*n-3)*a(n-3))/(n*(n+2)*(5*n-9)))
    end:
seq(a(n), n=0..30);  # Alois P. Heinz, Jun 29 2014

max = 30; t = Table[Differences[Table[CatalanNumber[k], {k, 0, max}], n], {n, 0, max}]; a[n_] := Sum[t[[n-k+1, k]], {k, 1, n}]; Array[a, max] (* Jean-François Alcover, Jan 21 2017 *)

{a(n) = if( n<0, 0, n++; subst( polinterpolate( vector(n, k, binomial( 2*k - 2, k - 1) / k)), x, n + 1))} /* Michael Somos, Jan 05 2012 */

{a(n) = local(A); if( n<0, 0, A = x * O(x^n); polcoeff( 2 / (sqrt( 1 - 2*x - 3*x^2 + A) + (1 + x) * sqrt( 1 - 4*x + A)) ,n))} /* Michael Somos, Jan 05 2012 */

G.f.: (sqrt( 1 - 2*x - 3*x^2 ) / (1 + x) - sqrt( 1 - 4*x )) / (2*x^2) = 2 / (sqrt( 1 - 2*x - 3*x^2 ) + (1 + x) * sqrt( 1 - 4*x )). - Michael Somos, Jan 05 2012
a(n) = A000108(n+1) - A005043(n+1).
a(n) ~ 2^(2*n+2) / (sqrt(Pi)*n^(3/2)). - Vaclav Kotesovec, Jan 21 2017
a(n) = A000296(n+2) - A247494(n+1); i.e., remove the crossing partitions from the partitions with cyclical adjacencies. - Yuchun Ji, Nov 17 2020

Typo in a(20) corrected and more terms from Alois P. Heinz, Jun 29 2014

cp's OEIS Frontend

A244454 Number T(n,k) of 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