A049019 Irregular triangle read by rows: Row n gives numbers of preferential arrangements (onto functions) of n objects that are associated with the partition of n, taken in Abramowitz and Stegun order.

1, 1, 2, 1, 6, 6, 1, 8, 6, 36, 24, 1, 10, 20, 60, 90, 240, 120, 1, 12, 30, 20, 90, 360, 90, 480, 1080, 1800, 720, 1, 14, 42, 70, 126, 630, 420, 630, 840, 5040, 2520, 4200, 12600, 15120, 5040, 1, 16, 56, 112, 70, 168, 1008, 1680, 1260, 1680, 1344, 10080, 6720

Offset: 1

Author

Alford Arnold

Keywords

• nonn
• tabf

Comments

This is a refinement of A019538 with row sums in A000670.

From Tom Copeland, Sep 29 2008: (Start)

This array is related to the reciprocal of an e.g.f. as sketched in A133314. For example, the coefficient of the fourth-order term in the Taylor series expansion of 1/(a(0) + a(1) x + a(2) x^2/2! + a(3) x^3/3! + ...) is a(0)^(-5) * {24 a(1)^4 - 36 a(1)^2 a(2) a(0) + [8 a(1) a(3) + 6 a(2)^2] a(0)^2 - a(4) a(0)^3}.

The unsigned coefficients characterize the P3 permutohedron depicted on page 10 in the Loday link with 24 vertices (0-D faces), 36 edges (1-D faces), 6 squares (2-D faces), 8 hexagons (2-D faces) and 1 3-D permutohedron. Summing coefficients over like dimensions gives A019538 and A090582. Compare to A133437 for the associahedron.

Given the n X n lower triangular matrix M = [ binomial(j,k) u(j-k) ], the first column of the inverse matrix M^(-1) contains the (n-1) rows of A049019 as the coefficients of the multinomials formed from the u(j). M^(-1) can be computed as (1/u(0)){I - [I- M/u(0)]^n} / {I - [I- M/u(0)]} = - u(0)^(-n) {sum(j=1 to n)(-1)^j bin(n,j) u(0)^(n-j) M^(j-1)} where I is the identity matrix.

Another method for computing the coefficients and partitions up to (n-1) rows is to use (1-x^n)/ (1-x) = 1+x^2+x^3+ ... + x^(n-1) with x replaced either by [I- M/a(0)] or [1- g(x)/a(0)] with the n X n matrix M = [bin(j,k) a(j-k)] and g(x)= a(0) + a(1)x + a(2)x^2/2! + ... + a(n) x^n/n!. The first n terms (rows of the first column) of the resulting series (matrix) divided by a(0) contain the (n-1) rows of signed coefficients and associated partitions for A049019.

To obtain unsigned coefficients, change a(j) to -a(j) for j>0. A133314 contains other matrices and recursion formulas that could be used. The Faa di Bruno formula gives the coefficients as n! [e(1)+e(2)+...+e(n)]! / [1!^e(1) e(1)! 2!^e(2) e(2)!... n!^e(n) e(n)! ] for the partition of form [a(1)^e(1)...a(n)^e(n)] with [e(1)+2e(2)+...+ n e(n)] = n (see Abramowitz and Stegun pages 823 and 831) in agreement with Arnold's formula. (End)

Examples

			Irregular triangle starts (note the grouping by ';' when comparing with A019538):
