login
Irregular triangle of multinomial coefficients of integer partitions read by rows (in Abramowitz and Stegun ordering) giving the coefficients of the cycle index polynomials for the symmetric groups S_n.
72

%I #307 Jun 10 2023 14:31:38

%S 1,1,1,2,3,1,6,8,3,6,1,24,30,20,20,15,10,1,120,144,90,40,90,120,15,40,

%T 45,15,1,720,840,504,420,504,630,280,210,210,420,105,70,105,21,1,5040,

%U 5760,3360,2688,1260,3360,4032,3360,1260,1120,1344,2520,1120,1680,105,420,1120,420,112,210,28,1

%N Irregular triangle of multinomial coefficients of integer partitions read by rows (in Abramowitz and Stegun ordering) giving the coefficients of the cycle index polynomials for the symmetric groups S_n.

%C The sequence of row lengths is A000041(n), n >= 1 (partition numbers).

%C Number of permutations whose cycle structure is the given partition. Row sums are factorials (A000142). - _Franklin T. Adams-Watters_, Jan 12 2006

%C A relation between partition polynomials formed from these "refined" Stirling numbers of the first kind and umbral operator trees and Lagrange inversion is presented in the link "Lagrange a la Lah".

%C These cycle index polynomials for the symmetric group S_n are also related to a raising operator / infinitesimal generator for fractional integro-derivatives, involving the digamma function and the Riemann zeta function values at positive integers, and to the characteristic polynomial for the adjacency matrix of complete n-graphs A055137 (cf. MathOverflow link). - _Tom Copeland_, Nov 03 2012

%C In the Lang link, replace all x(n) by t to obtain A132393. Furthermore replace x(1) by t and all other x(n) by 1 to obtain A008290. See A274760. - _Tom Copeland_, Nov 06 2012, Oct 29 2015 - corrected by _Johannes W. Meijer_, Jul 28 2016

%C The umbral compositional inverses of these polynomials are formed by negating the indeterminates x(n) for n>1, i.e., P(n,P(.,x(1),-x(2),-x(3),...),x(2),x(3),...) = x(1)^n (cf. A130561 for an example of umbral compositional inversion). The polynomials are an Appell sequence in x(1), i.e., dP(n,x(1))/dx(1) = n P(n-1, x(1)) and (P(.,x)+y)^n=P(n,x+y) umbrally, with P(0,x(1))=1. - _Tom Copeland_, Nov 14 2014

%C Regarded as the coefficients of the partition polynomials listed by Lang, a signed version of these polynomials IF(n,b1,b2,...,bn) (n! times polynomial on page 184 of Airault and Bouali) provides an inversion of the Faber polynomials F(n,b1,b2,...,bn) (page 52 of Bouali, A263916, and A115131). For example, F(3, IF(1,b1), IF(2,b1,b2)/2!, IF(3,b1,b2,b3)/3!) = b3 and IF(3, F(1,b1), F(2,b1,b2), F(3,b1,b2,b3))/3! = b3 with F(1,b1) = -b1. (Compare with A263634.) - _Tom Copeland_, Oct 28 2015; Sep 09 2016)

%C The e.g.f. for the row partition polynomials is Sum_{n>=0} P_n(b_1,...,b_n) x^n/n! = exp[Sum_{n>=1} b_n x^n/n], or, exp[P.(b_1,...,b_n)x] = exp[-<log(1-b.x)>], expressed umbrally with <"power series"> denoting umbral evaluation (b.)^n = b_n within the power series. This e.g.f. is central to the paper by Maxim and Schuermannn on characteristic classes (cf. Friedrich and McKay also). - _Tom Copeland_, Nov 11 2015

%C The elementary Schur polynomials are given by S(n,x(1),x(2),...,x(n)) = P(n,x(1), 2*x(2),...,n*x(n)) / n!. See p. 12 of Carrell. - _Tom Copeland_, Feb 06 2016

%C These partition polynomials are also related to the Casimir invariants associated to quantum density states on p. 3 of Boya and Dixit and pp. 5 and 6 of Byrd and Khaneja. - _Tom Copeland_, Jul 24 2017

