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!)
A180239 a(n) counts the distinct billiard words with length n on alphabet of 4 symbols. 5
1, 4, 16, 64, 244, 856, 2776, 8356, 23032, 59200, 142624, 324484, 696256, 1422436, 2779900, 5219452, 9455596 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,2

COMMENTS

Computation: Fred Lunnon for n <= 16 (MAGMA).

LINKS

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

Fred Lunnon, MAGMA Program

Jean-Pierre Borel, A geometrical Characterization of factors of multidimensional Billiards words and some Applications, Theoretical Computer Science 380 (2007) 286--303

Laurent Vuillon, Balanced Words, Bull. Belg. Math. Soc. 10 (2003), 787-805.

FORMULA

Expensive linear programming inequality analysis may be reduced by projecting each candidate word onto the axis hyperplanes, yielding m new (m-1)-symbol words which are necessarily also billiard, and can be validated from a precomputed list for dimension m-1. If any of these fails, the candidate fails; and if only one candidate remains after n-th symbols are attached to a valid (n-1)-length word, there is still no need for inequality analysis --- the ball cannot avoid bouncing next against some wall pair!

EXAMPLE

For n = 5 there are a(5) = 856 words, permutations on {1,2,3,4} of the 42 words

11111, 11112, 11121, 11123, 11211, 11212, 11213, 11231, 11234, 12111, 12112, 12113, 12121, 12122, 12123, 12131, 12132, 12134, 12212, 12213, 12221, 12222, 12223, 12231, 12232, 12234, 12311, 12312, 12313, 12314, 12321, 12322, 12323, 12324, 12331, 12332, 12333, 12334, 12341, 12342, 12343, 12344.

CROSSREFS

See A005598 for 2 symbols, A180238 for 3 symbols.

Sequence in context: A228735 A289694 A232425 * A006811 A269685 A269614

Adjacent sequences:  A180236 A180237 A180238 * A180240 A180241 A180242

KEYWORD

nonn

AUTHOR

Fred Lunnon, Aug 18 2010

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 September 28 17:43 EDT 2020. Contains 337393 sequences. (Running on oeis4.)