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

[Richard Mathar]

http://list.seqfan.eu/pipermail/seqfan/2012-March/016615.html

hv> From seqfan-bounces at list.seqfan.eu Wed Mar 21 22:39:20 2012
hv> Subject: [seqfan] Re: Number of k-divided sequences (corrected)
hv> 
hv> For k=2, I believe the definition above is equivalent to:
hv>   S can be 2-divided over A if there exists a way of splitting S into
hv>   2 non-empty substrings s_1 s_2, such that s_1 < s_2.
hv> 
hv> Considering base 2, k=2, length n, I then reasoned (for n >= 3):
hv> - if the first digit is 0 we can split immediately after if for s_1 < s_2;

Unless all the other digits are also 0...
hv> - if the first digit is 1, then:
hv>   - if there are 3 or more '1' digits, we can split before the second and
hv>     guarantee s_1 < s_2;

Counterexamples to that rule are for example at n=4 the words
 1 1 1 0 0
or
 1 1 1 1 0
If split as
 1.1 1 0 0
and
 1.1 1 1 0
we have the permuted products s2 s1
 1 1 0 0.1
and
 1 1 1 0.1
which are smaller than s1 s2.