A075900 -id:A075900 - cp's OEIS frontend

A063834 Twice partitioned numbers: the number of ways a number can be partitioned into not necessarily different parts and each part is again so partitioned.

1, 1, 3, 6, 15, 28, 66, 122, 266, 503, 1027, 1913, 3874, 7099, 13799, 25501, 48508, 88295, 165942, 299649, 554545, 997281, 1817984, 3245430, 5875438, 10410768, 18635587, 32885735, 58399350, 102381103, 180634057, 314957425, 551857780, 958031826, 1667918758

Offset: 0

Wouter Meeussen, Aug 21 2001

These are different from plane partitions.
For ordered partitions of partitions see A055887 which may be computed from A036036 and A048996. - Alford Arnold, May 19 2006
Twice partitioned numbers correspond to triangles (or compositions) in the multiorder of integer partitions. - Gus Wiseman, Oct 28 2015

			G.f. = 1 + x + 3*x^2 + 6*x^3 + 15*x^4 + 28*x^5 + 66*x^6 + 122*x^7 + 266*x^8 + ...
If n=6, a possible first partitioning is (3+3), resulting in the following second partitionings: ((3),(3)), ((3),(2+1)), ((3),(1+1+1)), ((2+1),(3)), ((2+1),(2+1)), ((2+1),(1+1+1)), ((1+1+1),(3)), ((1+1+1),(2+1)), ((1+1+1),(1+1+1)).

Alois P. Heinz, Table of n, a(n) for n = 0..5000 (terms n=1..500 from T. D. Noe)
Vaclav Kotesovec, Screenshot - A closed form formula for the constant c
Gus Wiseman, Comcategories and Multiorders
Gus Wiseman, Sequences enumerating triangles of integer partitions
Gus Wiseman, On the Categorical Structure of Weakly Ordered Sequences of Integer Partitions

Cf. A063835, A196545.
Cf. A036036, A048996, A055887.
Cf. A006906, A270995.
Cf. A007425, A047966, A047968, A271619, A279375, A279784-A279791.
The strict case is A296122.
Row sums of A321449.
Column k=2 of A323718.
Without singletons we have A327769, A358828, A358829.
For odd lengths we have A358823, A358824.
For distinct lengths we have A358830, A358912.
For strict partitions see A358914, A382524.
A000041 counts integer partitions, strict A000009.
A001970 counts multiset partitions of integer partitions.
Cf. A075900, A358831, A358833, A358906, A358908, A358909.

with(combinat):
b:= proc(n, i) option remember; `if`(n=0 or i=1, 1,
      b(n, i-1)+`if`(i>n, 0, numbpart(i)*b(n-i, i)))
    end:
a:= n-> b(n$2):
seq(a(n), n=0..50);  # Alois P. Heinz, Nov 26 2015

Table[Plus @@ Apply[Times, IntegerPartitions[i] /. i_Integer :> PartitionsP[i], 2], {i, 36}]
(* second program: *)
b[n_, i_] := b[n, i] = If[n==0 || i==1, 1, b[n, i-1] + If[i > n, 0, PartitionsP[i]*b[n-i, i]]]; a[n_] := b[n, n]; Table[a[n], {n, 0, 50}] (* Jean-François Alcover, Jan 20 2016, after Alois P. Heinz *)

{a(n) = if( n<0, 0, polcoeff( 1 / prod(k=1, n, 1 - numbpart(k) * x^k, 1 + x * O(x^n)), n))}; /* Michael Somos, Dec 19 2016 */

G.f.: 1/Product_{k>0} (1-A000041(k)*x^k). n*a(n) = Sum_{k=1..n} b(k)*a(n-k), a(0) = 1, where b(k) = Sum_{d|k} d*A000041(d)^(k/d) = 1, 5, 10, 29, 36, 110, 106, ... . - Vladeta Jovovic, Jun 19 2003
From Vaclav Kotesovec, Mar 27 2016: (Start)
a(n) ~ c * 5^(n/4), where
c = 96146522937.7161898848278970039269600938032826... if n mod 4 = 0
c = 96146521894.9433858914667933636782092683849082... if n mod 4 = 1
c = 96146522937.2138934755566928890704687838407524... if n mod 4 = 2
c = 96146521894.8218716328341714149619262713426755... if n mod 4 = 3
(End)

a(0)=1 prepended by Alois P. Heinz, Nov 26 2015

A133494 Diagonal of the array of iterated differences of A047848.

Original entry on oeis.org

1, 1, 3, 9, 27, 81, 243, 729, 2187, 6561, 19683, 59049, 177147, 531441, 1594323, 4782969, 14348907, 43046721, 129140163, 387420489, 1162261467, 3486784401, 10460353203, 31381059609, 94143178827, 282429536481, 847288609443, 2541865828329, 7625597484987, 22876792454961, 68630377364883

Offset: 0

Paul Barry, Paul Curtz, Dec 23 2007

a(n) is the number of ways to choose a composition C, and then choose a composition of each part of C. - Geoffrey Critzer, Mar 19 2012
a(n) is the top left entry of the n-th power of the 3 X 3 matrix [1, 1, 1; 1, 1, 1; 1, 1, 1]. - R. J. Mathar, Feb 03 2014
a(n) is the reptend length of 1/3^(n+1) in decimal. - Jianing Song, Nov 14 2018
Also the number of pairs of integer compositions, the first summing to n and the second with sum equal to the length of the first. If an integer composition is regarded as an arrow from sum to length, these are composable pairs, and the obvious composition operation founds a category of integer compositions. For example, we have (2,1,1,4) . (1,2,1) . (1,2) = (2,6), where dots represent the composition operation. The version without empty compositions is A000244. Composable triples are counted by 1 followed by A000302. The unordered version is A022811. - Gus Wiseman, Jul 14 2022

			From _Gus Wiseman_, Jul 15 2020: (Start)
