A056542 -id:A056542 - cp's OEIS frontend

A080048 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 in reversal step.

1, 7, 34, 182, 1107, 7773, 62212, 559948, 5599525, 61594835, 739138086, 9608795202, 134523132919, 2017846993897, 32285551902472, 548854382342168, 9879378882159177, 187708198761024543, 3754163975220491050

Offset: 2

Hugo Pfoertner, Jan 24 2003

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.

Cf. A038155, A038156, A056542, A080047, A080049, A079755.

Fortran
```
! Program available at link.
```

a(2)=1, a(n)=n*a(n-1) + (n-1)*floor[(n+1)/2] for n>=3.

c = limit n --> infinity a(n)/n! = 1.54308063481524377826 = (e+1/e)/2, a(n) = floor [c*n!-(n+1)/2] for n>=2.

A162995 A scaled version of triangle A162990.

Original entry on oeis.org

1, 3, 1, 12, 4, 1, 60, 20, 5, 1, 360, 120, 30, 6, 1, 2520, 840, 210, 42, 7, 1, 20160, 6720, 1680, 336, 56, 8, 1, 181440, 60480, 15120, 3024, 504, 72, 9, 1, 1814400, 604800, 151200, 30240, 5040, 720, 90, 10, 1

Offset: 1

Johannes W. Meijer, Jul 27 2009

We get this scaled version of triangle A162990 by dividing the coefficients in the left hand columns by their 'top-values' and then taking the square root.
T(n,k) = A173333(n+1,k+1), 1 <= k <= n. - Reinhard Zumkeller, Feb 19 2010
T(n,k) = A094587(n+1,k+1), 1 <= k <= n. - Reinhard Zumkeller, Jul 05 2012

			The first few rows of the triangle are:
[1]
[3, 1]
[12, 4, 1]
[60, 20, 5, 1]

Reinhard Zumkeller, Rows n = 1..150 of triangle, flattened

Cf. A094587.
A056542(n) equals the row sums for n>=1.
A001710, A001715, A001720, A001725, A001730, A049388, A049389, A049398, A051431 are related to the left hand columns.
A000012, A009056, A002378, A007531, A052762, A052787, A053625 and A159083 are related to the right hand columns.

a162995 n k = a162995_tabl !! (n-1) !! (k-1)
a162995_row n = a162995_tabl !! (n-1)
a162995_tabl = map fst $ iterate f ([1], 3)
   where f (row, i) = (map (* i) row ++ [1], i + 1)
-- Reinhard Zumkeller, Jul 04 2012

a := proc(n, m): (n+1)!/(m+1)! end: seq(seq(a(n, m), m=1..n), n=1..9); # Johannes W. Meijer, revised Nov 23 2012

Table[(n+1)!/(m+1)!, {n, 10}, {m, n}] (* Paolo Xausa, Mar 31 2024 *)

a(n,m) = (n+1)!/(m+1)! for n = 1, 2, 3, ..., and m = 1, 2, ..., n.

A080049 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 interchange operations in step L4.

Original entry on oeis.org

0, 2, 11, 63, 388, 2734, 21893, 197069, 1970726, 21678036, 260136487, 3381774403, 47344841720, 710172625898, 11362762014473, 193166954246169, 3477005176431178, 66063098352192544, 1321261967043851051, 27746501307920872271, 610423028774259190172, 14039729661807961374198

Offset: 2

Hugo Pfoertner, Jan 24 2003

Donald E. Knuth: The Art of Computer Programming, Volume 4, Fascicle 2, Generating All Tuples and Permutations. Addison-Wesley (2005). Chapter 7.2.1.2, 39-40.

D. E. Knuth, TAOCP Vol. 4, Pre-fascicle 2b (generating all permutations).
R. J. Ord-Smith, Generation of permutation sequences: Part 1, Computer J., 13 (1970), 151-155.
Hugo Pfoertner, FORTRAN implementation of Knuth's Algorithm L for lexicographic permutation generation.

