A247003 -id:A247003 - cp's OEIS frontend

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

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

Offset: 0

N. J. A. Sloane

nonn

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 Sloane-Wieder 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 non-isomorphic 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^(k-1) 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

			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}}

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), 83-89.
Thomas Wieder, An explicit formula for the n-th 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]

Cf. A034899, A075729, A247003, A004211, A104500 (Euler transform), A290222 (Multiset transform).

oo := 101: mul( 1/(1-x^j)^(2^(j-1)),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

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[n-1]+1];
allnmsp[0]={};allnmsp[1]={{{1}}};allnmsp[n_Integer]:=allnmsp[n]=Join[allnmsp[n-1],List/@allnorm[n],Join@@Function[ptn,Append[ptn,#]&/@Select[allnorm[n-Length[Join@@ptn]],OrderedQ[{Last[ptn],#}]&]]/@allnmsp[n-1]];
Apply[SequenceForm,Select[allnmsp[4],Length[Join@@#]===4&],{2}] (* to construct the example *)
Table[Length[Complement[allnmsp[n],allnmsp[n-1]]],{n,1,8}] (* Gus Wiseman, Mar 03 2016 *)

A034691(n,l=1+O('x^(n+1)))={polcoeff(1/prod(k=1,n,(l-'x^k)^2^(k-1)),n)} \\ Michael Somos, Nov 21 2011, edited by M. F. Hasler, Jul 24 2017

# uses[EulerTransform from A166861]
a = BinaryRecurrenceSequence(2, 0)
b = EulerTransform(a)
print([b(n) for n in range(30)]) # Peter Luschny, Nov 11 2020

G.f.: 1 / Product_{n>=1} (1-x^n)^(2^(n-1)).
Recurrence: a(n) = (1/n) * Sum_{m=1..n} a(n-m)*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^k-2)) ) = 1.3976490050836502... (see A247003). - Vaclav Kotesovec, Sep 08 2014

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

Original entry on oeis.org

1, 2, 7, 20, 59, 162, 449, 1200, 3194, 8348, 21646, 55480, 141152, 356056, 892284, 2221208, 5497945, 13533858, 33151571, 80826748, 196219393, 474425518, 1142758067, 2742784304, 6561052331, 15645062126, 37194451937, 88174252924, 208463595471, 491585775018

Offset: 0

N. J. A. Sloane

nonn

			From _Geoffrey Critzer_, Mar 07 2012: (Start)
Per comment in A102866, a(n) is also the number of multisets of binary words of total length n.
a(2) = 7 because the multisets are {a,a}, {b,b}, {a,b}, {aa}, {ab}, {ba}, {bb};
a(3) = 20 because the multisets are {a,a,a}, {b,b,b}, {a,a,b}, {a,b,b}, {a,aa}, {a,ab}, {a,ba}, {a,bb}, {b,aa}, {b,ab}, {b,ba}, {b,bb}, {aaa}, {aab}, {aba}, {abb}, {baa}, {bab}, {bba}, {bbb};
where the words within each multiset are separated by commas. (End)

Alois P. Heinz and Vaclav Kotesovec, Table of n, a(n) for n = 0..3150 (first 900 terms from Alois P. Heinz)
Vaclav Kotesovec, A method of finding the asymptotics of q-series based on the convolution of generating functions, arXiv:1509.08708 [math.CO], Sep 30 2015, p. 27.
N. J. A. Sloane and Thomas Wieder, The Number of Hierarchical Orderings, Order 21 (2004), 83-89.
G. S. Venkatesh and Kurusch Ebrahimi-Fard, A Formal Power Series Approach to Multiplicative Dynamic Feedback, arXiv:2301.04949 [math.OC], 2023.
Thomas Wieder, Additional comments on this sequence

Cf. A034691, the Euler transform of 1, 2, 4, 8, 16, 32, 64, ...
Cf. A075729, A102866.
Column k=2 of A144074.
Row sums of A055375 and of A209406.

m:=50; R:=PowerSeriesRing(Integers(), m); Coefficients(R!( (&*[1/(1-x^k)^(2^k): k in [1..m]]) )); // G. C. Greubel, Nov 09 2018 ~

series(1/product((1-x^(n))^(2^(n)),n=1..20),x=0,12); (Wieder)
# second Maple program:
with(numtheory):
a:= proc(n) option remember;
      `if`(n=0, 1, add(add(d*2^d, d=divisors(j))*a(n-j), j=1..n)/n)
    end:
seq(a(n), n=0..40);  # Alois P. Heinz, Sep 02 2011

nn = 20; p = Product[1/(1 - x^i)^(2^i), {i, 1, nn}]; CoefficientList[Series[p, {x, 0, nn}], x] (* Geoffrey Critzer, Mar 07 2012 *)

m=50; x='x+O('x^m); Vec(prod(k=1,m,1/(1-x^k)^(2^k))) \\ G. C. Greubel, Nov 09 2018