%C With the indeterminates (x_1,x_2,x_3,...) = (t,-c_2*t,-c_3*t,...) with c_n >0, umbrally P(n,a.) = P(n,t)|_{t^n = a_n} = 0 and P(j,a.)P(k,a.) = P(j,t)P(k,t)|_{t^n =a_n} = d_{j,k} >= 0 is the coefficient of x^j/j!*y^k/k! in the Taylor series expansion of the formal group law FGL(x,y) = f[f^{-1}(x)+f^{-1}(y)], where a_n are the inversion partition polynomials for calculating f(x) from the coefficients of the series expansion of f^{-1}(x) given in A133932. - _Tom Copeland_, Feb 09 2018

%C For relation to the Witt symmetric functions, as well as the basic power, elementary, and complete symmetric functions, see the Borger link p. 295. For relations to diverse zeta functions, determinants, and paths on graphs, see the MathOverflow question Cycling Through the Zeta Garden. - _Tom Copeland_, Mar 25 2018

%C Chmutov et al. identify the partition polynomials of this entry with the one-part Schur polynomials and assert that any linear combination with constant coefficients of these polynomials is a tau function for the KP hierarchy. - _Tom Copeland_, Apr 05 2018

%C With the indeterminates in the partition polynomials assigned as generalized harmonic numbers, i.e., as partial sums of the Dirichlet series for the Riemann zeta function, zeta(n), for integer n > 1, sums of simple normalizations of these polynomials give either unity or simple sums of consecutive zeta(n) (cf. Hoffman). Other identities involving these polynomials can be found in the Choi reference in Hoffman's paper. - _Tom Copeland_, Oct 05 2019

%C On p. 39 of Ma Luo's thesis is the e.g.f. of rational functions r_n obtained through the (umbral) formula 1/(1-r.T) = exp[log(1+P.T)], a differently signed e.g.f. of this entry, where (P.)^n = P_n are Eisenstein elliptic functions. P. 38 gives the example of 4! * r_4 as the signed 4th row partition polynomial of this entry. This series is equated through a simple proportionality factor to the Zagier Jacobi form on p. 25. Recurrence relations for the P_n are given on p. 24 involving the normalized k-weight Eisenstein series G_k introduced on p. 23 and related to the Bernoulli numbers. - _Tom Copeland_, Oct 16 2019

%C The Chern characteristic classes or forms of complex vector bundles and the characteristic polynomials of curvature forms for a smooth manifold can be expressed in terms of this entry's partition polynomials with the associated traces, or power sum polynomials, as the indeterminates. The Chern character is the e.g.f. of these traces and so its coefficients are given by the Faber polynomials with this entry's partition polynomials as the indeterminates. See the Mathoverflow question "A canonical reference for Chern characteristic classes". - _Tom Copeland_, Nov 04 2019

%C For an application to the physics of charged fermions in an external field, see Figueroa et al. - _Tom Copeland_, Dec 05 2019

%C Konopelchenko, in Proposition 5.2, p. 19, defines an operator P_k that is a differently signed operator version of the partition polynomials of this entry divided by a factorial. These operators give rise to bilinear Hirota equations for the KP hierarchy. These partition polynomials are also presented in Hopf algebras of symmetric functions by Cartier. - _Tom Copeland_, Dec 18 2019

%C For relationship of these partition polynomials to calculations of Pontryagin classes and the Riemann xi function, see A231846. - _Tom Copeland_, May 27 2020

%C Luest and Skliros summarize on p. 298 many of the properties of the cycle index polynomials given here; and Bianchi and Firrotta, a few on p. 6. - _Tom Copeland_, Oct 15 2020

%C From _Tom Copeland_, Oct 15 2020: (Start)

%C With a_n = n! * b_n = (n-1)! * c_n for n > 0, represent a function with f(0) = a_0 = b_0 = 1 as an

%C A) exponential generating function (e.g.f), or formal Taylor series: f(x) = e^{a.x} = 1 + Sum_{n > 0} a_n * x^n/n!

