A288942 Number A(n,k) of ordered rooted trees with n non-root nodes and all outdegrees <= k; square array A(n,k), n >= 0, k >= 0, read by antidiagonals.

1, 1, 0, 1, 1, 0, 1, 1, 1, 0, 1, 1, 2, 1, 0, 1, 1, 2, 4, 1, 0, 1, 1, 2, 5, 9, 1, 0, 1, 1, 2, 5, 13, 21, 1, 0, 1, 1, 2, 5, 14, 36, 51, 1, 0, 1, 1, 2, 5, 14, 41, 104, 127, 1, 0, 1, 1, 2, 5, 14, 42, 125, 309, 323, 1, 0, 1, 1, 2, 5, 14, 42, 131, 393, 939, 835, 1, 0

Offset: 0

Author

Alois P. Heinz, Sep 01 2017

Keywords

• nonn
• tabl

Comments

Also the number of Dyck paths of semilength n with all ascent lengths <= k. A(4,2) = 9: /\/\/\/\, //\\/\/\, /\//\\/\, /\/\//\\, //\/\\/\, //\/\/\\, /\//\/\\, //\\//\\, //\//\\\.

Also the number of permutations p of [n] such that in 0p all up-jumps are <= k and no down-jump is larger than 1. An up-jump j occurs at position i in p if p_{i} > p_{i-1} and j is the index of p_i in the increasingly sorted list of those elements in {p_{i}, ..., p_{n}} that are larger than p_{i-1}. A down-jump j occurs at position i in p if p_{i} < p_{i-1} and j is the index of p_i in the decreasingly sorted list of those elements in {p_{i}, ..., p_{n}} that are smaller than p_{i-1}. First index in the lists is 1 here. A(4,2) = 9: 1234, 1243, 1324, 1342, 2134, 2143, 2314, 2341, 2431.

Examples

			A(4,2) = 9:
.
.   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
.
Square array A(n,k) begins:
  1, 1,   1,   1,    1,    1,    1,    1,    1, ...
  0, 1,   1,   1,    1,    1,    1,    1,    1, ...
  0, 1,   2,   2,    2,    2,    2,    2,    2, ...
  0, 1,   4,   5,    5,    5,    5,    5,    5, ...
  0, 1,   9,  13,   14,   14,   14,   14,   14, ...
  0, 1,  21,  36,   41,   42,   42,   42,   42, ...
  0, 1,  51, 104,  125,  131,  132,  132,  132, ...
  0, 1, 127, 309,  393,  421,  428,  429,  429, ...
  0, 1, 323, 939, 1265, 1385, 1421, 1429, 1430, ...
		

Links

• Alois P. Heinz, Rows n = 0..140, flattened
• N. Hein and J. Huang, Modular Catalan Numbers, arXiv:1508.01688 [math.CO], 2015
• Index entries for sequences related to rooted trees

Crossrefs

Columns k=0..10 give: A000007, A000012, A001006, A036765, A036766, A036767, A036768, A036769, A291823, A291824, A291825.

Main diagonal (and upper diagonals) give A000108.

First lower diagonal gives A001453.

Cf. A203717.

Programs

Maple

b:= proc(u, o, k) option remember; `if`(u+o=0, 1,
      add(b(u-j, o+j-1, k), j=1..min(1, u))+
      add(b(u+j-1, o-j, k), j=1..min(k, o)))
    end:
A:= (n, k)-> b(0, n, k):
seq(seq(A(n, d-n), n=0..d), d=0..12);

Mathematica

b[u_, o_, k_] := b[u, o, k] = If[u + o == 0, 1, Sum[b[u - j, o + j - 1, k], {j, 1, Min[1, u]}] + Sum[b[u + j - 1, o - j, k], {j, 1, Min[k, o]}]];
A[n_, k_] := b[0, n, k];
Table[Table[A[n, d-n], {n, 0, d}], {d, 0, 12}] // Flatten (* Jean-François Alcover, Oct 27 2017, translated from Maple *)

PARI

T(n,k)=polcoeff(serreverse(x*(1-x)/(1-x*x^k) + O(x^2*x^n)), n+1);
for(n=0, 10, for(k=0, 10, print1(T(n, k), ", ")); print); \\ Andrew Howroyd, Nov 29 2017

Formula

A(n,k) = Sum_{j=0..k} A203717(n,j).

G.f. of column k: G(x)/x where G(x) is the reversion of x*(1-x)/(1-x^(k+1)). - Andrew Howroyd, Nov 30 2017

G.f. g_k(x) of column k satisfies: g_k(x) = Sum_{j=0..k} (x*g_k(x))^j. - Alois P. Heinz, May 05 2019

A(n,k) = Sum_{j=0..n/(k+1)} (-1)^j/(n+1) * binomial(n+1,j) * binomial(2*n-j*(k+1),n). [Hein Eq (10)] - R. J. Mathar, Oct 14 2022; corrected by Tijn Caspar de Leeuw, Jul 07 2024