[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/016590.html
:
:njas> From seqfan-bounces at list.seqfan.eu Mon Mar 19 18:00:48 2012
:njas> To: seqfan at list.seqfan.eu
:njas> Subject: [seqfan] Number of k-divided sequences (corrected)
:njas> 
:njas> A sequence (or string, or word) S of length n
:njas> with entries from A is called "k-divided over A" if
:njas> you can write it as
:njas> S = U_1 U_2 ... U_k
:njas> with the property that for any nontrivial permutation
:njas> pi of {1..k} we have
:njas> 
:njas> S < U_pi_1 U_pi_2 ... U_pi_k
:
:I have compared A209970, A210109 , A210323 (2 or 3 letters with k=2 or k=3) for 
:words of length n <=17 with my program and the counts match.
:Further results predicted as follows:
:
:base 2 k 2
:2 1
:3 4
:4 10
:5 24
:6 50
:7 108
:8 220
:9 452
:10 916
:11 1860
:12 3744
:13 7560
:14 15202

I guess I must have misunderstood the rules, so maybe I've inadvertently
invented a new [set of] sequence(s).

For k=2, I believe the definition above is equivalent to:
  S can be 2-divided over A if there exists a way of splitting S into
  2 non-empty substrings s_1 s_2, such that s_1 < s_2.

Considering base 2, k=2, length n, I then reasoned (for n >= 3):
- if the first digit is 0 we can split immediately after if for s_1 < s_2;
- if the first digit is 1, then:
  - if there are 3 or more '1' digits, we can split before the second and
    guarantee s_1 < s_2;
  - if there are 2 '1' digits, we can only usefully split just before the
    second one, and can be 2-divided only if the second '1' is before
    the midpoint;
  - if the first digit is the only '1' we cannot be 2-divided.

On that basis, I expected the above sequence to yield 2^n - (1 + floor(n/2))
for n >= 3.

What have I misunderstood?

Regardless of the answer to that question, I think my "equivalent" definition
above could produce an interesting family of sequences in its own right for
k > 2 (or for k >= 2, if it turns out that it is inequivalent even at 2) -
while for b=2, k=2 it seems quite tractable, it quickly gets more complex
for any other values.

Hugo