A038041 -id:A038041 - cp's OEIS frontend

A336137 Number of set partitions of the binary indices of n with equal block-sums.

1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 2, 1, 2, 1, 1, 1, 1, 1, 1, 2, 1, 1, 2, 1, 2, 1, 1, 2, 2, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 2, 1, 1, 2, 1, 2, 1, 2, 1, 2, 1, 1, 2, 1, 1, 1, 1, 3, 2, 1, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 1, 1, 1, 1, 1, 2, 1, 1, 2, 1

Offset: 0

Gus Wiseman, Jul 12 2020

nonn

A binary index of n is any position of a 1 in its reversed binary expansion. The binary indices of n are row n of A048793.

			The a(n) set partitions for n = 7, 59, 119, 367, 127:
  {123}    {12456}      {123567}      {1234679}    {1234567}
  {12}{3}  {126}{45}    {1236}{57}    {12346}{79}  {1247}{356}
           {15}{24}{6}  {156}{237}    {1249}{367}  {1256}{347}
                        {17}{26}{35}  {1267}{349}  {1346}{257}
                                      {169}{2347}  {167}{2345}
                                                   {16}{25}{34}{7}
The binary indices of 382 are {2,3,4,5,6,7,9}, with equal block-sum set partitions:
  {{2,7},{3,6},{4,5},{9}}
  {{2,4,6},{3,9},{5,7}}
  {{2,7,9},{3,4,5,6}}
  {{2,3,4,9},{5,6,7}}
  {{2,3,6,7},{4,5,9}}
  {{2,4,5,7},{3,6,9}}
  {{2,3,4,5,6,7,9}}
so a(382) = 7.

Gus Wiseman, Sequences counting and ranking multiset partitions whose part lengths, sums, or averages are constant or strict.

These set partitions are counted by A035470.
The version for twice-partitions is A279787.
The version for partitions of partitions is A305551.
The version for factorizations is A321455.
The version for normal multiset partitions is A326518.
The version for distinct block-sums is A336138.
Set partitions of binary indices are A050315.
Normal multiset partitions with equal lengths are A317583.
Normal multiset partitions with equal averages are A326520.
Multiset partitions with equal block-sums are ranked by A326534.
Cf. A000110, A007837, A032011, A038041, A271619, A275780, A322794.

bpe[n_]:=Join@@Position[Reverse[IntegerDigits[n,2]],1];
sps[{}]:={{}};sps[set:{i_,_}]:=Join@@Function[s,Prepend[#,s]&/@sps[Complement[set,s]]]/@Cases[Subsets[set],{i,_}];
Table[Length[Select[sps[bpe[n]],SameQ@@Total/@#&]],{n,0,100}]

A358905 Number of sequences of integer partitions with total sum n that are rectangular, meaning all lengths are equal.

Original entry on oeis.org

1, 1, 3, 6, 13, 24, 49, 91, 179, 341, 664, 1280, 2503, 4872, 9557, 18750, 36927, 72800, 143880, 284660, 564093, 1118911, 2221834, 4415417, 8781591, 17476099, 34799199, 69327512, 138176461, 275503854, 549502119, 1096327380, 2187894634, 4367310138, 8719509111

Offset: 0

Gus Wiseman, Dec 07 2022

nonn

			The a(0) = 1 through a(4) = 13 sequences:
  ()  ((1))  ((2))     ((3))        ((4))
             ((11))    ((21))       ((22))
             ((1)(1))  ((111))      ((31))
                       ((1)(2))     ((211))
                       ((2)(1))     ((1111))
                       ((1)(1)(1))  ((1)(3))
                                    ((2)(2))
                                    ((3)(1))
                                    ((11)(11))
                                    ((1)(1)(2))
                                    ((1)(2)(1))
                                    ((2)(1)(1))
                                    ((1)(1)(1)(1))

Andrew Howroyd, Table of n, a(n) for n = 0..1000

The case of set partitions is A038041.
The version for weakly decreasing lengths is A141199, strictly A358836.
For equal sums instead of lengths we have A279787.
The case of twice-partitions is A306319, distinct A358830.
The unordered version is A319066.
The case of plane partitions is A323429.
The case of constant sums also is A358833.
A055887 counts sequences of partitions with total sum n.
A281145 counts same-trees.
A319169 counts partitions with constant Omega, ranked by A320324.
A358911 counts compositions with constant Omega, distinct A358912.
Cf. A000041, A000219, A001970, A063834, A218482, A305551, A358835.

ptnseq[n_]:=Join@@Table[Tuples[IntegerPartitions/@comp],{comp,Join@@Permutations/@IntegerPartitions[n]}];
Table[Length[Select[ptnseq[n],SameQ@@Length/@#&]],{n,0,10}]

P(n,y) = {1/prod(k=1, n, 1 - y*x^k + O(x*x^n))}
seq(n) = {my(g=P(n,y)); Vec(1 + sum(k=1, n, 1/(1 - polcoef(g, k, y)) - 1))} \\ Andrew Howroyd, Dec 31 2022

G.f.: 1 + Sum_{k>=1} (1/(1 - [y^k]P(x,y)) - 1) where P(x,y) = 1/Product_{k>=1} (1 - y*x^k). - Andrew Howroyd, Dec 31 2022

Terms a(16) and beyond from Andrew Howroyd, Dec 31 2022

A382429 Number of normal multiset partitions of weight n into sets with a common sum.

Original entry on oeis.org

1, 1, 2, 3, 5, 7, 13, 26, 57, 113, 283, 854, 2401, 6998, 24072, 85061, 308956, 1190518, 4770078, 19949106, 87059592

Offset: 0

Gus Wiseman, Mar 26 2025

We call a multiset or multiset partition normal iff it covers an initial interval of positive integers. The weight of a multiset partition is the sum of sizes of its blocks.

			The a(1) = 1 through a(6) = 13 partitions:
  {1} {12}   {123}     {1234}       {12345}         {123456}
      {1}{1} {3}{12}   {12}{12}     {24}{123}       {123}{123}
             {1}{1}{1} {14}{23}     {34}{124}       {125}{134}
                       {3}{3}{12}   {3}{12}{12}     {135}{234}
                       {1}{1}{1}{1} {5}{14}{23}     {145}{235}
                                    {3}{3}{3}{12}   {12}{12}{12}
                                    {1}{1}{1}{1}{1} {14}{14}{23}
                                                    {14}{23}{23}
                                                    {16}{25}{34}
                                                    {3}{3}{12}{12}
                                                    {5}{5}{14}{23}
                                                    {3}{3}{3}{3}{12}
                                                    {1}{1}{1}{1}{1}{1}
The corresponding factorizations:
  2  6    30     210      2310       30030
     2*2  5*6    6*6      21*30      30*30
          2*2*2  14*15    35*42      6*6*6
                 5*5*6    5*6*6      66*70
                 2*2*2*2  5*5*5*6    110*105
                          11*14*15   154*165
                          2*2*2*2*2  5*5*6*6
                                     14*14*15
                                     14*15*15
                                     26*33*35
                                     5*5*5*5*6
                                     11*11*14*15
                                     2*2*2*2*2*2

Without the common sum we have A116540 (normal set multipartitions).
Twice-partitions of this type are counted by A279788.
For common sizes instead of sums we have A317583.
Without strict blocks we have A326518, non-strict blocks A326517.
For a common length instead of sum we have A331638.
For distinct instead of equal block-sums we have A381718.
Factorizations of this type are counted by A382080.
For distinct block-sums and constant blocks we have A382203.
For constant instead of strict blocks we have A382204.
A000670 counts patterns, ranked by A055932 and A333217, necklace A019536.
A001055 count multiset partitions of prime indices, strict A045778.
A321469 counts multiset partitions with distinct block-sums, ranks A326535.
Normal multiset partitions: A035310, A255906, A304969, A317532.
Set multipartitions: A089259, A116539, A270995, A296119, A318360.
Set multipartitions with distinct sums: A279785, A381806, A381870.
Constant blocks with distinct sums: A381635, A381636, A381716.
Cf. A000110, A034691, A038041, A050320, A255903, A326520, A381633, A381996, A382214, A382216.

allnorm[n_Integer]:=Function[s,Array[Count[s,y_/;y<=#]+1&,n]]/@Subsets[Range[n-1]+1];
sps[{}]:={{}};sps[set:{i_,_}]:=Join@@Function[s,Prepend[#,s]&/@sps[Complement[set,s]]]/@Cases[Subsets[set],{i,_}];
mps[mset_]:=Union[Sort[Sort/@(#/.x_Integer:>mset[[x]])]&/@sps[Range[Length[mset]]]];
Table[Length[Join@@(Select[mps[#],SameQ@@Total/@#&&And@@UnsameQ@@@#&]&/@allnorm[n])],{n,0,5}]

a(11) from Robert Price, Mar 30 2025

a(12)-a(20) from Christian Sievers, Apr 06 2025

A194560 G.f.: Sum_{n>=1} G_n(x)^n where G_n(x) = x + x*G_n(x)^n.

Original entry on oeis.org

1, 2, 2, 4, 2, 10, 2, 20, 14, 49, 2, 217, 2, 438, 310, 1580, 2, 6352, 2, 18062, 7824, 58799, 2, 258971, 2532, 742915, 246794, 2729095, 2, 11154954, 2, 35779660, 8414818, 129644809, 242354, 531132915, 2, 1767263211, 300830821, 6593815523, 2, 26289925026, 2, 91708135773

Offset: 1

Paul D. Hanna, Aug 28 2011

nonn

Number of Dyck n-paths with all ascents of equal length. - David Scambler, Nov 17 2011
From Gus Wiseman, Feb 15 2019: (Start)
Also the number of uniform (all blocks have the same size) non-crossing set partitions of {1,...,n}. For example, the a(3) = 2 through a(6) = 10 uniform non-crossing set partitions are:
  {{123}}      {{1234}}        {{12345}}          {{123456}}
  {{1}{2}{3}}  {{12}{34}}      {{1}{2}{3}{4}{5}}  {{123}{456}}
               {{14}{23}}                         {{126}{345}}
               {{1}{2}{3}{4}}                     {{156}{234}}
                                                  {{12}{34}{56}}
                                                  {{12}{36}{45}}
                                                  {{14}{23}{56}}
                                                  {{16}{23}{45}}
                                                  {{16}{25}{34}}
                                                  {{1}{2}{3}{4}{5}{6}}
(End)

			G.f.: A(x) = x + 2*x^2 + 2*x^3 + 4*x^4 + 2*x^5 + 10*x^6 + 2*x^7 + ...
where
A(x) = G_1(x) + G_2(x)^2 + G_3(x)^3 + G_4(x)^4 + G_5(x)^5 + ...
and G_n(x) = x + x*G_n(x)^n is given by:
G_n(x) = Sum_{k>=0} C(n*k+1,k)/(n*k+1)*x^(n*k+1),
G_n(x)^n = Sum_{k>=1} C(n*k,k)/(n*k-k+1)*x^(n*k);
the first few expansions of G_n(x)^n begin:
G_1(x) = x + x^2 + x^3 + x^4 + x^5 + ...
G_2(x)^2 = x^2 + 2*x^4 + 5*x^6 + 14*x^8 + ... + A000108(n)*x^(2*n) + ...
G_3(x)^3 = x^3 + 3*x^6 + 12*x^9 + 55*x^12 + ... + A001764(n)*x^(3*n) + ...
G_4(x)^4 = x^4 + 4*x^8 + 22*x^12 + 140*x^16 + ... + A002293(n)*x^(4*n) + ...
G_5(x)^5 = x^5 + 5*x^10 + 35*x^15 + 285*x^20 + ... + A002294(n)*x^(5*n) + ...

Paul D. Hanna, Table of n, a(n) for n = 1..1000
Eric Weisstein's World of Mathematics, Dyck Path.
Wikipedia, Noncrossing partition.

Row sums of A306437.

Cf. A000108, A001263, A001764, A016098, A038041, A061095, A125181, A134264, A194558, A306418, A306438.

Table[Sum[Binomial[n,d]/(n-d+1),{d,Divisors[n]}],{n,20}] (* Gus Wiseman, Feb 15 2019 *)

{a(n)=if(n<1,0,sumdiv(n,d,binomial(n,d)/(n-d+1)))}

{a(n)=polcoeff(sum(m=1,n,serreverse(x/(1+x^m+x*O(x^n)))^m),n)}

a(n) = Sum_{d|n} C(n,d)/(n-d+1).

G.f.: Sum_{n>=1} Series_Reversion( x/(1+x^n) )^n.

A236696 Number of forests on n vertices consisting of labeled rooted trees of the same size.

Original entry on oeis.org

1, 3, 10, 77, 626, 8707, 117650, 2242193, 43250842, 1049248991, 25937424602, 772559330281, 23298085122482, 817466439388341, 29223801257127976, 1181267018656911617, 48661191875666868482, 2232302772999145783735, 104127350297911241532842

Offset: 1

Emanuele Munarini, Jan 30 2014

nonn

			For n = 3 we have the following 10 forests (where the roots are denoted by ^):
                              3  2  3  1  2  1
                              |  |  |  |  |  |
         2   3  1   3  1   2  2  3  1  3  1  2
          \ /    \ /    \ /   |  |  |  |  |  |
  1 2 3    1      2      3    1  1  2  2  3  3
  ^ ^ ^,   ^,     ^,     ^,   ^, ^, ^, ^, ^, ^

Alois P. Heinz, Table of n, a(n) for n = 1..200

Cf. A000169, A038041, A005225, A055225.

Table[Sum[n!/(n/d)!*(d^(d-1)/d!)^(n/d), {d,Divisors[n]}], {n,1,100}]

a(n):= lsum(n!/(n/d)!*(d^(d-1)/d!)^(n/d),d,listify(divisors(n))); makelist(a(n),n,1,40); /* Emanuele Munarini, Feb 03 2014 */

a(n) = sum(d divides n, n!/(n/d)!*(d^(d-1)/d!)^(n/d) ).

E.g.f.: sum(k>=1, exp(k^(k-1)*x^k/k!)).

A275313 Number of set partitions of [n] where adjacent blocks differ in size.

Original entry on oeis.org

1, 1, 1, 4, 7, 23, 100, 333, 1443, 6910, 36035, 186958, 1095251, 6620976, 42151463, 290483173, 2030271491, 15044953241, 116044969497, 930056879535, 7749440529803, 66931578540965, 597728811956244, 5511695171795434, 52578231393128128, 515775207055816041

Offset: 0

Alois P. Heinz, Jul 22 2016

nonn

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

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

Cf. A007837, A038041, A275309, A275310, A275311, A275312, A275679, A280275, A286072.

b:= proc(n, i) option remember; `if`(n=0, 1, add(`if`(i=j, 0,
      b(n-j, `if`(j>n-j, 0, j))*binomial(n-1, j-1)), j=1..n))
    end:
a:= n-> b(n, 0):
seq(a(n), n=0..35);

b[n_, i_] := b[n, i] = If[n==0, 1, Sum[If[i==j, 0, b[n-j, If[j>n-j, 0, j]]* Binomial[n-1, j-1]], {j, 1, n}]]; a[n_] := b[n, 0]; Table[a[n], {n, 0, 35}] (* Jean-François Alcover, Dec 18 2016, after Alois P. Heinz *)

A326536 MM-numbers of multiset partitions where every part has the same average.

Original entry on oeis.org

1, 2, 3, 4, 5, 7, 8, 9, 11, 13, 16, 17, 19, 21, 23, 25, 27, 29, 31, 32, 37, 41, 43, 47, 49, 53, 57, 59, 61, 63, 64, 67, 71, 73, 79, 81, 83, 89, 97, 101, 103, 107, 109, 113, 115, 121, 125, 127, 128, 131, 133, 137, 139, 145, 147, 149, 151, 157, 159, 163, 167

Offset: 1

Gus Wiseman, Jul 12 2019

nonn

First differs from A322902 in having 145.

These are numbers where each prime index has the same average of prime indices. A prime index of n is a number m such that prime(m) divides n. The multiset of prime indices of n is row n of A112798. The multiset multisystem with MM-number n is obtained by taking the multiset of prime indices of each prime index of n. For example, the prime indices of 78 are {1,2,6}, so the multiset multisystem with MM-number 78 is {{},{1},{1,2}}.

			The sequence of multiset partitions where every part has the same average, preceded by their MM-numbers, begins:
   1: {}
   2: {{}}
   3: {{1}}
   4: {{},{}}
   5: {{2}}
   7: {{1,1}}
   8: {{},{},{}}
   9: {{1},{1}}
  11: {{3}}
  13: {{1,2}}
  16: {{},{},{},{}}
  17: {{4}}
  19: {{1,1,1}}
  21: {{1},{1,1}}
  23: {{2,2}}
  25: {{2},{2}}
  27: {{1},{1},{1}}
  29: {{1,3}}
  31: {{5}}
  32: {{},{},{},{},{}}

Gus Wiseman, Sequences counting and ranking multiset partitions whose part lengths, sums, or averages are constant or strict.

Cf. A038041, A051293, A112798, A302242, A320324, A326512, A326515, A326520, A326533, A326534, A326535, A326537.

primeMS[n_]:=If[n==1,{},Flatten[Cases[FactorInteger[n],{p_,k_}:>Table[PrimePi[p],{k}]]]];
Select[Range[100],SameQ@@Mean/@primeMS/@primeMS[#]&]

A132962 a(n) = n!Sum_{d|n} (-1)^(d+1)/(d!(n/d)!^d).

Original entry on oeis.org

1, 0, 2, -3, 2, 5, 2, -140, 282, 819, 2, -20482, 2, 133419, 1527528, -4661085, 2, -153296429, 2, 1402482796, 36278688162, 13748957859, 2, -14081800718427, 5194672859378, 7905848380325, 2977584150505252, 12956452725792600, 2, -1314647260913859151

Offset: 1

Vladeta Jovovic, Sep 06 2007

G. C. Greubel, Table of n, a(n) for n = 1..500

Cf. A038041, A132958, A132959, A132960, A132961, A132963.

Rest[ Range[0, 30]! CoefficientList[ Series[ Sum[1 - Exp[ -x^k/k! ], {k, 30}], {x, 0, 30}], x]] (* Robert G. Wilson v, Sep 13 2007 *)

a(n) = n!*sumdiv(n, d, (-1)^(d+1)/(d!*(n/d)!^d)); \\ Michel Marcus, Sep 29 2017

E.g.f.: Sum_{k>0}(1-exp(-x^k/k!)).

More terms from Robert G. Wilson v, Sep 13 2007

A275309 Number of set partitions of [n] with decreasing block sizes.

Original entry on oeis.org

1, 1, 1, 3, 4, 11, 36, 82, 239, 821, 3742, 10328, 42934, 156070, 729249, 4025361, 15032099, 68746675, 334541624, 1645575386, 9104991312, 65010298257, 282768687257, 1616844660914, 8660050947383, 53262316928024, 309119883729116, 2185141720645817

Offset: 0

Alois P. Heinz, Jul 22 2016

nonn

			a(3) = 3: 123, 12|3, 13|2.
a(4) = 4: 1234, 123|4, 124|3, 134|2.
a(5) = 11: 12345, 1234|5, 1235|4, 123|45, 1245|3, 124|35, 125|34, 1345|2, 134|25, 135|24, 145|23.

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

Cf. A007837, A038041, A275310, A275311, A275312, A275313, A286073.

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

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

A275310 Number of set partitions of [n] with nonincreasing block sizes.

Original entry on oeis.org

1, 1, 2, 4, 11, 30, 102, 346, 1353, 5444, 24170, 110082, 546075, 2777828, 15099359, 84491723, 499665713, 3035284304, 19375261490, 126821116410, 866293979945, 6072753348997, 44193947169228, 329387416656794, 2542173092336648, 20069525888319293

Offset: 0

Alois P. Heinz, Jul 22 2016

nonn

			a(3) = 4: 123, 12|3, 13|2, 1|2|3.
a(4) = 11: 1234, 123|4, 124|3, 12|34, 12|3|4, 134|2, 13|24, 13|2|4, 14|23, 14|2|3, 1|2|3|4.

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

Cf. A007837, A038041, A275309, A275311, A275312, A275313, A286071.

b:= proc(n, i) option remember; `if`(n=0, 1, add(
      b(n-j, j)*binomial(n-1, j-1), j=1..min(n, i)))
    end:
a:= n-> b(n$2):
seq(a(n), n=0..35);

b[n_, i_] := b[n, i] = If[n==0, 1, Sum[b[n-j, j]*Binomial[n-1, j-1], {j, 1, Min[n, i]}]]; a[n_] := b[n, n]; Table[a[n], {n, 0, 35}] (* Jean-François Alcover, Feb 02 2017, translated from Maple *)

cp's OEIS Frontend

A336137 Number of set partitions of the binary indices of n with equal block-sums.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A358905 Number of sequences of integer partitions with total sum n that are rectangular, meaning all lengths are equal.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A382429 Number of normal multiset partitions of weight n into sets with a common sum.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Extensions

A194560 G.f.: Sum_{n>=1} G_n(x)^n where G_n(x) = x + x*G_n(x)^n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

PARI

Formula

A236696 Number of forests on n vertices consisting of labeled rooted trees of the same size.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

Maxima

Formula

A275313 Number of set partitions of [n] where adjacent blocks differ in size.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

A326536 MM-numbers of multiset partitions where every part has the same average.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A132962 a(n) = n!*Sum_{d|n} (-1)^(d+1)/(d!*(n/d)!^d).

Views

Author

A132962 a(n) = n!Sum_{d|n} (-1)^(d+1)/(d!(n/d)!^d).