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

[Neil Sloane]

Hugo, Your version is also very interesting.
And is a lot more pleasing to think about (however, it isn't
the definition that pops out of Shirshov's theorem).

So it would be interesting if you produced analogs of
the sequences listed in A210109 that were based on your notion.

Also, if you have programs for your version, I would
very much like to see them. This investigation is connected
to a problem that my colleague David Applegate and I
have been working on.

I'll copy this to him.

Neil



On Fri, Mar 23, 2012 at 4:24 AM, <hv at crypt.org> wrote:

> 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
>
> _______________________________________________
>
> Seqfan Mailing list - http://list.seqfan.eu/
>



-- 
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