A091187 -id:A091187 - cp's OEIS frontend

A091869 Triangle read by rows: T(n,k) is the number of Dyck paths of semilength n having k peaks at even height.

1, 1, 1, 2, 2, 1, 4, 6, 3, 1, 9, 16, 12, 4, 1, 21, 45, 40, 20, 5, 1, 51, 126, 135, 80, 30, 6, 1, 127, 357, 441, 315, 140, 42, 7, 1, 323, 1016, 1428, 1176, 630, 224, 56, 8, 1, 835, 2907, 4572, 4284, 2646, 1134, 336, 72, 9, 1, 2188, 8350, 14535, 15240, 10710, 5292, 1890, 480, 90, 10, 1

Offset: 1

Emeric Deutsch, Mar 10 2004

Number of ordered trees with n edges having k leaves at even height. Row sums are the Catalan numbers (A000108). T(n,0)=A001006(n-1) (the Motzkin numbers). Sum_{k=0..n-1} k*T(n,k) = binomial(2n-2, n-2) = A001791(n-1). Mirror image of A091187.
T(n,k) is the number of Dyck paths of semilength n and having k dud's (here u=(1,1) and d=(1,-1)). Example: T(4,2)=3 because we have uud(du[d)ud], uu(dud)(dud) and uu(du[d)ud]d (the dud's are shown between parentheses).
T(n,k) is the number of Dyck paths of semilength n and containing exactly k double rises whose matching down steps form a doublefall. Example: UUUDUDDD has 2 double rises but only the first has matching Ds - the path's last 2 steps - forming a doublefall. (Travel horizontally east from an up step to encounter its matching down step.) - David Callan, Jul 15 2004
T(n,k) is the number of ordered trees on n edges containing k edges of outdegree 1. (The outdegree of an edge is the outdegree of its child vertex. Thus edges of outdegree 1 correspond to non-root vertices of outdegree 1.) T(3,2)=2 because
  /\.../\.
  |.....|.
each have one edge of outdegree 1. - David Callan, Oct 25 2004
Exponential Riordan array [exp(x)*Bessel_I(1,2x)/x, x]. - Paul Barry, Mar 09 2010
T(n, k) is the number of Dyck paths of semilength n and having k udu's (here u=(1,1) and d=(1,-1)). Note that reversing a path swaps u and d, thus udu becomes dud and vice versa. - Michael Somos, Feb 26 2020

			T(4,1)=6 because we have u(ud)dudud, udu(ud)dud, ududu(ud)d, uuudd(ud)d, u(ud)uuddd and uuu(ud)ddd (here u=(1,1), d=(1,-1) and the peaks at even height are shown between parentheses).
Triangle begins:
    1;
    1,    1;
    2,    2,    1;
    4,    6,    3,    1;
    9,   16,   12,    4,    1;
   21,   45,   40,   20,    5,    1;
   51,  126,  135,   80,   30,    6,   1;
  127,  357,  441,  315,  140,   42,   7,  1;
  323, 1016, 1428, 1176,  630,  224,  56,  8, 1;
  835, 2907, 4572, 4284, 2646, 1134, 336, 72, 9, 1;
  ...

Alois P. Heinz, Rows n = 1..200, flattened
J. L. Baril and S. Kirgizov, The pure descent statistic on permutations, Preprint, 2016. See Table 2.
David Callan, Bijections for Dyck paths with all peak heights of the same parity, arXiv:1702.06150 [math.CO], 2017.
M. Dziemianczuk, Enumerations of plane trees with multiple edges and Raney lattice paths, Discrete Mathematics 337 (2014): 9-24.
Sergi Elizalde, Johnny Rivera Jr., and Yan Zhuang, Counting pattern-avoiding permutations by big descents, arXiv:2408.15111 [math.CO], 2024. See p. 11.
A. Sapounakis, I. Tasoulas and P. Tsikouras, Counting strings in Dyck paths, Discrete Math., 307 (2007), 2909-2924.
Yidong Sun, The statistic "number of udu's" in Dyck paths, Discrete Math., 287 (2004), 177-186.
Chao-Jen Wang, Applications of the Goulden-Jackson cluster method to counting Dyck paths by occurrences of subwords.

Cf. A001006, A005717, A102839, A371408, A375253, A375259.
Cf. A000108, A001791, A091187, A243752.
T(2n,n) gives A371411.

