

A036040


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


89



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, 1, 1, 7, 21, 35, 21, 105, 70, 105, 35, 210, 105, 35, 105, 21, 1, 1, 8, 28, 56, 35, 28, 168, 280, 210, 280, 56, 420, 280, 840, 105, 70, 560, 420, 56, 210, 28, 1, 1, 9, 36, 84, 126, 36, 252
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,5


COMMENTS

This is different from A080575 and A178867.
T(n,m) = count of set partitions of n with block lengths given by the mth partition of n.
From Tilman Neumann, Oct 05 2008: (Start)
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.
Though the Bell polynomials seem quite unwieldy, they can be computed easily as the determinant of an ndimensional square matrix. (See, e.g., [Coffey] and program below.)
The complete Bell polynomial of the first n primes gives A007446.
(End)
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".
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".  Tom Copeland, Apr 29 2011


REFERENCES

Abramowitz and Stegun, Handbook, p. 831, column labeled "M_3".
C. Itzykson and J. Drouffe, Statistical Field Theory Vol. 2, Cambridge Univ. Press, 1989, page 412.
S. Ma, Statistical Mechanics, World Scientific, 1985, page 205.


LINKS

T. D. Noe, Rows n=1..25 of triangle, flattened
M. Abramowitz and I. A. Stegun, eds., Handbook of Mathematical Functions, National Bureau of Standards, Applied Math. Series 55, Tenth Printing, 1972 [alternative scanned copy].
F. Brglez, Of ndimensional Dice, Combinatorial Optimization, and Reproducible Research: An Introduction, Elektrotehniski Vestnik, 78(4): 181192, 2011.
Mark W. Coffey, A Set of Identities for a Class of Alternating Binomial Sums Arising in Computing Applications, arXiv:mathph/0608049, 2006.
T. Copeland, The creation / raising operators for Appell sequences
T. Copeland, Generators, Inversion, and Matrix, Binomial, and Integral Transforms
T. Copeland, Lagrange a la Lah
Wolfdieter Lang, First 10 rows and polynomials
Wikipedia, Bell polynomials


FORMULA

E.g.f.: A(t) = exp(Sum_{k>=1}x[k]*(t^k)/k!).
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 mth partition of n, counted in AbramowitzStegun(ASt) 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.
a(n, m) = n!/product((j!^e(m,j))*e(m,j)!,j=1..n ), with [1^e(m,1),2^e(m,2), ...,n^e(m, n)] the mth partition of n in the mentioned ASt order.
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,1,...) 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(n1,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)^(j1) (j1)! for j>1, S(n,x(1)) = [x(1)1]^n + n [x(1)1]^(n1).  Tom Copeland, Aug 01 2008
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
The nth row is generated by the determinant of [sum(k=0,..,n1 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
The partition polynomials of A036039 are obtained by substituting (n1)! x[n] for x[n] in the partition polynomials of this entry.  Tom Copeland, Nov 17 2015
(n1)! 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.  Tom Copeland, Nov 29 2015


EXAMPLE

1
1 1
1 3 1
1 4 3 6 1
1 5 10 10 15 10 1


MAPLE

with(combinat): nmax:=8: T:=0: for n from 1 to nmax do y(n):=numbpart(n): P(n):=sort(partition(n)): for r from 1 to y(n) do B(r):=P(n)[r] od: for k from 1 to y(n) do s:=0: j:=0: while s<n do j:=j+1: s:=s+B(k)[j]: x(j):=B(k)[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: M3[n, k]:= n!/(mul((t!)^q(t)*q(t)!, t=1..n)); od: for k from 1 to y(n) do T:= T+1: A036040(T):= M3[n, k]: od: od: seq(A036040(n), n=1..T); # Johannes W. Meijer, Jun 21 2010


MATHEMATICA

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}]


PROG

(MuPAD)
completeBellMatrix := proc(x, n) // x  vector x[1]...x[m], m>=n
local i, j, M; begin
M := matrix(n, n): // zeroinitialized
for i from 1 to n1 do M[i, i+1] := 1: end_for:
for i from 1 to n do for j from 1 to i do
M[i, j] := binomial(i1, j1)*x[ij+1]: end_for: end_for:
return (M): end_proc:
completeBellPoly := proc(x, n) begin
return (linalg::det(completeBellMatrix (x, n))): end_proc:
for i from 1 to 10 do print(i, completeBellPoly(x, i)): end_for:
// Tilman Neumann, Oct 05 2008
(PARI) A036040_poly(n, V=vector(n, i, eval(Str('x, i))))={matdet(matrix(n, n, i, j, if(j<=i, binomial(i1, j1)*V[ni+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
(Sage)
def A036040_row(n):
fn, C = factorial(n), []
for k in (0..n):
for p in Partitions(n, length=k):
factorial_product = 1
power_factorial_product = 1
for part, count in p.to_exp_dict().iteritems():
factorial_product *= factorial(count)
power_factorial_product *= factorial(part)**count
C.append(fn//(factorial_product*power_factorial_product))
return C
[A036040_row(n) for n in (1..8)] # Peter Luschny, Jan 02 2016


CROSSREFS

See A080575 for another version. Cf. A036036A036039.
Row sums are the Bell numbers A000110.
Cf. A000040, A007446.
Cf. A178866 and A178867 (version 3).
Cf. A263916.
Sequence in context: A126015 A247169 A144336 * A080575 A205117 A077228
Adjacent sequences: A036037 A036038 A036039 * A036041 A036042 A036043


KEYWORD

nonn,easy,nice,tabf,look,changed


AUTHOR

N. J. A. Sloane


EXTENSIONS

More terms from David W. Wilson
Additional comments from Wouter Meeussen, Mar 23 2003


STATUS

approved



