[seqfan] Re: What is THE random permutation?

[Frank Adams-Watters]

I've looked at things like this a few times. The problem I come up against is that "something like that". There seem to be lots of possibilities, none of which particularly recommend themselves. This one may be the best.

(I've mostly looked at sequences with every finite sequence of positive integers as a subsequence. That means you want all compositions of n to be in S_n. Otherwise it is a very similar challenge.)

By the way, you want to take minimal length as the first criterion, and only then look at the lexicographic order. Otherwise you can just keep inserting 1's.

Franklin T. Adams-Watters

-----Original Message-----
From: Neil Sloane <njasloane at gmail.com>
To: Sequence Fanatics Discussion list <seqfan at list.seqfan.eu>
Sent: Thu, Jun 25, 2015 5:34 pm
Subject: [seqfan] Re: What is THE random permutation?


PS Well, what if we try to build our own version?
We look for an infinite
sequence of natural numbers, with repeats.
Call it S_infinity.  This will be the
limiting sequence of S_1, S_2, S_3,...
We have:

S_1 = 1

S_2 = 121

S_3 is
(perhaps) 1213212312

The rules for finding S_n are:

   1. S_n must begin with
S_{n-1}

   2. Every one of the n! permutations of 1..n must appear somewhere
  
in a width-n window in S_n

   3. Out of all S_n satisfying 1. and 2. pick the
lexicographically
earliest

Or something like that!  Eric Angelini, is this
something you might
have considered?

Best regards
Neil

Neil J. A. Sloane,
President, OEIS Foundation.
11 South Adelaide Avenue, Highland Park, NJ 08904,
USA.
Also Visiting Scientist, Math. Dept., Rutgers University, Piscataway,
NJ.
Phone: 732 828 6098; home page: http://NeilSloane.com
Email:
njasloane at gmail.com


On Thu, Jun 25, 2015 at 6:02 PM, Neil Sloane
<njasloane at gmail.com> wrote:

> Allan, Thank you very much for looking into that
business!
> Pity the answer is "no sequence here".  I guess it
> was too much to
hope for that the permutation to end
> all permutations had managed to stay out
of the OEIS
> for all these years...
>
> Best regards
> Neil
>
> Neil J. A.
Sloane, President, OEIS Foundation.
> 11 South Adelaide Avenue, Highland Park,
NJ 08904, USA.
> Also Visiting Scientist, Math. Dept., Rutgers University,
Piscataway, NJ.
> Phone: 732 828 6098; home page: http://NeilSloane.com
> Email:
njasloane at gmail.com
>
>
> On Thu, Jun 25, 2015 at 1:48 PM, Allan Wechsler
<acwacw at gmail.com> wrote:
>
>> I nosed into the paper far enough to understand
that the so-called "random
>> permutation" is not itself a permutation of
anything. Rather, in some
>> technical sense, it "contains" all finite
permutations as "induced
>> substructures". Furthermore, it is the unique
smallest "structure" (this
>> is
>> a term of art from model theory) of the
class of all finite permutations.
>> This uniqueness, I think, is only up to
isomorphism, so even if it were
>> representable as, say, a permutation of the
integers (and I don't think it
>> is; I think it's a different kind of object),
the representation wouldn't
>> be unique.
>>
>>
>> On Mon, Jun 22, 2015 at 12:03
PM, Neil Sloane <njasloane at gmail.com>
>> wrote:
>>
>> > Dear Seq fans, there is
a paper in the latest issue of
>> > the Electronic J Combin, by Linman and
Pinsker,
>> > Permutations on the random permutation,
>> > see
http://www.combinatorics.org/ojs/index.php/eljc/issue/current
>> >
>> > They
talk about THE random permutation as a unique well-defined thing.
>> > It is the
Fraissee limit of something ...
>> >
>> > My question is, if this really is
unique and well-defined, what is it
>> > and shouldn't it be in the OEIS?
>>
>
>> > Maybe someone who is better educated in logic that I am can look into
>>
this?
>> >
>> >
>> > Best regards
>> > Neil
>> >
>> > Neil J. A. Sloane,
President, OEIS Foundation.
>> > 11 South Adelaide Avenue, Highland Park, NJ
08904, USA.
>> > Also Visiting Scientist, Math. Dept., Rutgers University,
Piscataway,
>> NJ.
>> > Phone: 732 828 6098; home page: http://NeilSloane.com
>>
> Email: njasloane at gmail.com
>> >
>> >
_______________________________________________
>> >
>> > Seqfan Mailing list -
http://list.seqfan.eu/
>> >
>>
>>
_______________________________________________
>>
>> Seqfan Mailing list -
http://list.seqfan.eu/
>>
>
>

_______________________________________________

Seqfan
Mailing list - http://list.seqfan.eu/