

A000522


Total number of arrangements of a set with n elements: a(n) = Sum_{k=0..n} n!/k!.
(Formerly M1497 N0589)


164



1, 2, 5, 16, 65, 326, 1957, 13700, 109601, 986410, 9864101, 108505112, 1302061345, 16926797486, 236975164805, 3554627472076, 56874039553217, 966858672404690, 17403456103284421, 330665665962404000, 6613313319248080001
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

0,2


COMMENTS

The number of onetoone sequences that can be formed from n distinct objects.
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 (Alford1940), 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(n1)=[1,1,1,2,4,14,38,...] is a(n1)=[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)=exp(1)*Gamma(n+1,1) where Gamma(z,t)=Integral_{x>=t} exp(x)x^(z1) dx is incomplete gamma function.  Michael Somos, Jul 01 2004
a(n) = b such that Integral_{x=0..1} x^n*exp(x) dx = ab*exp(1).  Sebastien DUMORTIER (sdumortier(AT)aclimoges.fr), Mar 05 2005
a(n) is the number of permutations on [n+1] whose lefttoright 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) = number of permutations on [n+1] that avoid the (scattered) pattern 123. 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 columnconvex 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) = number of permutations on [n+1] (written in oneline 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) 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 nXn 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(k1)]) and chg(.) counts 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


REFERENCES

Roland Bacher, Counting Packings of Generic Subsets in Finite Groups, Electr. J. Combinatorics, 19 (2012), #P7.
C. Banderier, M. BousquetMélou, A. Denise, P. Flajolet, D. Gardy and D. GouyouBeauchamps, [http://algo.inria.fr/banderier/Papers/DiscMath99.ps Generating Functions for Generating Trees], Discrete Mathematics 246(13), March 2002, pp. 2955.
E. Barcucci, A. Del Lungo and R. Pinzani, "Deco" polyominoes, permutations and random generation, Theoretical Computer Science, 159, 1996, 2942.
L. Comtet, Advanced Combinatorics, Reidel, 1974, p. 75, Problem 9.
D. Daly and L. Pudwell, Pattern avoidance in rook monoids, 2013; http://faculty.valpo.edu/lpudwell/slides/sandiego2013.pdf.
J.M. De Koninck, Ces nombres qui nous fascinent, Entry 65, p. 23, Ellipses, Paris 2008.
Philip Feinsilver and John McSorley, Zeons, Permanents, the Johnson Scheme, and Generalized Derangements, International Journal of Combinatorics, Volume 2011, Article ID 539030, 29 pages; doi:10.1155/2011/539030.
Stefan Forcey, Aaron Lauve and Frank Sottile, Cofree compositions of coalgebras, Annals of Combinatorics 17 (1) pp. 105130, March 2013; http://www.combinatorics.net/Annals/Abstract/17_1_105.aspx
Bernd Gaertner, Walter D. Jr. Morris and Leo Ruest, Unique Sink Orientations of Grids, Algorithmica, Volume 51, Number 2 / June 2008.
J. M. Gandhi, On logarithmic numbers, Math. Student, 31 (1963), 7383.
F. Luca and I. E. Shparlinski, On the squarefree parts of [ e n! ], Glasgow Math. J., 49 (2007), 391403.
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), 6670.
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).
J. Sondow, A geometric proof that e is irrational and a new measure of its irrationality, Amer. Math. Monthly 113 (2006) 637641.


LINKS