T := proc(n,k) if k0, b(x-1, y-1, 0)*z^irem(t*y+t, 2), 0)+
      `if`(y (p-> seq(coeff(p, z, i), i=0..degree(p)))(b(2*n, 0$2)):
seq(T(n), n=1..16);  # Alois P. Heinz, May 12 2017

(* m = MotzkinNumber *) m[0] = 1; m[n_] := m[n] = m[n - 1] + Sum[m[k]*m[n - 2 - k], {k, 0, n - 2}]; t[n_, n_] = 1; t[n_, k_] := m[n - k]*Binomial[n - 1, k - 1]; Table[t[n, k], {n, 1, 11}, {k, 1, n}] // Flatten (* Jean-François Alcover, Jul 10 2013 *)

{T(n, k) = my(y, c, w); if( k<0 || k>=n, 0, w = vector(n);   forvec(v=vector(2*n, k, [0, 1]), c=y=0; for(k=1, 2*n, if( 0>(y += (-1)^v[k]), break)); if( y, next); for(i=1, 2*n-2, c += ([0, 1, 0] == v[i..i+2])); w[c+1]++); w[k+1])}; /* Michael Somos, Feb 26 2020 */

T(n, k) = binomial(n-1, k)*(Sum_{j=0..ceiling((n-k)/2)} binomial(n-k, j)*binomial(n-k-j, j-1))/(n-k) for 0 <= k < n; T(n, k)=0 for k >= n.
G.f.: G = G(t, z) satisfies z*G^2 - (1 + z - t*z)*G + 1 + z - t*z = 0.
T(n, k) = M(n-k-1)*binomial(n-1, k), where M(n) = A001006(n) are the Motzkin numbers.
T(n+1, k+1) = n*T(n, k)/(k+1). - David Callan, Dec 09 2004
G.f.: 1/(1-x-xy-x^2/(1-x-xy-x^2/(1-x-xy-x^2/(1-x-xy-x^2/(1-... (continued fraction). - Paul Barry, Aug 03 2009
E.g.f.: exp(x+xy)*Bessel_I(1,2x)/x. - Paul Barry, Mar 10 2010

A355201 Normalized Schur self-convolution expansion coefficients K_{n+1}^n / n giving the coefficients of the Laurent series (compositionally) inverse to f(z) = c_0 z + c_1 + c_2 / z + c_3 / z^2 + ... . Irregular triangle for partition polynomials, with row lengths A000041(n) - 1 except for the first two, which are both of length 1.

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 3, 3, 3, 3, 1, 1, 6, 4, 2, 12, 6, 2, 4, 4, 1, 1, 10, 5, 10, 30, 10, 10, 10, 20, 10, 5, 5, 5, 1, 1, 15, 6, 30, 60, 15, 5, 60, 30, 60, 20, 15, 15, 30, 30, 15, 3, 6, 6, 6, 1, 1, 21, 7, 70, 105, 21, 35, 210, 70, 140, 35, 35, 105, 105, 105, 105, 35, 7, 42, 21, 21, 42, 42, 21, 7, 7, 7, 7, 1

Offset: 0

Tom Copeland, Jun 23 2022

For the formal Laurent series f(z) = a_0 z + a_1 + a_2 / z + a_3 / z^2 + ..., the formal compositional inverse is g(z) = b_0 z + b_1 + b_2 / z + b_3 / z^2 + ..., whose coefficients are partition polynomials whose numerical factors are those of this irregular triangle T(n,k). For the Schur coefficients defined in the formula section, -b_n = K_{n}^{n-1} / (n-1) for n > 1.
Analytic proofs of the relationship between the partition polynomials of the compositional inverse pair of Laurent series and Schur's self-convolution expansion coefficients are given in Schur (beware of a sign error) and in Airault and Ren.
Explicit examples (with a_0=1) of K_{n}^{n-1} up through n=5 are in Airault and Bouali on p. 182.
Various formulas for the b_n in terms of the associahedra (A133437), noncrossing (A134264), reciprocal (A263633), and Faber partition (A263916) polynomials are given in Copeland as well as a derivation of the explicit multi-factorial expression in the formula section and a combinatorial model.

			Triangle begins:
1) 1
2) 1
3) 1
4) 1,  1
5) 1,  1,  2,  1
6) 1,  3,  3,  3,  3,  1
7) 1,  6,  4,  2, 12,  6,  2,  4,  4,  1
8) 1, 10,  5, 10, 30, 10, 10, 10, 20, 10,  5,  5,  5,  1
  ...
The first few partition polynomials, with the monomials in the order of the partitions on p. 831 of Abramowitz and Stegun, are
b0 =    1 / a0
b1 = - a1 / a0
b2 = - a2
b3 = -(a1 a2 + a0 a3)
b4 = -(a1^2 a2 + a0 a2^2 + 2 a0 a1 a3 + a0^2 a4)
b5 = -(a1^3 a2+ 3 a0 a1 a2^2 + 3 a0 a1^2 a_3 + 3 a0^2 a2 a3 + 3 a0^2 a1 a4
      + a0^3 a_5)
