A291823 -id:A291823 - cp's OEIS frontend

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

Alois P. Heinz, Sep 01 2017

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.

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

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

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.

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

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

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

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

A261592 9-Modular Catalan Numbers C_{n,9}.

Original entry on oeis.org

1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16795, 58773, 207907, 742220, 2670564, 9674496, 35256723, 129164090, 475418625, 1757248194, 6519768464, 24272733060, 90648139140, 339497371575, 1274821281747, 4798525000860, 18102238168134, 68430875696534

Offset: 0

Nickolas Hein, Aug 25 2015

nonn

Definition: Given a primitive k-th root of unity w, a binary operation a*b=a+wb, and sufficiently general fixed complex numbers x_0, ..., x_n, the k-modular Catalan numbers C_{n,k} enumerate parenthesizations of x_0*x_1*...*x_n that give distinct values.
Theorem: C_{n,k} enumerates the following objects:
(1) binary trees with n internal nodes avoiding a certain subtree (i.e., comb_k^{+1}),
(2) plane trees with n+1 nodes whose non-root nodes have degree less than k,
(3) Dyck paths of length 2n avoiding a down-step followed immediately by k consecutive up-steps,
(4) partitions with n nonnegative parts bounded by the staircase partition (n-1,n-2,...,1,0) such that each positive number appears fewer than k times,
(5) standard 2-by-n Young tableaux whose top row avoids contiguous labels of the form i,j+1,j+2,...,j+k for all i(6) permutations of {1,2,...,n} avoiding 1-3-2 and 23...(k+1)1.

			The Catalan number C_10=16796 counts the parenthesizations of x_1*...*x_11 where * is arbitrary. Defining * and w as above and writing x_i compactly as xi, we have x1*(x2*(x3*(x4*(x5*(x6*(x7*(x8*(x9*(x10*(x11)))))))))) = x1+wx2+w^2x3+w^3x4+w^4x5+w^5x6+w^6x7+w^7x8+w^8x9+x10+wx11 = x1*(x2*(x3*(x4*(x5*(x6*(x7*(x8*(x9*(x10)))))))))*(x11). For n=10 and k=9, these are the only parenthesizations that give the same value for x1*...*x11, so C_{10,9}=16796-1=16795.

Andrew Howroyd, Table of n, a(n) for n = 0..200
Nickolas Hein, Jia Huang, Modular Catalan Numbers, arXiv:1508.01688 [math.CO], 2015-2016.

Column k=9 of A295679.
C_{n,1} is the all 1's sequence A000012. For C_{n,k} with k=2,3,4 see A011782, A005773, A159772. For k=5,6,7,8 see A261588, A261589, A261590, A261591.
Cf. A291823.

terms = 30; col[k_] := Module[{G}, G = InverseSeries[x*(1 - x)/(1 - x^k) + O[x]^terms, x]; CoefficientList[1/(1 - G), x]];
col[9] (* Jean-François Alcover, Dec 05 2017, after Andrew Howroyd *)

Vec(1/(1-serreverse(x*(1-x)/(1-x^9) + O(x*x^25)))) \\ Andrew Howroyd, Nov 29 2017

def C(k):
    print(1)
    for n in range(1,51):
        f = ((1-x^k)/(1-x))^n # ((x+1)^2-x^2*(x/(x+1))^(k-2))^n
        f = f.simplify_full()
        C = 0
        for i in range(n):
            C = C + (n-i)*f.coefficient(x,i)/n
        print(C)
time C(9)

sum( 1<=l<=n, (l/n)sum( m_1+...+m_k=n and m_2+2m_3+...+(k-1)m_k=n-l , MC(n;m_1,...,m_k) ) ), where MC(n;m_1,...,m_k) is the multinomial coefficient associated to the multiset (m_1,...,m_k).

G.f.: 1/(1-x*G(x)) where G(x) is g.f. of A291823. - Andrew Howroyd, Nov 29 2017

Showing 1-2 of 2 results.

cp's OEIS Frontend

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.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula