A262071 -id:A262071 - cp's OEIS frontend

A005651 Sum of multinomial coefficients (n_1+n_2+...)!/(n_1!n_2!...) where (n_1, n_2, ...) runs over all integer partitions of n.

1, 1, 3, 10, 47, 246, 1602, 11481, 95503, 871030, 8879558, 98329551, 1191578522, 15543026747, 218668538441, 3285749117475, 52700813279423, 896697825211142, 16160442591627990, 307183340680888755, 6147451460222703502, 129125045333789172825, 2841626597871149750951

Offset: 0

Simon Plouffe

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) 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
Also the number of ordered set partitions of {1,...,n} with weakly decreasing block sizes. - Gus Wiseman, Sep 03 2018
The parity of a(n) is that of A000110(A000120(n)), so a(n) is even if and only if A000120(n) == 2 (mod 3). - Álvar Ibeas, Aug 11 2020

			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
From _Gus Wiseman_, Sep 03 2018: (Start)
The a(3) = 10 ordered set partitions with weakly decreasing block sizes:
  {{1},{2},{3}}
  {{1},{3},{2}}
  {{2},{1},{3}}
  {{2},{3},{1}}
  {{3},{1},{2}}
  {{3},{2},{1}}
  {{2,3},{1}}
  {{1,2},{3}}
  {{1,3},{2}}
  {{1,2,3}}
(End)

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

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, and N. C. Wormald, The Asymptotic Number of Set Partitions with Unequal Block Sizes, The Electronic Journal of Combinatorics, 6 (1999), R2.
S. Schreiber & N. J. A. Sloane, Correspondence, 1980.

Main diagonal of: A226873, A261719, A309973.
Row sums of: A226874, A262071, A327803.
Column k=1 of A309951.
Column k=0 of A327801.
Cf. A000041, A000110, A000258, A000670, A007837, A008277, A008480, A036038, A140585, A178682, A212855, A247551, A300335, A318762.

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 or i=1, n!,
      b(n, i-1) +binomial(n, i)*b(n-i, min(n-i, i)))
    end:
a:= n-> b(n$2):
seq(a(n), n=0..25);  # Alois P. Heinz, Aug 29 2015, Dec 12 2016

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 *)

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 */

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

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

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 nVladimir Kruchinin, Sep 06 2014
E.g.f.: exp(Sum_{k>=1} Sum_{j>=1} x^(j*k)/(k*(j!)^k)). - Ilya Gutkovskiy, Jun 18 2018

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

A262072 Number T(n,k) of partitions of an n-set with distinct block sizes and maximal block size equal to k; triangle T(n,k), n>=0, ceiling((sqrt(1+8*n)-1)/2)<=k<=n, read by rows.

Original entry on oeis.org

1, 1, 1, 3, 1, 4, 1, 10, 5, 1, 60, 15, 6, 1, 140, 21, 7, 1, 280, 224, 28, 8, 1, 1260, 630, 336, 36, 9, 1, 12600, 3780, 1050, 480, 45, 10, 1, 34650, 7392, 1650, 660, 55, 11, 1, 110880, 74844, 12672, 2475, 880, 66, 12, 1, 360360, 276276, 140712, 20592, 3575, 1144, 78, 13, 1

Offset: 0

Alois P. Heinz, Sep 10 2015

			Triangle T(n,k) begins:
: 1;
:    1;
:       1;
:       3,  1;
:           4,     1;
:          10,     5,    1;
:          60,    15,    6,    1;
:                140,   21,    7,   1;
:                280,  224,   28,   8,  1;
:               1260,  630,  336,  36,  9,  1;
:              12600, 3780, 1050, 480, 45, 10, 1;

Alois P. Heinz, Rows n = 0..200, flattened

Row sums give A007837.
Column sums give A262073.
Cf. A002024, A262071, A262078 (same read by columns).

b:= proc(n, i) option remember; `if`(i*(i+1)/2n, 0, binomial(n, i)*b(n-i, i-1))))
    end:
T:= (n, k)-> b(n, k) -`if`(k=0, 0, b(n, k-1)):
seq(seq(T(n,k), k=ceil((sqrt(1+8*n)-1)/2)..n), n=0..14);

