cp's OEIS Frontend

This is a front-end for the Online Encyclopedia of Integer Sequences, made by Christian Perfect. The idea is to provide OEIS entries in non-ancient HTML, and then to think about how they're presented visually. The source code is on GitHub.

Showing 1-10 of 15 results. Next

A000522 Total number of ordered k-tuples (k=0..n) of distinct elements from an n-element set: a(n) = Sum_{k=0..n} n!/k!.

Original entry on oeis.org

1, 2, 5, 16, 65, 326, 1957, 13700, 109601, 986410, 9864101, 108505112, 1302061345, 16926797486, 236975164805, 3554627472076, 56874039553217, 966858672404690, 17403456103284421, 330665665962404000, 6613313319248080001, 138879579704209680022, 3055350753492612960485, 70273067330330098091156
Offset: 0

Views

Author

N. J. A. Sloane

Keywords

Comments

Total number of permutations of all subsets of an n-set.
Also the number of one-to-one sequences that can be formed from n distinct objects.
Old name "Total number of permutations of a set with n elements", or the same with the word "arrangements", both sound too much like A000142.
Related to number of operations of addition and multiplication to evaluate a determinant of order n by cofactor expansion - see A026243.
a(n) is also the number of paths (without loops) in the complete graph on n+2 vertices starting at one vertex v1 and ending at another v2. Example: when n=2 there are 5 paths in the complete graph with 4 vertices starting at the vertex 1 and ending at the vertex 2: (12),(132),(142),(1342),(1432) so a(2) = 5. - Avi Peretz (njk(AT)netvision.net.il), Feb 23 2001; comment corrected by Jonathan Coxhead, Mar 21 2003
Also row sums of Table A008279, which can be generated by taking the derivatives of x^k. For example, for y = 1*x^3, y' = 3x^2, y" = 6x, y'''= 6 so a(4) = 1 + 3 + 6 + 6 = 16. - Alford Arnold, Dec 15 1999
a(n) is the permanent of the n X n matrix with 2s on the diagonal and 1s elsewhere. - Yuval Dekel, Nov 01 2003
(A000166 + this_sequence)/2 = A009179, (A000166 - this_sequence)/2 = A009628.
Stirling transform of A006252(n-1) = [1,1,1,2,4,14,38,...] is a(n-1) = [1,2,5,16,65,...]. - Michael Somos, Mar 04 2004
Number of {12,12*,21*}- and {12,12*,2*1}-avoiding signed permutations in the hyperoctahedral group.
a(n) = b such that Integral_{x=0..1} x^n*exp(-x) dx = a-b*exp(-1). - Sébastien Dumortier, Mar 05 2005
a(n) is the number of permutations on [n+1] whose left-to-right record lows all occur at the start. Example: a(2) counts all permutations on [3] except 231 (the last entry is a record low but its predecessor is not). - David Callan, Jul 20 2005
a(n) is the number of permutations on [n+1] that avoid the (scattered) pattern 1-2-3|. The vertical bar means the "3" must occur at the end of the permutation. For example, 21354 is not counted by a(4): 234 is an offending subpermutation. - David Callan, Nov 02 2005
Number of deco polyominoes of height n+1 having no reentrant corners along the lower contour (i.e., no vertical step that is followed by a horizontal step). In other words, a(n)=A121579(n+1,0). A deco polyomino is a directed column-convex polyomino in which the height, measured along the diagonal, is attained only in the last column. Example: a(1)=2 because the only deco polyominoes of height 2 are the vertical and horizontal dominoes, having no reentrant corners along their lower contours. - Emeric Deutsch, Aug 16 2006
Unreduced numerators of partial sums of the Taylor series for e. - Jonathan Sondow, Aug 18 2006
a(n) is the number of permutations on [n+1] (written in one-line notation) for which the subsequence beginning at 1 is increasing. Example: a(2)=5 counts 123, 213, 231, 312, 321. - David Callan, Oct 06 2006
a(n) is the number of permutations (written in one-line notation) on the set [n + k], k >= 1, for which the subsequence beginning at 1,2,...,k is increasing. Example: n = 2, k = 2. a(2) = 5 counts 1234, 3124, 3412, 4123, 4312. - Peter Bala, Jul 29 2014
a(n) and (1,-2,3,-4,5,-6,7,...) form a reciprocal pair under the list partition transform and associated operations described in A133314. - Tom Copeland, Nov 01 2007
Consider the subsets of the set {1,2,3,...,n} formed by the first n integers. E.g., for n = 3 we have {}, {1}, {2}, {3}, {1,2}, {1,3}, {2,3}, {1,2,3}. Let the variable sbst denote a subset. For each subset sbst we determine its number of parts, that is nprts(sbst). The sum over all possible subsets is written as Sum_{sbst=subsets}. Then a(n) = Sum_{sbst=subsets} nprts(sbst)!. E.g., for n = 3 we have 1!+1!+1!+1!+2!+2!+2!+3!=16. - Thomas Wieder, Jun 17 2006
Equals row sums of triangle A158359(unsigned). - Gary W. Adamson, Mar 17 2009
Equals eigensequence of triangle A158821. - Gary W. Adamson, Mar 30 2009
For positive n, equals 1/BarnesG(n+1) times the determinant of the n X n matrix whose (i,j)-coefficient is the (i+j)th Bell number. - John M. Campbell, Oct 03 2011
a(n) is the number of n X n binary matrices with i) at most one 1 in each row and column and ii) the subset of rows that contain a 1 must also be the columns that contain a 1. Cf. A002720 where restriction ii is removed. - Geoffrey Critzer, Dec 20 2011
Number of restricted growth strings (RGS) [d(1),d(2),...,d(n)] such that d(k) <= k and d(k) <= 1 + (number of nonzero digits in prefix). The positions of nonzero digits determine the subset, and their values (decreased by 1) are the (left) inversion table (a rising factorial number) for the permutation, see example. - Joerg Arndt, Dec 09 2012
Number of a restricted growth strings (RGS) [d(0), d(1), d(2), ..., d(n)] where d(k) >= 0 and d(k) <= 1 + chg([d(0), d(1), d(2), ..., d(k-1)]) and chg(.) gives the number of changes of its argument. Replacing the function chg(.) by a function asc(.) that counts the ascents in the prefix gives A022493 (ascent sequences). - Joerg Arndt, May 10 2013
The sequence t(n) = number of i <= n such that floor(e*i!) is a square is mentioned in the abstract of Luca & Shparlinski. The values are t(n) = 0 for 0 <= n <= 2 and t(n) = 1 for at least 3 <= n <= 300. - R. J. Mathar, Jan 16 2014
a(n) = p(n,1) = q(n,1), where p and q are polynomials defined at A248664 and A248669. - Clark Kimberling, Oct 11 2014
a(n) is the number of ways at most n people can queue up at a (slow) ticket counter when one or more of the people may choose not to queue up. Note that there are C(n,k) sets of k people who quene up and k! ways to queue up. Since k can run from 0 to n, a(n) = Sum_{k=0..n} n!/(n-k)! = Sum_{k=0..n} n!/k!. For example, if n=3 and the people are A(dam), B(eth), and C(arl), a(3)=16 since there are 16 possible lineups: ABC, ACB, BAC, BCA, CAB, CBA, AB, BA, AC, CA, BC, CB, A, B, C, and empty queue. - Dennis P. Walsh, Oct 02 2015
As the row sums of A008279, Motzkin uses the abbreviated notation $n_<^\Sigma$ for a(n).
The piecewise polynomial function f defined by f(x) = a(n)*x^n/n! on each interval [ 1-1/a(n), 1-1/a(n+1) ) is continuous on [0,1) and lim_{x->1} f(x) = e. - Luc Rousseau, Oct 15 2019
a(n) is composite for 3 <= n <= 2015, but a(2016) is prime (or at least a strong pseudoprime): see Johansson link. - Robert Israel, Jul 27 2020 [a(2016) is prime, ECPP certificate generated with CM 0.4.3 and checked by factordb. - Jason H Parker, Jun 15 2025]
In general, sequences of the form a(0)=a, a(n) = n*a(n-1) + k, n>0, will have a closed form of n!*a + floor(n!*(e-1))*k. - Gary Detlefs, Oct 26 2020
From Peter Bala, Apr 03 2022: (Start)
a(2*n) is odd and a(2*n+1) is even. More generally, a(n+k) == a(n) (mod k) for all n and k. It follows that for each positive integer k, the sequence obtained by reducing a(n) modulo k is periodic, with the exact period dividing k. Various divisibility properties of the sequence follow from this; for example, a(5*n+2) == a(5*n+4) == 0 (mod 5), a(25*n+7) == a(25*n+19) == 0 (mod 25) and a(13*n+4) == a(13*n+10)== a(13*n+12) == 0 (mod 13). (End)
Number of possible ranking options on a typical ranked choice voting ballot with n candidates (allowing undervotes). - P. Christopher Staecker, May 05 2024
From Thomas Scheuerle, Dec 28 2024: (Start)
Number of decorated permutations of size n.
Number of Le-diagrams with bounding box semiperimeter n, for n > 0.
By counting over all k = 1..n and n > 0, the number of positroid cells for the totally nonnegative real Grassmannian Gr(k, n), equivalently the number of Grassmann necklaces of type (k, n). (End)