[1] 1;
[2] 1;  2;
[3] 1;  6;  6;
[4] 1;  8,  6; 36;  24;
[5] 1; 10, 20; 60,  90; 240; 120;
[6] 1; 12, 30, 20;  90, 360,  90; 480, 1080; 1800; 720;
[7] 1; 14, 42, 70; 126, 630, 420, 630;  840, 5040, 2520; 4200, 12600; 15120; 5040;
.
a(17) = 240 because we can write
A048996(17)*A036038(17) = 4*60 = A036040(17)*A036043(17)! = 10*24.
As in A133314, 1/exp[u(.)*x] = u(0)^(-1) [ 1 ] + u(0)^(-2) [ -u(1) ] x + u(0)^(-3) [ -u(0)u(2) + 2 u(1)^2 ] x^2/2! + u(0)^(-4) [ -u(0)^2 u(3) + 6 u(0)u(1)u(2) - 6 u(1)^3 ] x^3/3! + u(0)^(-5) [ -u(0)^3 u(4) + 8 u(0)^2 u(1)u(3) + 6 u(0)^2 u(2)^2 - 36 u(0)u(1)^2 u(2) + 24 u(1)^4 ] x^4/4! + ... . These are essentially refined face polynomials for permutohedra: empty set + point + line segment + hexagon + 3-D- permutohedron + ... . - _Tom Copeland_, Oct 04 2008
		

Links

• Peter Luschny, Rows n = 1..36, flattened
• M. Abramowitz and I. A. Stegun, eds., Handbook of Mathematical Functions, National Bureau of Standards, Applied Math. Series 55, Tenth Printing, 1972.
• N. Arkani-Hamed, Y. Bai, S. He, and G. Yan, Scattering forms and the positive geometry of kinematics, color, and the worldsheet , arXiv:1711.09102 [hep-th], 2017.
• Tom Copeland, Bijective mapping between face polytopes of permutohedra and partitions of integers, Math StackExchange question, 2016.
• S. Forcey, The Hedra Zoo.
• X. Gao, S. He, and Y. Zhan, Labelled tree graphs, Feynman diagrams and disk integrals , arXiv:1708.08701 [hep-th], 2017.
• J. Loday, The Multiple Facets of the Associahedron
• V. Pilaud, The Associahedron and its Friends, presentation for Seminaire Lotharingien de Combinatoire, April 4 - 6, 2016.
• A. Postnikov, Positive Grassmannian and Polyhedral Subdivisions, arXiv:1806.05307 [math.CO], (cf. p. 17), 2018.

Crossrefs

Cf. A000041, A000670, A019538, A036038, A036040, A036043, A048996, A133314.

Programs

SageMath

def A049019(n):
    if n == 0: return [1]
    P = lambda k: Partitions(n, min_length=k, max_length=k)
    Q = (p.to_list() for k in (1..n) for p in P(k))
    return [factorial(len(p))*SetPartitions(sum(p), p).cardinality() for p in Q]
for n in (1..7): print(A049019(n)) # Peter Luschny, Aug 30 2019

Formula

a(n) = A048996(n) * A036038(n);

a(n) = A036040(n) * factorial(A036043(n)).

A lowering operator for the unsigned multinomials in the brackets in the example is [d/du(1) 1/POP] where u(1) is treated as a continuous variable and POP is an operator that pulls off the number of parts of a partition ignoring u(0), e.g., [d/du(1) 1/POP][ u(0)u(2) + 2 u(1)^2 ] = (1/2) 2*2 u(1) = 2*u(1), analogous to the prototypical delta operator (d/dz) z^n = n z^(n-1). - Tom Copeland, Oct 04 2008

From the matrix formulation with M_m,k = 1/(m-k)!; g(x) = exp[ u(.) x]; an orthonormal vector basis x_1, ..., x_n and En(x^k) = x_k for k <= n and zero otherwise, for j=0 to n-1 the j-th signed row multinomial is given by the wedge product of x_1 with the wedge product (-1)^j * j! * u(0)^(-n) * Wedge{ En[x g(x), x^2 g(x), ..., x^(j) g(x), ~, x^(j+2) g(x), ..., x^n g(x)] } where Wedge{a,b,c} = a v b v c (the usual wedge symbol is inverted here to prevent confusion with the power notation, see Mathworld) and the (j+1)-th element is omitted from the product. Tom Copeland, Oct 06 2008 [Changed an x^n to x^(n-1) and "inner product of x_1" to "wedge". - Tom Copeland, Feb 03 2010]

Extensions

Partitions for 7 and 8 from Tom Copeland, Oct 02 2008

Definition edited by N. J. A. Sloane, Nov 06 2023