

A200544


Number of distinct bags of distinct sequences of 1s and 2s such that the sum of all terms is n.


5



1, 1, 3, 6, 14, 28, 61, 122, 253, 505, 1017, 2008, 3976, 7769, 15169, 29379, 56751, 108993, 208725, 397913, 756385, 1432578, 2705744, 5094749, 9568504, 17922756, 33492061, 62438472, 116151352, 215612548, 399451325, 738612472, 1363261171, 2511748010, 4620024202
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

0,3


COMMENTS

This is the number of distinct ways to build minimal Jenga towers out of n blocks. The number of distinct ways to build a single minimal Jenga tower out of n blocks is the Fibonacci number F(n+1) (A000045(n+1)).
To calculate this, first create all partitions of n.
An example partition, for n=4, is
1 1 1 1
1 1 2
1 3
2 2
4
Then each set of towers of the same size gets a configuration. For 2 2 2, for instance, there are two possibilities for each tower (a single level with two blocks or two levels with one block each) but the total possibilities is not 2*2*2=8, since the configuration "1/1,2,2" is the same as "2,1/1,2". Instead we want to choose three towers with repetition from two possibilities which is 3+21 choose 3, aka 4C3 = 4.
Multiply all the sets of towers of the same size and sum over partitions for the result.
For n=4, then, 1 1 2 becomes "1 with multiplicity 2" and "2 with multiplicity 1".
There is f(1+1)=1 way to build a tower of size 1, and f(1+1)+21 choose 2 = 2C2 = 1 way to build 2 towers of size 1. f(2+1)=2 ways to build a tower of size 2. 1 1 2 has 1*2=2 ways to be built. Sum over each of the 5 partitions of n=4.
Comment from R. J. Mathar, Aug 10 2020: (Start)
This is apparently the limit of the rowreversed rows of the Multiset transform T(n,k) of the Fibonacci sequence in A337009, a(k) = lim(n>oo) T(n,nk).  R. J. Mathar, Aug 10 2020


LINKS

Alois P. Heinz, Table of n, a(n) for n = 0..1000
W. S. Gray, K. EbrahimiFard, Affine SISO Feedback Transformation Group and Its Faa di Bruno Hopf Algebra, arXiv:1411.0222 [math.OC], 2014.
Vaclav Kotesovec, Asymptotics of the Euler transform of Fibonacci numbers, arXiv:1508.01796 [math.CO], Aug 07 2015
Vaclav Kotesovec, Asymptotics of sequence A034691
Guy P. Srinivasan, C# code to generate sequence terms
Wikipedia, Jenga


FORMULA

sum{m1*a1+m2*a2+...+mk*ak}(prod{k}(binomial(A000045[ak + 1]+mk1,mk))).
G.f.: Product_{s>=1}(sum{d>=0}(binomial(F(s+1)+d1,d)*x^(d*s))).  Guy P. Srinivasan, Oct 21 2013
Euler Transform of A000045 starting at index 2, i.e. EULER(1, 2, 3, 5, 8, 13, ...).  Guy P. Srinivasan, Nov 05 2013
a(n) ~ phi^(n+1/4) / (2 * sqrt(Pi) * 5^(1/8) * n^(3/4)) * exp(phi/10  3/5 + 2*5^(1/4)*sqrt(phi*n) + s), where s = Sum_{k>=2} (1+phi^k) / ((phi^(2*k)  phi^k  1)*k) = 0.7902214013751085262994702391769374769675268259229550490716908... and phi = A001622 = (1+sqrt(5))/2 is the golden ratio.  Vaclav Kotesovec, Aug 06 2015


EXAMPLE

For n = 4, a(4)=14 and the bags are: 1/1/1/1; 1/1/1,1; 1/1/2; 1/1,1,1; 1/1,2; 1/2,1; 1,1/1,1; 1,1/2; 2/1,1; 2/2; 1,1,1,1; 1,1,2; 1,2,1; 2,1,1.


MAPLE

with(numtheory):with(combinat):
a:= proc(n) option remember; `if`(n=0, 1, add(add(d*
fibonacci(d+1), d=divisors(j))*a(nj), j=1..n)/n)
end:
seq(a(n), n=0..40); # Alois P. Heinz, Nov 05 2013


MATHEMATICA

CoefficientList[Series[Product[1/(1x^k)^Fibonacci[k+1], {k, 1, 40}], {x, 0, 40}], x] (* Vaclav Kotesovec, Aug 05 2015 *)


PROG

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


CROSSREFS

Cf. A000045, A034691, A166861, A260787, A337009.
Sequence in context: A006951 A224840 A132891 * A308448 A055890 A306884
Adjacent sequences: A200541 A200542 A200543 * A200545 A200546 A200547


KEYWORD

nonn


AUTHOR

Guy P. Srinivasan, Nov 18 2011


EXTENSIONS

Corrected terms from n=8 and onwards by Guy P. Srinivasan, Oct 18 2013
C# program corrected and made much more efficient by Guy P. Srinivasan, Oct 18 2013


STATUS

approved



