A358904 -id:A358904 - cp's OEIS frontend

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

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

A358335 Number of integer compositions of n whose parts have weakly decreasing numbers of prime factors (with multiplicity).

Original entry on oeis.org

1, 1, 2, 3, 5, 8, 12, 19, 29, 44, 68, 100, 153, 227, 342, 509, 759, 1129, 1678, 2492, 3699, 5477, 8121, 12015, 17795, 26313, 38924, 57541, 85065, 125712, 185758, 274431, 405420, 598815, 884465, 1306165, 1928943, 2848360, 4205979, 6210289, 9169540

Offset: 0

Gus Wiseman, Dec 05 2022

nonn

			The a(0) = 1 through a(6) = 12 compositions:
  ()  (1)  (2)   (3)    (4)     (5)      (6)
           (11)  (21)   (22)    (23)     (33)
                 (111)  (31)    (32)     (42)
                        (211)   (41)     (51)
                        (1111)  (221)    (222)
                                (311)    (231)
                                (2111)   (321)
                                (11111)  (411)
                                         (2211)
                                         (3111)
                                         (21111)
                                         (111111)

Alois P. Heinz, Table of n, a(n) for n = 0..2000 (first 101 terms from Lucas A. Brown)
Lucas A. Brown, Python program.

For lengths of partitions see A141199, compositions A218482.
The strictly decreasing case is A358901.
The version not counting multiplicity is A358902, strict A358903.
The case of partitions is A358909, complement A358910.
The case of equality is A358911, partitions A319169.
A001222 counts prime factors, distinct A001221.
A011782 counts compositions.
A063834 counts twice-partitions.
Cf. A056239, A300335, A319071, A320324, A358831, A358904, A358908.

Table[Length[Select[Join @@ Permutations/@IntegerPartitions[n],GreaterEqual@@PrimeOmega/@#&]],{n,0,10}]

a(21) and beyond from Lucas A. Brown, Dec 15 2022

A359041 Number of finite sets of integer partitions with all equal sums and total sum n.

Original entry on oeis.org

1, 1, 2, 3, 6, 7, 14, 15, 32, 31, 63, 56, 142, 101, 240, 211, 467, 297, 985, 490, 1524, 1247, 2542, 1255, 6371, 1979, 7486, 7070, 14128, 4565, 32953, 6842, 42229, 37863, 56266, 17887, 192914, 21637, 145820, 197835, 371853, 44583, 772740, 63261, 943966, 1124840

Offset: 0

Gus Wiseman, Dec 14 2022

nonn

			The a(1) = 1 through a(6) = 14 sets:
  {(1)}  {(2)}   {(3)}    {(4)}       {(5)}      {(6)}
         {(11)}  {(21)}   {(22)}      {(32)}     {(33)}
                 {(111)}  {(31)}      {(41)}     {(42)}
                          {(211)}     {(221)}    {(51)}
                          {(1111)}    {(311)}    {(222)}
                          {(2),(11)}  {(2111)}   {(321)}
                                      {(11111)}  {(411)}
                                                 {(2211)}
                                                 {(3111)}
                                                 {(21111)}
                                                 {(111111)}
                                                 {(3),(21)}
                                                 {(3),(111)}
                                                 {(21),(111)}

This is the constant-sum case of A261049, ordered A358906.
The version for all different sums is A271619, ordered A336342.
Allowing repetition gives A305551, ordered A279787.
The version for compositions instead of partitions is A358904.
A001970 counts multisets of partitions.
A034691 counts multisets of compositions, ordered A133494.
A098407 counts sets of compositions, ordered A358907.
Cf. A000005, A000041, A038041, A055887, A063834, A074854, A289078, A304961, A305552, A306017.

Table[If[n==0,1,Sum[Binomial[PartitionsP[d],n/d],{d,Divisors[n]}]],{n,0,50}]

a(n) = if (n, sumdiv(n, d, binomial(numbpart(d), n/d)), 1); \\ Michel Marcus, Dec 14 2022

a(n) = Sum_{d|n} binomial(A000041(d),n/d).

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A358335 Number of integer compositions of n whose parts have weakly decreasing numbers of prime factors (with multiplicity).

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

Extensions

A359041 Number of finite sets of integer partitions with all equal sums and total sum n.

Views

Author

Keywords

Examples

Crossrefs

Programs

Mathematica

PARI

Formula