b[n_, i_] := b[n, i] = If[i*(i+1)/2n, 0, Binomial[n, i]*b[n-i, i-1]]]]; T[n_, k_] := b[n, k] - If[k == 0, 0, b[n, k-1]]; Table[T[n, k], {n, 0, 14}, {k, Ceiling[(Sqrt[1+8*n]-1)/2], n}] // Flatten (* Jean-François Alcover, Feb 04 2017, translated from Maple *)

A262078 Number T(n,k) of partitions of an n-set with distinct block sizes and maximal block size equal to k; triangle T(n,k), k>=0, k<=n<=k*(k+1)/2, read by columns.

Original entry on oeis.org

1, 1, 1, 3, 1, 4, 10, 60, 1, 5, 15, 140, 280, 1260, 12600, 1, 6, 21, 224, 630, 3780, 34650, 110880, 360360, 2522520, 37837800, 1, 7, 28, 336, 1050, 7392, 74844, 276276, 1513512, 9459450, 131171040, 428828400, 2058376320, 9777287520, 97772875200, 2053230379200

Offset: 0

Alois P. Heinz, Sep 10 2015

			Triangle T(n,k) begins:
: 1;
:    1;
:       1;
:       3,  1;
:           4,     1;
:          10,     5,    1;
:          60,    15,    6,    1;
:                140,   21,    7,   1;
:                280,  224,   28,   8,  1;
:               1260,  630,  336,  36,  9,  1;
:              12600, 3780, 1050, 480, 45, 10, 1;

Alois P. Heinz, Columns k = 0..36, flattened

Row sums give A007837.
Column sums give A262073.
Cf. A000217, A002024, A262071, A262072 (same read by rows).

b:= proc(n, i) option remember; `if`(i*(i+1)/2n, 0, binomial(n, i)*b(n-i, i-1))))
    end:
T:= (n, k)-> b(n, k) -`if`(k=0, 0, b(n, k-1)):
seq(seq(T(n, k), n=k..k*(k+1)/2), k=0..7);

b[n_, i_] := b[n, i] = If[i*(i+1)/2n, 0, Binomial[n, i]*b[n-i, i-1]]]]; T[n_, k_] :=  b[n, k] - If[k==0, 0, b[n, k-1]]; Table[T[n, k], {k, 0, 7}, {n, k, k*(k+1)/2}] // Flatten (* Jean-François Alcover, Dec 18 2016, after Alois P. Heinz *)

A266518 Number of ordered partitions of a 2n-set with nondecreasing block sizes and maximal block size equal to n.

Original entry on oeis.org

1, 2, 18, 200, 3290, 61992, 1480248, 39402792, 1229123610, 42349478600, 1640551617848, 69364811821032, 3222214209737432, 161656803984848200, 8772238289222220600, 509677254444910662000, 31677425399312755814970, 2092539622373193784503240

Offset: 0

Alois P. Heinz, Dec 30 2015

nonn

Alois P. Heinz, Table of n, a(n) for n = 0..300

Cf. A262071, A327801, A328156.

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-> `if`(n=0, 1, b(2*n, n)-b(2*n, n-1)):
seq(a(n), n=0..20);

b[n_, i_] := b[n, i] = If[n==0, 1, If[i<1, 0, b[n, i-1] + If[i>n, 0, Binomial[n, i]*b[n-i, i]]]]; a[n_] := If[n==0, 1, b[2n, n] - b[2n, n-1]]; Table[a[n], {n, 0, 20}] (* Jean-François Alcover, Feb 27 2017, translated from Maple *)

a(n) = (2n)! * [x^n] Product_{i=1..n} (i-1)!/(i!-x^i).
a(n) = A262071(2n,n).
a(n) ~ c * 2^(2*n+1/2) * n^n / exp(n), where c = A247551 = 2.529477472079152648... . - Vaclav Kotesovec, Jan 02 2016
a(n) = A327801(2n,n). - Alois P. Heinz, Sep 26 2019

A272492 Number of ordered set partitions of [n] with nondecreasing block sizes and maximal block size equal to two.

Original entry on oeis.org

1, 3, 18, 90, 630, 4410, 37800, 340200, 3515400, 38669400, 471517200, 6129723600, 86497210800, 1297458162000, 20841060240000, 354298024080000, 6389869069584000, 121407512322096000, 2430526127309280000, 51041048673494880000, 1123451899297247520000

Offset: 2

Alois P. Heinz, May 01 2016

nonn

Alois P. Heinz, Table of n, a(n) for n = 2..450

Column k=2 of A262071.

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-> (k-> b(n, k) -b(n, k-1))(2):
seq(a(n), n=2..30);

Table[n!*(1 + ((-1)^n*(Sqrt[2] - 1) - Sqrt[2] - 1)/2^(n/2 + 1)), {n, 2, 20}] (* Vaclav Kotesovec, May 07 2016 *)

E.g.f.: x^2 * Product_{i=1..2} (i-1)!/(i!-x^i).

Recurrence: 2*a(n) = 2*n*a(n-1) + (n-1)*n*a(n-2) - (n-2)*(n-1)*n*a(n-3). - Vaclav Kotesovec, May 07 2016

A272493 Number of ordered set partitions of [n] with nondecreasing block sizes and maximal block size equal to three.

Original entry on oeis.org

1, 4, 30, 200, 1610, 13440, 130200, 1327200, 15107400, 183321600, 2422820400, 34104470400, 515897382000, 8276556288000, 141290381232000, 2546760408192000, 48489153817104000, 970454450085120000, 20400874234060320000, 448974320483969280000

Offset: 3

Alois P. Heinz, May 01 2016

nonn

Alois P. Heinz, Table of n, a(n) for n = 3..450

Column k=3 of A262071.

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-> (k-> b(n, k) -b(n, k-1))(3):
seq(a(n), n=3..30);

FullSimplify[Table[n! * ((-35*(1 + Sqrt[2]) + 7*2^(1 + n/2)* (3*Sqrt[2] - 2) - 5*(-1)^n*(17*Sqrt[2] - 23))/2^(n/2) + 2^(5/6 - n/3)* 3^(-1 - n/3)*((11*3^(1/3) + 6*2^(1/3)* 3^(2/3))*(3 - Sqrt[2]) + 13*2^(1/6)*(3*Sqrt[2] - 2) + (26*2^(1/6)*(3*Sqrt[2] - 2) - (11*3^(1/3) + 6*2^(1/3)*3^(2/3))* (3 - Sqrt[2]))*Cos[2*n*Pi/3] + 3^(1/6)*(3 - Sqrt[2])*(11*3^(2/3) - 18*2^(1/3))*Sin[2*n*Pi/3])) / (35*(3*Sqrt[2] - 2)), {n, 3, 20}]] (* Vaclav Kotesovec, May 07 2016 *)

E.g.f.: x^3 * Product_{i=1..3} (i-1)!/(i!-x^i).

Recurrence: 12*a(n) = 12*n*a(n-1) + 6*(n-1)*n*a(n-2) - 4*(n-2)*(n-1)*n*a(n-3) - 2*(n-3)*(n-2)*(n-1)*n*a(n-4) - (n-4)*(n-3)*(n-2)*(n-1)*n*a(n-5) + (n-5)*(n-4)*(n-3)*(n-2)*(n-1)*n*a(n-6). - Vaclav Kotesovec, May 07 2016

A272494 Number of ordered set partitions of [n] with nondecreasing block sizes and maximal block size equal to four.

Original entry on oeis.org

1, 5, 45, 350, 3290, 30870, 334950, 3765300, 46950750, 617867250, 8815156350, 133031398500, 2149039893000, 36645888279000, 662781093975000, 12612741639498000, 252857867367105000, 5314211504296695000, 117053051989758885000, 2693288170000578150000

Offset: 4

Alois P. Heinz, May 01 2016

nonn

Alois P. Heinz, Table of n, a(n) for n = 4..450

Column k=4 of A262071.

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-> (k-> b(n, k) -b(n, k-1))(4):
seq(a(n), n=4..30);

b[n_, i_] := b[n, i] = If[n == 0, 1, If[i < 1, 0, b[n, i - 1] + If[i > n, 0, Binomial[n, i]*b[n - i, i]]]];
a[n_] := b[n, 4] - b[n, 3];
a /@ Range[4, 30] (* Jean-François Alcover, Dec 11 2020, after Alois P. Heinz *)

