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
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.
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!
Comments