[seqfan] Re: Number of k-divided sequences (corrected)
Richard Mathar
mathar at strw.leidenuniv.nl
Wed Mar 21 23:23:44 CET 2012
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.
More information about the SeqFan
mailing list