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