Cf. A080047, A080048, A038155, A038156, A056542, A073743, A079756, A080047, A080048.

c FORTRAN program available at Pfoertner link.

a(2)=0, a(n)=n*a(n-1) + (n-1)*floor((n-1)/2).
c = limit n ->infinity a(n)/n! = 0.5430806.. = (e+1/e)/2-1 = A073743 - 1.
a(n) = floor (c*n! - (n-1)/2) for n>=2.

A056543 a(n) = n*a(n-1) - 1 with a(1)=1.

Original entry on oeis.org

1, 1, 2, 7, 34, 203, 1420, 11359, 102230, 1022299, 11245288, 134943455, 1754264914, 24559708795, 368395631924, 5894330110783, 100203611883310, 1803665013899579, 34269635264092000, 685392705281839999, 14393246810918639978, 316651429840210079515, 7282982886324831828844

Offset: 1

Henry Bottomley, Jun 20 2000

If s(n) is a sequence defined by s(0)=x, s(n)=(n+1)*s(n-1)+k, n>0, then s(n) = n!*x +(n! - a(n+1))*k. - Gary Detlefs, Jun 10 2010

			a(4) = 4*a(3) - 1 = 4*2 - 1 = 7.

Harvey P. Dale, Table of n, a(n) for n = 1..450

nxt[{n_,a_}]:={n+1,a(n+1)-1}; NestList[nxt,{1,1},30][[All,2]] (* Harvey P. Dale, Dec 31 2022 *)

a(n) = ceiling((3-e)*n!) = n! - A056542(n) = 2*n! - A002627(n) = 3*n! - A000522(n).

More terms from James Sellers, Jul 04 2000

A329426 Number of non-isomorphic directed graphs where every vertex has outdegree 1, and no self-loops.

Original entry on oeis.org

1, 2, 6, 20, 97, 550, 3794, 29826, 266527, 2649156, 29040865, 347548542, 4509961264, 63050417976, 944767674590, 15103712944100, 256594870255076, 4616238126871328, 87670085904641440, 1752759735606185804, 36796608121601906104, 809312755145598475440, 18609995953274373396982

Offset: 2

Stephen Dunn, Nov 30 2019

nonn

			For n = 2, a(2) = 1 + A329427(2) + A056542(1) = 1 + 0 + 0 = 1, which is the graph A <--> B.
For n = 3, a(3) = 1 + A329427(3) + A056542(2) = 1 + 0 + 1 = 2, which are graphs A --> B <--> C and A --> B --> C --> A.
The middle term is nonzero when there are graphs with more than 1 component.

Stephen Dunn, Table of n, a(n) for n = 2..100

Cf. A329427, A056542.

fun A329427(n: Long): Long = (2L..(n/2)).map { a(it) * a(n-it) }.sum()
fun A056542(n: Long): Long = if (n == 1L) 0 else n * A056542(n-1) + 1
fun a(n: Long): Long = 1 + A329427(n) + A056542(n-1)

a(n) = 1 + A329427(n) + A056542(n-1).

a(n) = 1 + A056542(n-1) + Sum_{2..floor(n/2)} a(i)*a(n-i).

A329427 Number of directed graphs of n vertices with more than 1 component and outdegree 1.

Original entry on oeis.org

1, 2, 10, 32, 173, 864, 5876, 42654, 369352, 3490396, 37205377, 431835570, 5488938513, 75253166882, 1111054042385, 17529435042906, 294620759901439, 5250432711385802, 98912760811106081, 1963457208200874954, 40962100714228585825, 895889161265034629994, 20497593840242211891900

Offset: 4

Stephen Dunn, Nov 30 2019

nonn

a(n) gives the number of unique ways a directed graph of n vertices with outdegree 1 can be broken into smaller components of size >= 2. It can be generalized to higher degree by replacing A329426 in the formula with a suitable counting function.

			a(4) = A329426(2)*A329426(2) = 1*1 = 1, which represents the graph
  V <--> V
  V <--> V.
