A125181 -id:A125181 - cp's OEIS frontend

A125644 Table with T(n,k) = the number of Dyck paths whose ascent lengths, in order, are the k-th composition of n, for the standard composition order.

1, 1, 1, 1, 1, 2, 1, 1, 1, 3, 2, 3, 1, 2, 1, 1, 1, 4, 3, 6, 2, 5, 3, 4, 1, 3, 2, 3, 1, 2, 1, 1, 1, 5, 4, 10, 3, 9, 6, 10, 2, 7, 5, 9, 3, 7, 4, 5, 1, 4, 3, 6, 2, 5, 3, 4, 1, 3, 2, 3, 1, 2, 1, 1, 1, 6, 5, 15, 4, 14, 10, 20, 3, 12, 9, 19, 6, 16, 10, 15, 2, 9, 7, 16, 5, 14, 9, 14, 3, 10, 7, 12, 4, 9, 5, 6, 1, 5

Offset: 0

Franklin T. Adams-Watters, Nov 29 2006

The standard composition order is specified in A066099. Also, the number of ordered, rooted trees for which the out-degrees of the non-leaf nodes, in preorder, form the specified composition.

			Composition number 11 is 2,1,1; there are 3 Dyck paths with this pattern: UUDDUDUD, UUDUDDUD and UUDUDUDD, so a(11) = 3. The corresponding trees are:
      O         O
      |         |
      O  O   O  O
      |  |   |  |
  O   O  O   O  O   O
   \ /    \ /    \ /
    O      O      O
The table starts:
  1;
  1;
  1,1;
  1,2,1,1;
  1,3,2,3,1,2,1,1;
  1,4,3,6,2,5,3,4,1,3,2,3,1,2,1,1;
  ...

Alois P. Heinz, Rows n = 0..14, flattened
Jon Maiga, Computer-generated formulas for A125644, Sequence Machine.

Cf. A125181, A011782 (row lengths), A000108 (row sums), A066099.

a:= proc(l) option remember; `if`(nops(l)<=1, 1,
      add(a(subsop(1=NULL, 2=l[2]+i, l)), i=0..l[1]-1))
    end:
b:= proc(n, l) option remember; `if`(n=0, [a(l)],
      [seq(b(n-i, [i, l[]])[], i=1..n)])
    end:
T:= n-> b(n, [])[]:
seq(T(n), n=0..8);  # Alois P. Heinz, May 25 2013

a[l_] := a[l] = If[Length[l] <= 1, 1, Sum[a[ReplacePart[l,
     {1 -> Nothing, 2 -> l[[2]]+i}]], {i, 0, l[[1]]-1}]];
b[n_, l_] := b[n, l] = If[n == 0, {a[l]},
     Flatten @ Table[b[n - i, Join[{i}, l]], {i, 1, n}]];
T[n_] := b[n, {}];
T /@ Range[0, 8] // Flatten (* Jean-François Alcover, Feb 14 2021, after Alois P. Heinz *)

For a composition [b_1,...,b_m], we have a([b_1]) = 1, a([b_1,b_2,...,b_m]) = Sum_{i=0}^{b_1-1} a([b_2+i,b_3,...,b_m]).

Conjecture: a(n) = A347205(A035327(n)) for n >= 0 (noticed by Sequence Machine). - Mikhail Kurkov, Dec 15 2021

A354622 Irregular triangle read by rows: Refined 3-Narayana triangle. Coefficients of partition polynomials of A134264, a refined Narayana triangle enumerating noncrossing partitions, with all h_k other than h_0, h_3, h_6, ..., h_(3n), ... replaced by zero.

Original entry on oeis.org

1, 1, 3, 1, 9, 12, 1, 12, 6, 66, 55, 1, 15, 15, 105, 105, 455, 273, 1, 18, 18, 9, 153, 306, 51, 816, 1224, 3060, 1428, 1, 21, 21, 21, 210, 420, 210, 210, 1330, 3990, 1330, 5985, 11970, 20349, 7752, 1, 24, 24, 24, 12, 276, 552, 552, 276, 276, 2024, 6072, 3036, 6072, 506, 10626, 42504, 21252, 42504, 106260, 134596, 43263

