A180239 a(n) is the number of distinct billiard words with length n on an alphabet of 4 symbols.

1, 4, 16, 64, 244, 856, 2776, 8356, 23032, 59200, 142624, 324484, 696256, 1422436, 2779900, 5219452, 9455596

Offset

0,2

Comments

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

Links

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

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

Fred Lunnon, Magma Program

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.

Prog

(Magma) // See Links.

Crossrefs

See A005598 for 2 symbols, A180238 for 3 symbols.

Sequence in context: A289694 A232425 A375865 * A006811 A269685 A269614

Adjacent sequences: A180236 A180237 A180238 * A180240 A180241 A180242

Keyword

nonn,more

Author

Fred Lunnon, Aug 18 2010

Status

approved