cp's OEIS Frontend

This is a front-end for the Online Encyclopedia of Integer Sequences, made by Christian Perfect. The idea is to provide OEIS entries in non-ancient HTML, and then to think about how they're presented visually. The source code is on GitHub.

Showing 1-3 of 3 results.

A190186 Numerator of expression W_n occurring in analysis of bubble sort.

Original entry on oeis.org

1, 2, 10, 29, 97, 739, 6331, 8617, 633127, 1037497, 90414391, 1214394319, 17506484887, 38519714137, 4419404086711, 10972377997177, 1410921315134167, 27316952872520239, 555986170009834231, 154130283599461067, 265123004099257677847, 883735015159907270617, 150492959376114678237751, 293138621437723505079883, 100289605416287509517021527
Offset: 1

Views

Author

N. J. A. Sloane, May 05 2011

Keywords

Examples

			1, 2, 10/3, 29/6, 97/15, 739/90, 6331/630, 8617/720, 633127/45360, 1037497/64800, ...

References

  • D. E. Knuth, The Art of Computer Programming, Vol. 3, Section 5.2.2, p. 129.

Links

Crossrefs

Cf. A190187.

Programs

  • Maple
    W:=proc(n) local t1,r,s;
t1:=add( add(s!*r^(n-s), s=r+1..n), r=0..n-1);
t1/n!;
end;
  • Mathematica
    Numerator[Table[n! + Sum[ Sum[s!*k^(n - s), {s, k + 1, n}], {k, 1, n - 1}]/n!, {n, 1, 50}]] (* G. C. Greubel, Dec 29 2017 *)
  • PARI
    for(n=1,30, print1(numerator(1 + sum(k=1,n-1, sum(s=k+1, n, s!*k^(n-s)))/n!), ", ")) \\ G. C. Greubel, Dec 29 2017

Formula

W_n = Sum_{r=0..(n-1)}( Sum_{s=(r+1)..n} s!*r^(n-s) )/n!.
W_n = numerator(A190194(n)/n!).

A190187 Denominator of expression W_n occurring in analysis of bubble sort.

Original entry on oeis.org

1, 1, 3, 6, 15, 90, 630, 720, 45360, 64800, 4989600, 59875200, 778377600, 1556755200, 163459296000, 373621248000, 44460928512000, 800296713216000, 15205637551104000, 3949516247040000, 6386367771463680000, 20071441567457280000, 3231502092360622080000, 5965850016665763840000, 1938901255416373248000000, 7201633234403672064000000
Offset: 1

Views

Author

N. J. A. Sloane, May 05 2011

Keywords

Examples

			1, 2, 10/3, 29/6, 97/15, 739/90, 6331/630, 8617/720, 633127/45360, 1037497/64800, ...

References

  • D. E. Knuth, The Art of Computer Programming, Vol. 3, Section 5.2.2, p. 129.

Links

Crossrefs

Cf. A190186.

Programs

  • Maple
    W:=proc(n) local t1,r,s;
t1:=add( add(s!*r^(n-s), s=r+1..n), r=0..n-1);
t1/n!;
end;
  • Mathematica
    Denominator[Table[n! + Sum[ Sum[s!*k^(n - s), {s, k + 1, n}], {k, 1, n - 1}]/n!, {n, 1, 50}]] (* G. C. Greubel, Dec 28 2017 *)
  • PARI
    for(n=1,30, print1(denominator(1 + sum(k=1,n-1, sum(s=k+1, n, s!*k^(n-s)))/n!), ", ")) \\ G. C. Greubel, Dec 28 2017

Formula

W_n = Sum_{r=0..(n-1)}( Sum_{s=(r+1)..n} s!*r^(n-s) )/n!.
W_n = denominator(A190194(n)/n!).

A350660 a(n) is the average number of key comparisons, rounded to the nearest integer, required to sort n records with distinct keys using bubble sort (Algorithm B in Don Knuth's TAOCP Vol. 3).

Original entry on oeis.org

1, 3, 5, 9, 13, 18, 24, 31, 39, 48, 58, 69, 80, 93, 107, 121, 137, 153, 171, 189, 209, 229, 251, 273, 297, 321, 346, 373, 400, 428, 458, 488, 519, 551, 584, 619, 654, 690, 727, 765, 804, 845, 886, 928, 971, 1015, 1060, 1106, 1153, 1201, 1250, 1300, 1351, 1403
Offset: 2

Views

Author

Hugo Pfoertner, Feb 01 2022

Keywords

Examples

			        n        b(n)
        |         |         a(n)=
        |         |      round(b(n))
        |         |           |   b(n)/n^2
        2        1/1          1   0.2500
        3        8/3          3   0.2963
        4       31/6          5   0.3229
        5      128/15         9   0.3413
        6     1151/90        13   0.3552
        7    11309/630       18   0.3663
        8    17303/720       24   0.3755
        9  1408073/45360     31   0.3832
       10  2526503/64800     39   0.3899
      100                  4768   0.4768
     1000                496458   0.4965
    10000                         0.4995
   100000                         0.4999
  1000000                         0.5000

References

  • D. E. Knuth, The Art of Computer Programming Second Edition. Vol. 3, Sorting and Searching. Chapter 5.2.2 Sorting by Exchanging, pages 106-109, 128-130. Addison-Wesley, Reading, MA, 1998.

Crossrefs

Cf. A001620, A190186, A190187, A190194, A350428, A350568, A350569.

Formula

a(n) = round(b(n)).
b(n) = binomial(n+1,2) - A190186(n)/A190187(n).
b(n) = binomial(m,2) - ((m/2)*(log(m) + gamma +log(2)) - 2*sqrt(2*Pi*m)/3 + 49/36 + O(n^(-1/2))) with gamma = A001620, and m = n + 1 (Knuth's asymptotic formula (37), TAOCP vol. 3, page 130).
a(n)/n^2 -> 1/2 for n -> infinity.
Showing 1-3 of 3 results.

Started in 1964 by Neil J. A. Sloane | Maintained by The OEIS Foundation Inc.

Content is available under The OEIS End-User License Agreement.