A038156 -id:A038156 - cp's OEIS frontend

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.

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

A166554 a(0)=1, a(n) = n*(a(n-1) - 1) for n>0.

Original entry on oeis.org

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

Offset: 0

Philippe Deléham, Oct 16 2009

sign

G. C. Greubel, Table of n, a(n) for n = 0..500

Cf. A000142, A038156, A165793, A165814.

[n le 1 select 1 else (n-1)*(Self(n-1) - 1): n in [1..41]]; // G. C. Greubel, Nov 30 2024

RecurrenceTable[{a[0]==1,a[n]==n(a[n-1]-1)},a[n],{n,20}] (* Harvey P. Dale, Jul 25 2011 *)

def A166554(n): return 1 +factorial(n) -int(exp(1)*factorial(n)) +int(n==0)
print([A166554(n) for n in range(41)]) # G. C. Greubel, Nov 30 2024

a(n) = -A038156(n) for n>0.
a(n) = n! - floor(e*n!) + 1, n>0. - Gary Detlefs, Jun 06 2010
a(n) = (n+2)*a(n-1) - (2*n-1)*a(n-2) + (n-2)*a(n-3). - R. J. Mathar, Jul 28 2013

A268218 a(n) = (n!/3!)*Sum(1/k!,k=1..n-3).

Original entry on oeis.org

0, 0, 0, 0, 4, 30, 200, 1435, 11536, 103908, 1039200, 11431365, 137176600, 1783296086, 24966145568, 374492183975, 5991874944160, 101861874051400, 1833513732926016, 34836760925595273, 696735218511906600, 14631439588750039930, 321891670952500880000, 7403508431907520241771

Offset: 0

N. J. A. Sloane, Jan 30 2016

nonn

G. A. Kamel, Partial Chain Topologies on Finite Sets, Computational and Applied Mathematics Journal. Vol. 1, No. 4, 2015, pp. 174-179.

For others in this series, see A038156, A038158, A268219, A268220.

g:=(r,n)->(n!/r!)*add(1/k!,k=1..n-r);
g2:=r->[seq(g(r,n),n=0..30)];
g2(3);

a(n) = (n!/3!)*sum(k=1, n-3, 1/k!); \\ Michel Marcus, Jan 30 2016

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

A082459 Multiply by 1, add 1, multiply by 2, add 2, etc.

Original entry on oeis.org

-1, -1, 0, 0, 2, 6, 9, 36, 40, 200, 205, 1230, 1236, 8652, 8659, 69272, 69280, 623520, 623529, 6235290, 6235300, 68588300, 68588311, 823059732, 823059744, 10699776672, 10699776685, 149796873590, 149796873604, 2246953104060, 2246953104075, 35951249665200, 35951249665216

Offset: 0

Vladeta Jovovic, Apr 25 2003

sign

Bisections: A038156 and A038157.

Robert Israel, Table of n, a(n) for n = 0..898

Cf. A019464 - A019466.

seq(op(simplify([exp(1)*GAMMA(k+1,1)-k!-1, exp(1)*GAMMA(k+2,1)-(k+1)!-k-2])),k=0..20); # Robert Israel, Jan 11 2018