G.f.: 1/Product_{n>0} (1-x^n)^(2^n). - Thomas Wieder, Mar 06 2005
a(n) ~ c^2 * 2^(n-1) * exp(2*sqrt(n) - 1/2) / (sqrt(Pi) * n^(3/4)), where c = A247003 = exp( Sum_{k>=2} 1/(k*(2^k-2)) ) = 1.3976490050836502... . - Vaclav Kotesovec, Mar 09 2015
G.f.: exp(2*Sum_{k>=1} x^k/(k*(1 - 2*x^k))). - Ilya Gutkovskiy, Nov 09 2018

More terms from Thomas Wieder, Mar 06 2005

A319918 Expansion of Product_{k>=1} 1/(1 - x^k)^(2^k-1).

Original entry on oeis.org

1, 1, 4, 11, 32, 84, 230, 597, 1567, 4020, 10286, 25994, 65387, 163065, 404617, 997687, 2448220, 5977334, 14530835, 35173496, 84814982, 203760809, 487845377, 1164191563, 2769721073, 6570218773, 15542642042, 36671354125, 86306246887, 202637312099, 474684979292, 1109539437382

Offset: 0

Ilya Gutkovskiy, Oct 01 2018

nonn

Convolution of A010815 and A034899.

Euler transform of A000225.

Alois P. Heinz, Table of n, a(n) for n = 0..3171
N. J. A. Sloane, Transforms

Cf. A000225, A007070, A010815, A034691, A034899, A319919.

a:= proc(n) option remember; `if`(n=0, 1, add(a(n-j)*add(
       d*(2^d-1), d=numtheory[divisors](j)), j=1..n)/n)
    end:
seq(a(n), n=0..35);  # Alois P. Heinz, Aug 13 2021

nmax = 31; CoefficientList[Series[Product[1/(1 - x^k)^(2^k - 1), {k, 1, nmax}], {x, 0, nmax}], x]
nmax = 31; CoefficientList[Series[Exp[Sum[x^k/(k (1 - x^k) (1 - 2 x^k)), {k, 1, nmax}]], {x, 0, nmax}], x]
a[n_] := a[n] = If[n == 0, 1, Sum[Sum[d (2^d - 1), {d, Divisors[k]}] a[n - k], {k, 1, n}]/n]; Table[a[n], {n, 0, 31}]

G.f.: exp(Sum_{k>=1} x^k/(k*(1 - x^k)*(1 - 2*x^k))).

a(n) ~ A247003^2 * exp(2*sqrt(n) - 1/2) * 2^(n-1) / (A065446 * sqrt(Pi) * n^(3/4)). - Vaclav Kotesovec, Sep 15 2021

A261043 Number of multisets of nonempty words with a total of n letters over binary alphabet such that all letters occur at least once in the multiset.

Original entry on oeis.org

0, 0, 3, 14, 49, 148, 427, 1170, 3150, 8288, 21562, 55368, 140998, 355854, 892014, 2220856, 5497483, 13533264, 33150801, 80825768, 196218139, 474423934, 1142756063, 2742781794, 6561049181, 15645058210, 37194447065, 88174246904, 208463588035, 491585765888

Offset: 0

Vaclav Kotesovec, Aug 08 2015

nonn

Vaclav Kotesovec, Table of n, a(n) for n = 0..3000

Column k=2 of A257740.

Cf. A000041, A034899, A247003.