Offset: 1

Tom Copeland, Jul 08 2022

A set of partition polynomials with these coefficients and the polynomials of A338135 can be generated by substitution of the refined Narayana, or noncrossing partition, polynomials N_n[h_1,...,h_n] of A134264 (h_0=1) into themselves--once for A338135 and twice for this entry--or by setting the indeterminates h_n of A134264 to zero except for h_0, h_3, h_6, ..., h_(3n), ... with h_0 = 1 and ultimately re-indexing. This is equivalent to recursive use of the Lagrange inversion formula on f(x) = x / h(x) = x / (1 + h_1 x + h_2 x^2 + ...) since its compositional inverse is f^{(-1)}(x) = x + N_1(h_1) x + N_2(h_1,h_2) x^2 + .... The equivalence of the two methods of generation--the substitution and the zeroing out--follows from the general theorems stated by Peter Bala in his presentation of formulas for A108767 in 2008, which stem from a fixed point-iteration formalism of a basic identity for a compositional inverse pair, x* h(f^{(-1)}(x)) = f^{(-1)}(x), where, as above, h(x) = x / f(x).
The sets of refined m-Narayana polynomials are used by Cachazo and Umbert to characterize the scattering amplitudes of a class of quantum fields (see, e.g., section 7.3).
These could also be called the refined 3-Dyck path polynomials. From the interpretation of A134264 as Dyck paths in A125181, or staircases whose steps never rise above the diagonal of a square grid (see illustrations in Weisstein), the monomials of the partition polynomial N_4 = 1 (4') + 4 (1') (3') + 2 (2')^2 + 6 (1')^2 (2') + 1 (1')^4 of A134264 have the following correspondences:
1 (4') --> 1 staircase of one step of height 4,
4 (1') (3') --> 4 staircases of 1 step of height 1 and 1 step of height 3,
2 (2')^2 --> 2 staircases of 2 steps of height 2,
6 (1')^2 (2') --> 6 staircases of 2 steps of height 1 and 1 step of height 2,
1 (1')^4 --> 1 staircase of 4 steps of height 1.
Consequently, the partition polynomials G_{3n} of this entry enumerate staircases of height 3n with steps of heights 3, 6, 9, ..., 3k, ... only.
Diverse combinatorial models of the refined m-Narayana, or m-Dyck, polynomials are inherited from those presented for the refined Narayana, or noncrossing partition, polynomials in A134264 and A125181 and in the references therein.
A127537 gives a combinatorial model (see title and Domb and Barret therein, Table 2, p. 355) that contains the coefficients of the monomials h_1^n and h_1^(n-2) h_2, i.e., A001764 and A003408.

			Triangle begins:
  1;
  1,  3;
  1,  9, 12;
  1, 12,  6, 66,  55;
  1, 15, 15, 105, 105, 455, 273;
  ...
Row 1: G_3  = g_3
row 2: G_6  = g_6 + 3 g_3^2
row 3: G_9  = g_9 + 9 g_3 g_6 + 12 g_3^3
row 4: G_12 = g_12 + 12 g_3 g_9 + 6 g_6^2 + 66 g_3^2 g_6 + 55 g_3^4
row 5: G_15 = g_15 + 15 g_3 g_12 + 15 g_6 g_9 + 105 g_3^2 g_9 + 105 g_3 g_6^2
              + 455 g_3^3 g_6 + 273 g_3^5.
.
In the notation of Abramowitz and Stegun p. 831 with indices of the partitions above divided by 3 and partition indeterminates h_n denoted (n):
R_1 = (1);
R_2 = (2) + 3 (1)^2;
R_3 = (3) + 9 (1) (2) + 12 (1)^3;
R_4 = (4) + 12 (1) (3) + 6 (2)^2 + 66 (1)^2 (2) + 55 (1)^4;
R_5 = (5) + 15 (1) (4) + 15 (2) (3) + 105 (1)^2 (3) + 105 (1) (2)^2 + 455 (1)^3(2)
          + 273 (1)^5.

M. Abramowitz and I. A. Stegun, eds., Handbook of Mathematical Functions, National Bureau of Standards, Applied Math. Series 55, Tenth Printing, 1972 [alternative scanned copy]
F. Cachazo and B. Umbert, Connecting Scalar Amplitudes using The Positive Tropical Grassmannian, arXiv preprint arXiv:2205.02722 [hep-th], 2022.
MathOverflow, Combinatorics of iterated composition of noncrossing partition polynomials, a question posed by Tom Copeland, 2022.
Eric Weisstein's World of Mathematics, Dyck Path.

The length of row n is equal to A000041(n).
Row sums give A002293, n >= 1.
Cf. A001764, A003408, A004321, A108767, A125181, A127537, A134264, A173020, A179848, A235534, A338135.

Table[Binomial[Total[y], Length[y]-1] (Length[y]-1)! / Product[Count[y, i]!, {i, Max@@y}], {n, 8}, {y, Sort[Sort /@ IntegerPartitions[3n, n, Range[3, 3n, 3]]]}] // Flatten (* Andrey Zabolotskiy, Feb 19 2024, using Gus Wiseman's code for A134264 *)

\\ Compare with A134264
C(v)={my(n=vecsum(v), S=Set(v)); n!/((n-#v+1)!*prod(i=1, #S, my(x=S[i]); (#select(y->y==x, v))!))}
row(n)=[C(3*Vec(p)) | p<-partitions(n)]
{ for(n=1, 7, print(row(n))) } \\ Andrew Howroyd, Feb 19 2024

Coefficients of the monomials are those of the surviving monomials of the partition polynomials of A134264 after zeroing all indeterminates other than h_0, h_3, h_6, h_9, ..., h_(3n), .... The multinomial coefficients of A125181 also apply for G_n, giving the coefficient of the monomial h_1^e_1 h_2^e_2 ... h_n^n of R_n with se := e_1 + e_2 + ... + e_n as (3n)! / ((3n-se+1)! (e_1)! (e_2)! ... (e_n)!).
1*e_1 + 2*e_2 + ... + n*e_n = n for each monomial of R_n.
The partition polynomials R_n = N_n^3 of this entry can be determined from those of A338135, N_n^2, by substituting the partition polynomials of A134264, N_n, for the indeterminate h_n = (n) of N_n^2 or by doing the same for A134264 twice. E.g., N_1(h_1) = h_1, N_2(h_1,h_2) = h_2 + h_1^2, so N_2^2(h_1,h_2) = N_2(N_1,N_2) =  N_2 + N_1 = h_2 + h_1^2 + h_1^2 = h_2 + 2 h_1^2 and N_2^3(h_1,h_2) = N_2^2(N_1,N_2) = N_2 + 2 N_1^2 = h_2 + h_1^2 + 2 h_1^2 = h_2 + 3 h_1^2.
Reduces with all indeterminates h_n = (n) = t to A173020.
The coefficient of the monomial h_1^n is (3*n)! / ((3*n-n+1)! n!) = A001764(n) (see also A179848 and A235534). In general, the coefficients of these monomials of the refined (m+1)-Narayana polynomials are the Fuss-Catalan sequence associated to the row sums of the refined m-Narayana polynomials.
The coefficient of the monomial h_1^(n-2) h_2 is (3n)! / ((3n-n+2)! (n-2)!) = A003408(n-2) for n > 1.
The coefficient of the monomial h_1^(n-3) h_3 is (3n)! / ((3n-n+3)! (n-3)!) = A004321(n) for n > 2.

Rows 6-8 added by Andrey Zabolotskiy, Feb 19 2024

cp's OEIS Frontend

A125644 Table with T(n,k) = the number of Dyck paths whose ascent lengths, in order, are the k-th composition of n, for the standard composition order.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A138650 Table where T(n,k) is the number of unordered trees with n edges (n+1 nodes) whose node out-degrees form the k-th partition of the integer n (in Mathematica order).

Views

Author

Keywords

Examples

Crossrefs

A354622 Irregular triangle read by rows: Refined 3-Narayana triangle. Coefficients of partition polynomials of A134264, a refined Narayana triangle enumerating noncrossing partitions, with all h_k other than h_0, h_3, h_6, ..., h_(3n), ... replaced by zero.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions