A271423 -id:A271423 - cp's OEIS frontend

A007837 Number of partitions of n-set with distinct block sizes.

1, 1, 1, 4, 5, 16, 82, 169, 541, 2272, 17966, 44419, 201830, 802751, 4897453, 52275409, 166257661, 840363296, 4321172134, 24358246735, 183351656650, 2762567051857, 10112898715063, 62269802986835, 343651382271526, 2352104168848091, 15649414071734847

Offset: 0

Arnold Knopfmacher

nonn

Conjecture: the Gauss congruences a(n*p^k) == a(n*p^(k-1)) (mod p^k) hold for all primes p and positive integers n and k. Cf. A185895. - Peter Bala, Mar 17 2022

			From _Gus Wiseman_, Jul 13 2019: (Start)
The a(1) = 1 through a(5) = 16 set partitions with distinct block sizes:
  {{1}}  {{1,2}}  {{1,2,3}}    {{1,2,3,4}}    {{1,2,3,4,5}}
                  {{1},{2,3}}  {{1},{2,3,4}}  {{1},{2,3,4,5}}
                  {{1,2},{3}}  {{1,2,3},{4}}  {{1,2},{3,4,5}}
                  {{1,3},{2}}  {{1,2,4},{3}}  {{1,2,3},{4,5}}
                               {{1,3,4},{2}}  {{1,2,3,4},{5}}
                                              {{1,2,3,5},{4}}
                                              {{1,2,4},{3,5}}
                                              {{1,2,4,5},{3}}
                                              {{1,2,5},{3,4}}
                                              {{1,3},{2,4,5}}
                                              {{1,3,4},{2,5}}
                                              {{1,3,4,5},{2}}
                                              {{1,3,5},{2,4}}
                                              {{1,4},{2,3,5}}
                                              {{1,4,5},{2,3}}
                                              {{1,5},{2,3,4}}
(End)

Alois P. Heinz, Table of n, a(n) for n = 0..700
Philippe Flajolet, Éric Fusy, Xavier Gourdon, Daniel Panario and Nicolas Pouyanne, A Hybrid of Darboux's Method and Singularity Analysis in Combinatorial Asymptotics, Fig. 3, arXiv:math/0606370 [math.CO], 2006.
Knopfmacher, A., Odlyzko, A. M., Pittel, B., Richmond, L. B., Stark, D., Szekeres, G. and Wormald, N. C., The asymptotic number of set partitions with unequal block sizes, Electron. J. Combin., 6 (1999), no. 1, Research Paper 2, 36 pp.
Gus Wiseman, Sequences counting and ranking multiset partitions whose part lengths, sums, or averages are constant or strict.

Row sums of A131632 or A262072 or A262078 or A309992.
Cf. A000110, A005651, A007838, A032011, A035470, A038041, A178682, A265950, A271423, A275780, A326026, A326514, A326517, A326533.
Column k=0 of A327869.

a:= proc(n) option remember; `if`(n=0, 1, add(add((-d)*(-d!)^(-k/d),
       d=numtheory[divisors](k))*(n-1)!/(n-k)!*a(n-k), k=1..n))
    end:
seq(a(n), n=0..30);  # Alois P. Heinz, Sep 06 2008
# second Maple program:
A007837 := proc(n) option remember; local k; `if`(n = 0, 1,
add(binomial(n-1, k-1) * A182927(k) * A007837(n-k), k = 1..n)) end:
seq(A007837(i),i=0..24); # Peter Luschny, Apr 25 2011