Examples

			G.f. = 1 + 2*x + 5*x^2 + 16*x^3 + 65*x^4 + 326*x^5 + 1957*x^6 + 13700*x^7 + ...
With two objects we can form 5 sequences: (), (a), (b), (a,b), (b,a), so a(2) = 5.
From _Joerg Arndt_, Dec 09 2012: (Start)
The 16 arrangements of the 3-set and their RGS (dots denote zeros) are
  [ #]       RGS        perm. of subset
  [ 1]    [ . . . ]      [  ]
  [ 2]    [ . . 1 ]      [ 3 ]
  [ 3]    [ . 1 . ]      [ 2 ]
  [ 4]    [ . 1 1 ]      [ 2 3 ]
  [ 5]    [ . 1 2 ]      [ 3 2 ]
  [ 6]    [ 1 . . ]      [ 1 ]
  [ 7]    [ 1 . 1 ]      [ 1 3 ]
  [ 8]    [ 1 . 2 ]      [ 3 1 ]
  [ 9]    [ 1 1 . ]      [ 1 2 ]
  [10]    [ 1 1 1 ]      [ 1 2 3 ]
  [11]    [ 1 1 2 ]      [ 1 3 2 ]
  [12]    [ 1 1 3 ]      [ 2 3 1 ]
  [13]    [ 1 2 . ]      [ 2 1 ]
  [14]    [ 1 2 1 ]      [ 2 1 3 ]
  [15]    [ 1 2 2 ]      [ 3 1 2 ]
  [16]    [ 1 2 3 ]      [ 3 2 1 ]
(End)

References

  • L. Comtet, Advanced Combinatorics, Reidel, 1974, p. 75, Problem 9.
  • J.-M. De Koninck, Ces nombres qui nous fascinent, Entry 65, p. 23, Ellipses, Paris 2008.
  • J. M. Gandhi, On logarithmic numbers, Math. Student, 31 (1963), 73-83.
  • R. K. Guy, Unsolved Problems in Number Theory, Springer, 1st edition, 1981. See section E11.
  • J. Riordan, An Introduction to Combinatorial Analysis, Wiley, 1958, p. 16.
  • D. Singh, The numbers L(m,n) and their relations with prepared Bernoulli and Eulerian numbers, Math. Student, 20 (1952), 66-70.
  • N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
  • N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Links

Crossrefs

Cf. A000166, A002627, A006231, A064383, A064384, A008290, A010844, A010845, A014508, A038159, A054091, A058006, A072453, A072456, A073591, A082030, A095000, A095177, A108625, A121579, A124779, A142992, A143007, A158359, A158821, A195254, A222637-A222639, A038155, A000217.
Average of n-th row of triangle in A068424 [Corrected by N. J. A. Sloane, Feb 29 2024].
Row sums of A008279 and A094816.
First differences give A001339. Second differences give A001340.
Partial sums are in A001338, A002104.
A row of the array in A144502.
See also A370973, Nearest integer to e*n!.

Programs

  • Haskell
    import Data.List (subsequences, permutations)
a000522 = length . choices . enumFromTo 1 where
choices = concat . map permutations . subsequences
-- Reinhard Zumkeller, Feb 21 2012, Oct 25 2010
  • Magma
    [1] cat [n eq 1 select (n+1) else n*Self(n-1)+1: n in [1..25]]; // Vincenzo Librandi, Feb 15 2015
  • Maple
    a(n):= exp(1)*int(x^n*exp(-x)*Heaviside(x-1), x=0..infinity); # Karol A. Penson, Oct 01 2001
A000522 := n->add(n!/k!,k=0..n);
G(x):=exp(x)/(1-x): f[0]:=G(x): for n from 1 to 26 do f[n]:=diff(f[n-1],x) od: x:=0: seq(f[n],n=0..20);
# Zerinvary Lajos, Apr 03 2009
G:=exp(z)/(1-z): Gser:=series(G,z=0,21):
for n from 0 to 20 do a(n):=n!*coeff(Gser,z,n): end do
# Paul Weisenhorn, May 30 2010
k := 1; series(hypergeom([1,k],[],x/(1-x))/(1-x), x=0, 20); # Mark van Hoeij, Nov 07 2011
# one more Maple program:
a:= proc(n) option remember;
      `if`(n<0, 0, 1+n*a(n-1))
    end:
seq(a(n), n=0..23);  # Alois P. Heinz, Sep 13 2019
seq(simplify(KummerU(-n, -n, 1)), n = 0..23); # Peter Luschny, May 10 2022
  • Mathematica
    Table[FunctionExpand[Gamma[n + 1, 1]*E], {n, 0, 24}]
nn = 20; Accumulate[Table[1/k!, {k, 0, nn}]] Range[0, nn]! (* Jan Mangaldan, Apr 21 2013 *)
FoldList[#1*#2 + #2 &, 0, Range@ 23] + 1 (* or *)
f[n_] := Floor[E*n!]; f[0] = 1; Array[f, 20, 0] (* Robert G. Wilson v, Feb 13 2015 *)
RecurrenceTable[{a[n + 1] == (n + 1) a[n] + 1, a[0] == 1}, a, {n, 0, 12}] (* Emanuele Munarini, Apr 27 2017 *)
nxt[{n_,a_}]:={n+1,a(n+1)+1}; NestList[nxt,{0,1},30][[All,2]] (* Harvey P. Dale, Jan 29 2023 *)
  • Maxima
    a(n) := if n=0 then 1 else n*a(n-1)+1; makelist(a(n),n,0,12); /* Emanuele Munarini, Apr 27 2017 */
  • PARI
    {a(n) = local(A); if( n<0, 0, A = vector(n+1); A[1]=1; for(k=1, n, A[k+1] = k*A[k] + 1); A[n+1])}; /* Michael Somos, Jul 01 2004 */
  • PARI
    {a(n) = if( n<0, 0, n! * polcoeff( exp( x +x * O(x^n)) / (1 - x), n))}; /* Michael Somos, Mar 06 2004 */
  • PARI
    a(n)=local(A=1+x+x*O(x^n)); for(i=1, n, A=1/(1-x)^2+x^2*deriv(A)/(1-x)); polcoeff(A, n) \\ Paul D. Hanna, Sep 03 2008
  • PARI
    {a(n)=local(X=x+x*O(x^n));polcoeff(sum(m=0,n,(m+2)^m*x^m/(1+(m+1)*X)^(m+1)),n)} /* Paul D. Hanna */
  • PARI
    a(n)=sum(k=0,n,binomial(n,k)*k!); \\ Joerg Arndt, Dec 14 2014
  • Sage
    # program adapted from Alois P. Heinz's Maple code in A022493
@CachedFunction
def b(n, i, t):
    if n <= 1:
        return 1
    return sum(b(n - 1, j, t + (j == i)) for j in range(t + 2))
def a(n):
    return b(n, 0, 0)
v000522 = [a(n) for n in range(33)]
print(v000522)
# Joerg Arndt, May 11 2013

Formula

a(n) = n*a(n-1) + 1, a(0) = 1.
a(n) = A007526(n-1) + 1.
a(n) = A061354(n)*A093101(n).
a(n) = n! * Sum_{k=0..n} 1/k! = n! * (e - Sum_{k>=n+1} 1/k!). - Michael Somos, Mar 26 1999
a(0) = 1; for n > 0, a(n) = floor(e*n!).
E.g.f.: exp(x)/(1-x).
a(n) = 1 + Sum_{n>=k>=j>=0} (k-j+1)*k!/j! = a(n-1) + A001339(n-1) = A007526(n) + 1. Binomial transformation of n!, i.e., A000142. - Henry Bottomley, Jun 04 2001
a(n) = floor(2/(n+1))*A009578(n+1)-1. - Emeric Deutsch, Oct 24 2001
Integral representation as n-th moment of a nonnegative function on a positive half-axis: a(n) = e*Integral_{x>=0} x^n*e^(-x)*Heaviside(x-1) dx. - Karol A. Penson, Oct 01 2001
Formula, in Mathematica notation: Special values of Laguerre polynomials, a(n)=(-1)^n*n!*LaguerreL[n, -1-n, 1], n=1, 2, ... . This relation cannot be checked by Maple, as it appears that Maple does not incorporate Laguerre polynomials with second index equal to negative integers. It does check with Mathematica. - Karol A. Penson and Pawel Blasiak ( blasiak(AT)lptl.jussieu.fr), Feb 13 2004
G.f.: Sum_{k>=0} k!*x^k/(1-x)^(k+1). a(n) = Sum_{k=0..n} (-1)^(n-k)*binomial(n, k)*k^(n-k)*(k+1)^k. - Vladeta Jovovic, Aug 18 2002
a(n) = Sum_{k=0..n} A008290(n, k)*2^k. - Philippe Deléham, Dec 12 2003
a(n) = Sum_{k=0..n} A046716(n, k). - Philippe Deléham, Jun 12 2004
a(n) = e*Gamma(n+1,1) where Gamma(z,t) = Integral_{x>=t} e^(-x)*x^(z-1) dx is incomplete gamma function. - Michael Somos, Jul 01 2004
a(n) = Sum_{k=0..n} P(n, k). - Ross La Haye, Aug 28 2005
Given g.f. A(x), then g.f. A059115 = A(x/(1-x)). - Michael Somos, Aug 03 2006
a(n) = 1 + n + n*(n-1) + n*(n-1)*(n-2) + ... + n!. - Jonathan Sondow, Aug 18 2006
a(n) = Sum_{k=0..n} binomial(n,k) * k!; interpretation: for all k-subsets (sum), choose a subset (binomial(n,k)), and permutation of subset (k!). - Joerg Arndt, Dec 09 2012
a(n) = Integral_{x>=0} (x+1)^n*e^(-x) dx. - Gerald McGarvey, Oct 19 2006
a(n) = Sum_{k=0..n} A094816(n, k), n>=0 (row sums of Poisson-Charlier coefficient matrix). - N. J. A. Sloane, Nov 10 2007
From Tom Copeland, Nov 01 2007, Dec 10 2007: (Start)
Act on 1/(1-x) with 1/(1-xDx) = Sum_{j>=0} (xDx)^j = Sum_{j>=0} x^j*D^j*x^j = Sum_{j>=0} j!*x^j*L(j,-:xD:,0) where Lag(n,x,0) are the Laguerre polynomials of order 0, D the derivative w.r.t. x and (:xD:)^j = x^j*D^j. Truncating the operator series at the j = n term gives an o.g.f. for a(0) through a(n) consistent with Jovovic's.
These results and those of Penson and Blasiak, Arnold, Bottomley and Deleham are related by the operator A094587 (the reverse of A008279), which is the umbral equivalent of n!*Lag[n,(.)!*Lag[.,x,-1],0] = (1-D)^(-1) x^n = (-1)^n * n! Lag(n,x,-1-n) = Sum_{j=0..n} binomial(n,j)*j!*x^(n-j) = Sum_{j=0..n} (n!/j!)*x^j. Umbral substitution of b(.) for x and then letting b(n)=1 for all n connects the results. See A132013 (the inverse of A094587) for a connection between these operations and 1/(1-xDx).
(End)
From Peter Bala, Jul 15 2008: (Start)
a(n) = n!*e - 1/(n + 1/(n+1 + 2/(n+2 + 3/(n+3 + ...)))).
Asymptotic result (Ramanujan): n!*e - a(n) ~ 1/n - 1/n^3 + 1/n^4 + 2/n^5 - 9/n^6 + ..., where the sequence [1,0,-1,1,2,-9,...] = [(-1)^k*A000587(k)], for k>=1.
a(n) is a difference divisibility sequence, that is, the difference a(n) - a(m) is divisible by n - m for all n and m (provided n is not equal to m). For fixed k, define the derived sequence a_k(n) = (a(n+k)-a(k))/n, n = 1,2,3,... . Then a_k(n) is also a difference divisibility sequence.
For example, the derived sequence a_0(n) is just a(n-1). The set of integer sequences satisfying the difference divisibility property forms a ring with term-wise operations of addition and multiplication.
Recurrence relations: a(0) = 1, a(n) = (n-1)*(a(n-1) + a(n-2)) + 2, for n >= 1. a(0) = 1, a(1) = 2, D-finite with recurrence: a(n) = (n+1)*a(n-1) - (n-1)*a(n-2) for n >= 2. The sequence b(n) := n! satisfies the latter recurrence with the initial conditions b(0) = 1, b(1) = 1. This leads to the finite continued fraction expansion a(n)/n! = 1/(1-1/(2-1/(3-2/(4-...-(n-1)/(n+1))))), n >= 2.
Limit_{n->oo} a(n)/n! = e = 1/(1-1/(2-1/(3-2/(4-...-n/((n+2)-...))))). This is the particular case m = 0 of the general result m!/e - d_m = (-1)^(m+1) *(1/(m+2 -1/(m+3 -2/(m+4 -3/(m+5 -...))))), where d_m denotes the m-th derangement number A000166(m).
For sequences satisfying the more general recurrence a(n) = (n+1+r)*a(n-1) - (n-1)*a(n-2), which yield series acceleration formulas for e/r! that involve the Poisson-Charlier polynomials c_r(-n;-1), refer to A001339 (r=1), A082030 (r=2), A095000 (r=3) and A095177 (r=4).
For the corresponding results for the constants log(2), zeta(2) and zeta(3) refer to A142992, A108625 and A143007 respectively.
(End)
G.f. satisfies: A(x) = 1/(1-x)^2 + x^2*A'(x)/(1-x). - Paul D. Hanna, Sep 03 2008
From Paul Barry, Nov 27 2009: (Start)
G.f.: 1/(1-2*x-x^2/(1-4*x-4*x^2/(1-6*x-9*x^2/(1-8*x-16*x^2/(1-10*x-25*x^2/(1-... (continued fraction);
G.f.: 1/(1-x-x/(1-x/(1-x-2*x/(1-2*x/(1-x-3*x/(1-3*x/(1-x-4*x/(1-4*x/(1-x-5*x/(1-5*x/(1-... (continued fraction).
(End)
O.g.f.: Sum_{n>=0} (n+2)^n*x^n/(1 + (n+1)*x)^(n+1). - Paul D. Hanna, Sep 19 2011
G.f. hypergeom([1,k],[],x/(1-x))/(1-x), for k=1,2,...,9 is the generating function for A000522, A001339, A082030, A095000, A095177, A096307, A096341, A095722, and A095740. - Mark van Hoeij, Nov 07 2011
G.f.: 1/U(0) where U(k) = 1 - x - x*(k+1)/(1 - x*(k+1)/U(k+1)); (continued fraction). - Sergei N. Gladkovskii, Oct 14 2012
E.g.f.: 1/U(0) where U(k) = 1 - x/(1 - 1/(1 + (k+1)/U(k+1))); (continued fraction). - Sergei N. Gladkovskii, Nov 16 2012
G.f.: 1/(1-x)/Q(0), where Q(k) = 1 - x/(1-x)*(k+1)/(1 - x/(1-x)*(k+1)/Q(k+1)); (continued fraction). - Sergei N. Gladkovskii, May 19 2013
G.f.: 2/(1-x)/G(0), where G(k) = 1 + 1/(1 - x*(2*k+2)/(x*(2*k+3) - 1 + x*(2*k+2)/G(k+1))); (continued fraction). - Sergei N. Gladkovskii, May 31 2013
G.f.: (B(x)+ 1)/(2-2*x) = Q(0)/(2-2*x), where B(x) be g.f. A006183, Q(k) = 1 + 1/(1 - x*(k+1)/(x*(k+1) + (1-x)/Q(k+1) )); (continued fraction). - Sergei N. Gladkovskii, Aug 08 2013
G.f.: 1/Q(0), where Q(k) = 1 - 2*x*(k+1) - x^2*(k+1)^2/Q(k+1); (continued fraction). - Sergei N. Gladkovskii, Sep 30 2013
E.g.f.: e^x/(1-x) = (1 - 12*x/(Q(0) + 6*x - 3*x^2))/(1-x), where Q(k) = 2*(4*k+1)*(32*k^2 + 16*k + x^2 - 6) - x^4*(4*k-1)*(4*k+7)/Q(k+1); (continued fraction). - Sergei N. Gladkovskii, Nov 18 2013
G.f.: conjecture: T(0)/(1-2*x), where T(k) = 1 - x^2*(k+1)^2/(x^2*(k+1)^2 - (1 - 2*x*(k+1))*(1 - 2*x*(k+2))/T(k+1) ); (continued fraction). - Sergei N. Gladkovskii, Nov 18 2013
0 = a(n)*(+a(n+1) - 3*a(n+2) + a(n+3)) + a(n+1)*(+a(n+1) - a(n+3)) + a(n+2)*(+a(n+2)) for all n>=0. - Michael Somos, Jul 04 2014
From Peter Bala, Jul 29 2014: (Start)
a(n) = F(n), where the function F(x) := Integral_{0..infinity} e^(-u)*(1 + u)^x du smoothly interpolates this sequence to all real values of x. Note that F(-1) = G and for n = 2,3,... we have F(-n) = (-1)^n/(n-1)! *( A058006(n-2) - G ), where G = 0.5963473623... denotes Gompertz's constant - see A073003.
a(n) = n!*e - e*( Sum_{k >= 0} (-1)^k/((n + k + 1)*k!) ).
(End)
a(n) = hypergeometric_U(1, n+2, 1). - Peter Luschny, Nov 26 2014
a(n) ~ exp(1-n)*n^(n-1/2)*sqrt(2*Pi). - Vladimir Reshetnikov, Oct 27 2015
a(n) = A038155(n+2)/A000217(n+1). - Anton Zakharov, Sep 08 2016
a(n) = round(exp(1)*n!), n > 1 - Simon Plouffe, Jul 28 2020
a(n) = KummerU(-n, -n, 1). - Peter Luschny, May 10 2022
a(n) = (e/(2*Pi))*Integral_{x=-oo..oo} (n+1+i*x)!/(1+i*x) dx. - David Ulgenes, Apr 18 2023
Sum_{i=0..n} (-1)^(n-i) * binomial(n, i) * a(i) = n!. - Werner Schulte, Apr 03 2024

Extensions

Additional comments from Michael Somos

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

Original entry on oeis.org

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

Views

Author

N. J. A. Sloane

Keywords

Comments

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

Examples

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

References

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

Links

Crossrefs

Cf. A000522, A007526, A038155, A056542, A079884, A079750.
Row sums of A119741.

Programs

Formula

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

Extensions

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

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

Original entry on oeis.org

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

Views

Author

Henry Bottomley, Jun 20 2000

Keywords

Comments

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

Examples

			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

References

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

Links

Crossrefs

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

Programs

  • Haskell
    a056542 n = a056542_list !! (n-1)
a056542_list = 0 : map (+ 1) (zipWith (*) [2..] a056542_list)
-- Reinhard Zumkeller, Mar 24 2013
  • Magma
    [n le 2 select n-1 else n*Self(n-1)+1: n in [1..20]]; // Bruno Berselli, Dec 13 2013
  • Mathematica
    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 *)

Formula

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

Extensions

More terms from James Sellers, Jul 04 2000

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

Views

Author

Hugo Pfoertner, Jan 12 2003

Keywords

Comments

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

Examples

			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.

References

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

Links

Crossrefs

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

Programs

  • Fortran
    Program available at Pfoertner link
  • PARI
    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

Formula

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

A073107 Triangle T(n,k) read by rows, where e.g.f. for T(n,k) is exp((1+y)*x)/(1-x).

Original entry on oeis.org

1, 2, 1, 5, 4, 1, 16, 15, 6, 1, 65, 64, 30, 8, 1, 326, 325, 160, 50, 10, 1, 1957, 1956, 975, 320, 75, 12, 1, 13700, 13699, 6846, 2275, 560, 105, 14, 1, 109601, 109600, 54796, 18256, 4550, 896, 140, 16, 1, 986410, 986409, 493200, 164388, 41076, 8190, 1344, 180, 18, 1
Offset: 0

Views

Author

Vladeta Jovovic, Aug 19 2002

Keywords

Comments

Triangle is second binomial transform of A008290. - Paul Barry, May 25 2006
Ignoring signs, n-th row is the coefficient list of the permanental polynomial of the n X n matrix with 2's along the main diagonal and 1's everywhere else (see Mathematica code below). - John M. Campbell, Jul 02 2012

Examples

			exp((1 + y)*x)/(1 - x) =
  1 +
  1/1! * (2 + y) * x +
  1/2! * (5 + 4*y + y^2) * x^2 +
  1/3! * (16 + 15*y + 6*y^2 + y^3) * x^3 +
  1/4! * (65 + 64*y + 30*y^2 + 8*y^3 + y^4) * x^4 +
  1/5! * (326 + 325*y + 160*y^2 + 50*y^3 + 10*y^4 + y^5) * x^5 + ...
Triangle starts:
  [0]     1;
  [1]     2,     1;
  [2]     5,     4,    1;
  [3]    16,    15,    6,    1;
  [4]    65,    64,   30,    8,   1;
  [5]   326,   325,  160,   50,  10,   1;
  [6]  1957,  1956,  975,  320,  75,  12,  1;
  [7] 13700, 13699, 6846, 2275, 560, 105, 14, 1;

Links

Crossrefs

Cf. A008290, A008291, A046802, A093375 (unsigned inverse), A094587, A010842 (row sums), A000142 (alternating row sums), A367963 (central terms).
Column k=0..4 give A000522, A007526, A038155, A357479, A357480.

Programs

  • Maple
    T := (n, k) -> binomial(n,k)*KummerU(k-n, k-n, 1);
seq(seq(simplify(T(n, k)), k = 0..n), n=0..8);  # Peter Luschny, Oct 16 2024
  • Mathematica
    perm[m_List] := With[{v=Array[x,Length[m]]},Coefficient[Times@@(m.v),Times@@v]] ;
A[q_] := Array[KroneckerDelta[#1,#2] + 1&,{q,q}] ;
n = 1 ; Print[{1}]; While[n < 10, Print[Abs[CoefficientList[perm[A[n] - IdentityMatrix[n] * k], k]]]; n++] (* John M. Campbell, Jul 02 2012 *)
A073107[n_, k_] := If[n == k, 1, Floor[E*(n - k)!]*Binomial[n, k]];
Table[A073107[n, k], {n, 0, 10}, {k, 0, n}] (* Paolo Xausa, Oct 16 2024 *)
  • SageMath
    def T(n, k):
    return sum(binomial(j,k) * factorial(n) // factorial(j) for j in range(n+1))
for n in range(8): print([T(n, k) for k in range(n+1)])
# Peter Luschny, Oct 16 2024

Formula

O.g.f. for k-th column is (1/k!)*Sum_{i >= k} i!*x^i/(1-x)^(i+1).
For n > 0, T(n, 0) = floor(n!*exp(1)) = A000522(n), T(n, 1) = floor(n!*exp(1) - 1) = A007526(n), T(n, 2) = 1/2!*floor(n!*exp(1) - 1 - n) = A038155(n), T(n, 3) = 1/3!*floor(n!*exp(1) - 1 - n - n*(n - 1)), T(n, 4) = 1/4!*floor(n!*exp(1) - 1 - n - n*(n - 1) - n*(n - 1)*(n - 2)), ... .
Row sums give A010842.
E.g.f. for k-th column is (x^k/k!)*exp(x)/(1 - x).
O.g.f. for k-th row is n!*Sum_{k = 0..n} (1 + x)^k/k!.
T(n,k) = Sum_{j = 0..n} binomial(j,k)*n!/j!. - Paul Barry, May 25 2006
-exp(-x) * Sum_{k=0..n} T(n,k)*x^k = Integral (x+1)^n*exp(-x) dx = -exp(1)*Gamma(n+1,x+1). - Gerald McGarvey, Mar 15 2009
From Peter Bala, Sep 20 2012: (Start)
Exponential Riordan array [exp(x)/(1-x),x] belonging to the Appell subgroup, which factorizes in the Appell group as [1/1-x,x]*[exp(x),x] = A094587*A007318.
The n-th row polynomial R(n,x) of the triangle satisfies d/dx(R(n,x)) = n*R(n-1,x), as well as R(n,x + y) = Sum {k = 0..n} binomial(n,k)*R(k,x)*y^(n-k). The row polynomials are a Sheffer sequence of Appell type.
Matrix inverse of triangle is a signed version of A093375. (End)
From Tom Copeland, Oct 20 2015: (Start)
The raising operator, with D = d/dx, for the row polynomials is RP = x + d{log[e^D/(1-D)]}/dD = x + 1 + 1/(1-D) = x + 2 + D + D^2 + ..., i.e., RP R(n,x) = R(n+1,x).
This operator is the limit as t tends to 1 of the raising operator of the polynomials p(n,x;t) described in A046802, implying R(n,x) = p(n,x;1). Compare with the raising operator of A094587, x + 1/(1-D), and that of signed A093375, x - 1 - 1/(1-D).
From the Appell formalism, the row polynomials RI(n,x) of signed A093375 are the umbral inverse of this entry's row polynomials; that is, R(n,RI(.,x)) = x^n = RI(n,R(.,x)) under umbral composition. (End)
From Werner Schulte, Sep 07 2020: (Start)
T(n,k) = (n! / k!) * (Sum_{i=k..n} 1 / (n-i)!) for 0 <= k <= n.
T(n,k) = n * T(n-1,k) + binomial(n,k) for 0 <= k <= n with initial values T(0,0) = 1 and T(i,j) = 0 if j < 0 or j > i.
T(n,k) = A000522(n-k) * binomial(n,k) for 0 <= k <= n. (End)

Extensions

More terms from Emeric Deutsch, Feb 23 2004

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

Original entry on oeis.org

0, 0, 2, 12, 60, 320, 1950, 13692, 109592, 986400, 9864090, 108505100, 1302061332, 16926797472, 236975164790, 3554627472060, 56874039553200, 966858672404672, 17403456103284402, 330665665962403980, 6613313319248079980, 138879579704209680000
Offset: 0

Views

Author

N. J. A. Sloane

Keywords

Comments

The number of rank-orderings of (>=2)-element subsets of an n-set. (Counts nontrivial votes in a rank-ordering voting system.) E.g., a(5) = 320 = 120+120+60+20 because of 5-, 4-, 3- and 2-element subsets. - Warren D. Smith, Jul 06 2005
a(n) is the number of simple cycles through a vertex of the complete graph K_(n+1) on n+1 vertices [Hassani]. For example, in the complete graph K_4 with vertex set {A,B,C,D} there are a(3) = 12 simple cycles at the vertex A, namely the six 3-cycles ABCA, ABDA, ACBA, ACDA, ADBA and ADCA and the six 4-cycles ABCDA, ABDCA, ACBDA, ACDBA, ADBCA and ADCBA. The sum of the lengths of the cycles at a vertex of K_n is equal to A141834(n). - Peter Bala, Jul 09 2008
See A000522 for the number of paths between a pair of distinct vertices of K_n. - Peter Bala, Jul 09 2008
a(n) = n*a(n-1) + A000217(n-1), where A000217(n) is the n-th triangular number. - Gary Detlefs, May 20 2010

Examples

			0=1*0+0, 2=2*0+2, 12=3*2+6, 60=4*12+12, 320 = 5*60+20, ... - _Gary Detlefs_, May 20 2010

Links

Crossrefs

Cf. A000522, A038155, A141834.

Programs

  • Mathematica
    Table[n!Sum[1/k!,{k,0,n-2}],{n,0,30}] (* Harvey P. Dale, Jun 04 2012 *)
  • PARI
    main(size)=my(k); vector(size,n,(n-1)!*sum(k=0,n-3,1/k!)); \\ Anders Hellström, Jul 14 2015

Formula

a(n) = A007526(n) - n.
a(n) = floor(n!*exp(1))-n-1, n>0. - Vladeta Jovovic, Aug 25 2001
a(n) = n*a(n-1) + n*(n-1), for n>=3, a(2)=2 and a(3) = 12. - Ian Myers, Jul 19 2012
a(n) = A000522(n-2) * n*(n-1). - Doug Bell, Jun 30 2015
E.g.f.: exp(x)*x^2/(1 - x). - Ilya Gutkovskiy, Jan 26 2017
a(n) = 2*A038155(n). - Alois P. Heinz, Jan 26 2017

A080047 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 times l has to be repeatedly decreased in step L3.

Original entry on oeis.org

0, 1, 7, 41, 256, 1807, 14477, 130321, 1303246, 14335751, 172029067, 2236377937, 31309291196, 469639368031, 7514229888601, 127741908106337, 2299354345914202, 43687732572369991, 873754651447399991
Offset: 2

Views

Author

Hugo Pfoertner, Jan 25 2003

Keywords

References

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

Links

Crossrefs

Cf. A038155, A038156, A056542, A080048, A080049, A079754.

Programs

  • Mathematica
    Transpose[NestList[{First[#]+1,(First[#]+1)Last[#]+(First[#](First[#]-1))/2}&, {2,0},20]][[2]] (* Harvey P. Dale, Feb 27 2012 *)
Rest[Rest[CoefficientList[Series[(2-Exp[x]*(x^2-2*x+2))/(2*(x-1)),{x,0,20}],x]*Range[0,20]!]] (* Vaclav Kotesovec, Oct 21 2012 *)

Formula

a(2)=0, a(n) = n*a(n-1)+(n-1)*(n-2)/2 for n>=3 c = limit n--> infinity a(n)/n! = 0.35914091422952261768 = e/2-1, a(n) = floor [c*n! - (n-1)/2] for n>=2
E.g.f.: (2-exp(x)*(x^2-2*x+2))/(2*(x-1)). - Vaclav Kotesovec, Oct 21 2012

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.

Original entry on oeis.org

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

Views

Author

Hugo Pfoertner, Jan 24 2003

Keywords

References

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

Links

Crossrefs

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

Programs

  • Fortran
    ! Program available at link.

Formula

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.

A036918 a(n) = floor(e*(n-1)*(n-1)!).

Original entry on oeis.org

0, 2, 10, 48, 260, 1630, 11742, 95900, 876808, 8877690, 98641010, 1193556232, 15624736140, 220048367318, 3317652307270, 53319412081140, 909984632851472, 16436597430879730, 313262209859119578, 6282647653285676000, 132266266384961600020, 2916471173788403280462
Offset: 1

Views

Author

N. J. A. Sloane

Keywords

Comments

Also the number of positive integers with all distinct digits expressed in base n. E.g., a(10) = Sum_{j=1..10} A073531(j). - Labos Elemer, Dec 05 2002
For example, for n=3 we have 1, 2, 10, 12, 20, 21, 102, 120, 201, 210 (10 numbers in total). - Igor Krasikov, Aug 14 2023

Crossrefs

Cf. A001113, A073531, A073532.
a(n) = A001339(n)-1.
Equals (n-1)*A000522(n-1).

Programs

  • Mathematica
    Table[Apply[Plus, Table[((b-1)/b)*Binomial[b, j]*j!, {j, 1, b}]], {b, 1, 25}]
Table[Floor[E(n-1)(n-1)!],{n,25}] (* Harvey P. Dale, May 19 2025 *)

Formula

G.f.: Q(0)/(2*x) - 1/x - 1/(1-x), where Q(k) = 1 + 1/(1 - x*(k+1)/(x*(k+1) + (1-x)/Q(k+1) )); (continued fraction). - Sergei N. Gladkovskii, Aug 08 2013
a(n) = 2*(A038155(n) - A038155(n-1)). - Anton Zakharov, Oct 13 2016

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

Views

Author

Hugo Pfoertner, Jan 24 2003

Keywords

References

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

Links

Crossrefs

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

Programs

  • Fortran
    c FORTRAN program available at Pfoertner link.

Formula

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.
Showing 1-10 of 15 results. Next

Started in 1964 by Neil J. A. Sloane | Maintained by The OEIS Foundation Inc.

Content is available under The OEIS End-User License Agreement.