cp's OEIS Frontend

A178867 Irregular triangle read by rows: multinomial coefficients, version 3; alternatively, row n gives coefficients of the n-th complete exponential Bell polynomial B_n(x_1, x_2, ...) with monomials sorted into some unknown order.

%I A178867 #53 Feb 11 2021 13:47:15
%S A178867 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,
%T A178867 1,1,21,35,105,35,210,21,105,105,70,7,105,35,21,1,1,28,56,210,70,560,
%U A178867 56,420,420,280,28,840,280,168,8,280,210,105,56,35,28,1
%N A178867 Irregular triangle read by rows: multinomial coefficients, version 3; alternatively, row n gives coefficients of the n-th complete exponential Bell polynomial B_n(x_1, x_2, ...) with monomials sorted into some unknown order.
%C A178867 "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
%C A178867 From _Petros Hadjicostas_, May 27 2020: (Start)
%C A178867 According to the Maple help files for the "sort" command, polynomials in multiple variables are "sorted in total degree with ties broken by lexicographic order (this is called graded lexicographic order)."
%C A178867 Thus, for example, x_1^2*x_3 = x_1*x_1*x_3 > x_1*x_2*x_2 = x_1*x_2^2, while x_1^2*x_4 = x_1*x_1*x_4 > x_1*x_2*x_3.
%C A178867 It appears that the authors' n-th row does give the coefficients of the n-th complete exponential Bell polynomial. Starting with row 6, however, it is unknown in what order the monomials of the n-th complete exponential Bell polynomial follow. It is definitely not the standard order nor any other known order. (End)
%C A178867 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.
%C A178867 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).
%C A178867 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.
%C A178867 The number of multinomial coefficients in a triangle row leads to the partition numbers A000041. The row sums lead to the Bell numbers A000110.
%D A178867 L. Comtet, Advanced Combinatorics, Reidel, 1974, pp. 134, 307-310.
%D A178867 J. Riordan, An Introduction to Combinatorial Analysis, Wiley, 1958, Chapter 2, Section 8 and table on page 49.
%H A178867 Kevin Brown, <a href="http://www.mathpages.com/home/kmath057.htm">Generalized Birthday Problem (N Items in M Bins)</a>, 1994-2010.
%H A178867 Paul E. Gunnells, <a href="https://arxiv.org/abs/2102.05121">Generalized Catalan numbers from hypergraphs</a>, arXiv:2102.05121 [math.CO], 2021. Mentions this sequence p. 27.
%H A178867 J. W. Meijer and M. Nepveu, <a href="https://www.ucbcba.edu.bo/wp-content/uploads/PDF/Acta-Nova/v4.n1.Meijer.pdf">Euler's ship on the Pentagonal Sea</a>, Acta Nova, 4(1) (2008), 176-187.
%H A178867 Jin Wang, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL22/Wang/wang53.html">Nonlinear Inverse Relations for Bell Polynomials via the Lagrange Inversion Formula</a>, J. Int. Seq., Vol. 22 (2019), Article 19.3.8.
%F A178867 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]
%F A178867 For m >= 1, the formulas for the first few matrix columns are:
%F A178867 MCM[1,m] = A178866(1)*C(m,0) = 1*C(m,0);
%F A178867 MCM[2,m] = A178866(2)*C(m,2) = 1*C(m,2);
%F A178867 MCM[3,m] = A178866(3)*C(m,3) = 1*C(m,3);
%F A178867 MCM[4,m] = A178866(4)*C(m,4) = 3*C(m,4) and
%F A178867 MCM[5,m] = A178866(5)*C(m,4) = 1*C(m,4);
%F A178867 MCM[6,m] = A178866(6)*C(m,5) = 10*C(m,5) and
%F A178867 MCM[7,m] = A178866(7)*C(m,5) = 1*C(m,5);
%F A178867 MCM[8,m] = A178866(8)*C(m,6) = 15*C(m,6) and
%F A178867 MCM[9,m] = A178866(9)*C(m,6) = 15*C(m,6) and
%F A178867 MCM[10,m] = A178866(10)*C(m,6) = 10*C(m,6) and
%F A178867 MCM[11,m] = A178866(11)*C(m,6) = 1*C(m,6).
%e A178867 The first few complete exponential Bell polynomials are:
%e A178867 (1) x[1];
%e A178867 (2) x[1]^2 + x[2];
%e A178867 (3) x[1]^3 + 3*x[1]*x[2] + x[3];
%e A178867 (4) x[1]^4 + 6*x[1]^2*x[2] + 4*x[1]*x[3] + 3*x[2]^2 + x[4];
%e A178867 (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];
%e A178867 (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].
%e A178867 (7) x[1]^7 + 21*x[1]^5*x[2] + 35*x[1]^4*x[3] + 105*x[1]^3*x[2]^2 + 35*x[1]^3*x[4] + 210*x[1]^2*x[2]*x[3] + 21*x[1]^2*x[5] + 105*x[1]*x[2]^3 + 105*x[1]*x[2]*x[4] + 70*x[1]*x[3]^2 + 7*x[1]*x[6] + 105*x[2]^2*x[3] + 35*x[3]*x[4] + 21*x[2]*x[5] + x[7].
%e A178867 ...
%e A178867 The first few rows of the triangle are
%e A178867   1;
%e A178867   1,  1;
%e A178867   1,  3,  1;
%e A178867   1,  6,  4,   3,  1;
%e A178867   1, 10, 10,  15,  5,  10,  1;
%e A178867   1, 15, 20,  45, 15,  60,  6,  15,  15, 10, 1;
%e A178867   1, 21, 35, 105, 35, 210, 21, 105, 105, 70, 7, 105, 35, 21, 1;
%e A178867   ...
%p A178867 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:
%p A178867 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);
%p A178867 # To produce the complete exponential Bell polynomials in standard order, from _N. J. A. Sloane_, Oct 28 2015
%p A178867 M:=12;
%p A178867 EE:=add(x[i]*t^i/i!,i=1..M);
%p A178867 t1:=exp(EE);
%p A178867 t2:=series(t1,t,M);
%p A178867 Q:=k->sort(expand(k!*coeff(t2,t,k)));
%p A178867 for k from 1 to 8 do lprint(k,Q(k)); od;
%p A178867 # To produce the coefficients of the complete exponential Bell polynomials in standard order:
%p A178867 triangle := proc(numrows) local E, s, Q;
%p A178867 E := add(x[i]*t^i/i!, i=1..numrows);
%p A178867 s := series(exp(E), t, numrows+1);
%p A178867 Q := k -> sort(expand(k!*coeff(s, t, k)));
%p A178867 seq(print(coeffs(Q(k))), k=1..numrows) end:
%p A178867 triangle(6); # _Peter Luschny_, May 27 2020
%Y A178867 Cf. A036040 (version 1 of multinomial coefficients), A080575 (version 2).
%Y A178867 Cf. A000041, A000110, A000296, A178866, A263633.
%K A178867 easy,nonn,tabf
%O A178867 1,5
%A A178867 _Johannes W. Meijer_ and Manuel Nepveu (Manuel.Nepveu(AT)tno.nl), Jun 21 2010, Jun 24 2010
%E A178867 Alternative definition as coefficients of complete Bell polynomials added by _N. J. A. Sloane_, Oct 28 2015
%E A178867 Various sections and name edited by _Petros Hadjicostas_, May 28 2020