%C B) ordinary generating function (o.g.f.), or formal power series: f(x) = 1/(1-b.x) = 1 + Sum_{n > 0} b_n * x^n

%C C) logarithmic generating function (l.g.f): f(x) = 1 - log(1 - c.x) = 1 + Sum_{n > 0} c_n * x^n /n.

%C Expansions of log(f(x)) are given in

%C I) A127671 and A263634 for the e.g.f: log[ e^{a.*x} ] = e^{L.(a_1,a_2,...)x} = Sum_{n > 0} L_n(a_1,...,a_n) * x^n/n!, the logarithmic polynomials, cumulant expansion polynomials

%C II) A263916 for the o.g.f.: log[ 1/(1-b.x) ] = log[ 1 - F.(b_1,b_2,...)x ] = -Sum_{n > 0} F_n(b_1,...,b_n) * x^n/n, the Faber polynomials.

%C Expansions of exp(f(x)-1) are given in

%C III) A036040 for an e.g.f: exp[ e^{a.x} - 1 ] = e^{BELL.(a_1,...)x}, the Bell/Touchard/exponential partition polynomials, a.k.a. the Stirling partition polynomials of the second kind

%C IV) A130561 for an o.g.f.: exp[ b.x/(1-b.x) ] = e^{LAH.(b.,...)x}, the Lah partition polynomials

%C V) A036039 for an l.g.f.: exp[ -log(1-c.x) ] = e^{CIP.(c_1,...)x}, the cycle index polynomials of the symmetric groups S_n, a.k.a. the Stirling partition polynomials of the first kind.

%C Since exp and log are a compositional inverse pair, one can extract the indeterminates of the log set of partition polynomials from the exp set and vice versa. For a discussion of the relations among these polynomials and the combinatorics of connected and disconnected graphs/maps, see Novak and LaCroix on classical moments and cumulants and the two books on statistical mechanics referenced in A036040. (End)

%D Abramowitz and Stegun, Handbook, p. 831, column labeled "M_2".

%H David W. Wilson, <a href="/A036039/b036039.txt">Table of n, a(n) for n = 1..11731</a> (rows 1 through 26).

%H Milton Abramowitz and Irene A. Stegun, editors, <a href="http://www.convertit.com/Go/ConvertIt/Reference/AMS55.ASP">Multinomials: M_1, M_2 and M_3</a>, Handbook of Mathematical Functions, December 1972, pp. 831-2.

%H H. Airault and A. Bouali, <a href="http://dx.doi.org/10.1016/j.bulsci.2005.10.002">Differential calculus on the Faber polynomials</a>, Bulletin des Sciences Mathématiques, Volume 130, Issue 3, April-May 2006, Pages 179-222.

%H M. Bianchi and M. Firrotta, <a href="https://arxiv.org/abs/1902.07016">DDF operators, open string coherent states and their scattering amplitudes</a>, arXiv:1902.07016 [hep-th], 2019.

%H J. Borger, <a href="https://arxiv.org/abs/1310.3013">Witt vectors, semirings, and total positivity</a>, arXiv:1310.3013 [math.CO], 2015.

%H A. Bouali, <a href="http://dx.doi.org/10.1016/j.bulsci.2005.08.002">Faber polynomials Cayley-Hamilton equation and Newton symmetric functions</a>, Bulletin des Sciences Mathématiques, Volume 130, Issue 1, Jan-Feb 2006, Pages 49-70.

%H L. Boya and K. Dixit, <a href="https://arxiv.org/abs/0808.1930">Geometry of density states</a>, arXiv:808.1930 [quant-phy], 2017.

%H M. Byrd and N. Khaneja, <a href="https://arxiv.org/abs/quant-ph/0302024">Characterization of the positivity of the density matrix in terms of the coherence vector representation </a>, arXiv:quant-phy/0302024, 2003.

%H S. Carrell, <a href="https://uwspace.uwaterloo.ca/bitstream/handle/10012/4770/uw-ethesis.pdf?sequence=1">Combinatorics of the KP Hierarchy</a>, Thesis, University of Waterloo, Ontario, Canada, 2009.

