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

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A005651 Sum of multinomial coefficients (n_1+n_2+...)!/(n_1!*n_2!*...).
(Formerly M2870)
45
1, 1, 3, 10, 47, 246, 1602, 11481, 95503, 871030, 8879558, 98329551, 1191578522, 15543026747, 218668538441, 3285749117475, 52700813279423, 896697825211142, 16160442591627990, 307183340680888755, 6147451460222703502, 129125045333789172825 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,3

COMMENTS

This is the total number of hierarchies of n labeled elements arranged on 1 to n levels. A distribution of elements onto levels is "hierarchical" if a level l+1 contains <= elements than level l. Thus for n=4 the arrangement {1,2}:{3}{4} is not allowed. See also A140585. Examples: Let the colon ":" separate two consecutive levels l and l+1. Then n=2 --> 3: {1}{2}, {1}:{2}, {2}:{1}, n=3 --> 10: {1}{2}{3}, {1}{2}:{3}, {3}{1}:{2}, {2}{3}:{1}, {1}:{2}:{3}, {3}:{1}:{2}, {2}:{3}:{1}, {1}:{3}:{2}, {2}:{1}:{3}, {3}:{2}:{1}. - Thomas Wieder, May 17 2008

n identical objects are painted by dipping them into a long row of cans of paint of distinct colors. Begining with the first can and not skipping any cans k, 1<=k<=n, objects are dipped (painted) and not more objects are dipped into any subsequent can than were dipped into the previous can. The painted objects are then linearly ordered. - Geoffrey Critzer, Jun 08 2009

a(n) = the sum of all (n-1)!/p(n-1) where p(n-1) runs through the partitions of n-1 using numbers <= n-1 and each partition is treated as the product of factorials of each of its terms.  Example for n=6 gives 6-1=5, having partitions 5; 1,4; 2,3; 1,1,3; 1,2,2; 1,1,1,2; 1,1,1,1,1.  This gives the seven terms 5!/5!=120/120=1; 120/1!*4!=5; 120/2!*3!=10; 120/1!*1!*3!=20; 120/1!*2!*2!=30; 120/1!*1!*1!*2!=60; 120/1!*1!*1!*1!*1! having a sum of 1+5+10+20+30+60+120=246=a(6). - J. M. Bergot, May 07 2014

a(n) is the number of partitions of n where each part i is marked with a word of length i over an n-ary alphabet whose letters appear in alphabetical order and all n letters occur exactly once in the partition. a(3) = 10: 3abc, 2ab1c, 2ac1b, 2bc1a, 1a1b1c, 1a1c1b, 1b1a1c, 1b1c1a, 1c1a1b, 1c1b1a. - Alois P. Heinz, Aug 30 2015

REFERENCES

Abramowitz and Stegun, Handbook, p. 831, column labeled "M_1".

L. Comtet, Advanced Combinatorics, Reidel, 1974, p. 126.

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

LINKS

T. D. Noe and Alois P. Heinz, Table of n, a(n) for n = 0..450 (first 101 terms from T. D. Noe)

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

M. E. Hoffman, Updown categories: Generating functions and universal covers, arXiv preprint arXiv:1207.1705 [math.CO], 2012.

A. Knopfmacher, A. M. Odlyzko, B. Pittel, L. B. Richmond, D. Stark, G. Szekeres, N. C. Wormald, The Asymptotic Number of Set Partitions with Unequal Block Sizes, The Electronic Journal of Combinatorics, 1999.

S. Schreiber & N. J. A. Sloane, Correspondence, 1980

FORMULA

E.g.f.: 1 / Product (1 - x^k/k!).

a(n) = Sum_{k=1..n} (n-1)!/(n-k)!*b(k)*a(n-k), where b(k) = Sum_{d divides k} d*d!^(-k/d). - Vladeta Jovovic, Oct 14 2002

a(n) ~ c * n!, where c = Product_{k>=2} 1/(1-1/k!) = A247551 = 2.52947747207915264... . - Vaclav Kotesovec, May 09 2014

a(n) = S(n,1), where S(n,m) = sum(k=m..n/2 , binomial(n,k)*S(n-k,k))+1, S(n,n)=1, S(n,m)=0 for n<m. - Vladimir Kruchinin, Sep 06 2014

EXAMPLE

For n=3, say the first three cans in the row contain red, white, and blue paint respectively. The objects can be painted r,r,r or r,r,w or r,w,b and then linearly ordered in 1 + 3 + 6 = 10 ways. - Geoffrey Critzer, Jun 08 2009

MAPLE

A005651b := proc(k) add( d/(d!)^(k/d), d=numtheory[divisors](k)) ; end proc:

A005651 := proc(n) option remember; local k ; if n <= 1 then 1; else (n-1)!*add(A005651b(k)*procname(n-k)/(n-k)!, k=1..n) ; end if; end proc:

seq(A005651(k), k=0..10) ; # R. J. Mathar, Jan 03 2011

# second Maple program:

b:= proc(n, i) option remember; `if`(n=0, 1, `if`(i<1, 0,

       b(n, i-1)+`if`(i>n, 0, binomial(n, i)*b(n-i, i))))

    end:

a:= n-> b(n$2):

seq(a(n), n=0..25); # Alois P. Heinz, Aug 29 2015, Dec 12 2016

MATHEMATICA

Table[Total[n!/Map[Function[n, Apply[Times, n! ]], IntegerPartitions[n]]], {n, 0, 20}] (* Geoffrey Critzer, Jun 08 2009 *)

Table[Total[Apply[Multinomial, IntegerPartitions[n], {1}]], {n, 0, 20}] (* Jean-François Alcover and Olivier Gérard, Sep 11 2014 *)

b[n_, i_, t_] := b[n, i, t] = If[t==1, 1/n!, Sum[b[n-j, j, t-1]/j!, {j, i, n/t}]]; a[n_] := If[n==0, 1, n!*b[n, 0, n]]; Table[a[n], {n, 0, 25}] (* Jean-François Alcover, Nov 20 2015, after Alois P. Heinz *)

PROG

(Maxima)

a(m, n):=if n=m then 1 else sum(binomial(n, k)*a(k, n-k), k, m, (n/2))+1;

makelist(a(1, n), n, 0, 17); /* Vladimir Kruchinin, Sep 06 2014 */

(PARI) a(n)=my(N=n!, s); forpart(x=n, s+=N/prod(i=1, #x, x[i]!)); s \\ Charles R Greathouse IV, May 01 2015

(PARI) { my(n=25); Vec(serlaplace(prod(k=1, n, 1/(1-x^k/k!) + O(x*x^n)))) } \\ Andrew Howroyd, Dec 20 2017

CROSSREFS

Cf. A036038, A007837, A140585, A247551.

Main diagonal of A226873 and A261719.

Row sums of A226874 and A262071.

Cf. A178682.

Sequence in context: A226878 A226879 A226880 * A249479 A236410 A105748

Adjacent sequences:  A005648 A005649 A005650 * A005652 A005653 A005654

KEYWORD

nonn,easy,nice

AUTHOR

Simon Plouffe

EXTENSIONS

More terms from Antonio G. Astudillo (afg_astudillo(AT)lycos.com), Mar 29 2003

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 | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy .

Last modified May 27 03:48 EDT 2018. Contains 304690 sequences. (Running on oeis4.)