A079752 -id:A079752 - cp's OEIS frontend

A038155 a(n) = (n!/2) * Sum_{k=0..n-2} 1/k!.

0, 0, 1, 6, 30, 160, 975, 6846, 54796, 493200, 4932045, 54252550, 651030666, 8463398736, 118487582395, 1777313736030, 28437019776600, 483429336202336, 8701728051642201, 165332832981201990, 3306656659624039990, 69439789852104840000

Offset: 0

N. J. A. Sloane

For n>=2, a(n) gives the 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 the number of comparisons required to find the first interchangeable element in step L3 (see answer to exercise 5). - Hugo Pfoertner, Jan 27 2003
a(n) mod 5 = A011658(n+1). - G. C. Greubel, Apr 13 2016
a(450) has 1001 decimal digits. - Michael De Vlieger, Apr 13 2016
Also the number of (undirected) paths in the complete graph K_n. - Eric W. Weisstein, Jun 04 2017

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.

Michael De Vlieger, Table of n, a(n) for n = 0..449
D. E. Knuth, TAOCP Vol. 4, Pre-fascicle 2b (generating all permutations).
Hugo Pfoertner, FORTRAN implementation of Knuth's Algorithm L for lexicographic permutation generation.
Eric Weisstein's World of Mathematics, Complete Graph
Eric Weisstein's World of Mathematics, Graph Path

Cf. A011658, A038154, A038156, A056542, A079752, A079884, A080047, A080048, A080049.

A038155:=n->(n!/2)*add(1/k!, k=0..n-2): seq(A038155(n), n=0..30); # Wesley Ivan Hurt, Apr 16 2016

RecurrenceTable[{a[0] == 0, a[n] == Sum[a[n - 1] + k, {k, 0, n - 1}]}, a, {n, 21}] (* Ilya Gutkovskiy, Apr 13 2016 *)
Table[(n!/2) Sum[1/k!, {k, 0, n - 2}], {n, 0, 21}] (* Michael De Vlieger, Apr 13 2016 *)
Table[1/2 E (n - 1) n Gamma[n - 1, 1], {n, 0, 20}] (* Eric W. Weisstein, Jun 04 2017 *)
Table[If[n == 0, 0, Floor[n! E - n - 1]/2], {n, 0, 20}] (* Eric W. Weisstein, Jun 04 2017 *)

a(n) = 1/2*floor(n!*exp(1)-n-1), n>0. - Vladeta Jovovic, Aug 18 2002
E.g.f.: x^2/2*exp(x)/(1-x). - Vladeta Jovovic, Aug 25 2002
a(n) = Sum_{k=0..n-1} a(n-1) + k, a(0)=0. - Ilya Gutkovskiy, Apr 13 2016
a(n) = A038154(n)/2. - Alois P. Heinz, Jan 26 2017

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

Hugo Pfoertner, Jan 14 2003

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

See under A079884

Hugo Pfoertner, FORTRAN program for lexicographic permutation generation.

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

Fortran
```
c Program available at link.
```

a:=n->sum((n+1)!/j!,j=3..n): seq(a(n), n=2..20); # Zerinvary Lajos, Oct 20 2006

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

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

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

Hugo Pfoertner, Jan 16 2003

nonn

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

See under A079884

Indranil Ghosh, Table of n, a(n) for n = 3..101
Hugo Pfoertner, FORTRAN program for lexicographic permutation generation

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

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}]

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

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

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

Hugo Pfoertner, Jan 14 2003

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

See under A079884.

Hugo Pfoertner, FORTRAN program for lexicographic permutation generation.

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

a:=n->sum((n-j)!*binomial(n,j),j=4..n): seq(a(n), n=3..25); # Zerinvary Lajos, Jul 31 2006

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

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

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

Hugo Pfoertner, Jan 16 2003

nonn

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.

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

Hugo Pfoertner, FORTRAN program for lexicographic permutation generation

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

Fortran
```
Program available at Pfoertner link.
```

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 *)

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

More terms from Benoit Cloitre and Robert G. Wilson v, Jan 19 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

Hugo Pfoertner, Jan 16 2003

nonn

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

See under A079884

Hugo Pfoertner, FORTRAN program for lexicographic permutation generation

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

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

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

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

A079754 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 l has to be repeatedly decreased in step L3.1'.

Original entry on oeis.org

0, 1, 8, 54, 388, 3119, 28092, 280948, 3090464, 37085613, 482113024, 6749582402, 101243736108, 1619899777819, 27538296223028, 495689332014624, 9418097308277992, 188361946165559993, 3955600869476760024

Offset: 3

Hugo Pfoertner, Jan 16 2003

nonn

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

Lim_{n->infinity} a(n)/n! = 3*e/2 - 4. - Hugo Pfoertner, Sep 02 2017

See under A079884

Hugo Pfoertner, FORTRAN program for lexicographic permutation generation

Cf. A079884, A079750, A079751, A079752, A079753, A079755, A079756, A196533.

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

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

For n>=3 a(n)=floor(c*n!-(n-3)/2) where c=limit n --> infinity a(n)/n!=0.077422742688567853... - Benoit Cloitre, Jan 20 2003

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

cp's OEIS Frontend

A038155 a(n) = (n!/2) * Sum_{k=0..n-2} 1/k!.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Fortran

Maple

Mathematica

Formula

Extensions

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.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Mathematica

Python

Formula

Extensions

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

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

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Fortran

Mathematica

Formula

Extensions

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'.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

Views

Author

Keywords

Comments