|
%I #57 Aug 18 2022 22:45:29
%S 0,0,0,2,7,23,54,132,290,634,1342,2834,5868,12140,24899,50929,103735,
%T 210901,427623,865910,1750505,3535098,7131321,14374647,28952661,
%U 58280123,117248217,235770302,473897980,952183214,1912535827,3840345963,7709282937,15472242645,31045402788,62280978042
%N Number of 3-divided binary sequences (or words) of length n.
%C A binary sequence (or word) W of length n is 3-divided if it can be written as a concatenation W = XYZ such that XYZ is strictly earlier in lexicographic order than any of the five permutations XZY, ZYX, YXZ, YZX, ZXY.
%C More generally, fix an alphabet A = {0,1,2,...,a-1}.
%C Define lexicographic order on words over A in the obvious way: for single letters, i < j is the natural order; for words U, V, we set U < V iff u_i < v_i at the first place where they differ; also U < UV if V is nonempty, etc.
%C Then a word U over A is "k-divided over A" if it can be written as U = X_1 X_2 ... X_k in such a way that X is strictly less in lexicographic order than X_pi_1 X_pi_2 ... X_pi_k for all nontrivial permutations pi of [1..k].
%C All 2^n binary words are 1-divided. For 2-divided words see A209970.
%C "k-divisible" would sound better to me than "k-divided", but I have followed Lothaire and Pirillo-Varricchio in using the latter term. Neither reference gives this sequence.
%D M. Lothaire, Combinatorics on words. A collective work by Dominique Perrin, Jean Berstel, Christian Choffrut, Robert Cori, Dominique Foata, Jean Eric Pin, Guiseppe Pirillo, Christophe Reutenauer, Marcel-P. Schützenberger, Jacques Sakarovitch and Imre Simon. With a foreword by Roger Lyndon. Edited and with a preface by Perrin. Encyclopedia of Mathematics and its Applications, 17. Addison-Wesley Publishing Co., Reading, Mass., 1983. xix+238 pp. ISBN: 0-201-13516-7, MR0675953 (84g:05002). See p. 144.
%H Michael S. Branicky, <a href="/A210109/a210109.txt">Python program using bitwise operations</a>
%H Giuseppe Pirillo and Stefano Varricchio, <a href="http://dx.doi.org/10.1016/0012-365X(95)00140-R">Some combinatorial properties of infinite words and applications to semigroup theory</a>. Proceedings of the 5th Conference on Formal Power Series and Algebraic Combinatorics (Florence, 1993). Discrete Math. 153 (1996), no. 1-3, pages 239-251, MR1394958 (98f:05018).
%F Is there a formula or recurrence?
%e The two 3-divisible binary words of length 4 and the seven of length 5 are as follows. The periods indicate the division w = x.y.z. For example, 0.01.1 is 3-divided since 0011 < all of 0101, 1010, 0101, 1001, 0110.
%e 0.01.1
%e 0.10.1
%e 0.001.1
%e 0.010.1
%e 0.01.10
%e 0.01.11
%e 0.100.1
%e 0.10.11
%e 0.110.1
%o (Python) # see link for faster, bit-based version
%o from itertools import product
%o def is3div(b):
%o for i in range(1, len(b)-1):
%o for j in range(i+1, len(b)):
%o X, Y, Z = b[:i], b[i:j], b[j:]
%o if all(b < bp for bp in [Z+Y+X, Z+X+Y, Y+Z+X, Y+X+Z, X+Z+Y]):
%o return True
%o return False
%o def a(n): return sum(is3div("".join(b)) for b in product("01", repeat=n))
%o print([a(n) for n in range(1, 16)]) # _Michael S. Branicky_, Aug 27 2021
%Y Number of k-divided words of length n over alphabet of size A:
%Y A=2, k=2,3,4,5: A209970 (and A209919, A000031, A001037), A210109 (and A210145), A210321, A210322;
%Y A=3, k=2,3,4,5: A210323 (and A001867, A027376), A210324, A210325, A210326;
%Y A=4, k=2,3,4: A210424 (and A001868, A027377), A210425, A210426.
%K nonn
%O 1,4
%A _N. J. A. Sloane_, Mar 17 2012
%E Values confirmed and a(30)-a(31) by _David Applegate_, Mar 19 2012
%E a(32)-a(36) from _Michael S. Branicky_, Aug 27 2021
|
