cp's OEIS Frontend

A168368 Number of stable connected piles of n bricks.

%I A168368 #17 Feb 16 2025 08:33:11
%S A168368 0,1,1,2,4,7,12,21
%N A168368 Number of stable connected piles of n bricks.
%C A168368 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 A168368 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 A168368 Connected piles only (allowing piles with disconnected subpiles would produce a different sequence).
%C A168368 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 A168368 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 A168368 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 A168368 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 A168368 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 A168368 ... & ..... & ....... & ...|=|...
%C A168368 ... & ..... & ....... & ..|=|=|..
%C A168368 ... & ..... & ..|=|.. & .|=|=|=|.
%C A168368 ... & ..... & .|=|=|. & |=|=|=|=|
%C A168368 ... & .|=|. & |=|=|=| & .|=|=|=|.
%C A168368 ... & |=|=| & .|=|=|. & ..|=|=|..
%C A168368 |=| & .|=|. & ..|=|.. & ...|=|...
%C A168368 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 A168368 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 A168368 .<2>.
%C A168368 |B|B|
%C A168368 .<5>.
%C A168368 -----
%C A168368 = 6 = balancing bricks.
%C A168368 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 A168368 .|B|.
%C A168368 |B|B|
%C A168368 .<2>. or .<2>.
%C A168368 |B|B| or |B|B|
%C A168368 .<2>. or .<2>. or .<2>. or .|B|.
%C A168368 |B|B| or |B|B| or |B|B| or |B|B|
%C A168368 .<2>. or .<2>. or .<3>. or .<2>. or .<3>.
%C A168368 |B|B| or |B|B| or |B|B| or |B|B| or |B|B|
%C A168368 .<2>. or .<3>. or .<3>. or .<4>. or .<4>.
%C A168368 |B|B| or |B|B| or |B|B| or |B|B| or |B|B|
%C A168368 .<6>. or .<6>. or .<6>. or .<6>. or .<6>.
%C A168368 ----- .. ----- .. ----- .. ----- .. -----
%C A168368 = 27= .. = 29= .. = 28= .. = 27= .. = 29= balancing bricks.
%C A168368 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 A168368 .|B|.
%C A168368 |B|B|
%C A168368 .<3>.
%C A168368 |B|B|
%C A168368 .<5>.
%C A168368 |B|B|
%C A168368 .<6>.
%C A168368 |B|B|
%C A168368 .<7>.
%C A168368 -----
%C A168368 = 79 = balancing bricks (where <5> itself needs 6 balancing bricks).
%H A168368 Daniel Forgues, <a href="/A168368/a168368.txt">Graphic depictions for larger n</a>
%H A168368 Mike Paterson et al., <a href="http://math.dartmouth.edu/~pw/papers/maxover.pdf">Maximum Overhang</a>
%H A168368 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/FibonacciNumber.html">Fibonacci Number</a>
%H A168368 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/TribonacciNumber.html">Tribonacci Number</a>
%H A168368 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/Fibonaccin-StepNumber.html">Fibonacci n-Step Number</a>
%e A168368 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 A168368 For n = 0, the following 0 [F_0] piles:
%e A168368 ( { } )
%e A168368 For n = 1, the following 1 [F_1 = C(0, 0) = 1] pile:
%e A168368 ( { |=| } )
%e A168368 For n = 2, the following 1 [F_2 = C(1, 0) = 1] pile:
%e A168368 ( { |=|=| } )
%e A168368 For n = 3, the following 2 [F_3 = C(2, 0) + C(1, 1) = 2] piles:
%e A168368 ( { ....... } & { .|=|. } )
%e A168368 ( { |=|=|=| } & { |=|=| } )
%e A168368 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 A168368 ( { ......... } & { ....... & ....... } ) & { .|=|. }
%e A168368 ( { ......... } & { .|=|... & ...|=|. } ) & { |=|=| }
%e A168368 ( { |=|=|=|=| } & { |=|=|=| & |=|=|=| } ) & { .|=|. }
%Y A168368 Cf. A001524, A005169.
%K A168368 more,nonn
%O A168368 0,4
%A A168368 _Franklin T. Adams-Watters_, Nov 24 2009
%E A168368 Edited by _Daniel Forgues_, Nov 29 2009, Dec 13 2009