A168368 - OEIS

%I #16 Jan 15 2018 06:45:52

%S 0,1,1,2,4,7,12,21

%N Number of stable connected piles of n bricks.

%C This sequence is similar to various sequences with rows of coins (often pennies). Each brick must be offset by 1/2 brick from any bricks under it. However, a brick might only have a brick under one half, provided the pile is stable. A definition of stability is provided in the Paterson paper.

%C Since the main goal of the Paterson paper is the search for stable piles with maximum overhang (and not to find the number of stable piles), it is likely that some stable piles configurations not leading to significant overhangs have been passed over. So it is not easy to determine whether or not all the stable piles configurations have been accounted for! So even though I added graphic depictions for n=8 and n=9 (cf. A168368a), I will abstain for now from appending a(8) and a(9) to this sequence until it has been ascertained that none are missing (please verify A168368a).

%C Connected piles only (allowing piles with disconnected subpiles would produce a different sequence).

%C For this sequence I assumed that the bricks on any given row need not be contiguous. A different sequence would be produced if we required the bricks on any given row to be contiguous (fewer piles of bricks since the piles would constitute a subset of the ones obtained from the current piles).

%C a(0) is set to 0 (no pile) instead of 1 (empty pile) since the number a(n) of stable connected piles of n bricks with height <= 2 is F_n (n-th Fibonacci number) and at least 4 bricks are needed to make a stable connected pile of height greater than 2 and outgrow the Fibonacci sequence {0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ...}.

%C The number of stable connected piles of n bricks is T_n (n-th tribonacci numbers, with a(0)=0, a(1)=a(2)=1, T_n = {0, 1, 1, 2, 4, 7, 13, 24, 44, 81, ...}) up to n=5, after which it falls behind (for n >= 6).

%C The following few comments describe only one of many kinds of stacks known to be self stable or stabilizable via a balancing set on top, e.g. the n-diamonds stacks.

%C The n-diamonds <n> (of width n, with n^2 bricks) are self stable (no balancing set needed) for n = 1 to 4 only (<1>, <2>, <3>, <4> only):

%C ... & ..... & ....... & ...|=|...

%C ... & ..... & ....... & ..|=|=|..

%C ... & ..... & ..|=|.. & .|=|=|=|.

%C ... & ..... & .|=|=|. & |=|=|=|=|

%C ... & .|=|. & |=|=|=| & .|=|=|=|.

%C ... & |=|=| & .|=|=|. & ..|=|=|..

%C |=| & .|=|. & ..|=|.. & ...|=|...

%C For n >= 5, the n-diamonds <n> need a balancing set with at least 2^n-n^2-1 bricks on top of the n^2 bricks of the n-diamond for a combined total of 2^n-1 bricks.

%C For n=5 we need a balancing set of at least 2^5-5^2-1 = 6 bricks |B|, e.g., a 2-diamond <2> on top of |B|B| to stabilize <5>:

%C .<2>.

%C |B|B|

%C .<5>.

%C -----

%C = 6 = balancing bricks.

%C For n=6 we need a balancing set of at least 2^6-6^2-1 = 27 bricks |B| to stabilize <6>, e.g.:

%C .|B|.

%C |B|B|

%C .<2>. or .<2>.

%C |B|B| or |B|B|

%C .<2>. or .<2>. or .<2>. or .|B|.

%C |B|B| or |B|B| or |B|B| or |B|B|

%C .<2>. or .<2>. or .<3>. or .<2>. or .<3>.

%C |B|B| or |B|B| or |B|B| or |B|B| or |B|B|

%C .<2>. or .<3>. or .<3>. or .<4>. or .<4>.

%C |B|B| or |B|B| or |B|B| or |B|B| or |B|B|

%C .<6>. or .<6>. or .<6>. or .<6>. or .<6>.

%C ----- .. ----- .. ----- .. ----- .. -----

%C = 27= .. = 29= .. = 28= .. = 27= .. = 29= balancing bricks.

%C For n=7 we need a balancing set of at least 2^7-7^2-1 = 78 bricks |B| to stabilize <7>, where the balancing set itself might need its own balancing subset as in the following example:

%C .|B|.

%C |B|B|

%C .<3>.

%C |B|B|

%C .<5>.

%C |B|B|

%C .<6>.

%C |B|B|

%C .<7>.

%C -----

%C = 79 = balancing bricks (where <5> itself needs 6 balancing bricks).

%H Daniel Forgues, <a href="/A168368/a168368.txt">Graphic depictions for larger n</a>

%H Mike Paterson et al., <a href="http://math.dartmouth.edu/~pw/papers/maxover.pdf">Maximum Overhang</a>

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/FibonacciNumber.html">Fibonacci Number</a>

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/TribonacciNumber.html">Tribonacci Number</a>

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/Fibonaccin-StepNumber.html">Fibonacci n-Step Number</a>

%e Following is a graphic depiction of the stable connected piles of bricks for n = 0 to 4 ordered by increasing height (all piles of a given height within curly braces) and each variant of a given pattern within square brackets, where C(k, i) is k choose i (binomial coefficient), F_n is n-th Fibonacci number [F_n = Sum_{k+i = n-1, i <= k} C(k, i)]. Also, the piles of heights 1 and 2 are grouped within parentheses (since they give the n-th Fibonacci number).

%e For n = 0, the following 0 [F_0] piles:

%e ( { } )

%e For n = 1, the following 1 [F_1 = C(0, 0) = 1] pile:

%e ( { |=| } )

%e For n = 2, the following 1 [F_2 = C(1, 0) = 1] pile:

%e ( { |=|=| } )

%e For n = 3, the following 2 [F_3 = C(2, 0) + C(1, 1) = 2] piles:

%e ( { ....... } & { .|=|. } )

%e ( { |=|=|=| } & { |=|=| } )

%e For n = 4, the following 4 [F_4 + 1 = (C(3, 0) + C(2, 1)) + 1 = 3 + 1] piles (where the brick on the third level is necessary for stability):

%e ( { ......... } & { ....... & ....... } ) & { .|=|. }

%e ( { ......... } & { .|=|... & ...|=|. } ) & { |=|=| }

%e ( { |=|=|=|=| } & { |=|=|=| & |=|=|=| } ) & { .|=|. }

%Y Cf. A001524, A005169.

%K more,nonn

%O 0,4

%A _Franklin T. Adams-Watters_, Nov 24 2009

%E Edited by _Daniel Forgues_, Nov 29 2009, Dec 13 2009