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

Author

Fred Lunnon, Aug 18 2010

Keywords

• nonn
• more

Comments

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

Examples

			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.
		

Links

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

Crossrefs

See A005598 for 2 symbols, A180238 for 3 symbols.

Programs

Magma

// See Links.

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!