%H P. Cartier, <a href="http://preprints.ihes.fr/2006/M/M-06-40.pdf">A primer of Hopf algebras</a>, preprint, Institut des Hautes Etudes Scientifiques, France, 2006, pp. 56 and 57.

%H S. Chmutov, M. Kazarian, and S. Lando, <a href="https://arxiv.org/abs/1803.09800">Polynomial graph invariants and the KP hierarchy </a>, arXiv:1803.09800 [math.CO], p. 16-17, 2018.

%H Tom Copeland, <a href="http://tcjpn.wordpress.com/2011/04/11/lagrange-a-la-lah/">Lagrange a la Lah</a>, 2011; <a href="http://mathoverflow.net/questions/111165/riemann-zeta-function-at-positive-integers-and-an-appell-sequence-of-polynomials">Riemann zeta function at positive integers and an Appell sequence of polynomials</a>, 2012; <a href="http://tcjpn.wordpress.com/2015/11/21/the-creation-raising-operators-for-appell-sequences/">The creation / raising operators for Appell sequences</a>, 2015; <a href="http://tcjpn.wordpress.com/2015/12/21/generators-inversion-and-matrix-binomial-and-integral-transforms/">Generators, Inversion, and Matrix, Binomial, and Integral Transforms</a>, 2015; <a href="http://tcjpn.wordpress.com/2015/10/12/the-elliptic-lie-triad-kdv-and-ricattt-equations-infinigens-and-elliptic-genera/">Addendum to Elliptic Lie Triad</a>, 2015; <a href="https://tcjpn.wordpress.com/2018/01/23/formal-group-laws-and-binomial-sheffer-sequences/">Formal group laws and binomial Sheffer polynomials</a>, 2018; <a href="https://tcjpn.wordpress.com/2020/10/08/appells-and-roses-newton-leibniz-euler-riemann-and-symmetric-polynomials/">Appells and Roses: Newton, Leibniz, Euler, Riemann and Symmetric Polynomials</a>, 2020.

%H Mark Dominus <a href="http://blog.plover.com/math/fixpoints.html">Cycle classes of permutations</a> [From _Wouter Meeussen_, Jun 26 2009]

%H G. Duchamp, <a href="http://mathoverflow.net/questions/214927/important-formulas-in-combinatorics/215053#215053">Important formulas in combinatorics: The exponential formula</a>, a Mathoverflow answer, 2015.

%H H. Figueroa and J. Gracia-Bondia, <a href="https://arxiv.org/abs/hep-th/0408145">Combinatorial Hopf algebras in quantum field theory I</a>, arXiv:0408145 [hep-th], 2005, (pp. 40-41).

%H R. Friedrich and J. McKay, <a href="http://arxiv.org/abs/1204.6522">Formal groups, Witt vectors and free probability</a>, arXiv:1204.6522 [math.OA], 2012.

%H M. Hoffman, <a href="https://arxiv.org/abs/1602.03198">Harmonic-number summation identities, symmetric functions, and multiple zeta values</a>, arXiv:1602.03198 [math.NT], p. 2-3, 2016.

%H B. Konopelchenko, <a href="https://arxiv.org/abs/0802.3022">Quantum deformations of associative algebras and integrable systems</a>, arXiv:0802.3022 [nlin.SI], 2008.

%H Wolfdieter Lang, <a href="/A036039/a036039.pdf"> First ten rows and polynomials.</a>

%H D. Luest and D. Skliros, <a href="https://arxiv.org/abs/1912.01055">Handle Operators in String Theory</a>, arXiv:1912.01055 [hep-th], 2019.

%H Ma Luo, <a href="https://hdl.handle.net/10161/16809">Algebraic De Rham Theory for Completions of Fundamental Groups of Moduli Spaces of Elliptic Curves</a>, Ph.D. dissertation, Math Dept., Duke Univ., 2018.