E.g.f.: x^4 * Product_{i=1..4} (i-1)!/(i!-x^i).

A272495 Number of ordered set partitions of [n] with nondecreasing block sizes and maximal block size equal to five.

Original entry on oeis.org

1, 6, 63, 560, 5922, 61992, 739662, 9086616, 122792670, 1741884144, 26631631026, 428931318816, 7362963616008, 132977285400960, 2538822785931432, 50863863365419104, 1070731366348427784, 23576426902769412672, 542918591829347774040, 13035693339696004705728

Offset: 5

Alois P. Heinz, May 01 2016

nonn

Alois P. Heinz, Table of n, a(n) for n = 5..450

Column k=5 of A262071.

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-> (k-> b(n, k) -b(n, k-1))(5):
seq(a(n), n=5..30);

b[n_, i_] := b[n, i] = If[n == 0, 1, If[i < 1, 0, b[n, i - 1] + If[i > n, 0, Binomial[n, i]*b[n - i, i]]]];
a[n_] := b[n, 5] - b[n, 4];
a /@ Range[5, 30] (* Jean-François Alcover, Dec 11 2020, after Alois P. Heinz *)

E.g.f.: x^5 * Product_{i=1..5} (i-1)!/(i!-x^i).

A272496 Number of ordered set partitions of [n] with nondecreasing block sizes and maximal block size equal to six.

Original entry on oeis.org

1, 7, 84, 840, 9870, 113652, 1480248, 19699680, 286768482, 4358914560, 71096721696, 1216711960464, 22116370171896, 421629228820800, 8473857766133760, 178260053918650704, 3931319749640138856, 90499126549555707984, 2174651142277047610176, 54390059451824183287200

Offset: 6

Alois P. Heinz, May 01 2016

nonn

Alois P. Heinz, Table of n, a(n) for n = 6..450

Column k=6 of A262071.

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-> (k-> b(n, k) -b(n, k-1))(6):
seq(a(n), n=6..30);

E.g.f.: x^6 * Product_{i=1..6} (i-1)!/(i!-x^i).

A272497 Number of ordered set partitions of [n] with nondecreasing block sizes and maximal block size equal to seven.

Original entry on oeis.org

1, 8, 108, 1200, 15510, 194832, 2749032, 39402792, 614555370, 9964468800, 172686804576, 3129181488576, 60039964804248, 1204868044448640, 25426155055055040, 560350692475352064, 12919636322380914984, 310342487192287684992, 7768115419959585662400

Offset: 7

Alois P. Heinz, May 01 2016

nonn

Alois P. Heinz, Table of n, a(n) for n = 7..450

Column k=7 of A262071.

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-> (k-> b(n, k) -b(n, k-1))(7):
seq(a(n), n=7..30);

E.g.f.: x^7 * Product_{i=1..7} (i-1)!/(i!-x^i).

cp's OEIS Frontend

A005651 Sum of multinomial coefficients (n_1+n_2+...)!/(n_1!*n_2!*...) where (n_1, n_2, ...) runs over all integer partitions of n.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

Maxima

PARI

PARI

Formula

Extensions

A262072 Number T(n,k) of partitions of an n-set with distinct block sizes and maximal block size equal to k; triangle T(n,k), n>=0, ceiling((sqrt(1+8*n)-1)/2)<=k<=n, read by rows.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

A262078 Number T(n,k) of partitions of an n-set with distinct block sizes and maximal block size equal to k; triangle T(n,k), k>=0, k<=n<=k*(k+1)/2, read by columns.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

A266518 Number of ordered partitions of a 2n-set with nondecreasing block sizes and maximal block size equal to n.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A272492 Number of ordered set partitions of [n] with nondecreasing block sizes and maximal block size equal to two.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A272493 Number of ordered set partitions of [n] with nondecreasing block sizes and maximal block size equal to three.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A272494 Number of ordered set partitions of [n] with nondecreasing block sizes and maximal block size equal to four.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A272495 Number of ordered set partitions of [n] with nondecreasing block sizes and maximal block size equal to five.

Views

A005651 Sum of multinomial coefficients (n_1+n_2+...)!/(n_1!n_2!...) where (n_1, n_2, ...) runs over all integer partitions of n.