A079268 Triangle read by rows: d(n,k) = number of decreasing labeled trees with n nodes and largest leaf <= k, for 1 <= k <= n.

1, 1, 1, 1, 3, 3, 1, 7, 15, 15, 1, 15, 57, 105, 105, 1, 31, 195, 561, 945, 945, 1, 63, 633, 2685, 6555, 10395, 10395, 1, 127, 1995, 12105, 40725, 89055, 135135, 135135, 1, 255, 6177, 52605, 237555, 684495, 1381905, 2027025, 2027025, 1, 511, 18915, 223161

Offset: 1

Author

Jeremy Martin (martin(AT)math.umn.edu), Feb 05 2003

Keywords

• easy
• nonn
• tabl

Examples

			Triangle begins
1,
1, 1,
1, 3, 3,
1, 7, 15, 15,
1, 15, 57, 105, 105,
1, 31, 195, 561, 945, 945,
1, 63, 633, 2685, 6555, 10395, 10395,
...
		

Links

• J. L. Martin, The slopes determined by n points in the plane.
• Martin, Jeremy L. The slopes determined by n points in the plane. Duke Math. J. 131 (2006), no. 1, 119-165 (also arXiv math.AG/0302106, but beware errors).

Crossrefs

First three columns are A000012, A000225, A210448, rightmost two diagonals are both A001147, difference of second- and third-rightmost diagonals is A000165.

Formula

Recurrence: d(n, k) = 1 for n=0 or k=1, d(n, k) = 0 for n>0 and either k<0 or k>n, d(n, k) = d(n-1, k) + d(n, k-1) + Sum_{w=0..k-2, x=0..n-k-1} binomial(k-1, w) * binomial(n-k, x) * d(n-k+w-x, w+1) * d(k-w+x, k-w-1).