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

Author

Henry Bottomley, Sep 21 2001

Keywords

• nonn
• tabl

Comments

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

Examples

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

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.

Programs

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 *)

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

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.

Extensions

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