

A049019


Number of preferential arrangements (onto functions) associated with each numeric partition, partitions in Abramowitz and Stegun order, irregular triangle read by rows.


17



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
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,3


COMMENTS

a(n) 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 fourthorder 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 (0D faces), 36 edges (1D faces), 6 squares (2D faces), 8 hexagons (2D faces) and 1 3D 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(jk) ], the first column of the inverse matrix M^(1) contains the (n1) 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)^(nj) M^(j1)} where I is the identity matrix.
Another method for computing the coefficients and partitions up to (n1) rows is to use (1x^n)/ (1x) = 1+x^2+x^3+ ... + x^(n1) 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(jk)] 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 (n1) 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)


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. ArkaniHamed, Y. Bai, S. He, and G. Yan, Scattering forms and the positive geometry of kinematics, color, and the worldsheet , arXiv:1711.09102 [hepth], 2017.
T. 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, Y. Zhan, Labelled tree graphs, Feynman diagrams and disk integrals , arXiv:1708.08701 [hepth], 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.


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 # 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^(n1).  Tom Copeland, Oct 04 2008
From the matrix formulation with M_m,k = 1/(mk)!; 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 n1 the jth 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^(n1) and "inner product of x_1" to "wedge".  Tom Copeland, Feb 03 2010]


EXAMPLE

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 + 3D permutohedron + ... .  Tom Copeland, Oct 04 2008


PROG

(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


CROSSREFS

Cf. A000041, A019538, A000670.
Sequence in context: A218853 A048998 A213615 * A133314 A208909 A229565
Adjacent sequences: A049016 A049017 A049018 * A049020 A049021 A049022


KEYWORD

nonn,tabf


AUTHOR

Alford Arnold


EXTENSIONS

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


STATUS

approved