nn=20;p=Product[1+x^i/i!,{i,1,nn}];Drop[Range[0,nn]!CoefficientList[ Series[p,{x,0,nn}],x],1]  (* Geoffrey Critzer, Sep 22 2012 *)
a[0]=1; a[n_] := a[n] = Sum[(n-1)!/(n-k)!*DivisorSum[k, -#*(-#!)^(-k/#)&]* a[n-k], {k, 1, n}]; Table[a[n], {n, 0, 30}] (* Jean-François Alcover, Nov 23 2015, after Vladeta Jovovic *)

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

E.g.f.: Product_{m >= 1} (1+x^m/m!).
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) and a(0) = 1. - Vladeta Jovovic, Oct 13 2002
E.g.f.: exp(Sum_{k>=1} Sum_{j>=1} (-1)^(k+1)*x^(j*k)/(k*(j!)^k)). - Ilya Gutkovskiy, Jun 18 2018

More terms from Christian G. Bower

a(0)=1 prepended by Alois P. Heinz, Aug 29 2015

A271424 Number T(n,k) of set partitions of [n] with minimal block length multiplicity equal to k; triangle T(n,k), n>=0, 0<=k<=n, read by rows.

Original entry on oeis.org

1, 0, 1, 0, 1, 1, 0, 4, 0, 1, 0, 11, 3, 0, 1, 0, 51, 0, 0, 0, 1, 0, 132, 55, 15, 0, 0, 1, 0, 771, 105, 0, 0, 0, 0, 1, 0, 3089, 945, 0, 105, 0, 0, 0, 1, 0, 18388, 1218, 1540, 0, 0, 0, 0, 0, 1, 0, 96423, 15456, 3150, 0, 945, 0, 0, 0, 0, 1, 0, 627529, 26785, 24255, 0, 0, 0, 0, 0, 0, 0, 1

Offset: 0

Alois P. Heinz, Apr 07 2016

At least one block length occurs exactly k times, and all block lengths occur at least k times.

			T(4,1) = 11: 1234, 123|4, 124|3, 12|3|4, 134|2, 13|2|4, 1|234, 1|23|4, 14|2|3, 1|24|3, 1|2|34.
T(4,2) = 3: 12|34, 13|24, 14|23.
T(4,4) = 1: 1|2|3|4.
T(6,3) = 15: 12|34|56, 12|35|46, 12|36|45, 13|24|56, 13|25|46, 13|26|45, 14|23|56, 15|23|46, 16|23|45, 14|25|36, 14|26|35, 15|24|36, 16|24|35, 15|26|34, 16|25|34.
Triangle T(n,k) begins:
  1;
  0,     1;
  0,     1,     1;
  0,     4,     0,    1;
  0,    11,     3,    0,   1;
  0,    51,     0,    0,   0,   1;
  0,   132,    55,   15,   0,   0, 1;
  0,   771,   105,    0,   0,   0, 0, 1;
  0,  3089,   945,    0, 105,   0, 0, 0, 1;
  0, 18388,  1218, 1540,   0,   0, 0, 0, 0, 1;
  0, 96423, 15456, 3150,   0, 945, 0, 0, 0, 0, 1;

Alois P. Heinz, Rows n = 0..140, flattened
Wikipedia, Partition of a set

Columns k=0-10 give A000007, A271426, A271762, A271763, A271764, A271765, A271766, A271767, A271768, A271769, A271770.
Row sums give A000110.
Main diagonal gives A000012.
T(2n,n) gives A001147.
T(3n,n) gives A271715.
Cf. A271423.

with(combinat):
b:= proc(n, i, k) option remember; `if`(n=0, 1,
      `if`(i<1, 0, add(multinomial(n, n-i*j, i$j)
        *b(n-i*j, i-1, k)/j!, j={0, $k..n/i})))
    end:
T:= (n, k)-> b(n$2, k)-`if`(n=k,0,b(n$2, k+1)):
seq(seq(T(n, k), k=0..n), n=0..12);

multinomial[n_, k_List] := n!/Times @@ (k!); b[n_, i_, k_] := b[n, i, k] = If[n == 0, 1, If[i<1, 0, Sum[multinomial[n, Join[{n-i*j}, Array[i&, j]]]* b[n-i*j, i-1, k]/j!, {j, Join[{0}, Range[k, n/i]] // Union}]]]; T[n_, k_] := b[n, n, k] - If[n == k, 0, b[n, n, k + 1]]; Table[T[n, k], {n, 0, 12}, {k, 0, n}] // Flatten (* Jean-François Alcover, Jan 16 2017, adapted from Maple *)

A271425 Number of set partitions of [2n] with maximal block length multiplicity equal to n.

Original entry on oeis.org

1, 1, 9, 35, 385, 3717, 48279, 691119, 11229075, 200982925, 3928974907, 83060120871, 1885501840677, 45694145548625, 1176704027583075, 32077561625780175, 922854842240358825, 27951355368760441365, 889580295850449177975, 29707539555680924142975

Offset: 0

Alois P. Heinz, Apr 07 2016

nonn

In each set partition of [2n] counted by a(n) at least one block length occurs exactly n times, and all block lengths occur at most n times.

			a(1) = 1: 12.
a(2) = 9: 12|34, 12|3|4, 13|24, 13|2|4, 14|23, 1|23|4, 14|2|3, 1|24|3, 1|2|34.
a(3) = 35: 123|4|5|6, 124|3|5|6, 12|34|56, 125|3|4|6, 12|35|46, 12|36|45, 126|3|4|5, 134|2|5|6, 13|24|56, 135|2|4|6, 13|25|46, 13|26|45, 136|2|4|5, 14|23|56, 1|234|5|6, 15|23|46, 1|235|4|6, 16|23|45, 1|236|4|5, 145|2|3|6, 14|25|36, 14|26|35, 146|2|3|5, 15|24|36, 1|245|3|6, 16|24|35, 1|246|3|5, 15|26|34, 16|25|34, 1|2|345|6, 1|2|346|5, 156|2|3|4, 1|256|3|4, 1|2|356|4, 1|2|3|456.

Alois P. Heinz, Table of n, a(n) for n = 0..200
Wikipedia, Partition of a set

Cf. A271423, A372762.

with(combinat):
b:= proc(n, i, k) option remember; `if`(n=0, 1,
      `if`(i<1, 0, add(multinomial(n, n-i*j, i$j)
        *b(n-i*j, i-1, k)/j!, j=0..min(k, n/i))))
    end:
a:= n-> `if`(n=0, 1, b(2*n$2, n)-b(2*n$2, n-1)):
seq(a(n), n=0..20);

multinomial[n_, k_] := n!/Times @@ (k!); b[n_, i_, k_] := b[n, i, k] = If[n == 0, 1, If[i<1, 0, Sum[multinomial[n, Join[{n-i*j}, Array[i&, j]]]*b[n - i*j, i-1, k]/j!, {j, 0, Min[k, n/i]}]]]; a[n_] := If[n==0, 1, b[2n, 2n, n] - b[2n, 2n, n-1]]; Table[a[n], {n, 0, 20}] (* Jean-François Alcover, Feb 17 2017, translated from Maple *)

a(n) = A271423(2n,n).

a(n) = A372762(2n,n). - Alois P. Heinz, May 12 2024

A360182 Number of partitions of [n] where each block size occurs at most twice.

Original entry on oeis.org

1, 1, 2, 4, 14, 41, 152, 575, 2634, 13207, 59927, 312170, 1946870, 10547135, 65168469, 421552409, 3148178034, 20138277895, 141300123713, 1063603633154, 9108280640649, 68154636145922, 549824347467969, 4551458909818969, 39948625639349706, 406913301246314341

Offset: 0

Alois P. Heinz, May 13 2023

nonn

			a(0) = 1: (), the empty partition.
a(1) = 1: 1.
a(2) = 2: 12, 1|2.
a(3) = 4: 123, 12|3, 13|2, 1|23.
a(4) = 14: 1234, 123|4, 124|3, 12|34, 12|3|4, 134|2, 13|24, 13|2|4, 14|23, 1|234, 1|23|4, 14|2|3, 1|24|3, 1|2|34.
a(5) = 41: 12345, 1234|5, 1235|4, 123|45, 123|4|5, 1245|3, 124|35, 124|3|5, 125|34, 12|345, 12|34|5, 125|3|4, 12|35|4, 12|3|45, 1345|2, 134|25, 134|2|5, 135|24, 13|245, 13|24|5, 135|2|4, 13|25|4, 13|2|45, 145|23, 14|235, 14|23|5, 15|234, 1|2345, 1|234|5, 15|23|4, 1|235|4, 1|23|45, 145|2|3, 14|25|3, 14|2|35, 15|24|3, 1|245|3, 1|24|35, 15|2|34, 1|25|34, 1|2|345.

Alois P. Heinz, Table of n, a(n) for n = 0..648
Wikipedia, Partition of a set

Cf. A000110, A007837, A114917, A115275, A271423.

b:= proc(n, i) option remember; `if`(n=0, 1, `if`(i<1, 0,
      add(combinat[multinomial](n, n-i*j, i$j)/j!*
        b(n-i*j, i-1), j=0..min(2, n/i))))
    end:
a:= n-> b(n$2):
seq(a(n), n=0..25);

multinomial[n_, k_List] := n!/Times @@ (k!);
b[n_, i_] := b[n, i] = If[n == 0, 1, If[i < 1, 0, Sum[multinomial[n, {n - i*j}~Join~ Table[i, {j}]]/j!*b[n - i*j, i - 1], {j, 0, Min[2, n/i]}]]];
a[n_] :=  b[n, n];
Table[a[n], {n, 0, 25}](* Jean-François Alcover, Nov 21 2023, after Alois P. Heinz *)

a(n) = Sum_{k=0..2} A271423(n,k).

A271731 Number of set partitions of [n] with maximal block length multiplicity equal to two.

Original entry on oeis.org

1, 0, 9, 25, 70, 406, 2093, 10935, 41961, 267751, 1745040, 9744384, 60271016, 369277000, 2981920373, 19297914599, 136978951579, 1039245386419, 8924928983999, 65392069094065, 539711448752906, 4489189106832134, 39604974257078180, 404561197077466250

Offset: 2

Alois P. Heinz, Apr 13 2016

nonn

At least one block length occurs exactly 2 times, and all block lengths occur at most 2 times.

Alois P. Heinz, Table of n, a(n) for n = 2..648
Wikipedia, Partition of a set

Column k=2 of A271423.

with(combinat):
b:= proc(n, i, k) option remember; `if`(n=0, 1,
      `if`(i<1, 0, add(multinomial(n, n-i*j, i$j)
        *b(n-i*j, i-1, k)/j!, j=0..min(k, n/i))))
    end:
a:= n-> b(n$2, 2)-b(n$2, 1):
seq(a(n), n=2..30);

multinomial[n_, k_List] := n!/Times @@ (k!);
b[n_, i_, k_] := b[n, i, k] = If[n == 0, 1, If[i < 1, 0, Sum[multinomial[n, Join[{n - i*j}, Table[i, j]]]*b[n - i*j, i - 1, k]/j!, {j, 0, Min[k, n/i] }]]];
a[n_] := b[n, n, 2] - b[n, n, 1];
Table[a[n], {n, 2, 30}] (* Jean-François Alcover, May 08 2018, after Alois P. Heinz *)

A271732 Number of set partitions of [n] with maximal block length multiplicity equal to three.

Original entry on oeis.org

1, 0, 10, 35, 245, 1036, 4984, 37990, 242330, 1387595, 10324457, 73271562, 550531436, 3836993356, 32056517432, 271603606580, 2249464283038, 18909114389770, 173349802631034, 1639551357457112, 15220220305707538, 147729311772991971, 1423109890697311335

Offset: 3

Alois P. Heinz, Apr 13 2016

nonn

At least one block length occurs exactly 3 times, and all block lengths occur at most 3 times.

Alois P. Heinz, Table of n, a(n) for n = 3..626
Wikipedia, Partition of a set

Column k=3 of A271423.

with(combinat):
b:= proc(n, i, k) option remember; `if`(n=0, 1,
      `if`(i<1, 0, add(multinomial(n, n-i*j, i$j)
        *b(n-i*j, i-1, k)/j!, j=0..min(k, n/i))))
    end:
a:= n-> b(n$2, 3)-b(n$2, 2):
seq(a(n), n=3..30);

multinomial[n_, k_List] := n!/Times @@ (k!);
b[n_, i_, k_] := b[n, i, k] = If[n == 0, 1, If[i < 1, 0, Sum[multinomial[n, Join[{n - i*j}, Table[i, j]]]*b[n - i*j, i - 1, k]/j!, {j, 0, Min[k, n/i] }]]];
a[n_] := b[n, n, 3] - b[n, n, 2];
Table[a[n], {n, 3, 30}] (* Jean-François Alcover, May 08 2018, after Alois P. Heinz *)

A271733 Number of set partitions of [n] with maximal block length multiplicity equal to four.

Original entry on oeis.org

1, 0, 15, 35, 385, 2331, 13335, 88110, 629200, 4811235, 35992957, 276332420, 2325570065, 20036259075, 171879027000, 1583318184855, 14476456463826, 139849724906591, 1347082690705367, 13909222770509990, 144001190692525628, 1519193757875044900

Offset: 4

Alois P. Heinz, Apr 13 2016

nonn

At least one block length occurs exactly 4 times, and all block lengths occur at most 4 times.

Alois P. Heinz, Table of n, a(n) for n = 4..612
Wikipedia, Partition of a set

Column k=4 of A271423.

with(combinat):
b:= proc(n, i, k) option remember; `if`(n=0, 1,
      `if`(i<1, 0, add(multinomial(n, n-i*j, i$j)
        *b(n-i*j, i-1, k)/j!, j=0..min(k, n/i))))
    end:
a:= n-> b(n$2, 4)-b(n$2, 3):
seq(a(n), n=4..30);

multinomial[n_, k_List] := n!/Times @@ (k!);
b[n_, i_, k_] := b[n, i, k] = If[n == 0, 1, If[i < 1, 0, Sum[multinomial[n, Join[{n - i*j}, Table[i, j]]]*b[n - i*j, i - 1, k]/j!, {j, 0, Min[k, n/i] }]]];
a[n_] := b[n, n, 4] - b[n, n, 3];
Table[a[n], {n, 4, 30}] (* Jean-François Alcover, May 08 2018, after Alois P. Heinz *)

A271734 Number of set partitions of [n] with maximal block length multiplicity equal to five.

Original entry on oeis.org

1, 0, 21, 56, 504, 3717, 29337, 190674, 1460745, 12532520, 100025926, 845104624, 7657043576, 69364078980, 657324748866, 6374275533525, 64070264089020, 653567576544498, 6979149079277683, 74951288500334708, 835338959385664426, 9373747854520238761

Offset: 5

Alois P. Heinz, Apr 13 2016

nonn

At least one block length occurs exactly 5 times, and all block lengths occur at most 5 times.

Alois P. Heinz, Table of n, a(n) for n = 5..603
Wikipedia, Partition of a set

Column k=5 of A271423.

with(combinat):
b:= proc(n, i, k) option remember; `if`(n=0, 1,
      `if`(i<1, 0, add(multinomial(n, n-i*j, i$j)
        *b(n-i*j, i-1, k)/j!, j=0..min(k, n/i))))
    end:
a:= n-> b(n$2, 5)-b(n$2, 4):
seq(a(n), n=5..30);

multinomial[n_, k_List] := n!/Times @@ (k!);
b[n_, i_, k_] := b[n, i, k] = If[n == 0, 1, If[i < 1, 0, Sum[multinomial[n, Join[{n - i*j}, Table[i, j]]]*b[n - i*j, i - 1, k]/j!, {j, 0, Min[k, n/i] }]]];
a[n_] := b[n, n, 5] - b[n, n, 4];
Table[a[n], {n, 5, 30}] (* Jean-François Alcover, May 08 2018, after Alois P. Heinz *)

A271735 Number of set partitions of [n] with maximal block length multiplicity equal to six.

Original entry on oeis.org

1, 0, 28, 84, 840, 5082, 48279, 413127, 3093090, 26601575, 255431176, 2309491548, 20998179748, 209051155600, 2137087555220, 21652990622410, 230200208290745, 2517313465793819, 28104615964752327, 320432370881428575, 3760667223506993800, 45094960570293757695

Offset: 6

Alois P. Heinz, Apr 13 2016

nonn

At least one block length occurs exactly 6 times, and all block lengths occur at most 6 times.

Alois P. Heinz, Table of n, a(n) for n = 6..597
Wikipedia, Partition of a set

Column k=6 of A271423.

with(combinat):
b:= proc(n, i, k) option remember; `if`(n=0, 1,
      `if`(i<1, 0, add(multinomial(n, n-i*j, i$j)
        *b(n-i*j, i-1, k)/j!, j=0..min(k, n/i))))
    end:
a:= n-> b(n$2, 6)-b(n$2, 5):
seq(a(n), n=6..30);

multinomial[n_, k_List] := n!/Times @@ (k!);
b[n_, i_, k_] := b[n, i, k] = If[n == 0, 1, If[i < 1, 0, Sum[multinomial[n, Join[{n - i*j}, Table[i, j]]]*b[n - i*j, i - 1, k]/j!, {j, 0, Min[k, n/i] }]]];
a[n_] := b[n, n, 6] - b[n, n, 5];
Table[a[n], {n, 6, 30}] (* Jean-François Alcover, May 08 2018, after Alois P. Heinz *)

A271736 Number of set partitions of [n] with maximal block length multiplicity equal to seven.

Original entry on oeis.org

1, 0, 36, 120, 1320, 8712, 70356, 691119, 6628050, 55398200, 528441056, 5607882072, 55953959256, 559256993400, 6033783063160, 66852986570260, 743874599106485, 8455383000184208, 100088596628849400, 1202568046655647100, 14764362076427728050

Offset: 7

Alois P. Heinz, Apr 13 2016

nonn

At least one block length occurs exactly 7 times, and all block lengths occur at most 7 times.

Alois P. Heinz, Table of n, a(n) for n = 7..592
Wikipedia, Partition of a set

Column k=7 of A271423.

with(combinat):
b:= proc(n, i, k) option remember; `if`(n=0, 1,
      `if`(i<1, 0, add(multinomial(n, n-i*j, i$j)
        *b(n-i*j, i-1, k)/j!, j=0..min(k, n/i))))
    end:
a:= n-> b(n$2, 7)-b(n$2, 6):
seq(a(n), n=7..30);

multinomial[n_, k_List] := n!/Times @@ (k!);
b[n_, i_, k_] := b[n, i, k] = If[n == 0, 1, If[i < 1, 0, Sum[multinomial[n, Join[{n - i*j}, Table[i, j]]]*b[n - i*j, i - 1, k]/j!, {j, 0, Min[k, n/i] }]]];
a[n_] := b[n, n, 7] - b[n, n, 6];
Table[a[n], {n, 7, 30}] (* Jean-François Alcover, May 08 2018, after Alois P. Heinz *)

cp's OEIS Frontend

A007837 Number of partitions of n-set with distinct block sizes.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

Extensions

A271424 Number T(n,k) of set partitions of [n] with minimal block length multiplicity equal to k; triangle T(n,k), n>=0, 0<=k<=n, read by rows.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

A271425 Number of set partitions of [2n] with maximal block length multiplicity equal to n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A360182 Number of partitions of [n] where each block size occurs at most twice.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A271731 Number of set partitions of [n] with maximal block length multiplicity equal to two.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

A271732 Number of set partitions of [n] with maximal block length multiplicity equal to three.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

A271733 Number of set partitions of [n] with maximal block length multiplicity equal to four.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

A271734 Number of set partitions of [n] with maximal block length multiplicity equal to five.