T. D. Noe, Table of n, a(n) for n = 0..100
F. Ardila, F. Rincón, L. Williams, Positroids and noncrossing partitions, arXiv preprint arXiv:1308.2698, 2013
P. Blasiak, A. Horzela, K. A. Penson, G.H.E. Duchamp and A. I. Solomon, Boson normal ordering via substitutions and Sheffertype polynomials
J. Brzozowski, M. Szykula, Large Aperiodic Semigroups, arXiv preprint arXiv:1401.0157, 2013
P. J. Cameron, Sequences realized by oligomorphic permutation groups, J. Integ. Seqs. Vol. 3 (2000), #00.1.5.
P. Flajolet and R. Sedgewick, Analytic Combinatorics, 2009; see page 114
Lorenz Halbeisen and Norbert Hungerbuehler, Number theoretic aspects of a combinatorial function, Notes on Number Theory and Discrete Mathematics 5 (1999) 138150. (ps, pdf)
Lorenz Halbeisen and Saharon Shelah, Consequences of arithmetic for set theory, The Journal of Symbolic Logic, vol. 59 (1994), pp. 3040.
M. Hassani, Counting and computing by e
INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 35
J. W. Layman, The Hankel Transform and Some of its Properties, J. Integer Sequences, 4 (2001), #01.1.5.
F. Luca and I. E. Shparlinski, On the squarefree parts of [ e n! ], Glasgow Math. J., 49 (2007), 391403.
T. Mansour and J. West, Avoiding 2letter signed patterns.
Alexsandar Petojevic, The Function vM_m(s; a; z) and Some WellKnown Sequences, Journal of Integer Sequences, Vol. 5 (2002), Article 02.1.7
Robert A. Proctor, Let's Expand Rota's Twelvefold Way For Counting Partitions!, arXiv:math.CO/0606404, Jan 05, 2007
J. Sondow, A geometric proof that e is irrational and a new measure of its irrationality
J. Sondow, The Taylor series for e and the primes 2, 5, 13, 37, 463, ...: a surprising connection
J. Sondow and K. Schalm, Which partial sums of the Taylor series for e are convergents to e? (and a link to the primes 2, 5, 13, 37, 463), II, Gems in Experimental Mathematics (T. Amdeberhan, L. A. Medina, and V. H. Moll, eds.), Contemporary Mathematics, vol. 517, Amer. Math. Soc., Providence, RI, 2010.
Eric Weisstein's World of Mathematics, Binomial Sums
Index entries for sequences related to logarithmic numbers
Index entries for related partitioncounting sequences
Index entries for sequences related to factorial numbers


FORMULA

a(n) = n*a(n1) + 1, a(0) = 1.
a(n) = A007526(n1) + 1.
a(n) = A061354(n)*A093101(n).
a(n) = n! * Sum(1/k!, k=0..n) = 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)/(1x).
a(n) = 1+sum{n >= k >= j >= 0}((kj+1)*k!/j!) = a(n1)+A001339(n1) = A007526(n)+1. Binomial transformation of n!, i.e. A000142.  Henry Bottomley, Jun 04 2001
a(n)=[2/(n+1)]A009578(n+1)1.  Emeric Deutsch, Oct 24 2001
Integral representation as nth moment of a nonnegative function on a positive halfaxis, in Maple notation: a(n)=exp(1)*int(x^n*exp(x)*Heaviside(x1), x=0..infinity), n=0, 1...  Karol A. Penson, Oct 01 2001
Formula, in Mathematica notation: Special values of Laguerre polynomials, a(n)=(1)^n*n!*LaguerreL[n, 1n, 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/(1x)^(k+1). a(n) = Sum_{k=0..n} (1)^(nk)*binomial(n, k)*k^(nk)*(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) = Sum[P(n, k), {k, 0, n}].  Ross La Haye, Aug 28 2005
Given g.f. A(x), then g.f. A059115 = A(x/(1x)).  Michael Somos, Aug 03 2006
a(n) = 1 + n + n*(n1) + n*(n1)*(n2) + ... + n!.  Jonathan Sondow, Aug 18 2006
a(n) = sum(k=0..n, C(n,k) * k! ); interpretation: for all ksubsets (sum), choose a subset (C(n,k)), and permutation of subset (k!).  Joerg Arndt, Dec 09 2012
a(n) = Integral_{0..infinity} (x+1)^n*exp(x) dx.  Gerald McGarvey, Oct 19 2006
From Tom Copeland, Nov 01 2007, Dec 10 2007: (Start) Act on 1/(1x) with 1/(1xDx) = sum(j=0,1,...) (xDx)^j = sum(j=0,1,...) x^j*D^j*x^j = sum(j=0,1,...) 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] = (1D)^(1) x^n = (1)^n * n! Lag(n,x,1n) = sum(j=0,...,n) Binom(n,j)*j!*x^(nj) = 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/(1xDx). (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(n1). The set of integer sequences satisfying the difference divisibility property forms a ring with termwise operations of addition and multiplication.
Recurrence relations: a(0) = 1, a(n) = (n1)*(a(n1) + a(n2)) + 2, for n >= 1. a(0) = 1, a(1) = 2, a(n) = (n+1)*a(n1)  (n1)*a(n2) 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/(11/(21/(32/(4...(n1)/(n+1))))), n >= 2.
Lim n > infinity a(n)/n! = e = 1/(11/(21/(32/(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(n1)  (n1)*a(n2), which yield series acceleration formulas for e/r! that involve the PoissonCharlier 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/(1x)^2 + x^2*A'(x)/(1x).  Paul D. Hanna, Sep 03 2008
From Paul Barry, Nov 27 2009: (Start)
G.f.: 1/(12xx^2/(14x4x^2/(16x9x^2/(18x16x^2/(110x25x^2/(1... (continued fraction);
G.f.: 1/(1xx/(1x/(1x2x/(12x/(1x3x/(13x/(1x4x/(14x/(1x5x/(15x/(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/(1x))/(1x), 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, 2step).  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, 3rd kind 3step).  Sergei N. Gladkovskii, Nov 16 2012
G.f.: 1/(1x)/Q(0), where Q(k)= 1  x/(1x)*(k+1)/(1  x/(1x)*(k+1)/Q(k+1)); (continued fraction).  Sergei N. Gladkovskii, May 19 2013
G.f.: 2/(1x)/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)/(22*x) = Q(0)/(22*x), where B(x) be g.f. A006183, Q(k)= 1 + 1/(1  x*(k+1)/(x*(k+1) + (1x)/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.: exp(x)/(1x)= (1 12*x/(Q(0)+6*x3*x^2))/(1x), where Q(k) = 2*(4*k+1)*(32*k^2+16*k+x^26)  x^4*(4*k1)*(4*k+7)/Q(k+1) ; (continued fraction).  Sergei N. Gladkovskii, Nov 18 2013
G.f.: conjecture: T(0)/(12*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


EXAMPLE

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 3set 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)


MAPLE

A000522 := n>add(n!/k!, k=0..n);
restart: G(x):=exp(x)/(1x): f[0]:=G(x): for n from 1 to 26 do f[n]:=diff(f[n1], x) od: x:=0: seq(f[n], n=0..20);
# Zerinvary Lajos, Apr 03 2009
G:=exp(z)/(1z): 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/(1x))/(1x), x=0, 20); # Mark van Hoeij, Nov 07 2011


MATHEMATICA

Table[FunctionExpand[Gamma[n, 1]*E], {n, 1, 24}]
s=2; lst={1, s}; Do[s += s++ n; AppendTo[lst, s], {n, 5!}]; lst (* Vladimir Joseph Stephan Orlovsky, Oct 23 2008 *)
nn = 20; Accumulate[Table[1/k!, {k, 0, nn}]] Range[0, nn]! (* Jan Mangaldan, Apr 21 2013 *)


PROG

(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)=floor(exp(1)*(n)!  1/(n +1 ))  Alexander R. Povolotsky, Nov 05 2007
(PARI) {a(n)=local(A=1+x+x*O(x^n)); for(i=1, n, A=1/(1x)^2+x^2*deriv(A)/(1x)); 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 */
(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
(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(n1, j, t+(j==i)) for j in xrange(0, t+2) )
def a(n): return b(n, 0, 0)
v000522=[a(n) for n in xrange(0, 33)]
print v000522
# Joerg Arndt, May 11 2013


CROSSREFS

Cf. A010844, A010845, A038159, A002627, A006231, A000166, A072453, A072456, A008290, A007526, A054091, A073591, A001339, A082030, A095000, A095177, A142992, A108625, A143007, A064383, A064384, A124779, A121579, A158359, A158821, A195254, A222637  A222639.
Average of nth row of triangle in A007526.
Row sums of A008279.
First differences give A001339. Second differences give A001340.
Partial sums are in A001338, A002104.
a(n)=sum(A094816(n, k), k=0..n), n>=0 (row sums of PoissonCharlier coefficient matrix).
A row of the array in A144502.
Sequence in context: A131178 A003149 A027046 * A182290 A007469 A091139
Adjacent sequences: A000519 A000520 A000521 * A000523 A000524 A000525


KEYWORD

nonn,easy,nice,changed


AUTHOR

N. J. A. Sloane


EXTENSIONS

Additional comments from Michael Somos


STATUS

approved



