login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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+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

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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified June 24 02:56 EDT 2021. Contains 345415 sequences. (Running on oeis4.)