[seqfan] Re: What is THE random permutation?

[Neil Sloane]

Franklin, Thanks, yes, you are right: first make
sure that S_n has the minimal length, and *then*
if there is more than one choice, take the lex. earliest

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:45 PM, Frank Adams-Watters <franktaw at netscape.net>
wrote:

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