A079750 -id:A079750 - cp's OEIS frontend

A038156 a(n) = n! * Sum_{k=1..n-1} 1/k!.

0, 0, 2, 9, 40, 205, 1236, 8659, 69280, 623529, 6235300, 68588311, 823059744, 10699776685, 149796873604, 2246953104075, 35951249665216, 611171244308689, 11001082397556420, 209020565553571999, 4180411311071440000, 87788637532500240021, 1931350025715005280484

Offset: 0

N. J. A. Sloane

Related to number of operations of addition and multiplication to evaluate a determinant of order n by cofactor expansion - see A026243.
Also number of operations needed 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 comparisons required to find j in step L2 (see answer to exercise 5). - Hugo Pfoertner, Jan 24 2003
For n>1, the number of possible ballots where there are n candidates and voters may identify their top m most preferred ones, where 0 < m < n. - Shaye Horwitz, Jun 28 2011
For n > 1, a(n) is the expected number of comparisons required to sort a random list of n distinct elements using the "bogosort" algorithm. - Andrew Slattery, Jun 02 2022
The number of permutations of all proper nonempty subsets of an n element set. - P. Christopher Staecker, May 09 2024

			a(2) = floor((2.718... - 1)*2) - 1 = 3 - 1 = 2,
a(3) = floor((2.718... - 1)*6) - 1 = 10 - 1 = 9.

D. E. Knuth: The Art of Computer Programming, Volume 4, Fascicle 2. Generating All Tuples and Permutations, Addison-Wesley, 2005.

Georg Fischer, Table of n, a(n) for n = 0..200 [first 28 terms from _Vincenzo Librandi_]
INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 836
G. A. Kamel, Partial Chain Topologies on Finite Sets, Computational and Applied Mathematics Journal. Vol. 1, No. 4, 2015, pp. 174-179.
Hugo Pfoertner, FORTRAN implementation of Knuth's Algorithm L for lexicographic permutation generation.
Wikipedia, Bogosort
Index entries for sequences related to factorial numbers

Cf. A000522, A007526, A038155, A056542, A079884, A079750.

Row sums of A119741.

a:= proc(n) option remember;
      `if`(n<2, 0, a(n-1)*n+n)
    end:
seq(a(n), n=0..30);  # Alois P. Heinz, Apr 11 2020

a=1; Join[{0},Table[a=(a-1)*(n+1);Abs[a],{n,0,60}]] (* Vladimir Joseph Stephan Orlovsky, Nov 20 2009; 0 prefixed by _Georg Fischer Apr 11 2020 *)
Join[{0},FoldList[#1*#2 + #2 + #1 + 1 &, 0, Range@ 20]] (* Robert G. Wilson v, Feb 21 2015 *)

a(n)=floor((exp(1)-1)*n!-1) \\ Charles R Greathouse IV, Jun 29 2011

a(n)=(expm1(1)*n!-1)\1 \\ Charles R Greathouse IV, Jan 28 2014

a(n) = floor((e-1)*n!) - 1.
a(0) = a(1) = 0, a(n) = n*(a(n-1) + 1) for n>1. - Philippe Deléham, Oct 16 2009
E.g.f.: (exp(x) - 1)*x/(1 - x). - Ilya Gutkovskiy, Jan 26 2017
a(n) = A002627(n)-1, n>=1. - R. J. Mathar, Jan 03 2018
a(n) = A000522(n)-n!-1, n>=1. - P. Christopher Staecker, May 09 2024

a(28) ff. corrected by Georg Fischer, Apr 11 2020

A079884 Number of comparisons 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

11, 54, 285, 1731, 12145, 97196, 874809, 8748145, 96229661, 1154756010, 15011828221, 210165595199, 3152483928105, 50439742849816, 857475628447025, 15434561312046621, 293256664928885989, 5865133298577719990, 123167799270132120021, 2709691583942906640715, 62322906430686852736721

Offset: 3

Hugo Pfoertner, Jan 12 2003

The method generates all permutations in lexicographic order. It is described in the answer to Exercise 1, Section 7.2.1.2 of Knuth's The Art of Computer Programming Vol. 4. The description is based on the Algol procedure NEXTPERM by J.P.N.Phillips. The operation counts were determined with a FORTRAN subroutine LPG. To create all permutations of n distinct elements the number of comparisons between the array elements approaches 2.410756*n! for large n (e.g. n>8).

			The "streamlined" permutation algorithm L' needs fewer comparisons a(n) than the original Algorithm L, for which the number of required comparisons between the elements to be permuted is given by A038156(n) for step L2 and A038155(n) for step L3. A038156(3)+A038155(3)=9+6=15 > a(3)=11 A038156(4)+A038155(4)=40+30=70 > a(4)=54 A038156(10)+A038155(10)=6235300+4932045=11167345 > a(10)=8748145.

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.
J. P. N. Phillips: "Algorithm 28, PERMUTATIONS OF THE ELEMENTS OF A VECTOR IN LEXICOGRAPHIC ORDER" The Computer Journal, Volume 10, Issue 3: November 1967. (Algorithms supplement), page 311. See link.

Hugo Pfoertner, FORTRAN program for lexicographic permutation generation.
J. P. N. Phillips, Algorithm 28 from Algorithms supplement.

Partial counts given in A079750, A079753.
Number of index tests: A079885.
Cf. A000217, A000142, A038155, A038156.

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

a079884(nmax) = {my(a=vector(nmax)); a[3]=11; for(k=4, nmax, a[k]=k*a[k-1]+k*(k+1)/2); a[3..nmax]} \\ Hugo Pfoertner, Jun 05 2024

a(3) = 11; a(n) = n*a(n-1) + n*(n+1)/2.
a(n) = 2*n! - 1 + A079750(n) + A079753(n).
For n>=3, a(n)=floor(c*n!-(n-3)/2) where c = lim_{n->oo} a(n)/n! = 2.4107560760219... - Benoit Cloitre; c=3*e/2-5/3 - Guido Dhondt (dhondt(AT)t-online.de), Jan 20 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

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

A285268 Triangle read by rows: T(m,n) = Sum_{i=1..n} P(m,i) where P(m,n) = m!/(m-n)! is the number of permutations of m items taken n at a time, for 1 <= n <= m.

Original entry on oeis.org

1, 2, 4, 3, 9, 15, 4, 16, 40, 64, 5, 25, 85, 205, 325, 6, 36, 156, 516, 1236, 1956, 7, 49, 259, 1099, 3619, 8659, 13699, 8, 64, 400, 2080, 8800, 28960, 69280, 109600, 9, 81, 585, 3609, 18729, 79209, 260649, 623529, 986409, 10, 100, 820, 5860, 36100, 187300, 792100, 2606500, 6235300, 9864100

Offset: 1

Rick Nungester, Apr 15 2017

T(m, n) is the total number of ordered sets of size 1 to n that can be created from m distinct items. For example, for 4 items taken 1 to 3 at a time, there are P(4, 1) + P(4, 2) + P(4, 3) = 4 + 12 + 24 = 40 total sets: 1, 12, 123, 124, 13, 132, 134, 14, 142, 143, 2, 21, 213, 214, 23, 231, 234, 24, 241, 243, 3, 31, 312, 314, 32, 321, 324, 34, 341, 342, 4, 41, 412, 413, 42, 421, 423, 43, 431, 432.
T(m, n) is the total number of tests in a software program that generates all P(m, n) possible solutions to a problem, allowing early-termination testing on each partial permutation, and not doing any such early termination. For example, from a deck of 52 cards, evaluate all possible 5-card deals as each card is dealt. T(52, 5) = 318507904 total evaluations.
T(m, n) counts the numbers with <= n distinct nonzero digits in base m+1. - M. F. Hasler, Oct 10 2019

			Triangle begins:
  1;
  2,  4;
  3,  9,  15;
  4, 16,  40,   64;
  5, 25,  85,  205,   325;
  6, 36, 156,  516,  1236,  1956;
  7, 49, 259, 1099,  3619,  8659,  13699;
  8, 64, 400, 2080,  8800, 28960,  69280, 109600;
  9, 81, 585, 3609, 18729, 79209, 260649, 623529, 986409;
  ...

Rick Nungester, Table of n, a(n) for n = 1..20100

Mirror of triangle A121662.
Row sums give A030297.
Diagonals (1..4): A007526 (less the initial 0), A038156 (less the initial 0, 0), A224869 (less the initial -1, 0), A079750 (less the initial 0).
Columns (1..3): A000027, A000290 (less the initial 0, 1), A053698 (less the initial 1, 4).

SumPermuteTriangle := proc(M)
  local m;
  for m from 1 to M do print(seq(add(m!/(m-k)!, k=1..n), n=1..m)) od;
end:
SumPermuteTriangle(10);
# second Maple program:
T:= proc(n, k) option remember;
     `if`(k<1, 0, T(n-1, k-1)*n+n)
    end:
seq(seq(T(n, k), k=1..n), n=1..10);  # Alois P. Heinz, Jun 26 2022

Table[Sum[m!/(m - i)!, {i, n}], {m, 9}, {n, m}] // Flatten (* Michael De Vlieger, Apr 22 2017 *)
(* Sum-free code *)
b[j_] = If[j==0, 0, Floor[j! E - 1]]; T[m_,n_] = b[m] - m! b[m-n]/(m-n)!; Table[T[m, n],{m, 24},{n, m}]//Flatten
(* Manfred Boergens, Jun 22 2022 *)

A285268(m,n,s=m-n+1)={for(k=m-n+2,m,s=(s+1)*k);s} \\ Much faster than sum(k=1,n,m!\(m-k)!), e.g., factor 6 for m=1..99, factor 57 for m=1..199.
apply( A285268_row(m)=vector(m,n,A285268(m,n)), [1..9]) \\ M. F. Hasler, Oct 10 2019

T(n, k) = {exp(1)*(incgam(n+1, 1) - incgam(n-k, 1)*(n-k)*n!/(n-k)!) - 1;}
  apply(Trow(n) = vector(n, k, round(T(n, k))), [1..10]) \\ Adjust the realprecision if needed. Peter Luschny, Oct 10 2019

T(m, n) = Sum_{k=1..n} m!/(m-k)! = m*(1 + (m-1)*(1 + (m-2)*(1 + ... + m-n+1)...)), cf. PARI code. - M. F. Hasler, Oct 10 2019
T(n, k) = exp(1)*(Gamma(n+1, 1) - Gamma(n-k, 1)*(n-k)*n!/(n-k)!) - 1. - Peter Luschny, Oct 10 2019
Sum-free and Gamma-free formula: T(m, n) = b(m) - m!*b(m-n)/(m-n)! where b(0)=0, b(j)=floor(j!*e-1) for j>0. - Manfred Boergens, Jun 22 2022

A080093 Let sum(k>=0, k^n/(2k+1)!) = (x(n)e + y(n)/e)/z(n), where x(n) and z(n) are >0, then a(n)=x(n).

Original entry on oeis.org

0, 1, 1, 2, 11, 41, 81, 715, 3425, 8861, 98253, 580317, 1816640, 24011157, 166888165, 608035190, 9264071767, 73600798037, 304238004061, 5224266196935, 46499892038437, 214184962059157, 4078345814329009, 40073660040755337

Offset: 1

Benoit Cloitre and Paul D. Hanna, Jan 28 2003

nonn

			Values of sum(k>=0,k^n/(2*k+1)!) = (x(n)*e + y(n)/e)/z(n) are given by n=1: (1/e)/2 = 0.183939720585721160..., n=2: (e - 3/e)/8 = 0.201830438118089783..., n=3: (e + 3/e)/16 = 0.238870009498335762..., n=4: (2e - 1/e)/16 = 0.316792763484165509..., n=5: (11e + 3/e)/64 = 0.484449038071309758..., n=6: (41e - 5/e)/128 = 0.856329357507528461..., n=7: (81e - 2/e)/128 = 1.71441460330343577..., n=8: (715e - 5/e)/512 = 3.79244552762179713..., n=9: (3425e + 55/e)/1024 = 9.11166858568033130..., n=10: (8861e + 106/e)/1024 = 23.5602446315818092...

Cf. A080094, A080095, A079750 - A079756.

cp's OEIS Frontend

A038156 a(n) = n! * Sum_{k=1..n-1} 1/k!.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

PARI

Formula

Extensions

A079884 Number of comparisons 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.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Fortran

PARI

Formula

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

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

A080093 Let sum(k>=0, k^n/(2k+1)!) = (x(n)e + y(n)/e)/z(n), where x(n) and z(n) are >0, then a(n)=x(n).