%H Ma Luo, <a href="https://arxiv.org/abs/1804.06977">Algebraic De Rham Theory for Completions of Fundamental Groups of Moduli Spaces of Elliptic Curves</a>, arXiv:1804.06977 [math.NT], 2019.

%H MathOverflow, <a href="https://mathoverflow.net/questions/111770/cycling-through-the-zeta-garden-zeta-functions-for-graphs-cycle-index-polynomi">Cycling through the Zeta Garden: Zeta functions for graphs, cycle index polynomials, and determinants</a>, a question posed by Tom Copeland, 2012.

%H MathOverflow, <a href="https://mathoverflow.net/questions/345437/canonical-reference-for-chern-characteristic-classes">Canonical reference for Chern characteristic classes</a>, a question posed by Tom Copeland, 2019.

%H L. Maxim and J. Schuermann, <a href="http://arxiv.org/abs/1508.04356">Equivariant characteristic classes of external and symmetric products of varieties</a>, arXiv:1508.04356 [math.AG], 2015.

%H R. Szabo, <a href="http://arxiv.org/abs/1507.00685">N=2 gauge theories, instanton moduli spaces and geometric representation theory</a>, arXiv:1507.00685 [hep-th], 2015.

%H Andrei Vieru, <a href="https://arxiv.org/abs/1601.04703">Analytic renormalization of multiple zeta functions. Geometry and combinatorics of generalized Euler reflection formula for MZV</a>, arXiv preprint arXiv:1601.04703 [math.NT], 2016.

%F T(n,k) = n!/Product_{j=1..n} j^a(n,k,j)*a(n,k,j)!, with the k-th partition of n >= 1 in Abromowitz-Stegun order written as Product_{j=1..n} j^a(n,k,j) with nonnegative integers a(n,k,j) satisfying Sum_{j=1..n} j*a(n,k,j) = n, and the number of parts is Sum_{j=1..n} a(n,k,j) =: m(n,k). - _Wolfdieter Lang_, May 25 2019

%F Raising and lowering operators are given for the partition polynomials formed from this sequence in the link in "Lagrange a la Lah Part I" on p. 23. - _Tom Copeland_, Sep 18 2011

%F From Szabo p. 34, with b_n = q^n / (1-q^n)^2, the partition polynomials give an expansion of the MacMahon function M(q) = Product_{n>=1} 1/(1-q^n)^n = Sum_{n>=0} PL(n) q^n, the generating function for PL(n) = n! P_n(b_1,...,b_n), the number of plane partitions with sum n. - _Tom Copeland_, Nov 11 2015

%F From _Tom Copeland_, Nov 18 2015: (Start)

%F The partition polynomials of A036040 are obtained by substituting x[n]/(n-1)! for x[n] in the partition polynomials of this entry.

%F CIP_n(t-F(1,b1),-F(2,b1,b2),...,-F(n,b1,...,bn)) = P_n(b1,...,bn;t), where CIP_n are the partition polynomials of this entry; F(n,...), those of A263916; and P_n, those defined in my formula in A094587, e.g., P_2(b1,b2;t) = 2 b2 + 2 b1 t + t^2.

%F CIP_n(-F(1,b1),-F(2,b1,b2),...,-F(n,b1,...,bn)) = n! bn. (End)

%F From the relation to the elementary Schur polynomials given in A130561 and above, the partition polynomials of this array satisfy (d/d(x_m)) P(n,x_1,...,x_n) = (1/m) * (n!/(n-m)!) * P(n-m,x_1,...,x_(n-m)) with P(k,...) = 0 for k<0. - _Tom Copeland_, Sep 07 2016

%F Regarded as Appell polynomials in the indeterminate x(1)=u, the partition polynomials of this entry P_n(u) obey d/du P_n(u) = n * P_{n-1}(u), so the abscissas for the zeros of P_n(u) are the same as those of the extrema of P{n+1}(u). In addition, the coefficient of u^{n-1} in P_{n}(u) is zero since these polynomials are related to the characteristic polynomials of matrices with null main diagonals, and, therefore, the trace is zero, further implying the abscissa for any zero is the negative of the sum of the abscissas of the remaining zeros. This assumes all zeros are distinct and real. - _Tom Copeland_, Nov 10 2019

