A210323 -id:A210323 - cp's OEIS frontend

A210109 Number of 3-divided binary sequences (or words) of length n.

0, 0, 0, 2, 7, 23, 54, 132, 290, 634, 1342, 2834, 5868, 12140, 24899, 50929, 103735, 210901, 427623, 865910, 1750505, 3535098, 7131321, 14374647, 28952661, 58280123, 117248217, 235770302, 473897980, 952183214, 1912535827, 3840345963, 7709282937, 15472242645, 31045402788, 62280978042

Offset: 1

N. J. A. Sloane, Mar 17 2012

nonn

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.
More generally, fix an alphabet A = {0,1,2,...,a-1}.
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.
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].
All 2^n binary words are 1-divided. For 2-divided words see A209970.
"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.

			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.
0.01.1
0.10.1
0.001.1
0.010.1
0.01.10
0.01.11
0.100.1
0.10.11
0.110.1

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.

Michael S. Branicky, Python program using bitwise operations
Giuseppe Pirillo and Stefano Varricchio, Some combinatorial properties of infinite words and applications to semigroup theory. 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).

Number of k-divided words of length n over alphabet of size A:
A=2, k=2,3,4,5: A209970 (and A209919, A000031, A001037), A210109 (and A210145), A210321, A210322;
A=3, k=2,3,4,5: A210323 (and A001867, A027376), A210324, A210325, A210326;
A=4, k=2,3,4: A210424 (and A001868, A027377), A210425, A210426.

# see link for faster, bit-based version
from itertools import product
def is3div(b):
    for i in range(1, len(b)-1):
        for j in range(i+1, len(b)):
            X, Y, Z = b[:i], b[i:j], b[j:]
            if all(b < bp for bp in [Z+Y+X, Z+X+Y, Y+Z+X, Y+X+Z, X+Z+Y]):
                return True
    return False
def a(n): return sum(is3div("".join(b)) for b in product("01", repeat=n))
print([a(n) for n in range(1, 16)]) # Michael S. Branicky, Aug 27 2021

Is there a formula or recurrence?

Values confirmed and a(30)-a(31) by David Applegate, Mar 19 2012

a(32)-a(36) from Michael S. Branicky, Aug 27 2021

A209970 a(n) = 2^n - A000031(n).

Original entry on oeis.org

0, 0, 1, 4, 10, 24, 50, 108, 220, 452, 916, 1860, 3744, 7560, 15202, 30576, 61420, 123360, 247542, 496692, 996088, 1997272, 4003558, 8023884, 16077964, 32212248, 64527436, 129246660, 258847876, 518358120, 1037949256, 2078209980, 4160747500, 8329633416, 16674575056, 33378031536

Offset: 0

David Applegate and N. J. A. Sloane, Mar 17 2012

nonn

a(n) is also the number of 2-divided binary words of length n (see A210109 for definition, see A209919 for further details).
This is a special case of a more general result: Let A={0,1,...,s-1} be an alphabet of size s. Let A* = set of words over A. Let < denote lexicographic order on A*. Let f be the morphism on A* defined by i -> s-i for i in A.
Theorem: Let d(n) be the number of 2-divided words in A* of length n, and let b(n) be the number of rotationally inequivalent necklaces with n beads each in A. Then d(n)+b(n)=s^n.
Proof: Let w in A* have length n. If w is <= all of its cyclic shifts then w contributes to the b(n) count. Otherwise w = uv with vu < uv. But then f(w)=f(u)f(v) with f(u)f(v) < f(v)f(u) is 2-divided, and w contributes to the count in d(n). QED
Cor.: A000031(n) + A209970(n) = 2^n, A001867(n) + A210323(n) = 3^n, A001868(n) + A210424(n) = 4^n.

Cf. A000031, A210109, A209919.

cp's OEIS Frontend

A210109 Number of 3-divided binary sequences (or words) of length n.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Python

Formula