A386673 Indices of ascending runs in a random sequence in order of increasing expected length.
1, 2, 3, 7, 8, 9, 13, 14, 12, 18, 19, 23, 24, 25, 29, 30, 28, 34, 35, 39, 40, 41, 45, 46, 44, 50, 51, 55, 56, 57, 61, 60, 62, 66, 67, 71, 72, 73, 77, 76, 78, 82, 83, 87, 88, 89, 93, 92, 94, 98, 99, 103, 104, 105, 109, 108, 110, 114, 115, 119, 120, 121, 125
Offset: 1
Keywords
Examples
min{L(k) : k>=1} = L(1) = e-1, so the first run has shortest expected length and a(1) = 1.
The second and third runs have second and third shortest expected length, so a(2) = 2 and a(3) = 3.
The fourth smallest value in the set {L(k) : k>=1} is L(7), so the seventh run has fourth shortest expected length and a(4) = 7.
References
- Donald E. Knuth. The Art of Computer Programming. Vol. 3: Sorting and Searching. Addison-Wesley, second edition, 1998, pages 39-42,45,603.
Links
- David Bevan, Table of n, a(n) for n = 1..1000
- Betty Jane Gassner, Sorting by replacement selecting, Commun. ACM, 10(2):89-93, 1967.
- William W. Hooker, On the expected lengths of sequences generated in sorting by replacement selecting, Commun. ACM, 12(7):411-413, 1969.
Crossrefs
The natural numbers are partitioned between this sequence and A386674.
Programs
-
Mathematica
eLen[1]=N[E-1];eLen[k_]:=N[k Sum[(-1)^j(k-j)^(j-1)/j!E^(k-j),{j,0,k-1}],k+10];incList[n_]:=First/@Take[SortBy[Table[{k,eLen[k]},{k,2n+8}],Last],n];incList@20
Formula
If k>=2, then the expected length of the k-th ascending run is L(k) = k * Sum_{j=0..k-1} (-1)^j*(k-j)^(j-1)*exp(k-j)/j!. The expected length of the first run is L(1) = e-1.
The o.g.f. for L(k) is z*(1-z)/(exp(z-1)-z)-z.
Limit_{k->oo} L(k) = 2.
If z ~ 3.088843 + 7.461489i satisfies z=exp(z-1), then asymptotically L(k)-2 ~ 2*r^-k*cos(k*t), where r = |z| ~ 8.075566, and t = arg(z) ~ 1.178304 ~ Pi/2.666199.
Comments