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,5

Links

Table of n, a(n) for n=1..49.

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

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( binomial(k-1, w)*binomial(n-k, x)*d(n-k+w-x, w+1)*d(k-w+x, k-w-1), w=0..k-2, x=0..n-k-1)

Example

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,
...

Crossrefs

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

Sequence in context: A181304 A339435 A118408 * A102316 A261767 A355315

Adjacent sequences: A079265 A079266 A079267 * A079269 A079270 A079271

Keyword

easy,nonn,tabl

Author

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

Status

approved