The a(0) = 1 through a(3) = 9 ways to choose a composition of each part of a composition:
  ()  (1)  (2)      (3)
           (1,1)    (1,2)
           (1),(1)  (2,1)
                    (1,1,1)
                    (1),(2)
                    (2),(1)
                    (1),(1,1)
                    (1,1),(1)
                    (1),(1),(1)
(End)

G. C. Greubel, Table of n, a(n) for n = 0..1000
Bishal Deb, Cyclic sieving phenomena via combinatorics of continued fractions, arXiv:2508.13709 [math.CO], 2025. See p. 42.
Index entries for linear recurrences with constant coefficients, signature (3).

The strict version is A336139.
Splittings of partitions are A323583.
Multiset partitions of partitions are A001970.
Partitions of each part of a partition are A063834.
Compositions of each part of a partition are A075900.
Strict partitions of each part of a strict partition are A279785.
Compositions of each part of a strict partition are A304961.
Strict compositions of each part of a composition are A307068.
Compositions of each part of a strict composition are A336127.
Cf. A000012, A000244, A000302, A001906, A006951, A011782, A022811, A071919.
Cf. A072706, A078008, A112467, A182105, A316245, A336128, A336135.
Cf. A339006, A355382, A355384, A355387.

[n eq 0 select 1 else 3^(n-1): n in [0..30]]; // G. C. Greubel, Nov 20 2023

a:= n-> ceil(3^(n-1)):
seq(a(n), n=0..30);  # Alois P. Heinz, Jul 26 2020

CoefficientList[Series[(1 - 2 x)/(1 - 3 x), {x, 0, 50}], x] (* Vladimir Joseph Stephan Orlovsky, Jun 21 2011 *)
Join[{1}, 3^(Range[0, 30])] (* G. C. Greubel, Nov 20 2023 *)

a(n)=max(1,3^(n-1)) \\ Charles R Greathouse IV, Jul 07 2011

Vec((1-2*x)/(1-3*x) + O(x^100)) \\  Altug Alkan, Oct 30 2015

