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-7 of 7 results.

A079750 Operation count to create all permutations of n distinct elements using the "streamlined" version of Algorithm L (lexicographic permutation generation) from Knuth's The Art of Computer Programming, Vol. 4, chapter 7.2.1.2. Sequence gives number of comparisons required to find j in step L2.2'.

Original entry on oeis.org

0, 4, 25, 156, 1099, 8800, 79209, 792100, 8713111, 104557344, 1359245485, 19029436804, 285441552075, 4567064833216, 77640102164689, 1397521838964420, 26552914940323999, 531058298806480000, 11152224274936080021
Offset: 3

Views

Author

Hugo Pfoertner, Jan 14 2003

Keywords

Comments

The asymptotic value for large n is 0.21828...*n! See also comment for A079884

References

Links

Crossrefs

Cf. A079884, A079751, A079752, A079753, A079754, A079755, A079756.

Programs

  • Fortran
    c Program available at link.
  • Maple
    a:=n->sum((n+1)!/j!,j=3..n): seq(a(n), n=2..20); # Zerinvary Lajos, Oct 20 2006
  • Mathematica
    a[3] = 0; a[n_] := n*a[n - 1] + n; Table[a[n], {n, 3, 21}]

Formula

a(3)=0, a(n) = n * a(n-1) + n for n >= 4.
a(n) = Sum_{j=3..n} (n+1)!/j!. - Zerinvary Lajos, Oct 20 2006
For n >= 3, a(n) = floor((e - 5/2)*n! - 1/2). - Benoit Cloitre, Aug 03 2007

Extensions

Edited and extended by Robert G. Wilson v, Jan 22 2003

A079756 Operation count to create all permutations of n distinct elements using the "streamlined" version of Algorithm L (lexicographic permutation generation) from Knuth's The Art of Computer Programming, Vol. 4, chapter 7.2.1.2. Sequence gives number of interchanges in reversal step.

Original entry on oeis.org

0, 0, 4, 29, 215, 1734, 15630, 156327, 1719637, 20635688, 268264004, 3755696121, 56335441899, 901367070474, 15323240198170, 275818323567179, 5240548147776545, 104810962955531052, 2201030222066152272
Offset: 3

Views

Author

Hugo Pfoertner, Jan 16 2003

Keywords

Comments

The asymptotic value for large n is 0.04308...*n! = (e+1/e-3)/2 * n! See also comment for A079884.

References

Links

Crossrefs

Cf. A079884, A079750, A079751, A079752, A079753, A079754, A079755.

Programs

  • Mathematica
    a[3] = 0; a[4] = 0; a[n_] := n*a[n - 1] + (n - 1)*(Floor[(n - 1)/2] - 1); Table[a[n ], {n, 3, 21}]
  • Python
    l=[0, 0, 0, 0, 0]
for n in range(5, 22):
    l.append(n*l[n - 1] + (n - 1)*((n - 1)//2 - 1))
print(l[3:]) # Indranil Ghosh, Jul 18 2017

Formula

a(3)=0, a(4)=0, a(n) = n*a(n-1) + (n-1)*(floor((n-1)/2)-1) for n>=5.
For n>=3, a(n) = floor(c*n!-(n-3)/2) where c = lim_{n->infinity} a(n)/n! = 0.04308063481524377... - Benoit Cloitre, Jan 19 2003
Recurrence: (n-5)*(n-3)*(n-2)*a(n) = (n-3)*(n^3 - 7*n^2 + 11*n - 1)*a(n-1) - (n-1)*(2*n - 5)*a(n-2) - (n-4)*(n-2)^2*(n-1)*a(n-3). - Vaclav Kotesovec, Mar 16 2014

Extensions

More terms from Benoit Cloitre and Robert G. Wilson v, Jan 19 2003

A079751 Operation count to create all permutations of n distinct elements using the "streamlined" version of Algorithm L (lexicographic permutation generation) from Knuth's The Art of Computer Programming, Vol. 4, chapter 7.2.1.2. Sequence gives number of cases where the j search loop runs beyond j=n-3.

Original entry on oeis.org

0, 1, 6, 37, 260, 2081, 18730, 187301, 2060312, 24723745, 321408686, 4499721605, 67495824076, 1079933185217, 18358864148690, 330459554676421, 6278731538852000, 125574630777040001, 2637067246317840022, 58015479418992480485, 1334356026636827051156
Offset: 3

Views

Author

Hugo Pfoertner, Jan 14 2003

Keywords

Comments

The asymptotic value for large n is 0.051615...*n! = (e - 8/3)*n!. See also comment for A079884.

References

Links

Crossrefs

Cf. A079885, A079750, A079752, A079753, A079754, A079755, A079756.

Programs

  • Maple
    a:=n->sum((n-j)!*binomial(n,j),j=4..n): seq(a(n), n=3..25); # Zerinvary Lajos, Jul 31 2006
  • Mathematica
    a[3] = 0; a[n_] := n*a[n - 1] + 1; Table[a[n], {n, 3, 21}]

Formula

a(3)=0, a(n) = n * a(n-1) + 1 for n >= 4.
For n >= 3, a(n) = floor(c*n!) where c = lim_{n->infinity} a(n)/n! = 0.05161516179237856869. - Benoit Cloitre
a(n) = Sum_{j=4..n} (n-j)! * binomial(n,j). - Zerinvary Lajos, Jul 31 2006
E.g.f.: (exp(x) - Sum_{k=0..3} x^k/k!) / (1 - x). - Ilya Gutkovskiy, Jun 26 2022

Extensions

Edited and extended by Robert G. Wilson v, Jan 22 2003

A079755 Operation count to create all permutations of n distinct elements using the "streamlined" version of Knuth's Algorithm L (lexicographic permutation generation).

Original entry on oeis.org

0, 3, 23, 148, 1054, 8453, 76109, 761126, 8372436, 100469287, 1306100803, 18285411320, 274281169898, 4388498718473, 74604478214169, 1342880607855178, 25514731549248544, 510294630984971051, 10716187250684392271, 235756119515056630172, 5422390748846302494198, 130137377972311259861005
Offset: 3

Views

Author

Hugo Pfoertner, Jan 16 2003

Keywords

Comments

Sequence gives number of loop repetitions in reversal step.
The asymptotic value for large n is 0.20975...*n! = (e + 1/e - 8/3)/2 * n!. See also comment for A079884.

References

  • Knuth's The Art of Computer Programming, Vol. 4, chapter 7.2.1.2.
  • See also under A079884.

Links

Crossrefs

Cf. A079884, A079750, A079751, A079752, A079753, A079754, A079756, A079885.

Programs

  • Fortran
    Program available at Pfoertner link.
  • Mathematica
    a[3] = 0; a[n_] := n*a[n - 1] + (n - 1)*Floor[(n - 1)/2]; Table[a[n], {n, 3, 21}]
RecurrenceTable[{a[3]==0,a[n]==n*a[n-1]+(n-1)Floor[(n-1)/2]},a,{n,20}] (* Harvey P. Dale, May 31 2019 *)

Formula

a(3) = 0, a(n) = n * a(n - 1) + (n - 1)*floor((n - 1)/2) for n >= 4.
a(n) = floor(c*n! - (n - 1)/2) for n > 4, where c = lim n -> infinity a(n)/n! = 0.209747301481910445... - Benoit Cloitre, Jan 19 2003

Extensions

More terms from Benoit Cloitre and Robert G. Wilson v, Jan 19 2003

A079752 Operation count to create all permutations of n distinct elements using the "streamlined" version of Algorithm L (lexicographic permutation generation) from Knuth's The Art of Computer Programming, Vol. 4, chapter 7.2.1.2. Sequence gives number of times the search for an element exchangeable with a_j has to be started.

Original entry on oeis.org

0, 2, 13, 82, 579, 4638, 41749, 417498, 4592487, 55109854, 716428113, 10029993594, 150449903923, 2407198462782, 40922373867309, 736602729611578, 13995451862619999, 279909037252399998, 5878089782300399977
Offset: 3

Views

Author

Hugo Pfoertner, Jan 14 2003

Keywords

Comments

The asymptotic value for large n is 0.11505...*n! = (17/6-e)*n!. See also comment for A079884

Links

Crossrefs

Cf. A079884, A079750, A079751, A079753, A079754, A079755, A079756.

Programs

  • Mathematica
    a[3] = 0; a[n_] := n*a[n - 1] + n - 2; Table[a[n], {n, 3, 21}]

Formula

a(3)=0, a(n) = n * a(n-1) + n - 2 for n>=4

Extensions

Edited and extended by Robert G. Wilson v, Jan 22 2003

A079753 Operation count to create all permutations of n distinct elements using the "streamlined" version of Algorithm L (lexicographic permutation generation) from Knuth's The Art of Computer Programming, Vol. 4, chapter 7.2.1.2. Sequence gives total executions of step L3.1'.

Original entry on oeis.org

0, 3, 21, 136, 967, 7757, 69841, 698446, 7682951, 92195467, 1198541137, 16779575996, 251693640031, 4027098240601, 68460670090337, 1232292061626202, 23413549170897991, 468270983417959991, 9833690651777160001
Offset: 3

Views

Author

Hugo Pfoertner, Jan 16 2003

Keywords

Comments

The asymptotic value for large n is 0.19247...*n! = (e/2-7/6)*n!. See also comment for A079884.

References

Links

Crossrefs

Cf. A079884, A079750, A079751, A079752, A079754, A079755, A079756.

Programs

  • Mathematica
    a[3] = 0; a[n_] := n*a[n - 1] + (n - 1)*(n - 2)/2; Table[a[n], {n, 3, 21}]

Formula

a(3)=0, a(n)= n*a(n-1) + (n-1)*(n-2)/2 for n>=4 a(n) = A079752(n) + A079754(n)
For n>=3, a(n)=floor(c*n!-(n-1)/2) where c=limit n-->infinity a(n)/n!= 0.192474247562855951... - Benoit Cloitre, Jan 20 2003

Extensions

Edited and extended by Robert G. Wilson v, Jan 22 2003

A080047 Operation count to create all permutations of n distinct elements using Algorithm L (lexicographic permutation generation) from Knuth's The Art of Computer Programming, Vol. 4, chapter 7.2.1.2. Sequence gives number of times l has to be repeatedly decreased in step L3.

Original entry on oeis.org

0, 1, 7, 41, 256, 1807, 14477, 130321, 1303246, 14335751, 172029067, 2236377937, 31309291196, 469639368031, 7514229888601, 127741908106337, 2299354345914202, 43687732572369991, 873754651447399991
Offset: 2

Views

Author

Hugo Pfoertner, Jan 25 2003

Keywords

References

  • D. E. Knuth: The Art of Computer Programming, Volume 4, Combinatorial Algorithms, Volume 4A, Enumeration and Backtracking. Pre-fascicle 2B, A draft of section 7.2.1.2: Generating all permutations. Available online; see link.

Links

Crossrefs

Cf. A038155, A038156, A056542, A080048, A080049, A079754.

Programs

  • Mathematica
    Transpose[NestList[{First[#]+1,(First[#]+1)Last[#]+(First[#](First[#]-1))/2}&, {2,0},20]][[2]] (* Harvey P. Dale, Feb 27 2012 *)
Rest[Rest[CoefficientList[Series[(2-Exp[x]*(x^2-2*x+2))/(2*(x-1)),{x,0,20}],x]*Range[0,20]!]] (* Vaclav Kotesovec, Oct 21 2012 *)

Formula

a(2)=0, a(n) = n*a(n-1)+(n-1)*(n-2)/2 for n>=3 c = limit n--> infinity a(n)/n! = 0.35914091422952261768 = e/2-1, a(n) = floor [c*n! - (n-1)/2] for n>=2
E.g.f.: (2-exp(x)*(x^2-2*x+2))/(2*(x-1)). - Vaclav Kotesovec, Oct 21 2012
Showing 1-7 of 7 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.