a(5) = A329426(2)*A329426(3) = 1*2 = 2, which represents the two possible graphs of size 3 (V --> V <--> V, etc.) paired with V <--> V.
a(6) = A329426(2)*A329426(4) + A329426(3)*A329426(3) = 1*6 + 2*2 = 10.

Stephen Dunn, Table of n, a(n) for n = 4..100

Cf. A329426, A056542.

fun A056542(n: Long): Long = if (n == 1L) 0 else n * A056542(n-1) + 1
fun A329426(n: Long): Long = 1 + a(n) + A056542(n-1)
fun a(n: Long): Long = (2L..(n/2)).map { A329426(it) * A329426(n-it) }.sum()

a(n) = Sum_{i=2..floor(n/2)} A329426(i) * A329426(n-i).

Term a(26) corrected by Sidney Cadot, Jan 06 2023.

A134433 Triangle read by rows: T(n,k) is the number of permutations of {1,2,...,n} in which the last entry of the first increasing run is equal to k (1 <= k <= n).

Original entry on oeis.org

1, 0, 2, 0, 1, 5, 0, 2, 6, 16, 0, 6, 16, 33, 65, 0, 24, 60, 114, 196, 326, 0, 120, 288, 522, 848, 1305, 1957, 0, 720, 1680, 2952, 4632, 6850, 9786, 13700, 0, 5040, 11520, 19800, 30336, 43710, 60672, 82201, 109601

Offset: 1

Emeric Deutsch, Nov 22 2007

T(n,n) = A000522(n-1) (number of arrangements of {1,2,...,n-1}).
T(n,2) = (n-2)! for n >= 3.
Sum_{k=1..n} k*T(n,k) = A056542(n+1).

			T(4,3)=6 because we have 3124, 3142, 3214, 3241, 1324 and 2314.
Triangle starts:
  1;
  0,   2;
  0,   1,   5;
  0,   2,   6,  16;
  0,   6,  16,  33,  65;
  0,  24,  60, 114, 196, 326;

Michael De Vlieger, Table of n, a(n) for n = 1..11325 (rows 1 <= n <= 150, flattened.)

Cf. A000522, A056542.

T:=proc(n,k): if k < n then sum(factorial(k-1)*factorial(n-j-1)/(factorial(j-1)*factorial(k-j-1)), j=1..k-1) elif k = n then factorial(n-1)*(sum(1/factorial(j), j = 0 .. n-1)) else 0 end if end proc: for n to 9 do seq(T(n, k),k=1..n) end do; # yields sequence in triangular form

Table[If[k < n, Sum[(n - j - 1)!*(k - j)*Binomial[k - 1, j - 1], {j, k - 1}], (n - 1)!*Sum[1/j!, {j, 0, n - 1}]], {n, 9}, {k, n}] // Flatten (* Michael De Vlieger, Nov 15 2019 *)

T(n,k) = Sum_{j=1..k-1} (n-j-1)!*(k-j)*binomial(k-1,j-1) for k < n;

T(n,n) = (n-1)!*Sum_{j=0..n-1} 1/j!.

cp's OEIS Frontend

A080048 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 in reversal step.

Views

Author

Keywords

References

Links

Crossrefs

Programs

Fortran

Formula

A162995 A scaled version of triangle A162990.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

Formula

A080049 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 interchange operations in step L4.

Views

Author

Keywords

References

Links

Crossrefs

Programs

Fortran

Formula

A056543 a(n) = n*a(n-1) - 1 with a(1)=1.

Views

Author

Keywords

Comments

Examples

Links

Programs

Mathematica

Formula

Extensions

A329426 Number of non-isomorphic directed graphs where every vertex has outdegree 1, and no self-loops.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Kotlin

Formula

A329427 Number of directed graphs of n vertices with more than 1 component and outdegree 1.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Kotlin

Formula

Extensions

A134433 Triangle read by rows: T(n,k) is the number of permutations of {1,2,...,n} in which the last entry of the first increasing run is equal to k (1 <= k <= n).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula