login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A178867 Irregular triangle read by rows: multinomial coefficients, version 3; alternatively, row n gives coefficients of n-th exponential Bell polynomial B_n(x_1, x_2, ...) with monomials sorted into standard order. 10
1, 1, 1, 1, 3, 1, 1, 6, 4, 3, 1, 1, 10, 10, 15, 5, 10, 1, 1, 15, 20, 45, 15, 60, 6, 15, 15, 10, 1, 1, 21, 35, 105, 35, 210, 21, 105, 105, 70, 7, 105, 35, 21, 1, 1, 28, 56, 210, 70, 560, 56, 420, 420, 280, 28, 840, 280, 168, 8, 280, 210, 105, 56, 35, 28, 1 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,5

COMMENTS

"Exponential" here means in contrast to "ordinary", cf. A263633 (see Comtet). "Standard order" means as produced by Maple's "sort" command. - N. J. A. Sloane, Oct 28 2015

This version of the multinomial coefficients was discovered while calculating the probability that two 23 year old chessplayers would play each other on their birthday during a Dutch Chess Championship. This unique encounter took place on Apr 05 2008. Its probability is 1 in 50000 years, see the Meijer-Nepveu article.

The third version of the multinomial coefficients can be constructed with the basic multinomial coefficients A178866, see the formulas below. These multinomial coefficients appear in the columns of the multinomial coefficient matrix MCM[n,m] (n>=1 and m>=1).

We observe that the sum of the C(m,n) coefficients follow the A000296(n) sequence. The missing C(m,n=1) corresponds to A000296(1)=0.

The number of multinomial coefficients in a triangle row lead to the partition numbers A000041. The row sums lead to the Bell numbers A000110.

REFERENCES

L. Comtet, Advanced Combinatorics, Reidel, 1974, pp. 134, 307-310.

J. Riordan, An Introduction to Combinatorial Analysis, Wiley, 1958, Chapter 2, Section 8 and table on page 49..

LINKS

Table of n, a(n) for n=1..66.

Kevin Brown, Generalized Birthday Problem (N Items in M Bins), 1994-2010.

J. W. Meijer and M. Nepveu, Euler's ship on the Pentagonal Sea, Acta Nova, Volume 4, No.1, December 2008. pp. 176-187.

FORMULA

G.f.: Exp (Sum_{i >= 1} x_i*t^i/i!) = 1 + Sum_{n >= 1} B_n(x_1, x_2,...)*t^n/n!. [Comtet, p. 134, Eq. [3b]. - N. J. A. Sloane, Oct 28 2015

The formulas for the first few matrix columns are (m>=1):

MCM[1,m] = A178866(1)*C(m,0) = 1*C(m,0);

MCM[2,m] = A178866(2)*C(m,2) = 1*C(m,2);

MCM[3,m] = A178866(3)*C(m,3) = 1*C(m,3);

MCM[4,m] = A178866(4)*C(m,4) = 3*C(m,4) and

MCM[5,m] = A178866(5)*C(m,4) = 1*C(m,4);

MCM[6,m] = A178866(6)*C(m,5) = 10*C(m,5) and

MCM[7,m] = A178866(7)*C(m,5) = 1*C(m,5);

MCM[8,m] = A178866(8)*C(m,6) = 15*C(m,6) and

MCM[9,m] = A178866(9)*C(m,6) = 15*C(m,6) and

MCM[10,m] = A178866(10)*C(m,6) = 10*C(m,6) and

MCM[11,m] = A178866(11)*C(m,6) = 1*C(m,6).

EXAMPLE

The first few exponential Bell polynomials are:

1, x[1]

2, x[1]^2+x[2]

3, x[1]^3+3*x[1]*x[2]+x[3]

4, x[1]^4+6*x[1]^2*x[2]+4*x[1]*x[3]+3*x[2]^2+x[4]

5, x[1]^5+10*x[1]^3*x[2]+10*x[1]^2*x[3]+15*x[1]*x[2]^2+5*x[1]*x[4]+10*x[2]*x[3]+x[5]

6, x[1]^6+15*x[1]^4*x[2]+20*x[1]^3*x[3]+45*x[1]^2*x[2]^2+15*x[1]^2*x[4]+60*x[1]*x[2]*x[3]+6*x[1]*x[5]+15*x[2]^3+15*x[2]*x[4]+10*x[3]^2+x[6]

...

The first few triangle rows:

1;

1, 1;

1, 3, 1;

1, 6, 4, 3, 1;

1, 10, 10, 15, 5, 10, 1;

...

MAPLE

with(combinat): nmax:=11; A178866(1):=1: T:=1: for n from 1 to nmax do y(n):=numbpart(n): P(n):=sort(partition(n)): k:=0: for r from 1 to y(n) do if P(n)[r, 1]>1 then k:=k+1; B(k):=P(n)[r]: fi; od: A002865(n):=k; for k from 1 to A002865(n) do s:=0: j:=1: while s<n do s:=s+B(k)[j]: x(j+1):=B(k)[j]: j:=j+1; end do; jmax:=j; for r from 1 to n do q(r):=0 od: for r from 2 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!/(product((t!)^q(t)*q(t)!, t=1..n)): od: a:=sort([seq(M3[n, k], k=1..A002865(n))], `>`): for k from 1 to A002865(n) do M3[n, k]:=a[k] od: for k from 1 to A002865(n) do T:=T+1: A178866(T):= M3[n, k]: od: od:

mmax:=nmax: n:=1: for m from 1 to mmax do MCM[n, m]:= A178866(n) od: n:=2: r:=1: for i from 2 to nmax do p:=A002865(i): r:=r+1: while p>0 do for m from 1 to mmax do MCM[n, m]:=A178866(n)*binomial(m, r) od: p:=p-1: n:=n+1: od: od: T:=0: for m from 1 to mmax do for n from 1 to numbpart(m) do T:=T+1; A178867(T):= MCM[n, m]; od: od; seq(A178867(n), n=1..T);

# to produce the exponential Bell polynomials, from N. J. A. Sloane, Oct 28 2015

M:=12;

EE:=add(x[i]*t^i/i!, i=1..M);

t1:=exp(EE);

t2:=series(t1, t, M);

Q:=k->sort(expand(k!*coeff(t2, t, k)));

for k from 1 to 8 do lprint(k, Q(k)); od;

CROSSREFS

Cf. A036040 (version 1 of multinomial coefficients), A080575 (version 2).

For triangle of coefficients of exponential Bell polynomials see A178867.

Sequence in context: A211351 A124802 A211350 * A102036 A121524 A103141

Adjacent sequences:  A178864 A178865 A178866 * A178868 A178869 A178870

KEYWORD

easy,nonn,tabf

AUTHOR

Johannes W. Meijer and Manuel Nepveu (Manuel.Nepveu(AT)tno.nl), Jun 21 2010, Jun 24 2010

EXTENSIONS

Alternative definition as coefficients of Bell polynomials added by N. J. A. Sloane, Oct 28 2015

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 20 13:18 EDT 2019. Contains 321345 sequences. (Running on oeis4.)