[(3^n + 2*int(n==0))//3 for n in range(31)] # G. C. Greubel, Nov 20 2023

Binomial transform of A078008. - Paul Curtz, Aug 04 2008
From R. J. Mathar, Nov 11 2008: (Start)
G.f.: (1 - 2*x)/(1 - 3*x).
a(n) = A000244(n-1), n > 0. (End)
From Philippe Deléham, Nov 13 2008: (Start)
a(n) = Sum_{k=0..n} A112467(n,k)*2^k.
a(n) = Sum_{k=0..n} A071919(n,k)*2^k. (End)
Let A(x) be the g.f. Then B(x) = x*A(x) satisfies B(x/(1-x)) = x/(1 - 2*B(x)). - Vladimir Kruchinin, Dec 05 2011
G.f.: 1/(1 - (Sum_{k>=1} (x/(1 - x))^k)). - Joerg Arndt, Sep 30 2012
For n > 0, a(n) = 2*(Sum_{k=0..n-1} a(k)) - 1 = 3^(n-1). - J. Conrad, Oct 29 2015
G.f.: 1 + x/(1 + x)*(1 + 4*x/(1 + 4*x)*(1 + 7*x/(1 + 7*x)*(1 + 10*x/(1 + 10*x)*(1 + .... - Peter Bala, May 27 2017
Invert transform of A011782(n) = 2^(n-1). Second invert transform of A000012. - Gus Wiseman, Jul 19 2020
a(n) = ceiling(3^(n-1)). - Alois P. Heinz, Jul 26 2020
From Elmo R. Oliveira, Mar 31 2025: (Start)
E.g.f.: (2 + exp(3*x))/3.
a(n) = 3*a(n-1) for n > 1. (End)

Definition clarified by R. J. Mathar, Nov 11 2008

A304961 Expansion of Product_{k>=1} (1 + 2^(k-1)*x^k).

Original entry on oeis.org

1, 1, 2, 6, 12, 32, 72, 176, 384, 960, 2112, 4992, 11264, 26112, 58368, 136192, 301056, 688128, 1548288, 3489792, 7766016, 17596416, 38993920, 87293952, 194248704, 432537600, 957349888, 2132803584, 4699717632, 10406068224, 23001563136, 50683969536, 111434268672, 245819768832

Offset: 0

Ilya Gutkovskiy, May 22 2018

nonn

Number of compositions of partitions of n into distinct parts. a(3) = 6: 3, 21, 12, 111, 2|1, 11|1. - Alois P. Heinz, Sep 16 2019
Also the number of ways to split a composition of n into contiguous subsequences with strictly decreasing sums. - Gus Wiseman, Jul 13 2020
This sequence is obtained from the generalized Euler transform in A266964 by taking f(n) = -1, g(n) = (-1) * 2^(n-1). - Seiichi Manyama, Aug 22 2020

			From _Gus Wiseman_, Jul 13 2020: (Start)
The a(0) = 1 through a(4) = 12 splittings:
  ()  (1)  (2)    (3)        (4)
           (1,1)  (1,2)      (1,3)
                  (2,1)      (2,2)
                  (1,1,1)    (3,1)
                  (2),(1)    (1,1,2)
                  (1,1),(1)  (1,2,1)
                             (2,1,1)
                             (3),(1)
                             (1,1,1,1)
                             (1,2),(1)
                             (2,1),(1)
                             (1,1,1),(1)
(End)

Cf. A000009, A011782, A022629, A098407, A102866, A266964, A271619, A279785.
The non-strict version is A075900.
Starting with a reversed partition gives A323583.
Starting with a partition gives A336134.
Partitions of partitions are A001970.
Splittings with equal sums are A074854.
Splittings of compositions are A133494.
Splittings with distinct sums are A336127.
Cf. A006951, A063834, A316245, A317715, A319794, A323582, A336135, A336136.

nmax = 33; CoefficientList[Series[Product[(1 + 2^(k - 1) x^k), {k, 1, nmax}], {x, 0, nmax}], x]

N=40; x='x+O('x^N); Vec(prod(k=1, N, 1+2^(k-1)*x^k)) \\ Seiichi Manyama, Aug 22 2020

G.f.: Product_{k>=1} (1 + A011782(k)*x^k).

a(n) ~ 2^n * exp(2*sqrt(-polylog(2, -1/2)*n)) * (-polylog(2, -1/2))^(1/4) / (sqrt(6*Pi) * n^(3/4)). - Vaclav Kotesovec, Sep 19 2019

A358914 Number of twice-partitions of n into distinct strict partitions.

Original entry on oeis.org

1, 1, 1, 3, 4, 7, 13, 20, 32, 51, 83, 130, 206, 320, 496, 759, 1171, 1786, 2714, 4104, 6193, 9286, 13920, 20737, 30865, 45721, 67632, 99683, 146604, 214865, 314782, 459136, 668867, 972425, 1410458, 2040894, 2950839, 4253713, 6123836, 8801349, 12627079

Offset: 0

Gus Wiseman, Dec 11 2022

nonn

A twice-partition of n (A063834) is a sequence of integer partitions, one of each part of an integer partition of n.

			The a(1) = 1 through a(6) = 13 twice-partitions:
  ((1))  ((2))  ((3))     ((4))      ((5))      ((6))
                ((21))    ((31))     ((32))     ((42))
                ((2)(1))  ((3)(1))   ((41))     ((51))
                          ((21)(1))  ((3)(2))   ((321))
                                     ((4)(1))   ((4)(2))
                                     ((21)(2))  ((5)(1))
                                     ((31)(1))  ((21)(3))
                                                ((31)(2))
                                                ((3)(21))
                                                ((32)(1))
                                                ((41)(1))
                                                ((3)(2)(1))
                                                ((21)(2)(1))

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

The unordered version is A050342, non-strict A261049.
This is the distinct case of A270995.
The case of strictly decreasing sums is A279785.
The case of constant sums is A279791.
For distinct instead of weakly decreasing sums we have A336343.
This is the twice-partition case of A358913.
A001970 counts multiset partitions of integer partitions.
A055887 counts sequences of partitions.
A063834 counts twice-partitions.
A330462 counts set systems by total sum and length.
A358830 counts twice-partitions with distinct lengths.
Cf. A000009, A000219, A075900, A271619, A296122, A304969, A321449, A336342, A358901, A358906, A358907.

twiptn[n_]:=Join@@Table[Tuples[IntegerPartitions/@ptn],{ptn,IntegerPartitions[n]}];
Table[Length[Select[twiptn[n],UnsameQ@@#&&And@@UnsameQ@@@#&]],{n,0,10}]

seq(n,k)={my(u=Vec(eta(x^2 + O(x*x^n))/eta(x + O(x*x^n))-1)); Vec(prod(k=1, n, my(c=u[k]); sum(j=0, min(c,n\k), x^(j*k)*c!/(c-j)!,  O(x*x^n))))} \\ Andrew Howroyd, Dec 31 2022

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

A075729 Number of different hierarchical orderings that can be formed from n labeled elements: these are divided into groups and the elements in each group are then arranged in a "preferential arrangement" or "weak order" as in A000670.

Original entry on oeis.org

1, 1, 4, 23, 173, 1602, 17575, 222497, 3188806, 50988405, 899222457, 17329515172, 362164300173, 8155216185781, 196789115887252, 5064722539020379, 138457553073641465, 4006059432756066914, 122284085809137076203, 3926775294104305483621, 132313462760902116605534

Offset: 0

Thomas Wieder and N. J. A. Sloane, Oct 06 2002

If all individuals form a single society ("uniparate society"), then the number of different hierarchies for that single society is equal to the ordered Bell number Bell_ordered(n) (A000670).

Represent a labeled pre-order (quasi-order, topology, A000798) as a directed graph. a(n) is the number of such digraphs in which the underlying graph of each component is complete. a(3)=23 because there are 29 such digraphs but o->o<-o and o<-o->o are not counted. Each has 3 labelings. 29 - 6 = 23. - Geoffrey Critzer, Jul 30 2014

			a(3) = 23: Let the n = 3 individuals be named 1, 2 and 3. Let a pair of parentheses () indicate a society and let square brackets [] denote a set of disparate societies. Finally, let the ranks be ordered from left to right and separated by a colon, e.g., (1,2:3) is a society with individual 3 on top and individuals 1 and 2 on the same bottom rank.
Then the hierarchical ordering for n = 3 is composed of the following sets: [(1),(2),(3)], [(1,2)(3)], [(3,2)(1)], [(3,1)(2)], [(1:2)(3)], [(3:2)(1)], [(1:3)(2)], [(2:1)(3)], [(2:3)(1)], [(3:1)(2)], [(3:2:1)], [(1:3:2)], [(2:1:3)], [(1:2:3)], [(3:1:2)], [(2:3:1)], [(1,3:2)], [(3,2:1)], [(2,1:3)], [(3:1,2)], [(1:2,3)], [(2:3,1)], [(1,2,3)].

Alois P. Heinz, Table of n, a(n) for n = 0..419 (first 101 terms from T. D. Noe)
José A. Adell and Sithembele Nkonkobe, A unified generalization of Touchard and Fubini polynomial extensions, Integers (2023) 23, #A80.
INRIA, Algolib: The Algorithms Project's Library
P. Flajolet and R. Sedgewick, Analytic Combinatorics, 2009; see page 571.
Robert Gill, The number of elements in a generalized partition semilattice, Discrete mathematics 186.1-3 (1998): 125-134. See Example 2.
Norihiro Nakashima and Shuhei Tsujie, Enumeration of Flats of the Extended Catalan and Shi Arrangements with Species, arXiv:1904.09748 [math.CO], 2019.
K. A. Penson, P. Blasiak, G. Duchamp, A. Horzela and A. I. Solomon, Hierarchical Dobinski-type relations via substitution and the moment problem [J. Phys. A 37 (2004), 3475-3487]
N. J. A. Sloane and Thomas Wieder, The Number of Hierarchical Orderings, Order 21 (2004), 83-89.
Kruchinin Vladimir Victorovich, Composition of ordinary generating functions, arXiv:1009.2565 [math.CO], 2010.
Thomas Wieder, The number of certain rankings and hierarchies formed from labeled or unlabeled elements and sets, Applied Mathematical Sciences, vol. 3, 2009, no. 55, 2707 - 2724. - _Thomas Wieder_, Nov 14 2009
Index entries for sequences related to parenthesizing

Cf. A000670, A075744. See A075900 for the unlabeled case.

A075729 := n->n!*exp(1/4/ln(2)-3/4)/2/sqrt(Pi)/(2*ln(2))^(1/4)*exp(-n*ln(ln(2)))*exp(sqrt(2*n/ln(2)))*n^(-3/4);
with(combstruct); SetSeqSetL := [T, {T=Set(S), S=Sequence(U,card >= 1), U=Set(Z,card >=1)},labeled]; seq(count(SetSeqSetL,size=j),j=1..12);
# alternative Maple program:
b:= proc(n) option remember: `if`(n<2, 1,
      (2*n-1)*b(n-1) -(n-1)*(n-2)*b(n-2))
    end:
a:= n-> add(b(k)*Stirling2(n,k), k=0..n):
seq(a(n), n=0..20);  # Alois P. Heinz, May 22 2018

Range[0, 20]!CoefficientList[Series[E^(1/(2 - E^x) - 1), {x, 0, 20}], x] (* Robert G. Wilson v, Jul 13 2004 *)
Fubini[n_, r_] := Sum[k!*Sum[(-1)^(i+k+r)(i+r)^(n-r)/(i!*(k-i-r)!), {i, 0, k-r}], {k, r, n}]; Fubini[0, 1] = 1; a[0] = 1; a[n_] := a[n] = (n-1)! Sum[a[n-k] Fubini[k, 1]/((n-k)! (k-1)!), {k, 1, n}]; Table[a[n], {n, 0, 20}] (* Jean-François Alcover, Mar 31 2016 *)
Table[Sum[BellY[n, k, PolyLog[-Range[n], 1/2]/2], {k, 0, n}], {n, 0, 20}] (* Vladimir Reshetnikov, Nov 09 2016 *)
With[{nn=20},CoefficientList[Series[Exp[1/(2-Exp[x])-1],{x,0,nn}],x] Range[0,nn]!] (* Harvey P. Dale, Aug 26 2022 *)

a(n):= sum(sum(stirling2(n,k)*k!*binomial(k-1,m-1), k,m,n)/m!, m,1,n) /* Vladimir Kruchinin, Aug 10 2010 */

E.g.f.: exp(f(x)-1) where f(x) = 1/(2-exp(x)) = e.g.f. for A000670.
STIRLINGi transform of A000262.
a(n) = (n-1)! * Sum_k=1^n a(n-k)*b(k)/((n-k)!*(k-1)!); a(n) = a(n) + C(n-1, k-1)*a(n-k)*b(k) (where b(n) = A000670(n)). - Thomas Wieder, Dec 31 2002
a(n) = (Sum_{j=1..n} m(j))*(n!*Product_{j=1..n} B(j)^m(j))/(Product_{j=1..n} (m(j))!*(j!)^m(j)), where the sum is over all (m(1),m(2),...,m(n)) such that Sum_{j=1..n} (j*m(j)) = n. - Thomas Wieder, May 18 2003
a(n) is asymptotic to exp(1/(4*log(2))-3/4) /(2*sqrt(Pi*sqrt(2*log(2)))) *n!*exp(-log(log(2))*n)*exp(sqrt(2*n /log(2))) /n^(3/4). Calculated using the Maple package "algolib", using the command "equivalent(exp(1/(2-exp(x))-1), x, n);". - Thomas Wieder, Nov 12 2002
a(n) = Sum_{k=0..n} A079641(n,k)*A000110(k). - Vladeta Jovovic, Sep 25 2006
a(n) = sum(sum(stirling2(n,k)*k!*C(k-1,m-1), k=m..n)/m!, m=1..n). - Vladimir Kruchinin, Aug 10 2010

A218482 First differences of the binomial transform of the partition numbers (A000041).

Original entry on oeis.org

1, 1, 3, 8, 21, 54, 137, 344, 856, 2113, 5179, 12614, 30548, 73595, 176455, 421215, 1001388, 2371678, 5597245, 13166069, 30873728, 72185937, 168313391, 391428622, 908058205, 2101629502, 4853215947, 11183551059, 25718677187, 59030344851, 135237134812, 309274516740

Offset: 0

Paul D. Hanna, Oct 29 2012

nonn

a(n) = A103446(n) for n>=1; here a(0) is set to 1 in accordance with the definition and other important generating functions.
From Gus Wiseman, Dec 12 2022: (Start)
Also the number of sequences of compositions (A133494) with weakly decreasing lengths and total sum n. For example, the a(0) = 1 through a(3) = 8 sequences are:
  ()  ((1))  ((2))     ((3))
             ((11))    ((12))
             ((1)(1))  ((21))
                       ((111))
                       ((1)(2))
                       ((2)(1))
                       ((11)(1))
                       ((1)(1)(1))
The case of constant lengths is A101509.
The case of strictly decreasing lengths is A129519.
The case of sequences of partitions is A141199.
The case of twice-partitions is A358831.
(End)

			G.f.: A(x) = 1 + x + 3*x^2 + 8*x^3 + 21*x^4 + 54*x^5 + 137*x^6 + 344*x^7 +...
The g.f. equals the product:
A(x) = (1-x)/((1-x)-x) * (1-x)^2/((1-x)^2-x^2) * (1-x)^3/((1-x)^3-x^3) * (1-x)^4/((1-x)^4-x^4) * (1-x)^5/((1-x)^5-x^5) * (1-x)^6/((1-x)^6-x^6) * (1-x)^7/((1-x)^7-x^7) *...
and also equals the series:
A(x) = 1  +  x*(1-x)/((1-x)-x)^2  +  x^4*(1-x)^2/(((1-x)-x)*((1-x)^2-x^2))^2  +  x^9*(1-x)^3/(((1-x)-x)*((1-x)^2-x^2)*((1-x)^3-x^3))^2  +  x^16*(1-x)^4/(((1-x)-x)*((1-x)^2-x^2)*((1-x)^3-x^3)*((1-x)^4-x^4))^2 +...

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

Cf. A000041, A000219, A011782, A055887, A063834, A075900, A098407, A101509, A103446, A129519, A141199, A218481.

b:= proc(n) option remember;
      add(combinat[numbpart](k)*binomial(n,k), k=0..n)
    end:
a:= n-> b(n)-b(n-1):
seq(a(n), n=0..50);  # Alois P. Heinz, Aug 19 2014

Flatten[{1, Table[Sum[Binomial[n-1,k]*PartitionsP[k+1],{k,0,n-1}],{n,1,30}]}] (* Vaclav Kotesovec, Jun 25 2015 *)

{a(n)=sum(k=0,n,(binomial(n,k)-if(n>0,binomial(n-1,k)))*numbpart(k))}
for(n=0,40,print1(a(n),", "))

{a(n)=local(X=x+x*O(x^n));polcoeff(prod(k=1,n,(1-x)^k/((1-x)^k-X^k)),n)}

{a(n)=local(X=x+x*O(x^n));polcoeff(sum(m=0,n,x^m*(1-x)^(m*(m-1)/2)/prod(k=1,m,((1-x)^k - X^k))),n)}

{a(n)=local(X=x+x*O(x^n));polcoeff(sum(m=0,n,x^(m^2)*(1-X)^m/prod(k=1,m,((1-x)^k - x^k)^2)),n)}

{a(n)=local(X=x+x*O(x^n));polcoeff(exp(sum(m=1,n+1,x^m/((1-x)^m-X^m)/m)),n)}

{a(n)=local(X=x+x*O(x^n));polcoeff(exp(sum(m=1,n+1,sigma(m)*x^m/(1-X)^m/m)),n)}

{a(n)=local(X=x+x*O(x^n));polcoeff(prod(k=1,n,(1 + x^k/(1-X)^k)^valuation(2*k,2)),n)}

G.f.: Product_{n>=1} (1-x)^n / ((1-x)^n - x^n).
G.f.: Sum_{n>=0} x^n * (1-x)^(n*(n-1)/2) / Product_{k=1..n} ((1-x)^k - x^k).
G.f.: Sum_{n>=0} x^(n^2) * (1-x)^n / Product_{k=1..n} ((1-x)^k - x^k)^2.
G.f.: exp( Sum_{n>=1} x^n/((1-x)^n - x^n) / n ).
G.f.: exp( Sum_{n>=1} sigma(n) * x^n/(1-x)^n / n ), where sigma(n) is the sum of divisors of n (A000203).
G.f.: Product_{n>=1} (1 + x^n/(1-x)^n)^A001511(n), where 2^A001511(n) is the highest power of 2 that divides 2*n.
a(n) ~ exp(Pi*sqrt(n/3) + Pi^2/24) * 2^(n-2) / (n*sqrt(3)). - Vaclav Kotesovec, Jun 25 2015

A098407 Number of different hierarchical orderings that can be formed from n unlabeled elements with no repetition of subhierarchies.

Original entry on oeis.org

1, 1, 2, 6, 13, 33, 78, 186, 436, 1028, 2394, 5566, 12877, 29689, 68198, 156194, 356599, 811959, 1843956, 4177436, 9442166, 21295934, 47932572, 107677140, 241443980, 540441068, 1207689636, 2694452060, 6002389882, 13351958546, 29659179804, 65794744420, 145768641091

Offset: 0

Thomas Wieder, Sep 07 2004; corrected Sep 09 2004

nonn

a(n) is the number of finite sets of compositions with total sum n. The case of constant sums is A358904, cf. A074854. The case of distinct sums is A304961, ordered A336127. The ordered version (sequences of distinct compositions) is A358907. - Gus Wiseman, Dec 12 2022

			Let a pair of parentheses () indicate a subhierarchy and let square brackets [] denote a set of subhierarchies, that is, a hierarchy (also called a society). Let the ranks be ordered from left to right and separated by a colon; e.g., (2:3) is a subhierarchy with three elements ("individuals") on top and two elements on the bottom rank.
Then the hierarchical ordering for n = 4 is composed of the following sets: [(1:1),(2)]; [(1),(3)]; [(1),(1:1:1)]; [(1),(2:1)]; [(1),(1:2)]; [(4)]; [(2:2)]; [(1:3)]; [(3:1)]; [(1:1:2)]; [(1:2:1)]; [(2:1:1)]; [(1:1:1:1)]; thus a(4) = 13.
For example, the following hierarchy is not allowed: [(1),(1),(1),(1)] because of the repetition of (1).

Alois P. Heinz, Table of n, a(n) for n = 0..3217
N. J. A. Sloane and Thomas Wieder, The Number of Hierarchical Orderings, arXiv:math/0307064 [math.CO], 2003; Order 21 (2004), 83-89.

Cf. A011782, A075729.
A034691 counts multisets of compositions, ordered A133494.
A261049 counts sets of partitions, ordered A358906.
Cf. A000009, A000219, A001970, A055887, A075900, A218482, A296122, A304961.

main := proc(n::integer) local a, ListOfPartitions, NumberOfPartitions, APartition, APart, ASet, MultipliticityOfAPart, ndxprttn, ndxprt, Term, Produkt; with(combinat): with(ListTools): a := 0; ListOfPartitions := partition(n); NumberOfPartitions := nops(ListOfPartitions); for ndxprttn from 1 to NumberOfPartitions do APartition := ListOfPartitions[ndxprttn]; ASet := convert(APartition,set); Produkt := 1; for ndxprt from 1 to nops(ASet) do APart := op(ndxprt,ASet); MultipliticityOfAPart := Occurrences(APart, APartition); Term := 2^(APart-1); Term := binomial(Term,MultipliticityOfAPart); Produkt := Produkt * Term; # End of do-loop *** ndxprt ***. end do; a := a + Produkt; # End of do-loop *** ndxprttn ***. end do; print("n, a(n):",n,a); end proc;
PartitionList := proc (n, k) # Authors: # Herbert S. Wilf and Joanna Nordlicht, # Source: # Lecture Notes "East Side West Side,..." # University of Pennsylvania, USA, 2002. # Available from http://www.cis.upenn.edu/~wilf/lecnotes.html # Berechnet die Partitionen von n mit k Summanden. local East, West; if n < 1 or k < 1 or n < k then RETURN([]) elif n = 1 then RETURN([[1]]) else if n < 2 or k < 2 or n < k then West := [] else West := map(proc (x) options operator, arrow; [op(x), 1] end proc, PartitionList(n-1, k-1)) end if; if k <= n-k then East := map(proc(y) options operator, arrow; map(proc (x) options operator, arrow; x+1 end proc, y) end proc, PartitionList(n-k, k)) else East := [] end if; RETURN([op(West), op(East)]) end if end proc;
# second Maple program:
series(exp(add((-1)^(j-1)/j*z^j/(1-2*z^j), j=1..40)), z, 40); # Cf. A102866; Vladeta Jovovic, Feb 19 2008
# alternative Maple program:
b:= proc(n, i) option remember; `if`(n=0 or i=1, `if`(n>1, 0, 1),
      add(b(n-i*j, i-1)*binomial(2^(i-1), j), j=0..n/i))
    end:
a:= n-> b(n$2):
seq(a(n), n=0..32);  # Alois P. Heinz, May 22 2018

terms = 32; CoefficientList[Product[(1 + x^k)^(2^(k-1)), {k, 1, terms+1}] + O[x]^(terms+1), x] // Rest (* Jean-François Alcover, Nov 10 2017, after Vladeta Jovovic *)
nmax = 40; CoefficientList[Series[Exp[Sum[-(-1)^k*x^k/(k*(1 - 2 x^k)), {k, 1, nmax}]], {x, 0, nmax}], x] (* Vaclav Kotesovec, Jun 08 2018 *)

a(n) = Sum_{ partitions n = s_1 + ... + s_n } Product_{ Set{s_i} } C(2^(s_i - 1), m(s_i)), where the sum runs over all partitions of n, the product runs over the set of parts of a given partition, s_i is the i-th part in the set of parts, C(k, l) denotes the binomial coefficient and m(s_i) is the multiplicity of part s_i in the given partition.
G.f.: Product_{k>=1} (1+x^k)^(2^(k-1)). - Vladeta Jovovic, Feb 19 2008
a(n) ~ 2^n * exp(sqrt(2*n) - 1/4 + c) / (sqrt(2*Pi) * 2^(3/4) * n^(3/4)), where c = Sum_{k>=2} -(-1)^k / (k*(2^k-2)) = -0.207530918644117743551169251314627032059... - Vaclav Kotesovec, Jun 08 2018
Weigh transform of A011782. - Alois P. Heinz, Jun 25 2018

More terms from Alois P. Heinz, Apr 21 2012

a(0)=1 prepended by Alois P. Heinz, May 22 2018

A072574 Triangle T(n,k) of number of compositions (ordered partitions) of n into exactly k distinct parts, 1<=k<=n.

Original entry on oeis.org

1, 1, 0, 1, 2, 0, 1, 2, 0, 0, 1, 4, 0, 0, 0, 1, 4, 6, 0, 0, 0, 1, 6, 6, 0, 0, 0, 0, 1, 6, 12, 0, 0, 0, 0, 0, 1, 8, 18, 0, 0, 0, 0, 0, 0, 1, 8, 24, 24, 0, 0, 0, 0, 0, 0, 1, 10, 30, 24, 0, 0, 0, 0, 0, 0, 0, 1, 10, 42, 48, 0, 0, 0, 0, 0, 0, 0, 0, 1, 12, 48, 72, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 12, 60, 120, 0

Offset: 1

Henry Bottomley, Jun 21 2002

If terms in the compositions did not need to be distinct then the triangle would have values C(n-1,k-1), essentially A007318 offset.

			T(6,2)=4 since 6 can be written as 1+5=2+4=4+2=5+1.
Triangle starts (trailing zeros omitted for n>=10):
[ 1]  1;
[ 2]  1, 0;
[ 3]  1, 2, 0;
[ 4]  1, 2, 0, 0;
[ 5]  1, 4, 0, 0, 0;
[ 6]  1, 4, 6, 0, 0, 0;
[ 7]  1, 6, 6, 0, 0, 0, 0;
[ 8]  1, 6, 12, 0, 0, 0, 0, 0;
[ 9]  1, 8, 18, 0, 0, 0, 0, 0, 0;
[10]  1, 8, 24, 24, 0, 0, ...;
[11]  1, 10, 30, 24, 0, 0, ...;
[12]  1, 10, 42, 48, 0, 0, ...;
[13]  1, 12, 48, 72, 0, 0, ...;
[14]  1, 12, 60, 120, 0, 0, ...;
[15]  1, 14, 72, 144, 120, 0, 0, ...;
[16]  1, 14, 84, 216, 120, 0, 0, ...;
[17]  1, 16, 96, 264, 240, 0, 0, ...;
[18]  1, 16, 114, 360, 360, 0, 0, ...;
[19]  1, 18, 126, 432, 600, 0, 0, ...;
[20]  1, 18, 144, 552, 840, 0, 0, ...;
These rows (without the zeros) are shown in the Richmond/Knopfmacher reference.
From _Gus Wiseman_, Oct 17 2022: (Start)
Column n = 8 counts the following compositions.
  (8)  (1,7)  (1,2,5)
       (2,6)  (1,3,4)
       (3,5)  (1,4,3)
       (5,3)  (1,5,2)
       (6,2)  (2,1,5)
       (7,1)  (2,5,1)
              (3,1,4)
              (3,4,1)
              (4,1,3)
              (4,3,1)
              (5,1,2)
              (5,2,1)
(End)

Joerg Arndt, Table of n, a(n) for n = 1..5050 (rows 1..100, flattened).
B. Richmond and A. Knopfmacher, Compositions with distinct parts, Aequationes Mathematicae 49 (1995), pp. 86-97.
Index entries for sequences related to compositions

Columns (offset) include A057427 and A052928.
Row sums are A032020.
Cf. A060016, A072576.
A008289 is the version for partitions (zeros removed).
A072575 counts strict compositions by maximum.
A097805 is the non-strict version, or A007318 (zeros removed).
A113704 is the constant instead of strict version.
A216652 is a condensed version (zeros removed).
A336131 counts splittings of partitions with distinct sums.
A336139 counts strict compositions of each part of a strict composition.
Cf. A075900, A097910, A307068, A336127, A336128, A336130, A336132, A336141, A336142, A336342, A336343.

Table[Length[Select[Join@@Permutations/@Select[IntegerPartitions[n],UnsameQ@@#&],Length[#]==k&]],{n,0,15},{k,1,n}] (* Gus Wiseman, Oct 17 2022 *)

N=21;  q='q+O('q^N);
gf=sum(n=0,N, n! * z^n * q^((n^2+n)/2) / prod(k=1,n, 1-q^k ) );
/* print triangle: */
gf -= 1; /* remove row zero */
P=Pol(gf,'q);
{ for (n=1,N-1,
    p = Pol(polcoeff(P, n),'z);
    p += 'z^(n+1);  /* preserve trailing zeros */
    v = Vec(polrecip(p));
    v = vector(n,k,v[k]); /* trim to size n */
    print(v);
); }
/* Joerg Arndt, Oct 20 2012 */

T(n, k) = T(n-k, k)+k*T(n-k, k-1) [with T(n, 0)=1 if n=0 and 0 otherwise] = A000142(k)*A060016(n, k).

G.f.: sum(n>=0, n! * z^n * q^((n^2+n)/2) / prod(k=1..n, 1-q^k ) ), rows by powers of q, columns by powers of z; includes row 0 (drop term for n=0 for this triangle, see PARI code); setting z=1 gives g.f. for A032020. [Joerg Arndt, Oct 20 2012]

A336127 Number of ways to split a composition of n into contiguous subsequences with different sums.

Original entry on oeis.org

1, 1, 2, 8, 16, 48, 144, 352, 896, 2432, 7168, 16896, 46080, 114688, 303104, 843776, 2080768, 5308416, 13762560, 34865152, 87818240, 241172480, 583008256, 1503657984, 3762290688, 9604956160, 23689428992, 60532195328, 156397207552, 385137770496, 967978254336

Offset: 0

Gus Wiseman, Jul 09 2020

nonn

A composition of n is a finite sequence of positive integers summing to n.

			The a(0) = 1 through a(4) = 16 splits:
  ()  (1)  (2)    (3)        (4)
           (1,1)  (1,2)      (1,3)
                  (2,1)      (2,2)
                  (1,1,1)    (3,1)
                  (1),(2)    (1,1,2)
                  (2),(1)    (1,2,1)
                  (1),(1,1)  (1),(3)
                  (1,1),(1)  (2,1,1)
                             (3),(1)
                             (1,1,1,1)
                             (1),(1,2)
                             (1),(2,1)
                             (1,2),(1)
                             (2,1),(1)
                             (1),(1,1,1)
                             (1,1,1),(1)

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

The version with equal instead of different sums is A074854.
Starting with a strict composition gives A336128.
Starting with a partition gives A336131.
Starting with a strict partition gives A336132
Partitions of partitions are A001970.
Partitions of compositions are A075900.
Compositions of compositions are A133494.
Compositions of partitions are A323583.
Cf. A006951, A063834, A279786, A305551, A316245, A317715, A323433, A336130, A336134, A336135.

splits[dom_]:=Append[Join@@Table[Prepend[#,Take[dom,i]]&/@splits[Drop[dom,i]],{i,Length[dom]-1}],{dom}];
Table[Sum[Length[Select[splits[ctn],UnsameQ@@Total/@#&]],{ctn,Join@@Permutations/@IntegerPartitions[n]}],{n,0,10}]

a(n) = Sum_{k=0..n} 2^(n-k) k! A008289(n,k).

A336128 Number of ways to split a strict composition of n into contiguous subsequences with different sums.

Original entry on oeis.org

1, 1, 1, 5, 5, 9, 29, 37, 57, 89, 265, 309, 521, 745, 1129, 3005, 3545, 5685, 8201, 12265, 16629, 41369, 48109, 77265, 107645, 160681, 214861, 316913, 644837, 798861, 1207445, 1694269, 2437689, 3326705, 4710397, 6270513, 12246521, 14853625, 22244569, 30308033, 43706705, 57926577, 82166105, 107873221, 148081785, 257989961, 320873065, 458994657, 628016225, 875485585, 1165065733

Offset: 0

Gus Wiseman, Jul 10 2020

nonn

A composition of n is a finite sequence of positive integers summing to n.

			The a(0) = 1 through a(5) = 5 splits:
  ()  (1)  (2)  (3)     (4)     (5)
                (12)    (13)    (14)
                (21)    (31)    (23)
                (1)(2)  (1)(3)  (32)
                (2)(1)  (3)(1)  (41)
                                (1)(4)
                                (2)(3)
                                (3)(2)
                                (4)(1)
The a(6) = 29 splits:
  (6)    (1)(5)   (1)(2)(3)
  (15)   (2)(4)   (1)(3)(2)
  (24)   (4)(2)   (2)(1)(3)
  (42)   (5)(1)   (2)(3)(1)
  (51)   (1)(23)  (3)(1)(2)
  (123)  (1)(32)  (3)(2)(1)
  (132)  (13)(2)
  (213)  (2)(13)
  (231)  (2)(31)
  (312)  (23)(1)
  (321)  (31)(2)
         (32)(1)

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

The version with equal instead of different sums is A336130.
Starting with a non-strict composition gives A336127.
Starting with a partition gives A336131.
Starting with a strict partition gives A336132.
Partitions of partitions are A001970.
Partitions of compositions are A075900.
Compositions of compositions are A133494.
Set partitions with distinct block-sums are A275780.
Compositions of partitions are A323583.
Cf. A006951, A063834, A271619, A279375, A305551, A326519, A317508, A318684, A336133, A336134, A336135.

splits[dom_]:=Append[Join@@Table[Prepend[#,Take[dom,i]]&/@splits[Drop[dom,i]],{i,Length[dom]-1}],{dom}];
Table[Sum[Length[Select[splits[ctn],UnsameQ@@Total/@#&]],{ctn,Join@@Permutations/@Select[IntegerPartitions[n],UnsameQ@@#&]}],{n,0,15}]

a(31)-a(50) from Max Alekseyev, Feb 14 2024

cp's OEIS Frontend

A063834 Twice partitioned numbers: the number of ways a number can be partitioned into not necessarily different parts and each part is again so partitioned.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

Extensions

A133494 Diagonal of the array of iterated differences of A047848.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

PARI

SageMath

Formula

Extensions

A304961 Expansion of Product_{k>=1} (1 + 2^(k-1)*x^k).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A358914 Number of twice-partitions of n into distinct strict partitions.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Extensions

A075729 Number of different hierarchical orderings that can be formed from n labeled elements: these are divided into groups and the elements in each group are then arranged in a "preferential arrangement" or "weak order" as in A000670.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Maxima

Formula

A218482 First differences of the binomial transform of the partition numbers (A000041).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica