|
| |
|
|
A080575
|
|
Triangle of multinomial coefficients, read by rows (version 2).
|
|
20
|
|
|
|
1, 1, 1, 1, 3, 1, 1, 4, 3, 6, 1, 1, 5, 10, 10, 15, 10, 1, 1, 6, 15, 15, 10, 60, 20, 15, 45, 15, 1, 1, 7, 21, 21, 35, 105, 35, 70, 105, 210, 35, 105, 105, 21, 1, 1, 8, 28, 28, 56, 168, 56, 35, 280, 210, 420, 70, 280, 280, 840, 560, 56, 105, 420, 210, 28, 1, 1, 9, 36, 36, 84, 252, 84, 126, 504, 378, 756, 126, 315, 1260, 1260, 1890, 1260, 126, 280, 2520, 840, 1260, 3780, 1260, 84, 945, 1260, 378, 36, 1, 1, 10, 45, 45, 120, 360, 120, 210, 840, 630, 1260, 210
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
1,5
|
|
|
COMMENTS
|
T[n,m] = count of set partitions of n with block lengths given by the m-th partition of n in the canonical ordering.
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 n-dimensional square matrix. (see e.g. [Coffey] and program below)
The complete Bell polynomial of the first n primes gives A007446. (End)
The difference with A036040 and A178867 lies in the ordering of the monomials. This sequence uses lexicographic ordering, while in A036040 the total order (power) of the monomials prevails (Abramowitz-Stegun style): e.g., in row 6 we have ...+ 15*x[3]*x[5] + 15*x[3]*x[6]^2 + 10*x[4]^2 +...; in A036040 the coefficient of x[3]*x[6]^2 would come after that of x[4]^2 because the total order is higher, here it comes before in view of the lexicographic order. - M. F. Hasler, Jul 12 2015
|
|
|
REFERENCES
|
See A036040 for the column labeled "M_3" in Abramowitz and Stegun, Handbook, p. 831.
|
|
|
LINKS
|
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].
|
|
|
EXAMPLE
|
For n=4 the 5 integer partitions in canonical ordering with corresponding set partitions and counts are:
[4] -> #{1234} = 1
[3,1] -> #{123/4, 124/3, 134/2, 1/234} = 4
[2,2] -> #{12/34, 13/24, 14/23} = 3
[2,1,1] -> #{12/3/4, 13/2/4, 1/23/4, 14/2/3, 1/24/3, 1/2/34} = 6
[1,1,1,1] -> #{1/2/3/4} = 1
Thus row 4 is [1, 4, 3, 6, 1].
Triangle begins:
1;
1, 1;
1, 3, 1;
1, 4, 3, 6, 1;
1, 5, 10, 10, 15, 10, 1;
1, 6, 15, 15, 10, 60, 20, 15, 45, 15, 1;
1, 7, 21, 21, 35, 105, 35, 70, 105, 210, 35, 105, 105, 21, 1;
...
Row 4 represents 1*k(4)+4*k(3)*k(1)+3*k(2)^2+6*k(2)*k(1)^2+1*k(1)^4 and T(4,4)=6 since there are six ways of partitioning four labeled items into one part with two items and two parts each with one item.
|
|
|
MATHEMATICA
|
runs[li:{__Integer}] := ((Length/@ Split[ # ]))&[Sort@ li]; Table[Apply[Multinomial, IntegerPartitions[w], {1}]/Apply[Times, (runs/@ IntegerPartitions[w])!, {1}], {w, 6}]
(* Second program: *)
completeBellMatrix[x_, n_] := Module[{M, i, j}, M[_, _] = 0; For[i=1, i <= n-1 , i++, M[i, i+1] = -1]; For[i=1, i <= n , i++, For[j=1, j <= i, j++, M[i, j] = Binomial[i-1, j-1]*x[i-j+1]]]; Array[M, {n, n}]]; completeBellPoly[x_, n_] := Det[completeBellMatrix[x, n]]; row[n_] := List @@ completeBellPoly[x, n] /. x[_] -> 1 // Reverse; Table[row[n], {n, 1, 10}] // Flatten (* Jean-François Alcover, Aug 31 2016, after Tilman Neumann *)
B[0] = 1;
B[n_] := B[n] = Sum[Binomial[n-1, k] B[n-k-1] x[k+1], {k, 0, n-1}]//Expand;
row[n_] := Reverse[List @@ B[n] /. x[_] -> 1];
|
|
|
PROG
|
(MuPAD)
completeBellMatrix := proc(x, n) // x - vector x[1]...x[m], m>=n
local i, j, M; begin M:=matrix(n, n): // zero-initialized
for i from 1 to n-1 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(i-1, j-1)*x[i-j+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: (End)
(PARI) See links.
A080575_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))))}
A080575_row(n)={(f(s)=if(type(s)!="t_INT", concat(apply(f, select(t->t, Vec(s)))), s))(A080575_poly(n))} \\ (End)
|
|
|
CROSSREFS
|
Maximum value in row n gives A102356(n).
|
|
|
KEYWORD
|
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
