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

Author

Sarah Nibs, Nov 18 2011

Keywords

• nonn

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.

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

Examples

			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.
		

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
• Sarah Nibs, C# code to generate sequence terms
• Wikipedia, Jenga

Crossrefs

Cf. A000045, A034691, A166861, A260787, A337009.

Programs

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 *)

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

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))). - Sarah Nibs, Oct 21 2013

Euler Transform of A000045 starting at index 2, i.e. EULER(1, 2, 3, 5, 8, 13, ...). - Sarah Nibs, 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

Extensions

Corrected terms from n=8 and onwards by Sarah Nibs, Oct 18 2013

C# program corrected and made much more efficient by Sarah Nibs, Oct 18 2013