A354622 - OEIS

%I #74 Feb 20 2024 01:16:24

%S 1,1,3,1,9,12,1,12,6,66,55,1,15,15,105,105,455,273,1,18,18,9,153,306,

%T 51,816,1224,3060,1428,1,21,21,21,210,420,210,210,1330,3990,1330,5985,

%U 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

%N 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.

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

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

%C 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:

%C 1 (4') --> 1 staircase of one step of height 4,

%C 4 (1') (3') --> 4 staircases of 1 step of height 1 and 1 step of height 3,

%C 2 (2')^2 --> 2 staircases of 2 steps of height 2,

%C 6 (1')^2 (2') --> 6 staircases of 2 steps of height 1 and 1 step of height 2,

%C 1 (1')^4 --> 1 staircase of 4 steps of height 1.

%C Consequently, the partition polynomials G_{3n} of this entry enumerate staircases of height 3n with steps of heights 3, 6, 9, ..., 3k, ... only.

%C 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.

%C 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.

%H M. Abramowitz and I. A. Stegun, eds., <a href="http://www.convertit.com/Go/ConvertIt/Reference/AMS55.ASP">Handbook of Mathematical Function</a>s, National Bureau of Standards, Applied Math. Series 55, Tenth Printing, 1972 [alternative scanned copy]

%H F. Cachazo and B. Umbert, <a href="https://arxiv.org/abs/2205.02722">Connecting Scalar Amplitudes using The Positive Tropical Grassmannian</a>, arXiv preprint arXiv:2205.02722 [hep-th], 2022.

%H MathOverflow, <a href="https://mathoverflow.net/questions/425283/combinatorics-of-iterated-composition-of-noncrossing-partition-polynomials">Combinatorics of iterated composition of noncrossing partition polynomials</a>, a question posed by Tom Copeland, 2022.

%H Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/DyckPath.html">Dyck Path</a>.

%F 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)!).

%F 1*e_1 + 2*e_2 + ... + n*e_n = n for each monomial of R_n.

%F 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.

%F Reduces with all indeterminates h_n = (n) = t to A173020.

%F 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.

%F The coefficient of the monomial h_1^(n-2) h_2 is (3n)! / ((3n-n+2)! (n-2)!) = A003408(n-2) for n > 1.

%F The coefficient of the monomial h_1^(n-3) h_3 is (3n)! / ((3n-n+3)! (n-3)!) = A004321(n) for n > 2.

%e Triangle begins:

%e   1;

%e   1,  3;

%e   1,  9, 12;

%e   1, 12,  6, 66,  55;

%e   1, 15, 15, 105, 105, 455, 273;

%e   ...

%e Row 1: G_3  = g_3

%e row 2: G_6  = g_6 + 3 g_3^2

%e row 3: G_9  = g_9 + 9 g_3 g_6 + 12 g_3^3

%e 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

%e 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

%e               + 455 g_3^3 g_6 + 273 g_3^5.

%e .

%e 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):

%e R_1 = (1);

%e R_2 = (2) + 3 (1)^2;

%e R_3 = (3) + 9 (1) (2) + 12 (1)^3;

%e R_4 = (4) + 12 (1) (3) + 6 (2)^2 + 66 (1)^2 (2) + 55 (1)^4;

%e R_5 = (5) + 15 (1) (4) + 15 (2) (3) + 105 (1)^2 (3) + 105 (1) (2)^2 + 455 (1)^3(2)

%e           + 273 (1)^5.

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

%o (PARI) \\ Compare with A134264

%o 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))!))}

%o row(n)=[C(3*Vec(p)) | p<-partitions(n)]

%o { for(n=1, 7, print(row(n))) } \\ _Andrew Howroyd_, Feb 19 2024

%Y The length of row n is equal to A000041(n).

%Y Row sums give A002293, n >= 1.

%Y Cf. A001764, A003408, A004321, A108767, A125181, A127537, A134264, A173020, A179848, A235534, A338135.

%K nonn,tabf

%O 1,3

%A _Tom Copeland_, Jul 08 2022

%E Rows 6-8 added by _Andrey Zabolotskiy_, Feb 19 2024