login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A232193 Numerators of the expected value of the length of a random cycle in a random n-permutation. 4
1, 3, 23, 55, 1901, 4277, 198721, 16083, 14097247, 4325321, 2132509567, 4527766399, 13064406523627, 905730205, 13325653738373, 362555126427073, 14845854129333883, 57424625956493833, 333374427829017307697, 922050973293317, 236387355420350878139797 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,2

COMMENTS

In this experiment we randomly select (uniform distribution) an n-permutation and then randomly select one of the cycles from that permutation.  Cf. A102928/A175441 which gives the expected cycle length when we simply randomly select a cycle.

LINKS

Alois P. Heinz, Table of n, a(n) for n = 1..250

FORMULA

a(n) = Numerator( 1/(n-1)! * Sum_{i=1..n} A132393(n,i)/i ). - Alois P. Heinz, Nov 23 2013

a(n) = numerator(Sum_{k=0..n} A002657(k)/A091137(k)) (conjectured). - Michel Marcus, Jul 19 2019

EXAMPLE

Expectations for n=1,... are 1/1, 3/2, 23/12, 55/24, 1901/720, 4277/1440, 198721/60480, 16083/4480, ... = A232193/A232248

For n=3 there are 6 permutations.  We have probability 1/6 of selecting (1)(2)(3) and the cycle size is 1.  We have probability 3/6 of selecting a permutation with cycle type (1)(23) and (on average) the cycle length is 3/2.  We have probability 2/6 of selecting a permutation of the form (123) and the cycle size is 3.  1/6*1 + 3/6*3/2 + 2/6*3 = 23/12.

MAPLE

with(combinat):

b:= proc(n, i) option remember; `if`(n=0, 1, `if`(i<1, 0,

      expand(add(multinomial(n, n-i*j, i$j)/j!*(i-1)!^j

      *b(n-i*j, i-1) *x^j, j=0..n/i))))

    end:

a:= n->numer((p->add(coeff(p, x, i)/i, i=1..n))(b(n$2))/(n-1)!):

seq(a(n), n=1..30);  # Alois P. Heinz, Nov 21 2013

# second Maple program:

a:= n-> numer(add(abs(combinat[stirling1](n, i))/i, i=1..n)/(n-1)!):

seq(a(n), n=1..30);  # Alois P. Heinz, Nov 23 2013

MATHEMATICA

Table[Numerator[Total[Map[Total[#]!/Product[#[[i]], {i, 1, Length[#]}]/Apply[Times, Table[Count[#, k]!, {k, 1, Max[#]}]]/(Total[#]-1)!/Length[#]&, Partitions[n]]]], {n, 1, 25}]

CROSSREFS

Denominators are A232248.

Cf. A028417(n)/n! the expected value of the length of the shortest cycle in a random n-permutation.

Cf. A028418(n)/n! the expected value of the length of the longest cycle in a random n-permutation.

Sequence in context: A031907 A181422 A082244 * A141047 A196538 A216418

Adjacent sequences:  A232190 A232191 A232192 * A232194 A232195 A232196

KEYWORD

nonn,frac

AUTHOR

Geoffrey Critzer, Nov 20 2013

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified June 26 11:11 EDT 2022. Contains 354881 sequences. (Running on oeis4.)