FoldList[If[OddQ@ #2, #1 ((#2 + 1)/2), #1 + #2/2] &, -1, Range@ 31] (* Michael De Vlieger, Jan 11 2018 *)

From Robert Israel, Jan 11 2018: (Start)
a(2*k) = e*Gamma(k+1,1) - k! - 1.
a(2*k+1) = e*Gamma(k+2,1) - (k+1)! - k - 2. (End)

A224869 a(n) = n*( a(n-1)+1 ), initialized by a(1) = -1.

Original entry on oeis.org

-1, 0, 3, 16, 85, 516, 3619, 28960, 260649, 2606500, 28671511, 344058144, 4472755885, 62618582404, 939278736075, 15028459777216, 255483816212689, 4598708691828420, 87375465144739999, 1747509302894800000, 36697695360790800021, 807349297937397600484

Offset: 1

Alex Ratushnyak, Jul 22 2013

			a(4) = 4*(a(3)+1) = 4*4 = 16.

Cf. A007526, A038156, A166554, A121662 (3rd column).

A224869[1] := -1; A224869[n_] := A224869[n - 1]n + n; Table[A224869[n], {n, 40}] (* Alonso del Arte, Jul 22 2013 *)

a=-1
for n in range(2,24):
  print(a, end=', ')
  a= n*(a+1)

a(n) +(-n-2)*a(n-1) +(2*n-1)*a(n-2) +(-n+2)*a(n-3)=0. - R. J. Mathar, Jul 28 2013

a(n) = exp(1)*n*Gamma(n,1) - 2*Gamma(n+1,0). - Martin Clever, Mar 27 2023

A268220 a(n) = (n!/5!)*Sum(1/k!,k=1..n-5).

Original entry on oeis.org

0, 0, 0, 0, 0, 0, 6, 63, 560, 5166, 51912, 571494, 6858720, 89164647, 1248307060, 18724608903, 299593746816, 5093093702060, 91675686645648, 1741838046278940, 34836760925594304, 731571979437500733, 16094583547625042460, 370175421595376010229, 8884210118289024288000

Offset: 0

N. J. A. Sloane, Jan 30 2016

nonn

G. A. Kamel, Partial Chain Topologies on Finite Sets, Computational and Applied Mathematics Journal. Vol. 1, No. 4, 2015, pp. 174-179.

For others in this series, see A038156, A038158, A268218, A268219.

g:=(r,n)->(n!/r!)*add(1/k!,k=1..n-r);
g2:=r->[seq(g(r,n),n=0..30)];
g2(5);

a(n) = (n!/5!)*sum(k=1, n-5, 1/k!); \\ Michel Marcus, Jan 30 2016

A296964 Expansion of e.g.f. (exp(x)-x)*x/(1-x).

Original entry on oeis.org

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

Offset: 0

J. Devillet, Dec 22 2017

Number of quasilinear weak orderings R on {1,...,n} and for which {1,...,n} has exactly one maximal element for the quasilinear weak ordering R.

Essentially the same as A038156. - R. J. Mathar, Jan 02 2018

J. Devillet, Bisymmetric and quasitrivial operations: characterizations and enumerations, arXiv:1712.07856 [math.RA], 2017.

Cf. A002627, A038156.

Join[{0,1},Drop[With[{nn=30},CoefficientList[Series[(Exp[x]-x)*x/(1-x),{x,0,nn}],x] Range[0,nn]!],2]] (* Harvey P. Dale, Apr 02 2018 *)

x = QQ[['x']].gen()
f = (exp(x) - x) * x / (1 - x)
f.egf_to_ogf()  # F. Chapoton, Jul 21 2025

a(n) = A002627(n)-1, a(0)=0, a(1)=1.

A117643 a(n) = n*(a(n-1)-1) starting with a(0)=3.

Original entry on oeis.org

3, 2, 2, 3, 8, 35, 204, 1421, 11360, 102231, 1022300, 11245289, 134943456, 1754264915, 24559708796, 368395631925, 5894330110784, 100203611883311, 1803665013899580, 34269635264092001, 685392705281840000

Offset: 0

Henry Bottomley, Apr 10 2006

Starting with a(0)=0 would give -A007526(n); starting with a(0)=1 would give -A038156(n). In general, for this recurrence, a(n) = ceiling(1 + n!*(a(0)-e)) for n>0; this is the first case with positive terms.

			a(5) = 5*(a(4)-1) = 5*(8-1) = 35.

a=3;Table[a=a*n-n,{n,1,2*4!}] (* Vladimir Joseph Stephan Orlovsky, Apr 22 2010 *)
RecurrenceTable[{a[0]==3,a[n]==n(a[n-1]-1)},a,{n,20}] (* Harvey P. Dale, Jul 17 2018 *)

a(n) = ceiling(1 + n!*(3-e)) for n>0.

a(n) = n! - floor(e*n!) + 1, n>0. - Gary Detlefs, Jun 06 2010

cp's OEIS Frontend

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.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Fortran

Formula

A166554 a(0)=1, a(n) = n*(a(n-1) - 1) for n>0.

Views

Author

Keywords

Links

Crossrefs

Programs

Magma

Mathematica

Python

Formula

A268218 a(n) = (n!/3!)*Sum(1/k!,k=1..n-3).

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

PARI

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.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

PARI

Formula

A082459 Multiply by 1, add 1, multiply by 2, add 2, etc.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A224869 a(n) = n*( a(n-1)+1 ), initialized by a(1) = -1.

Views

Author

Keywords

Examples

Crossrefs

Programs

Mathematica

Python

Formula

A268220 a(n) = (n!/5!)*Sum(1/k!,k=1..n-5).

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

PARI

A296964 Expansion of e.g.f. (exp(x)-x)*x/(1-x).

Views

Author

Keywords