CoefficientList[Series[Product[1/(1-x^k)^(2^k), {k, 1, 30}] - 2*Product[1/(1 - x^k), {k, 1, 30}] + 1, {x, 0, 30}], x]
(* Second program: *)
A[n_, k_] := A[n, k] = If[n == 0, 1, Sum[DivisorSum[j, #*k^# &]*A[n - j, k], {j, 1, n}]/n];
T[n_, k_] := Sum[A[n, k - i]*(-1)^i*Binomial[k, i], {i, 0, k}];
a[n_] := T[n, 2];
Table[a[n], {n, 0, 30}] (* Jean-François Alcover, Jun 01 2022, after Alois P. Heinz in A257740 *)

a(n) = A034899(n) - 2*A000041(n) + 1.

a(n) ~ c^2 * 2^(n-1) * exp(2*sqrt(n) - 1/2) / (sqrt(Pi) * n^(3/4)), where c = A247003 = exp( Sum_{k>=2} 1/(k*(2^k-2)) ) = 1.3976490050836502...

New name from Alois P. Heinz, Oct 07 2018

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

Original entry on oeis.org

1, 2, 6, 18, 50, 138, 374, 994, 2610, 6778, 17414, 44346, 112034, 280970, 700038, 1733706, 4269970, 10463154, 25518198, 61962458, 149839602, 360958306, 866405702, 2072579058, 4942074082, 11748730482, 27849974598, 65837539522, 155236876018, 365125130490, 856767548022

Offset: 0

Ilya Gutkovskiy, May 22 2018

nonn

Convolution of the sequences A034691 and A098407.

Alois P. Heinz, Table of n, a(n) for n = 0..1000
Simon Plouffe, Conjectures of the OEIS, as of June 20, 2018.
Simon Plouffe, Approximations de séries génératrices et quelques conjectures, Master's thesis, 1992. [see page 24]
N. J. A. Sloane, Transforms
Index entries for sequences related to partitions
Index entries for sequences related to compositions

Cf. A011782, A015128, A034691, A098407, A156616, A261519, A302239.

g:= proc(n) option remember; `if`(n=0, 1, add(add(d*
      2^(d-1), d=numtheory[divisors](j))*g(n-j), j=1..n)/n)
    end:
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-> add(g(n-j)*b(j$2), j=0..n):
seq(a(n), n=0..35);  # Alois P. Heinz, May 22 2018
# Maple program to compute c(n) from a(n) or a(n) from c(n).
with(numtheory):
andrews:=proc(liste) local n,z,serie,ls,i,d,aaa;
   n:=nops(liste);
aaa:=liste;
serie:=listtoseries(aaa,z,ogf):
ls:=series(ln(serie),z,n);
   [seq(coeff(ls,z,d),d=1..n)];
   [seq(elemmobius(%,i),i=1..n-1)]
end:
swerdna:=proc(liste) local n,i,z;
  n:=nops(liste);
  series(convert([seq((1-z^i)^(-liste[i]),i=1..n)],`*`),z,n);
  [seq(coeff(%,z,i),i=0..n-1)]
end:
elemmobius:=proc(liste,d) local k,rep;
   rep:=0;
   for k in divisors(d) do
      rep:=rep+liste[k]*mobius(iquo(d,k))/iquo(d,k)
   od;
   rep
end:
# Here andrews() finds the c(n) and swerdna() finds the a(n) if the c(n) are known.
# For ordinary partitions the c(n) are [1,1,1,1,1, ...].
# Simon Plouffe, Jun 20 2018

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

G.f.: Product_{k>=1} ((1 + x^k)/(1 - x^k))^A011782(k).
Euler transform of c(n) with g.f.: -x*(-2*x^2-x+2)/(-4*x^3+2*x^2+2*x-1). - Simon Plouffe, Jun 20 2018
a(n) ~ A247003 * 2^(n-1) * exp(2*sqrt(n) - 1/2 + c) / (sqrt(Pi)*n^(3/4)), where c = Sum_{k>=2} -(-1)^k / (k*(2^k-2)) = -0.207530918644117743551169251314627032... - Vaclav Kotesovec, Sep 15 2021

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

SageMath

Formula

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

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

Formula

Extensions

A319918 Expansion of Product_{k>=1} 1/(1 - x^k)^(2^k-1).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A261043 Number of multisets of nonempty words with a total of n letters over binary alphabet such that all letters occur at least once in the multiset.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

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

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

Formula