%e The partition array T(n, k) begins (see the W. Lang link for rows 1..10):

%e n\k 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 ...

%e 1: 1

%e 2: 1 1

%e 3: 2 3 1

%e 4 6 8 3 6 1

%e 5 24 30 20 20 15 10 1

%e 6 120 144 90 40 90 120 15 40 45 15 1

%e 7 720 840 504 420 504 630 280 210 210 420 105 70 105 21 1

%e ... reformatted by _Wolfdieter Lang_, May 25 2019

%p nmax:=7: with(combinat): for n from 1 to nmax do P(n):=sort(partition(n)): for r from 1 to numbpart(n) do B(r):=P(n)[r] od: for m from 1 to numbpart(n) do s:=0: j:=0: while s<n do j:=j+1: s:=s+B(m)[j]: x(j):=B(m)[j]: end do; jmax:=j; for r from 1 to n do q(r):=0 od: for r from 1 to n do for j from 1 to jmax do if x(j)=r then q(r):=q(r)+1 fi: od: od: A036039(n, m) := n!/ (mul((t)^q(t)*q(t)!, t=1..n)); od: od: seq(seq(A036039(n, m), m=1..numbpart(n)), n=1..nmax); # _Johannes W. Meijer_, Jul 14 2016

%p # 2nd program:

%p A036039 := proc(n,k)

%p local a,prts,e,ai ;

%p a := n! ;

%p # ASPrts is implemented in A119441

%p prts := ASPrts(n)[k] ;

%p ai := 1;

%p for e from 1 to nops(prts) do

%p if e>1 then

%p if op(e,prts) = op(e-1,prts) then

%p ai := ai+1 ;

%p else

%p ai := 1;

%p end if;

%p end if;

%p a := a/(op(e,prts)*ai) ;

%p end do:

%p a ;

%p end proc:

%p seq(seq(A036039(n,k),k=1..combinat[numbpart](n)),n=1..15) ; # _R. J. Mathar_, Dec 18 2016

%t aspartitions[n_]:=Reverse/@Sort[Sort/@IntegerPartitions[n]];(* Abramowitz & Stegun ordering *);

%t ascycleclasses[n_Integer]:=n!/(Times@@ #)&/@((#!

%t Range[n]^#)&/@Function[par,Count[par,# ]&/@Range[n]]/@aspartitions[n])

%t (* The function "ascycleclasses" is then identical with A&S multinomial M2. *)

%t Table[ascycleclasses[n], {n, 1, 8}] // Flatten

%t (* _Wouter Meeussen_, Jun 26 2009, Jun 27 2009 *)

%o (Sage)

%o def PartAS(n):

%o P = []

%o for k in (1..n):

%o Q = [p.to_list() for p in Partitions(n, length=k)]

%o for q in Q: q.reverse()

%o P = P + sorted(Q)

%o return P

%o def A036039_row(n):

%o fn, C = factorial(n), []

%o for q in PartAS(n):

%o q.reverse()

%o p = Partition(q)

%o fp = 1; pf = 1

%o for a, c in p.to_exp_dict().items():

%o fp *= factorial(c)

%o pf *= factorial(a)**c

%o co = fn//(fp*pf)

%o C.append(co*prod([factorial(i-1) for i in p]))

%o return C

%o for n in (1..10):

%o print(A036039_row(n)) # _Peter Luschny_, Dec 18 2016

%Y Cf. A036036, A036037, A036038, A036040.

%Y Cf. other versions based on different partition orderings: A102189 (rows reversed), A181897, A319192.

%Y Cf. A094587, A115131, A130561, A263634, A263916.

%Y Cf. A133932.

%Y Cf. A231846.

%Y Cf. A127671.

%K nonn,easy,nice,tabf,look,hear

%O 1,4

%A _N. J. A. Sloane_

%E More terms from _David W. Wilson_

%E Title expanded by _Tom Copeland_, Oct 15 2020