login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A168368 Number of stable connected piles of n bricks. 1
0, 1, 1, 2, 4, 7, 12, 21 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,4

COMMENTS

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.

Since the main goal of the Paterson paper is the search for stable piles with maximum overhang (and not to count 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).

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

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 (less piles of bricks since the piles would constitute a subset of the ones obtained from the current piles.)

a(0) 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, ...}.

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

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

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

... & ..... & ....... & ...|=|...

... & ..... & ....... & ..|=|=|..

... & ..... & ..|=|.. & .|=|=|=|.

... & ..... & .|=|=|. & |=|=|=|=|

... & .|=|. & |=|=|=| & .|=|=|=|.

... & |=|=| & .|=|=|. & ..|=|=|..

|=| & .|=|. & ..|=|.. & ...|=|...

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.

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

.<2>.

|B|B|

.<5>.

-----

= 6 = balancing bricks.

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

.|B|.

|B|B|

.<2>. or .<2>.

|B|B| or |B|B|

.<2>. or .<2>. or .<2>. or .|B|.

|B|B| or |B|B| or |B|B| or |B|B|

.<2>. or .<2>. or .<3>. or .<2>. or .<3>.

|B|B| or |B|B| or |B|B| or |B|B| or |B|B|

.<2>. or .<3>. or .<3>. or .<4>. or .<4>.

|B|B| or |B|B| or |B|B| or |B|B| or |B|B|

.<6>. or .<6>. or .<6>. or .<6>. or .<6>.

----- .. ----- .. ----- .. ----- .. -----

= 27= .. = 29= .. = 28= .. = 27= .. = 29= balancing bricks.

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:

.|B|.

|B|B|

.<3>.

|B|B|

.<5>.

|B|B|

.<6>.

|B|B|

.<7>.

-----

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

LINKS

Table of n, a(n) for n=0..7.

Daniel Forgues, Graphic depictions for larger n.

Mike Paterson et al, Maximum Overhang

Eric Weisstein's World of Mathematics, Fibonacci Number.

Eric Weisstein's World of Mathematics, Tribonacci Number.

Eric Weisstein's World of Mathematics, Fibonacci n-Step Number.

EXAMPLE

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

For n = 0, the following 0 [F_0] pile:

( { } )

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

( { |=| } )

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

( { |=|=| } )

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

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

( { |=|=|=| } & { |=|=| } )

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

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

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

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

CROSSREFS

Cf. A005169, A001524.

Sequence in context: A079970 A079816 A178937 * A182746 A100482 A003293

Adjacent sequences:  A168365 A168366 A168367 * A168369 A168370 A168371

KEYWORD

more,nonn

AUTHOR

Franklin T. Adams-Watters, Nov 24 2009

EXTENSIONS

Edited by Daniel Forgues, Nov 29 2009, Dec 13 2009

STATUS

approved

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

Content is available under The OEIS End-User License Agreement .

Last modified October 25 17:33 EDT 2014. Contains 248557 sequences.