A079751 -id:A079751 - cp's OEIS frontend

A056542 a(n) = n*a(n-1) + 1, a(1) = 0.

0, 1, 4, 17, 86, 517, 3620, 28961, 260650, 2606501, 28671512, 344058145, 4472755886, 62618582405, 939278736076, 15028459777217, 255483816212690, 4598708691828421, 87375465144740000, 1747509302894800001, 36697695360790800022, 807349297937397600485

Offset: 1

Henry Bottomley, Jun 20 2000

For n >= 2 also 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 loop repetitions of the j search loop in step L2. - Hugo Pfoertner, Feb 06 2003
More directly: sum over all permutations of length n-1 of the product of the length of the first increasing run by the value of the first position. The recurrence follows from this definition. - Olivier Gérard, Jul 07 2011
This sequence shares divisibility properties with A000522; each of the primes in A072456 divide only a finite number of terms of this sequence. - T. D. Noe, Jul 07 2005
This sequence also represents the number of subdeterminant evaluations when calculation a determinant by Laplace recursive method. - Reinhard Muehlfeld, Sep 14 2010
Also, a(n) equals the number of non-isomorphic directed graphs of n+1 vertices with 1 component, where each vertex has exactly one outgoing edge, excluding loops and cycle graphs. - Stephen Dunn, Nov 30 2019

			a(4) = 4*a(3) + 1 = 4*4 + 1 = 17.
Permutations of order 3 .. Length of first run * First position
123..3*1
132..2*1
213..1*2
231..2*2
312..1*3
321..1*3
a(4) = 3+2+2+4+3+3 = 17. - _Olivier Gérard_, Jul 07 2011

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.

T. D. Noe, Table of n, a(n) for n = 1..100
D. E. Knuth, TAOCP Vol. 4, Pre-fascicle 2b (generating all permutations).
Tom Muller, Prime and Composite Terms in Sloane's Sequence A056542, Journal of Integer Sequences, Vol. 8 (2005), Article 05.3.3. [Includes factorizations of a(1) through a(50)]
Hugo Pfoertner, FORTRAN implementation of Knuth's Algorithm L for lexicographic permutation generation.
R. Sedgewick, Permutation generation methods, Computing Surveys, 9 (1977), 137-164.
Sam Wagstaff, Factorizations of a(51) through a(90)

Cf. A079751 (same recursion formula, but starting from a(3)=0), A038155, A038156, A080047, A080048, A080049.
Cf. A007808, A002627.
Equals the row sums of A162995 triangle (n>=2). - Johannes W. Meijer, Jul 21 2009
Cf. A073333, A002627, A185108.
Cf. A329426, A329427.
Cf. A070213 (indices of primes).

a056542 n = a056542_list !! (n-1)
a056542_list = 0 : map (+ 1) (zipWith (*) [2..] a056542_list)
-- Reinhard Zumkeller, Mar 24 2013

[n le 2 select n-1 else n*Self(n-1)+1: n in [1..20]]; // Bruno Berselli, Dec 13 2013

tmp=0; Join[{tmp}, Table[tmp=n*tmp+1, {n, 2, 100}]] (* T. D. Noe, Jul 12 2005 *)
FoldList[ #1*#2 + 1 &, 0, Range[2, 21]] (* Robert G. Wilson v, Oct 11 2005 *)

a(n) = floor((e-2)*n!).
a(n) = A002627(n) - n!.
a(n) = A000522(n) - 2*n!.
a(n) = n! - A056543(n).
a(n) = (n-1)*(a(n-1) + a(n-2)) + 2, n > 2. - Gary Detlefs, Jun 22 2010
1/(e - 2) = 2! - 2!/(1*4) - 3!/(4*17) - 4!/(17*86) - 5!/(86*517) - ... (see A002627 and A185108). - Peter Bala, Oct 09 2013
E.g.f.: (exp(x) - 1 - x) / (1 - x). - Ilya Gutkovskiy, Jun 26 2022

More terms from James Sellers, Jul 04 2000

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

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

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

Hugo Pfoertner, Jan 14 2003

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

Hugo Pfoertner, FORTRAN program for lexicographic permutation generation.

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

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

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

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

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

A079885 Number of index tests required 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.

Original entry on oeis.org

0, 4, 29, 185, 1314, 10534, 94839, 948427, 10432748, 125193032, 1627509489, 22785132925

Offset: 3

Hugo Pfoertner, Jan 13 2003

nonn

The required number of index tests (test for termination and test in the final reversion loop) becomes 0.2613625*n! for large n, if the test for n=3 is excluded. If n=3 is included the additionally required termination test adds n!/6 index comparisons, increasing the number of index comparisons to 0.428029*n! (63.8% more index comparisons).

The corresponding number of index tests needed by the "pure" Algorithm L is given by A038156(n)+A080048(n), which is 12.478..*a(n) for large n.

For references and corresponding links see under A079884

Hugo Pfoertner, FORTRAN program for lexicographic permutation generation.

Cf. A000142, partial counts given in A079751, A079755. Number of element comparisons: A079884.

Cf. A038156, A080048.

Fortran
```
! program available at link
```

a(3)=0, a(n)=n*a(n-1)+1+(n-1)*floor((n-1)/2) for n>=4 a(n) = A079751(n) + A079755(n)
For n>=3 a(n)=floor(c*n!-(n-3)/2) where c=limit n-->infinity a(n)/n!= 0.261362463274289013838... - Benoit Cloitre, Jan 20 2003
In closed form, c = 3*exp(1)/2 + exp(-1)/2 - 4. - Vaclav Kotesovec, Mar 18 2014

cp's OEIS Frontend

A056542 a(n) = n*a(n-1) + 1, a(1) = 0.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Haskell

Magma

Mathematica

Formula

Extensions

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

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

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

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