cp's OEIS Frontend

A232193 Numerators of the expected value of the length of a random cycle in a random n-permutation.

%I A232193 #25 Jul 19 2019 04:24:09
%S A232193 1,3,23,55,1901,4277,198721,16083,14097247,4325321,2132509567,
%T A232193 4527766399,13064406523627,905730205,13325653738373,362555126427073,
%U A232193 14845854129333883,57424625956493833,333374427829017307697,922050973293317,236387355420350878139797
%N A232193 Numerators of the expected value of the length of a random cycle in a random n-permutation.
%C A232193 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.
%H A232193 Alois P. Heinz, <a href="/A232193/b232193.txt">Table of n, a(n) for n = 1..250</a>
%F A232193 a(n) = Numerator( 1/(n-1)! * Sum_{i=1..n} A132393(n,i)/i ). - _Alois P. Heinz_, Nov 23 2013
%F A232193 a(n) = numerator(Sum_{k=0..n} A002657(k)/A091137(k)) (conjectured). - _Michel Marcus_, Jul 19 2019
%e A232193 Expectations for n=1,... are 1/1, 3/2, 23/12, 55/24, 1901/720, 4277/1440, 198721/60480, 16083/4480, ... = A232193/A232248
%e A232193 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.
%p A232193 with(combinat):
%p A232193 b:= proc(n, i) option remember; `if`(n=0, 1, `if`(i<1, 0,
%p A232193       expand(add(multinomial(n, n-i*j, i$j)/j!*(i-1)!^j
%p A232193       *b(n-i*j, i-1) *x^j, j=0..n/i))))
%p A232193     end:
%p A232193 a:= n->numer((p->add(coeff(p, x, i)/i, i=1..n))(b(n$2))/(n-1)!):
%p A232193 seq(a(n), n=1..30);  # _Alois P. Heinz_, Nov 21 2013
%p A232193 # second Maple program:
%p A232193 a:= n-> numer(add(abs(combinat[stirling1](n, i))/i, i=1..n)/(n-1)!):
%p A232193 seq(a(n), n=1..30);  # _Alois P. Heinz_, Nov 23 2013
%t A232193 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}]
%Y A232193 Denominators are A232248.
%Y A232193 Cf. A028417(n)/n! the expected value of the length of the shortest cycle in a random n-permutation.
%Y A232193 Cf. A028418(n)/n! the expected value of the length of the longest cycle in a random n-permutation.
%K A232193 nonn,frac
%O A232193 1,2
%A A232193 _Geoffrey Critzer_, Nov 20 2013