|
%I M1497 N0589 #476 Apr 14 2024 14:00:32
%S 1,2,5,16,65,326,1957,13700,109601,986410,9864101,108505112,
%T 1302061345,16926797486,236975164805,3554627472076,56874039553217,
%U 966858672404690,17403456103284421,330665665962404000,6613313319248080001,138879579704209680022,3055350753492612960485,70273067330330098091156
%N 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!.
%C Total number of permutations of all subsets of an n-set.
%C Also the number of one-to-one sequences that can be formed from n distinct objects.
%C 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.
%C Related to number of operations of addition and multiplication to evaluate a determinant of order n by cofactor expansion - see A026243.
%C 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
%C 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
%C a(n) is the permanent of the n X n matrix with 2s on the diagonal and 1s elsewhere. - Yuval Dekel, Nov 01 2003
%C (A000166 + this_sequence)/2 = A009179, (A000166 - this_sequence)/2 = A009628.
%C 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
%C Number of {12,12*,21*}- and {12,12*,2*1}-avoiding signed permutations in the hyperoctahedral group.
%C a(n) = b such that Integral_{x=0..1} x^n*exp(-x) dx = a-b*exp(-1). - _Sébastien Dumortier_, Mar 05 2005
%C 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
%C 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
%C 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
%C Unreduced numerators of partial sums of the Taylor series for e. - _Jonathan Sondow_, Aug 18 2006
%C 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
%C 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
%C 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
%C 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
%C Equals row sums of triangle A158359(unsigned). - _Gary W. Adamson_, Mar 17 2009
%C Equals eigensequence of triangle A158821. - _Gary W. Adamson_, Mar 30 2009
%C 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
%C 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
%C 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
%C 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
%C 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
%C a(n) = p(n,1) = q(n,1), where p and q are polynomials defined at A248664 and A248669. - _Clark Kimberling_, Oct 11 2014
%C 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
%C As the row sums of A008279, Motzkin uses the abbreviated notation $n_<^\Sigma$ for a(n).
%C 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
%C 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
%C 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
%C From _Peter Bala_, Apr 03 2022: (Start)
%C 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)
%D L. Comtet, Advanced Combinatorics, Reidel, 1974, p. 75, Problem 9.
%D J.-M. De Koninck, Ces nombres qui nous fascinent, Entry 65, p. 23, Ellipses, Paris 2008.
%D J. M. Gandhi, On logarithmic numbers, Math. Student, 31 (1963), 73-83.
%D J. Riordan, An Introduction to Combinatorial Analysis, Wiley, 1958, p. 16.
%D D. Singh, The numbers L(m,n) and their relations with prepared Bernoulli and Eulerian numbers, Math. Student, 20 (1952), 66-70.
%D N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H Alois P. Heinz, <a href="/A000522/b000522.txt">Table of n, a(n) for n = 0..450</a> (first 101 terms from T. D. Noe)
%H J. L. Adams, <a href="/A000522/a000522_1.pdf">Conceptual Blockbusting: A Guide to Better Ideas</a>, Freeman, San Francisco, 1974. [Annotated scans of pages 69 and 70 only]
%H F. Ardila, F. Rincón, and L. Williams, <a href="http://arxiv.org/abs/1308.2698">Positroids and non-crossing partitions</a>, arXiv preprint arXiv:1308.2698 [math.CO], 2013.
%H F. Ardila, F. Rincón, and L. Williams, <a href="https://doi.org/10.46298/dmtcs.2431">Positroids, non-crossing partitions, and positively oriented matroids</a>, in FPSAC 2014, Chicago, USA; Discrete Mathematics and Theoretical Computer Science (DMTCS) Proceedings, 2014, 555-666.
%H Juan S. Auli and Sergi Elizalde, <a href="https://arxiv.org/abs/1906.07365">Consecutive patterns in inversion sequences II: avoiding patterns of relations</a>, arXiv:1906.07365 [math.CO], 2019. See Table 1, p. 6.
%H Roland Bacher, <a href="https://doi.org/10.37236/2522">Counting Packings of Generic Subsets in Finite Groups</a>, Electr. J. Combinatorics, 19 (2012), #P7.
%H C. Banderier, M. Bousquet-Mélou, A. Denise, P. Flajolet, D. Gardy and D. Gouyou-Beauchamps, <a href="http://dx.doi.org/10.1016/S0012-365X(01)00250-3">Generating functions for generating trees</a>, Discrete Mathematics 246(1-3), March 2002, pp. 29-55.
%H E. Barcucci, A. Del Lungo and R. Pinzani, <a href="http://dx.doi.org/10.1016/0304-3975(95)00199-9">"Deco" polyominoes, permutations and random generation</a>, Theoretical Computer Science, 159, 1996, 29-42.
%H Paul Barry, <a href="https://arxiv.org/abs/2107.14278">Series reversion with Jacobi and Thron continued fractions</a>, arXiv:2107.14278 [math.NT], 2021.
%H Lisa Berry, Stefan Forcey, Maria Ronco, and Patrick Showers, <a href="https://arxiv.org/abs/1608.08546">Species substitution, graph suspension, and graded hopf algebras of painted tree polytopes</a>, arXiv:1608.08546 [math.CO], 2016-2019.
%H Louis J. Billera, Sara C. Billey, and Vasu Tewari, <a href="https://arxiv.org/abs/1806.02943">Boolean product polynomials and Schur-positivity</a>, arXiv:1806.02943 [math.CO], 2018.
%H P. Blasiak, A. Horzela, K. A. Penson, G.H.E. Duchamp and A. I. Solomon, <a href="http://arXiv.org/abs/quant-ph/0501155">Boson normal ordering via substitutions and Sheffer-type polynomials</a>, arXiv:quant-ph/0501155, 2005.
%H E. Biondi, L. Divieti, and G. Guardabassi, <a href="http://dx.doi.org/10.4153/CJM-1970-003-9">Counting paths, circuits, chains and cycles in graphs: A unified approach</a>, Canad. J. Math. 22 1970 22-35. See Table I.
%H Olivier Bodini, Antoine Genitrini, and Mehdi Naima, <a href="https://arxiv.org/abs/1808.08376">Ranked Schröder Trees</a>, arXiv:1808.08376 [cs.DS], 2018.
%H Adam Brandenburger, <a href="http://adambrandenburger.com/wp/wp-content/uploads/2018/03/strategy-from-combination-optimized-03-08-18.pdf">The Strategist: Strategy from Combination</a>, 2018.
%H J. Brzozowski and M. Szykula, <a href="http://arxiv.org/abs/1401.0157">Large Aperiodic Semigroups</a>, arXiv preprint arXiv:1401.0157 [cs.FL], 2013.
%H P. J. Cameron, <a href="http://www.cs.uwaterloo.ca/journals/JIS/VOL3/groups.html">Sequences realized by oligomorphic permutation groups</a>, J. Integ. Seqs. Vol. 3 (2000), #00.1.5.
%H Jean Cardinal, Arturo Merino, and Torsten Mütze, <a href="https://arxiv.org/abs/2106.16204">Combinatorial generation via permutation languages. IV. Elimination trees</a>, arXiv:2106.16204 [cs.DM], 2021.
%H CombOS - Combinatorial Object Server, <a href="http://combos.org/elim">Generate partial permutations</a>
%H Dan Daly and Lara Pudwell, <a href="http://faculty.valpo.edu/lpudwell/slides/sandiego2013.pdf">Pattern avoidance in rook monoids</a>, Special Session on Patterns in Permutations and Words, Joint Mathematics Meetings, 2013.
%H Philip Feinsilver and John McSorley, <a href="http://dx.doi.org/10.1155/2011/539030">Zeons, Permanents, the Johnson Scheme, and Generalized Derangements</a>, International Journal of Combinatorics, Volume 2011, Article ID 539030, 29 pages.
%H P. Flajolet and R. Sedgewick, <a href="http://algo.inria.fr/flajolet/Publications/books.html">Analytic Combinatorics</a>, 2009; see page 114.
%H Stefan Forcey, Aaron Lauve and Frank Sottile, <a href="http://dx.doi.org/10.1007/s00026-012-0170-5">Cofree compositions of coalgebras</a>, Annals of Combinatorics 17 (1) pp. 105-130 March, 2013.
%H Stefan Forcey, M. Ronco, and P. Showers, <a href="https://arxiv.org/abs/1608.08546">Polytopes and algebras of grafted trees: Stellohedra</a>, arXiv preprint arXiv:1608.08546 [math.CO], 2016.
%H Bernd Gaertner, Walter D. Jr. Morris and Leo Ruest, <a href="http://www.inf.ethz.ch/personal/gaertner/texts/own_work/ipco.pdf">Unique Sink Orientations of Grids</a>, Algorithmica, Volume 51, Number 2 / June 2008.
%H J. M. Gandhi, <a href="/A002741/a002741.pdf">On logarithmic numbers</a>, Math. Student, 31 (1963), 73-83. [Annotated scanned copy]
%H Xing Gao and William F. Keigher, <a href="https://doi.org/10.1080/00927872.2016.1226885">Interlacing of Hurwitz series</a>, Communications in Algebra, 45:5 (2017), 2163-2185, DOI: 10.1080/00927872.2016.1226885. See Ex. 2.16.
%H Jan Geuenich, <a href="https://arxiv.org/abs/1803.10707">Tilting modules for the Auslander algebra of K[x]/(xn)</a>, arXiv:1803.10707 [math.RT], 2018.
%H Henry W. Gould, <a href="/A003099/a003099_1.pdf">Letter to N. J. A. Sloane, Nov 1973, and various attachments</a>.
%H R. K. Guy, <a href="/A006231/a006231.pdf">Letter to N. J. A. Sloane, 1977</a>
%H Lorenz Halbeisen and Norbert Hungerbuehler, Number theoretic aspects of a combinatorial function, Notes on Number Theory and Discrete Mathematics 5 (1999) 138-150. (<a href="http://math.berkeley.edu/~halbeis/publications/psf/seq.ps">ps</a>, <a href="http://math.berkeley.edu/~halbeis/publications/pdf/seq.pdf">pdf</a>)
%H Lorenz Halbeisen and Saharon Shelah, <a href="http://arxiv.org/abs/math/9308220v1">Consequences of arithmetic for set theory</a>, The Journal of Symbolic Logic, vol. 59 (1994), pp. 30-40.
%H M. Hassani, <a href="https://arxiv.org/abs/math/0606613">Counting and computing by e</a>, arXiv:math/0606613 [math.CO], 2006.
%H INRIA Algorithms Project, <a href="http://ecs.inria.fr/services/structure?nbr=35">Encyclopedia of Combinatorial Structures 35</a>
%H M. Janjic, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL12/Janjic/janjic22.html">Some classes of numbers and derivatives</a>, JIS 12 (2009) 09.8.3.
%H F. Johansson et al, MathOverflow, <a href="https://mathoverflow.net/questions/366663/is-sum-k-1n-fracn-1k-1-composite-for-n-geq-4">Is Sum_{k=1..n} (n-1)!/(k-1)! composite for n >= 4?</a>
%H Michael Joswig, Max Klimm, and Sylvain Spitz, <a href="https://arxiv.org/abs/2108.00979">Generalized permutahedra and optimal auctions</a>, arXiv:2108.00979 [math.MG], 2021.
%H Marin Knežević, Vedran Krčadinac, and Lucija Relić, <a href="https://arxiv.org/abs/2012.15307">Matrix products of binomial coefficients and unsigned Stirling numbers</a>, arXiv:2012.15307 [math.CO], 2020.
%H Germain Kreweras, <a href="http://archive.numdam.org/ARCHIVE/MSH/MSH_1963__3_/MSH_1963__3__31_0/MSH_1963__3__31_0.pdf">Une dualité élémentaire souvent utile dans les problèmes combinatoires</a>, Mathématiques et Sciences Humaines 3 (1963): 31-41.
%H J. W. Layman, <a href="http://www.cs.uwaterloo.ca/journals/JIS/VOL4/LAYMAN/hankel.html">The Hankel Transform and Some of its Properties</a>, J. Integer Sequences, 4 (2001), #01.1.5.
%H F. Luca and I. E. Shparlinski, <a href="https://doi.org/10.1017/S0017089507003734">On the squarefree parts of floor(e*n!)</a>, Glasgow Math. J., 49 (2007), 391-403.
%H T. Manneville and V. Pilaud, <a href="http://arxiv.org/abs/1501.07152">Compatibility fans for graphical nested complexes</a>, arXiv preprint arXiv:1501.07152 [math.CO], 2015.
%H T. Mansour and J. West, <a href="https://arxiv.org/abs/math/0207204">Avoiding 2-letter signed patterns</a>, arXiv:math/0207204 [math.CO], 2002.
%H T. S. Motzkin, <a href="/A000262/a000262.pdf">Sorting numbers for cylinders and other classification numbers</a>, in Combinatorics, Proc. Symp. Pure Math. 19, AMS, 1971, pp. 167-176. [Annotated, scanned copy]
%H Emanuele Munarini, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL23/Munarini2/muna24.html">Combinatorial Identities for the Tricomi Polynomials</a>, J. Int. Seq., Vol. 23 (2020), Article 20.9.4.
%H Emanuele Munarini, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL26/Munarini/muna25.html">Two-Parameter Identities for q-Appell Polynomials</a>, Journal of Integer Sequences, Vol. 26 (2023), Article 23.3.1.
%H R. Ondrejka, <a href="/A000522/a000522.pdf">Letter to N. J. A. Sloane, May 15 1976</a>
%H Alexsandar Petojevic, <a href="http://www.cs.uwaterloo.ca/journals/JIS/VOL5/Petojevic/petojevic5.html">The Function vM_m(s; a; z) and Some Well-Known Sequences</a>, Journal of Integer Sequences, Vol. 5 (2002), Article 02.1.7
%H Robert A. Proctor, <a href="http://arxiv.org/abs/math/0606404">Let's Expand Rota's Twelvefold Way For Counting Partitions!</a>, arXiv:math/0606404 [math.CO], 2006-2007.
%H D. Singh, <a href="/A002627/a002627.pdf">The numbers L(m,n) and their relations with prepared Bernoulli and Eulerian numbers</a>, Math. Student, 20 (1952), 66-70. [Annotated scanned copy]
%H J. Sondow, <a href="http://arxiv.org/abs/0704.1282">A geometric proof that e is irrational and a new measure of its irrationality</a>, Amer. Math. Monthly 113 (2006) 637-641. arXiv:0704.1282 [math.HO], 2007-2010.
%H J. Sondow, <a href="http://home.earthlink.net/~jsondow/PrimesAndE.pdf">The Taylor series for e and the primes 2, 5, 13, 37, 463, ...: a surprising connection</a>
%H J. Sondow and K. Schalm, <a href="http://arxiv.org/abs/0709.0671">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</a>, arXiv:0709.0671 [math.NT], 2006-2009; Gems in Experimental Mathematics (T. Amdeberhan, L. A. Medina, and V. H. Moll, eds.), Contemporary Mathematics, vol. 517, Amer. Math. Soc., Providence, RI, 2010.
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/BinomialSums.html">Binomial Sums</a>
%H <a href="/index/Lo#logarithmic">Index entries for sequences related to logarithmic numbers</a>
%H <a href="/index/Par#partN">Index entries for related partition-counting sequences</a>
%H <a href="/index/Fa#factorial">Index entries for sequences related to factorial numbers</a>
%F a(n) = n*a(n-1) + 1, a(0) = 1.
%F a(n) = A007526(n-1) + 1.
%F a(n) = A061354(n)*A093101(n).
%F a(n) = n! * Sum_{k=0..n} 1/k! = n! * (e - Sum_{k>=n+1} 1/k!). - _Michael Somos_, Mar 26 1999
%F a(0) = 1; for n > 0, a(n) = floor(e*n!).
%F E.g.f.: exp(x)/(1-x).
%F 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
%F a(n) = floor(2/(n+1))*A009578(n+1)-1. - _Emeric Deutsch_, Oct 24 2001
%F Integral representation as n-th moment of a nonnegative function on a positive half-axis: a(n) = e*Integral_{x=0..infinity} (x^n*e^(-x)*Heaviside(x-1). - _Karol A. Penson_, Oct 01 2001
%F 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
%F 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
%F a(n) = Sum_{k=0..n} A008290(n, k)*2^k. - _Philippe Deléham_, Dec 12 2003
%F a(n) = Sum_{k=0..n} A046716(n, k). - _Philippe Deléham_, Jun 12 2004
%F 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
%F a(n) = Sum_{k=0..n} P(n, k). - _Ross La Haye_, Aug 28 2005
%F Given g.f. A(x), then g.f. A059115 = A(x/(1-x)). - _Michael Somos_, Aug 03 2006
%F a(n) = 1 + n + n*(n-1) + n*(n-1)*(n-2) + ... + n!. - _Jonathan Sondow_, Aug 18 2006
%F 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
%F a(n) = Integral_{x>=0} (x+1)^n*e^(-x) dx. - _Gerald McGarvey_, Oct 19 2006
%F 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
%F From _Tom Copeland_, Nov 01 2007, Dec 10 2007: (Start)
%F 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.
%F 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).
%F (End)
%F From _Peter Bala_, Jul 15 2008: (Start)
%F a(n) = n!*e - 1/(n + 1/(n+1 + 2/(n+2 + 3/(n+3 + ...)))).
%F 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.
%F 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.
%F 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.
%F 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.
%F Limit_{n->infinity} 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).
%F 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).
%F For the corresponding results for the constants log(2), zeta(2) and zeta(3) refer to A142992, A108625 and A143007 respectively.
%F (End)
%F G.f. satisfies: A(x) = 1/(1-x)^2 + x^2*A'(x)/(1-x). - _Paul D. Hanna_, Sep 03 2008
%F From _Paul Barry_, Nov 27 2009: (Start)
%F 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);
%F 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).
%F (End)
%F O.g.f.: Sum_{n>=0} (n+2)^n*x^n/(1 + (n+1)*x)^(n+1). - _Paul D. Hanna_, Sep 19 2011
%F 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
%F 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
%F 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
%F 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
%F 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
%F 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
%F 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
%F 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
%F 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
%F 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
%F From _Peter Bala_, Jul 29 2014: (Start)
%F 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.
%F a(n) = n!*e - e*( Sum_{k >= 0} (-1)^k/((n + k + 1)*k!) ).
%F (End)
%F a(n) = hypergeometric_U(1, n+2, 1). - _Peter Luschny_, Nov 26 2014
%F a(n) ~ exp(1-n)*n^(n-1/2)*sqrt(2*Pi). - _Vladimir Reshetnikov_, Oct 27 2015
%F a(n) = A038155(n+2)/A000217(n+1). - _Anton Zakharov_, Sep 08 2016
%F a(n) = round(exp(1)*n!), n > 1 - _Simon Plouffe_, Jul 28 2020
%F a(n) = KummerU(-n, -n, 1). - _Peter Luschny_, May 10 2022
%F a(n) = (e/(2*Pi))*Integral_{x=-oo..oo} (n+1+i*x)!/(1+i*x) dx. - _David Ulgenes_, Apr 18 2023
%F Sum_{i=0..n} (-1)^(n-i) * binomial(n, i) * a(i) = n!. - _Werner Schulte_, Apr 03 2024
%e G.f. = 1 + 2*x + 5*x^2 + 16*x^3 + 65*x^4 + 326*x^5 + 1957*x^6 + 13700*x^7 + ...
%e With two objects we can form 5 sequences: (), (a), (b), (a,b), (b,a), so a(2) = 5.
%e From _Joerg Arndt_, Dec 09 2012: (Start)
%e The 16 arrangements of the 3-set and their RGS (dots denote zeros) are
%e [ #] RGS perm. of subset
%e [ 1] [ . . . ] [ ]
%e [ 2] [ . . 1 ] [ 3 ]
%e [ 3] [ . 1 . ] [ 2 ]
%e [ 4] [ . 1 1 ] [ 2 3 ]
%e [ 5] [ . 1 2 ] [ 3 2 ]
%e [ 6] [ 1 . . ] [ 1 ]
%e [ 7] [ 1 . 1 ] [ 1 3 ]
%e [ 8] [ 1 . 2 ] [ 3 1 ]
%e [ 9] [ 1 1 . ] [ 1 2 ]
%e [10] [ 1 1 1 ] [ 1 2 3 ]
%e [11] [ 1 1 2 ] [ 1 3 2 ]
%e [12] [ 1 1 3 ] [ 2 3 1 ]
%e [13] [ 1 2 . ] [ 2 1 ]
%e [14] [ 1 2 1 ] [ 2 1 3 ]
%e [15] [ 1 2 2 ] [ 3 1 2 ]
%e [16] [ 1 2 3 ] [ 3 2 1 ]
%e (End)
%p a(n):= exp(1)*int(x^n*exp(-x)*Heaviside(x-1), x=0..infinity); # _Karol A. Penson_, Oct 01 2001
%p A000522 := n->add(n!/k!,k=0..n);
%p 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);
%p # _Zerinvary Lajos_, Apr 03 2009
%p G:=exp(z)/(1-z): Gser:=series(G,z=0,21):
%p for n from 0 to 20 do a(n):=n!*coeff(Gser,z,n): end do
%p # _Paul Weisenhorn_, May 30 2010
%p k := 1; series(hypergeom([1,k],[],x/(1-x))/(1-x), x=0, 20); # _Mark van Hoeij_, Nov 07 2011
%p # one more Maple program:
%p a:= proc(n) option remember;
%p `if`(n<0, 0, 1+n*a(n-1))
%p end:
%p seq(a(n), n=0..23); # _Alois P. Heinz_, Sep 13 2019
%p seq(simplify(KummerU(-n, -n, 1)), n = 0..23); # _Peter Luschny_, May 10 2022
%t Table[FunctionExpand[Gamma[n + 1, 1]*E], {n, 0, 24}]
%t nn = 20; Accumulate[Table[1/k!, {k, 0, nn}]] Range[0, nn]! (* _Jan Mangaldan_, Apr 21 2013 *)
%t FoldList[#1*#2 + #2 &, 0, Range@ 23] + 1 (* or *)
%t f[n_] := Floor[E*n!]; f[0] = 1; Array[f, 20, 0] (* _Robert G. Wilson v_, Feb 13 2015 *)
%t RecurrenceTable[{a[n + 1] == (n + 1) a[n] + 1, a[0] == 1}, a, {n, 0, 12}] (* _Emanuele Munarini_, Apr 27 2017 *)
%t nxt[{n_,a_}]:={n+1,a(n+1)+1}; NestList[nxt,{0,1},30][[All,2]] (* _Harvey P. Dale_, Jan 29 2023 *)
%o (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 */
%o (PARI) {a(n) = if( n<0, 0, n! * polcoeff( exp( x +x * O(x^n)) / (1 - x), n))}; /* _Michael Somos_, Mar 06 2004 */
%o (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
%o (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_ */
%o (PARI) a(n)=sum(k=0,n,binomial(n,k)*k!); \\ _Joerg Arndt_, Dec 14 2014
%o (Haskell)
%o import Data.List (subsequences, permutations)
%o a000522 = length . choices . enumFromTo 1 where
%o choices = concat . map permutations . subsequences
%o -- _Reinhard Zumkeller_, Feb 21 2012, Oct 25 2010
%o (Sage)
%o # program adapted from _Alois P. Heinz_'s Maple code in A022493
%o @CachedFunction
%o def b(n, i, t):
%o if n <= 1:
%o return 1
%o return sum(b(n - 1, j, t + (j == i)) for j in range(t + 2))
%o def a(n):
%o return b(n, 0, 0)
%o v000522 = [a(n) for n in range(33)]
%o print(v000522)
%o # _Joerg Arndt_, May 11 2013
%o (Magma) [1] cat [n eq 1 select (n+1) else n*Self(n-1)+1: n in [1..25]]; // _Vincenzo Librandi_, Feb 15 2015
%o (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 */
%Y 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.
%Y Average of n-th row of triangle in A068424 [Corrected by _N. J. A. Sloane_, Feb 29 2024].
%Y Row sums of A008279 and A094816.
%Y First differences give A001339. Second differences give A001340.
%Y Partial sums are in A001338, A002104.
%Y A row of the array in A144502.
%Y See also A370973, Nearest integer to e*n!.
%K nonn,easy,nice,changed
%O 0,2
%A _N. J. A. Sloane_
%E Additional comments from _Michael Somos_
| 