b6 = -(a1^4 a2 + 6 a0 a1^2 a2^2 + 4 a0 a1^3 a3 + 2 a0^2 a2^3 + 12 a0^2 a1 a2 a3
      + 6 a0^2 a1^2 a4  + 2 a0^3 a3^2 + 4a0^3 a2 a4 + 4 a0^3 a1 a5 + a0^4 a6)
b7 = -(a1^5 a2 + 10 a_0 a1^3 a2^2 + 5 a0 a1^4 a3 + 10 a0^2 a1 a2^3
      + 30 a0^2 a1^2 a2 a3 + 10 a0^2 a1^3 a4 + 10 a0^3 a2^2 a3 + 10 a0^3 a1 a3^2
      + 20 a0^3 a1 a2 a4 + 10 a0^3 a1^2 a5 + 5 a0^4 a3 a4 + 5 a0^4 a2 a5
      + 5 a0^4 a1 a6 + a0^5 a7)
_____________________

H. Airault and A. Bouali, Differential calculus on the Faber polynomials, Bulletin des Sciences Mathématiques, Volume 130, Issue 3, April-May 2006, pages 179-222.
H. Airault and J. Ren, An algebra of differential operators and generating functions on the set of univalent functions, Bulletin des Sciences Mathématiques, Volume 126, Issue 5, June 2002, pages 343-367.
T. Copeland, One Matrix to Rule Them All: Schur self-Konvolution expansion Koefficients; inversion of Laurent and power series; and associahedra, noncrossing, and reciprocal partition polynomials, 2022.
I. Schur, Identities in the theory of power series, American Journal of Mathematics, Volume 69, No. 1, Jan 1947, pages 14-26.

Cf. A000108, A001263, A091187, A091869, A111785, A133437, A134264, A263633, A263916.

row[0] = row[1] = {1};
row[n_] := With[{s = Expand[Coefficient[Sum[c[k] x^k, {k, 0, n}]^(n-1), x, n] / (n-1)]}, Table[Coefficient[s, Product[c[t], {t, p}]], {p, Reverse[Sort[Sort /@ IntegerPartitions[n, {n-1}, Range[0, n]]]]}]];
Table[row[n], {n, 0, 8}] // Flatten (* Andrey Zabolotskiy, Feb 05 2023 *)

The index notations b(n), b_n, and bn are used interchangeably in this entry for indeterminates.
For n > 1, b_n(a_0,a_1,...,a_n) is a sum of monomials of the form a0^{e0} a1^{e1} a2^{e2} ... an^{en} with e1 * 1 + e2 * 2 + ... + en * n = n. When a_0 is not set to unity, e0 + e1 + ... + en = n - 1. (a1^n is not present.)
From a combinatorial argument in Copeland, the unsigned numerical coefficient of the monomial is given by (n-2)! / [(n - 1 - (e1 + e2 + ... + en))! e1! e2! ... en!].
The partition polynomials are generated by a subset of the Schur self-convolution expansion coefficients as -b_n = K_{n}^{n-1} / (n-1) =(D_{x=0}^n / n!) (a_0 + a_1 x + a_2 x^2 + ... + a_n x^n)^{n-1} / (n-1).
Row sums are the Catalan numbers A000108, ignoring the overall sign, for b_1 onwards.
Reduces to the Narayana triangle A001263 with a_0 = t and all the other indeterminates unity, ignoring the overall sign, for b_2 onwards.
Reduces to A091869 (reversed A091187) with a_1 = t and all the other indeterminates unity, ignoring the overall sign, for b_2 onwards.
b_n(c_1,...,c_n) = - Sum_{k=0}^{n-1} b_k(c_1,...,c_k) N_{n-k}(c_1,...,c_{n-k}) with c_0 = 1 and N_k(c_1,...,c_k) the noncrossing partition polynomials of A134264.
[b] = [R][N], representing the substitution of the noncrossing partition polynomials of A134264 for the indeterminates of the signed reciprocal polynomials of A263633 defined by R_n = 1 / (1 + c_1 x + c_2 x^2 + ...).
Conversely, [R][b] = [N] since the substitution transformation denoted by [R] is an involution, i.e., [R]^2 = [I], the identity substitution.
[b] = [R][A][R], a substitutional conjugation of the set of associahedra partition polynomials of A133147, or A111785, with re-indexing and (1') = 1, e.g., A_0 = 1, A_1 = -c_1, and A_2 = 2 c_1^2 - c_2.
Conversely, [A] = [R][b][R].

Rows 8-9 added by Andrey Zabolotskiy, Feb 05 2023

cp's OEIS Frontend

A091869 Triangle read by rows: T(n,k) is the number of Dyck paths of semilength n having k peaks at even height.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula