cp's OEIS Frontend

A036040 Irregular triangle of multinomial coefficients, read by rows (version 1).

%I A036040 #239 Dec 31 2024 06:33:03
%S A036040 1,1,1,1,3,1,1,4,3,6,1,1,5,10,10,15,10,1,1,6,15,10,15,60,15,20,45,15,
%T A036040 1,1,7,21,35,21,105,70,105,35,210,105,35,105,21,1,1,8,28,56,35,28,168,
%U A036040 280,210,280,56,420,280,840,105,70,560,420,56,210,28,1,1,9,36,84,126,36,252
%N A036040 Irregular triangle of multinomial coefficients, read by rows (version 1).
%C A036040 This is different from A080575 and A178867.
%C A036040 T(n,m) = count of set partitions of n with block lengths given by the m-th partition of n.
%C A036040 From _Tilman Neumann_, Oct 05 2008: (Start)
%C A036040 These are also the coefficients occurring in complete Bell polynomials, Faa di Bruno's formula (in its simplest form) and computation of moments from cumulants.
%C A036040 Though the Bell polynomials seem quite unwieldy, they can be computed easily as the determinant of an n-dimensional square matrix. (See, e.g., Coffey (2006) and program below.)
%C A036040 The complete Bell polynomial of the first n primes gives A007446. (End)
%C A036040 From _Tom Copeland_, Apr 29 2011: (Start)
%C A036040 A relation between partition polynomials formed from these "refined" Stirling numbers of the second kind and umbral operator trees and Lagrange inversion is presented in the link "Lagrange a la Lah".
%C A036040 For simple diagrams of the relation between connected graphs, cumulants, and A036040, see the references on statistical physics below. In some sense, these graphs are duals of the umbral bouquets presented in "Lagrange a la Lah". (End)
%C A036040 These M3 (Abramowitz-Stegun) partition polynomials are the complete Bell polynomials (see a comment above) with recurrence (see the Wikipedia link) B_0 = 1, B_n = Sum_{k=0..n-1} binomial(n-1,k) * B_{n-1-k}*x[k+1], n >= 1. - _Wolfdieter Lang_, Aug 31 2016
%C A036040 With the indeterminates (x_1, x_2, x_3,...) = (t, -c_2*t, -c_3*t, ...) with c_n > 0, umbrally B(n,a.) =  B(n,t)|_{t^n = a_n} = 0 and B(j,a.)B(k,a.) = B(j,t)B(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 A134685. - _Tom Copeland_, Feb 09 2018
%C A036040 For applications to functionals in quantum field theory, see Figueroa et al., Brouder, Kreimer and Yeats, and Balduf. In the last two papers, the Bell polynomials with the indeterminates (x_1, x_2, x_3,...) = (c_1, 2!c_2, 3!c_3, ...) are equivalent to the partition polynomials of A130561 in the indeterminates c_n. - _Tom Copeland_, Dec 17 2019
%C A036040 From _Tom Copeland_, Oct 15 2020: (Start)
%C A036040 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 A036040 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 A036040 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 A036040 C) logarithmic generating function (l.g.f): f(x) = 1 - log(1 - c.x) = 1 + Sum_{n > 0}  c_n * x^n /n.
%C A036040 Expansions of log(f(x)) are given in
%C A036040 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 A036040 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 A036040 Expansions of exp(f(x)-1) are given in
%C A036040 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 A036040 IV) A130561 for an o.g.f.: exp[ b.x/(1-b.x) ] = e^{LAH.(b.,...)x}, the Lah partition polynomials
%C A036040 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 A036040 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 below. (End)
%C A036040 From _Tom Copeland_, Jun 12 2021: (Start)
%C A036040 These Bell polynomials and their relations to the Faa di Bruno Hopf bialgebra, correlation functions in quantum field theory, and the moment-cumulant duality are given on pp. 134 -144 of Zeidler.
%C A036040 An interpretation of the coefficients of the polynomials is given in expositions of the exponential formula, or principle, in Cameron et al., Duchamp, Duchamp et al., Labelle and Leroux, and Scott and Sokal along with some history. The simplest applications of this principle are given in A060540. (End)
%D A036040 Abramowitz and Stegun, Handbook, p. 831, column labeled "M_3".
%D A036040 C. Itzykson and J. Drouffe, Statistical Field Theory Vol. 2, Cambridge Univ. Press, 1989, page 412.
%D A036040 S. Ma, Statistical Mechanics, World Scientific, 1985, page 205.
%D A036040 E. Zeidler, Quantum Field Theory II: Quantum Electrodynamics, Springer, 2009.
%H A036040 David W. Wilson, <a href="/A036040/b036040.txt">Table of n, a(n) for n = 1..11731</a> (rows 1 through 26).
%H A036040 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 A036040 P. Balduf, <a href="http://www2.mathematik.hu-berlin.de/~kreimer/wp-content/uploads/PaulMaster">The propagator and diffeomorphisms of an interacting field theory</a>, Master's thesis, submitted to the Institut für Physik, Mathematisch-Naturwissenschaftliche Fakultät, Humboldt-Universtität, Berlin, 2018.
%H A036040 F. Brglez, <a href="http://ev.fe.uni-lj.si/4-2011/Brglez.pdf">Of n-dimensional Dice, Combinatorial Optimization, and Reproducible Research: An Introduction</a>, Elektrotehniski Vestnik, 78(4): 181-192, 2011.
%H A036040 P. Cameron, C. Krattenthaler, and T. Muller, <a href="https://arxiv.org/abs/0911.3760">Decomposable functors and the exponential principle, ll</a>, arXiv:0911.3760 [math.CO], 2011.
%H A036040 Mark W. Coffey, <a href="http://arxiv.org/abs/math-ph/0608049">A Set of Identities for a Class of Alternating Binomial Sums Arising in Computing Applications</a>, arXiv:math-ph/0608049, 2006.
%H A036040 Tom Copeland, <a href="http://tcjpn.wordpress.com/2011/04/11/lagrange-a-la-lah/">Lagrange a la Lah</a>, Nov 11, 2011.
%H A036040 Tom Copeland, <a href="http://tcjpn.wordpress.com/2015/11/21/the-creation-raising-operators-for-appell-sequences/">The creation / raising operators for Appell sequences</a>, Nov 21, 2015.
%H A036040 Tom Copeland, <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>, Dec 21, 2015.
%H A036040 Tom Copeland, <a href="https://tcjpn.wordpress.com/2018/01/23/formal-group-laws-and-binomial-sheffer-sequences/">Formal group laws and binomial Sheffer sequences</a>, 2018.
%H A036040 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 A036040 G. Duchamp, S. Goodenough, K. Penson, and L. Poinsot, <a href="https://arxiv.org/abs/0910.0695">Statistics on graphs, exponential formula, and combinatorial physics</a>, arXiv:0910.0695 [cs.DM], 2010.
%H A036040 K. Ebrahimi-Fard and F. Patras, <a href="http://arxiv.org/abs/1409.5664">Cumulants, free cumulants and half-shuffles</a>, arXiv:1409.5664v2 [math.CO], 2015, p. 16. [_Tom Copeland_, Feb 29 2016]
%H A036040 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, (p. 41).
%H A036040 P. Guha, <a href="http://webdoc.sub.gwdg.de/ebook/serien/e/MPI_Math_Nat/preprint2006_143.pdf">Riccati Chain, Higher Order Painlevé Type Equations and Stabilizer Set of Virasoro Orbit</a>, 2006.
%H A036040 D. Kreimer and K. Yeats, <a href="http://arxiv.org/abs/1610.01837">Diffeomorphisms of quantum fields</a>, arXiv:1610.01837 [math-ph], 2016. [_Tom Copeland_, Nov 23 2016]
%H A036040 G. Labelle and P. Leroux, <a href="https://doi.org/10.37236/1270">An extension of the exponential formula in enumerative combinatorics </a>, The Electron. J. Comb., Vol. 3, Issue 2, 1996.
%H A036040 Wolfdieter Lang, <a href="/A036040/a036040.pdf">First 10 rows and polynomials</a>
%H A036040 J. Novak and M. LaCroix, <a href="https://arxiv.org/abs/1205.2097">Three lectures on free probability</a>, arXiv:1205.2097 [math.CO], 2012.
%H A036040 A. Scott and A. Sokal, <a href="https://arxiv.org/abs/0803.1477">Some variants of the exponential formula with applications to the multivariate Tutte polynomials (alias Potts model)</a>, arXiv:0803.1477 [math.CO], 2009.
%H A036040 J. Taylor, <a href="https://digital.lib.washington.edu/researchworks/handle/1773/36757">Formal group laws and hypergraph colorings</a>, doctoral thesis, Univ. of Wash., 2016, p. 95. [_Tom Copeland_, Dec 20 2018]
%H A036040 Wikipedia, <a href="http://en.wikipedia.org/wiki/Bell_polynomials">Bell polynomials</a>
%F A036040 E.g.f.: A(t) = exp(Sum_{k>=1} x[k]*(t^k)/k!).
%F A036040 T(n,m) is the coefficient of ((t^n)/n!)* x[1]^e(m,1)*x[2]^e(m,2)*...*x[n]^e(m,n) in A(t). Here the m-th partition of n, counted in Abramowitz-Stegun(A-St) order, is [1^e(m,1), 2^e(m,2), ..., n^e(m,n)] with e(m,j) >= 0 and if e(m, j)=0 then j^0 is not recorded.
%F A036040 a(n, m) = n!/Product_{j=1..n} j!^e(m,j)*e(m,j)!, with [1^e(m,1), 2^e(m,2), ..., n^e(m, n)] the m-th partition of n in the mentioned A-St order.
%F A036040 With the notation in the Lang reference, x(1) treated as a variable and D the derivative w.r.t. x(1), a raising operator for the polynomial S(n,x(1)) = P3_n(x[1], ..., x[n]) is R = Sum_{n>=0} x(n+1) D^n / n! ; i.e., R S(n, x(1)) = S(n+1, x(1)). The lowering operator is D; i.e., D S(n, x(1)) = n S(n-1, x(1)). The sequence of polynomials is an Appell sequence, so [S(.,x(1)) + y]^n = S(n, x(1) + y). For x(j) = (-1)^(j-1)* (j-1)! for j > 1, S(n, x(1)) = [x(1) - 1]^n + n [x(1) - 1]^(n-1). - _Tom Copeland_, Aug 01 2008
%F A036040 Raising and lowering operators are given for the partition polynomials formed from A036040 in the link in "Lagrange a la Lah Part I" on page 22. - _Tom Copeland_, Sep 18 2011
%F A036040 The n-th row is generated by the determinant of [Sum_{k=0..n-1} (x_(k+1)*(dP_n)^k/k!) - S_n], where dP_n is the n X n submatrix of A132440 and S_n is the n X n submatrix of A129185. The coefficients are flagged by the partitions of n represented by the monomials in the indeterminates x_k. Letting all x_n = t, generates the Bell / Touchard / exponential polynomials of A008277. - _Tom Copeland_, May 03 2014
%F A036040 The partition polynomials of A036039 are obtained by substituting (n-1)! x[n] for x[n] in the partition polynomials of this entry. - _Tom Copeland_, Nov 17 2015
%F A036040 -(n-1)! F(n, B(1, x[1]), B(2, x[1], x[2])/2!, ..., B(n, x[1], ..., x[n])/n!) = x[n] extracts the indeterminates of the complete Bell partition polynomials B(n, x[1], ..., x[n]) of this entry, where F(n, x[1], ..., x[n]) are the Faber polynomials of A263916. (Compare with A263634.) - _Tom Copeland_, Nov 29 2015; Sep 09 2016
%F A036040 T(n, m) = A127671(n, m)/A264753(n, m), n >= 1 and 1 <= m <= A000041(n). - _Johannes W. Meijer_, Jul 12 2016
%F A036040 From _Tom Copeland_, Sep 07 2016: (Start)
%F A036040 From the connections among the elementary Schur polynomials and the partition polynomials of A130561, A036039 and this array, the partition polynomials of this array satisfy (d/d(x_m)) P(n, x_1, ..., x_n) = binomial(n,m) * P(n-m, x_1, ..., x_(n-m)) with P(k, x_1, ..., x_n) = 0 for k < 0.
%F A036040 Just as in the discussion and example in A130561, the umbral compositional inverse sequence is given by the sequence P(n, x_1, -x_2, -x_3, ..., -x_n).
%F A036040 (End)
%F A036040 The partition polynomials with an index shift can be generated by (v(x) + d/dx)^n v(x). Cf. Guha, p. 12. - _Tom Copeland_, Jul 19 2018
%e A036040 Triangle begins:
%e A036040   1;
%e A036040   1,  1;
%e A036040   1,  3,  1;
%e A036040   1,  4,  3,  6,  1;
%e A036040   1,  5, 10, 10, 15, 10,  1;
%e A036040   1,  6, 15, 10, 15, 60, 15, 20, 45, 15, 1;
%e A036040   ...
%e A036040 The first partition of 3 (i.e., (3)) induces the set {{1, 2, 3}}, so T(3, 1) = 1; the second one (i.e., (2, 1)) the sets {{1, 2}, {3}}, {{1, 3}, {2}}, and {{2, 3}, {1}}, so T(3, 2) = 3; and the third one (i.e., (1, 1, 1)) the set {{1}, {2}, {3}}, so T(3, 1) = 1. - _Lorenzo Sauras Altuzarra_, Jun 20 2022
%p A036040 with(combinat): nmax:=8: 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: A036040(n,m):= n!/(mul((t!)^q(t)*q(t)!,t=1..n)); od: od: seq(seq(A036040(n, m), m=1..numbpart(n)), n=1..nmax); # _Johannes W. Meijer_, Jun 21 2010, Jul 12 2016
%t A036040 runs[li:{__Integer}] := ((Length/@ Split[ # ]))&[Sort@ li]; Table[temp=Map[Reverse, Sort@ (Sort/@ IntegerPartitions[w]), {1}]; Apply[Multinomial, temp, {1}]/Apply[Times, (runs/@ temp)!, {1}], {w, 6}]
%o A036040 (MuPAD)
%o A036040 completeBellMatrix := proc(x,n) // x - vector x[1]...x[m], m>=n
%o A036040 local i,j,M; begin
%o A036040 M := matrix(n,n): // zero-initialized
%o A036040 for i from 1 to n-1 do M[i,i+1] := -1: end_for:
%o A036040 for i from 1 to n do for j from 1 to i do
%o A036040     M[i,j] := binomial(i-1,j-1)*x[i-j+1]: end_for: end_for:
%o A036040 return (M): end_proc:
%o A036040 completeBellPoly := proc(x, n) begin
%o A036040 return (linalg::det(completeBellMatrix (x,n))): end_proc:
%o A036040 for i from 1 to 10 do print(i, completeBellPoly(x,i)): end_for:
%o A036040 // _Tilman Neumann_, Oct 05 2008
%o A036040 (PARI) A036040_poly(n,V=vector(n,i,eval(Str('x,i))))={matdet(matrix(n,n,i,j,if(j<=i,binomial(i-1,j-1)*V[n-i+j],-(j==i+1))))} \\ Row n of the sequence is made of the coefficients of the monomials ordered by increasing total order (sum of powers) and then lexicographically. - _M. F. Hasler_, Nov 16 2013, updated Jul 12 2014
%o A036040 (Sage) from collections import Counter
%o A036040 def ASPartitions(n, k):
%o A036040     Q = [p.to_list() for p in Partitions(n, length=k)]
%o A036040     for q in Q: q.reverse()
%o A036040     return sorted(Q)
%o A036040 def A036040_row(n):
%o A036040     h = lambda p: product(map(factorial, Counter(p).values()))
%o A036040     return [multinomial(p)//h(p) for k in (0..n) for p in ASPartitions(n, k)]
%o A036040 for n in (1..10): print(A036040_row(n))
%o A036040 # _Peter Luschny_, Dec 18 2016, corrected Apr 30 2022
%Y A036040 See A080575 for another version.
%Y A036040 Row sums are the Bell numbers A000110.
%Y A036040 Cf. A036036, A036037, A036038, A036039.
%Y A036040 Cf. A000040, A007446, A178866 and A178867 (version 3).
%Y A036040 Cf. A130561, A263634, A263916, A134685.
%Y A036040 Cf. A127671.
%Y A036040 Cf. A060540 for the coefficients of the compositions e^{ x^m/m! }.
%K A036040 nonn,easy,nice,tabf,look,hear
%O A036040 1,5
%A A036040 _N. J. A. Sloane_
%E A036040 More terms from _David W. Wilson_
%E A036040 Additional comments from _Wouter Meeussen_, Mar 23 2003