cp's OEIS Frontend

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

%I A180239 #28 Mar 31 2024 12:04:34
%S A180239 1,4,16,64,244,856,2776,8356,23032,59200,142624,324484,696256,1422436,
%T A180239 2779900,5219452,9455596
%N A180239 a(n) is the number of distinct billiard words with length n on an alphabet of 4 symbols.
%C A180239 Computation: _Fred Lunnon_ for n <= 16 (Magma).
%H A180239 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 A180239 Fred Lunnon, <a href="/A180239/a180239_2.txt">Magma Program</a>
%H A180239 Laurent Vuillon, <a href="http://projecteuclid.org/euclid.bbms/1074791332">Balanced Words</a>, Bull. Belg. Math. Soc. 10 (2003), 787-805.
%F A180239 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 A180239 For n = 5 there are a(5) = 856 words, permutations on {1,2,3,4} of the 42 words
%e A180239 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 A180239 (Magma) // See Links.
%Y A180239 See A005598 for 2 symbols, A180238 for 3 symbols.
%K A180239 nonn,more
%O A180239 0,2
%A A180239 _Fred Lunnon_, Aug 18 2010