[seqfan] Number of k-divided sequences (corrected)

[Neil Sloane]

There were 2 typos. Here is a corrected version

Dear Seq Fans

Fix the alphabet A = {0,1,2,... a-1}

There is a lexicographic order on words over A defined
in the obvious way: i<j for single letters,
U < V if in the first place where they differ, U_i < V_i,
U < UV if V is nonempty, etc.

A sequence (or string, or word) S of length n
with entries from A is called "k-divided over A" if
you can write it as
S = U_1 U_2 ... U_k
with the property that for any nontrivial permutation
pi of {1..k} we have

S < U_pi_1 U_pi_2 ... U_pi_k

Examples: take A={0,1}

S = 011011 is 2-divided because we can take U_1=0, U_2=11011
and  S < 11011.0 = 110110
You only need to find one way of breaking up the string that works.

S = 1111 is not 2-divided, because where ever you break it
you get S = U_2 U_1 and we require strict inequality.

S = 0.01.011 is 3-divided

Sequences A209970 and A210109 give the numbers of
2-divided and 3-divided words of length n over {0,1}
(unless there is a bug in my program, which is not impossible).

What I would like are the numbers of k-divided sequences
over A={0,1} and A={0,1,2} for more small
values of k, or even larger values in the binary case.

Since this involves permutations and strings,
I'm wondering if any of the Magma experts on
this list could produce a program?

Neil


-- 
Dear Friends, I will soon be retiring from AT&T. New coordinates:

Neil J. A. Sloane, President, OEIS Foundation
11 South Adelaide Avenue, Highland Park, NJ 08904, USA
Phone: 732 828 6098; home page: http://NeilSloane.com
Email: njasloane at gmail.com