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

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

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+2-1 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)+2-1 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 row-reversed rows of the Multiset transform T(n,k) of the Fibonacci sequence in A337009, a(k) = lim(n->oo) T(n,n-k). - R. J. Mathar, Aug 10 2020

Links

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

W. S. Gray, K. Ebrahimi-Fard, 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]+mk-1,mk))).

G.f.: Product_{s>=1}(sum{d>=0}(binomial(F(s+1)+d-1,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

a(n) = A337009(2*n,n). - Alois P. Heinz, Apr 30 2023

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(n-j), j=1..n)/n)
    end:
seq(a(n), n=0..40);  # Alois P. Heinz, Nov 05 2013

Mathematica

CoefficientList[Series[Product[1/(1-x^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: A345334 A354294 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