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

%I #28 Mar 31 2024 12:04:34

%S 1,4,16,64,244,856,2776,8356,23032,59200,142624,324484,696256,1422436,

%T 2779900,5219452,9455596

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

%C Computation: _Fred Lunnon_ for n <= 16 (Magma).

%H Jean-Pierre Borel, <a href="http://hal.archives-ouvertes.fr/hal-00465586">A geometrical Characterization of factors of multidimensional Billiards words and some Applications</a>, Theoretical Computer Science 380 (2007) 286--303.

%H Fred Lunnon, <a href="/A180239/a180239_2.txt">Magma Program</a>

%H Laurent Vuillon, <a href="http://projecteuclid.org/euclid.bbms/1074791332">Balanced Words</a>, Bull. Belg. Math. Soc. 10 (2003), 787-805.

%F 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!

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

%e 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.

%o (Magma) // See Links.

%Y See A005598 for 2 symbols, A180238 for 3 symbols.

%K nonn,more

%O 0,2

%A _Fred Lunnon_, Aug 18 2010