A064580 Triangle associated with rooted trees with a degree constraint (A036765).

1, 1, 1, 1, 2, 2, 1, 3, 5, 5, 1, 4, 9, 14, 13, 1, 5, 14, 28, 40, 36, 1, 6, 20, 48, 87, 118, 104, 1, 7, 27, 75, 161, 273, 357, 309, 1, 8, 35, 110, 270, 536, 866, 1100, 939, 1, 9, 44, 154, 423, 951, 1782, 2772, 3441, 2905, 1, 10, 54, 208, 630, 1572, 3310, 5928, 8946, 10900, 9118

Offset

0,5

Comments

Main diagonal is A036765. - Paul D. Hanna, Nov 18 2016

Links

Table of n, a(n) for n=0..65.

Formula

a(n, k) = a(n-1, k) + a(n-1, k-1) + a(n-1, k-2) + a(n-1, k-3) with a(0, 0)=1 and a(n, k)=0 if n < k or k < 0.

Example

Triangle begins:
  1;
  1,  1;
  1,  2,  2;
  1,  3,  5,  5;
  1,  4,  9, 14, 13;
  1,  5, 14, 28, 40, 36;
  ...

Mathematica

a[n_, k_] /; 0 <= k <= n = a[n, k] = a[n - 1, k] + a[n - 1, k - 1] + a[n - 1, k - 2] + a[n - 1, k - 3]; a[0, 0] = 1; a[_, _] = 0;
Table[a[n, k], {n, 0, 10}, {k, 0, n}] // Flatten (* Jean-François Alcover, Jul 30 2018 *}

Prog

(Sage) # uses[riordan_array from A256893]
M = riordan_array(1, x/(1+x+x^2+x^3), 12).inverse()
for m in M[1:]:
    print([r for r in reversed(list(m)) if r != 0]) # Peter Luschny, Aug 17 2016

Crossrefs

Columns include A000012, A000027, A000096.

Main diagonal is A036765.

The sequence of triangles A010054 (triangle indicator), A007318 (Pascal), A026300 (Motzkin), A064580, ... converges to the triangle A009766 (Catalan).

Row sums give A159772.

Sequence in context: A139687 A188181 A064581 * A009766 A059718 A076038

Adjacent sequences: A064577 A064578 A064579 * A064581 A064582 A064583

Keyword

nonn,tabl

Author

Henry Bottomley, Sep 21 2001

Extensions

Edited by N. J. A. Sloane at the suggestion of Andrew S. Plewe, Jun 17 2007

Status

approved