

A034691


Euler transform of powers of 2 [1,2,4,8,16,...].


134



1, 1, 3, 7, 18, 42, 104, 244, 585, 1373, 3233, 7533, 17547, 40591, 93711, 215379, 493735, 1127979, 2570519, 5841443, 13243599, 29953851, 67604035, 152258271, 342253980, 767895424, 1719854346, 3845443858
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

0,3


COMMENTS

This is the number of different hierarchical orderings that can be formed from n unlabeled elements: these are divided into groups and the elements in each group are then arranged in an "unlabeled preferential arrangement" or "composition" as in A000079.  Thomas Wieder and N. J. A. Sloane, Jun 10 2003
From Gus Wiseman, Mar 03 2016: (Start)
The original SloaneWieder definition, "To obtain a hierarchical ordering we partition the elements into unlabeled nonempty subsets and form a composition of each subset," [arXiv:math/0307064] has two possible meanings. The first possible meaning is that we should (1) choose a set partition pi of {1...n} and (2) for each block of pi choose a composition of the number of elements. In this case the correct number of such structures would evidently be counted by A004211 which differs from a(n) for n > 2.
The other possible meaning is that after we have done (1) and (2) above we (3) "forget" the choice of pi. We will have produced a collection M of multisets of compositions. The span of M (its set of distinct elements) is correctly counted by A034691 and it seems that nonisomorphic hierarchical orderings of unlabeled sets are nothing more than multisets of compositions. This discovery is due to Wieder. (End)
The asymptotic formula in the article by N. J. A. Sloane and Thomas Wieder, "The Number of Hierarchical Orderings" (Theorem 3) is incorrect (a multiplicative factor of 1.397... is missing, see my formula below).  Vaclav Kotesovec, Sep 08 2014
Number of partitions of n into 1 sort of 1, 2 sorts of 2's, 4 sorts of 3's, ..., 2^(k1) sorts of k's, ... .  Joerg Arndt, Sep 09 2014
Also number of normal multiset partitions of weight n, where a multiset is normal if it spans an initial interval of positive integers.  Gus Wiseman, Mar 03 2016


LINKS

T. D. Noe and Vaclav Kotesovec, Table of n, a(n) for n = 0..3190 (first 300 terms from T. D. Noe)
Vaclav Kotesovec, Asymptotics of sequence A034691
Vaclav Kotesovec, Asymptotics of the Euler transform of Fibonacci numbers, arXiv:1508.01796 [math.CO], Aug 07 2015
N. J. A. Sloane and Thomas Wieder, The Number of Hierarchical Orderings, arXiv:math/0307064 [math.CO], 2003; Order 21 (2004), 8389.
Thomas Wieder, An explicit formula for the nth term
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. [From Thomas Wieder, Nov 14 2009]


FORMULA

G.f.: 1 / Product_{n>=1} (1x^n)^(2^(n1)).
Recurrence: a(n) = (1/n) * Sum_{m=1..n} a(nm)*c(m) where c(m) = A083413(m).
a(n) ~ c * 2^n * exp(sqrt(2*n)) / (sqrt(2*Pi) * exp(1/4) * 2^(3/4) * n^(3/4)), where c = exp( Sum_{k>=2} 1/(k*(2^k2)) ) = 1.3976490050836502... (see A247003).  Vaclav Kotesovec, Sep 08 2014


EXAMPLE

The normal multiset partitions for a(4) = 18: {{1111},{1222},{1122},{1112},{1233},{1223},{1123},{1234},{1,111},{1,122},{1,112},{1,123},{11,11},{11,12},{12,12},{1,1,11},{1,1,12},{1,1,1,1}}


MAPLE

oo := 101: mul( 1/(1x^j)^(2^(j1)), j=1..oo): series(%, x, oo): t1 := seriestolist(%); A034691 := n> t1[n+1];
with(combstruct); SetSeqSetU := [T, {T=Set(S), S=Sequence(U, card >= 1), U=Set(Z, card >=1)}, unlabeled]; seq(count(SetSeqSetU, size=j), j=1..12);
# Alternative, uses EulerTransform from A358369:
a := EulerTransform(BinaryRecurrenceSequence(2, 0)):
seq(a(n), n = 0..27); # Peter Luschny, Nov 17 2022


MATHEMATICA

nn = 30; b = Table[2^n, {n, 0, nn}]; CoefficientList[Series[Product[1/(1  x^m)^b[[m]], {m, nn}], {x, 0, nn}], x] (* T. D. Noe, Nov 21 2011 *)
Table[SeriesCoefficient[E^(Sum[x^k/(1  2*x^k)/k, {k, 1, n}]), {x, 0, n}], {n, 0, 30}] (* Vaclav Kotesovec, Sep 08 2014 *)
allnorm[n_Integer]:=Function[s, Array[Count[s, y_/; y<=#]+1&, n]]/@Subsets[Range[n1]+1];
allnmsp[0]={}; allnmsp[1]={{{1}}}; allnmsp[n_Integer]:=allnmsp[n]=Join[allnmsp[n1], List/@allnorm[n], Join@@Function[ptn, Append[ptn, #]&/@Select[allnorm[nLength[Join@@ptn]], OrderedQ[{Last[ptn], #}]&]]/@allnmsp[n1]];
Apply[SequenceForm, Select[allnmsp[4], Length[Join@@#]===4&], {2}] (* to construct the example *)
Table[Length[Complement[allnmsp[n], allnmsp[n1]]], {n, 1, 8}] (* Gus Wiseman, Mar 03 2016 *)


PROG

(PARI) A034691(n, l=1+O('x^(n+1)))={polcoeff(1/prod(k=1, n, (l'x^k)^2^(k1)), n)} \\ Michael Somos, Nov 21 2011, edited by M. F. Hasler, Jul 24 2017
(SageMath) # uses[EulerTransform from A166861]
a = BinaryRecurrenceSequence(2, 0)
b = EulerTransform(a)
print([b(n) for n in range(30)]) # Peter Luschny, Nov 11 2020


CROSSREFS

Cf. A034899, A075729, A247003, A004211, A104500 (Euler transform), A290222 (Multiset transform).
Sequence in context: A208771 A036884 A102291 * A317546 A319001 A000633
Adjacent sequences: A034688 A034689 A034690 * A034692 A034693 A034694


KEYWORD

nonn


AUTHOR

N. J. A. Sloane.


STATUS

approved



