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

[hv at crypt.org]

Richard Mathar <mathar at strw.leidenuniv.nl> wrote:
:
: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.

Thanks Richard, so I was trying to assert A < B instead of AB < BA; and
worse, the latter cannot even be determined locally (ie there are clearly
A, B, C with AB < BA and BC < CB but CAB > ABC).

I'll look further this weekend.

Hugo