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 36 results. Next

A000166 Subfactorial or rencontres numbers, or derangements: number of permutations of n elements with no fixed points.

Original entry on oeis.org

1, 0, 1, 2, 9, 44, 265, 1854, 14833, 133496, 1334961, 14684570, 176214841, 2290792932, 32071101049, 481066515734, 7697064251745, 130850092279664, 2355301661033953, 44750731559645106, 895014631192902121, 18795307255050944540, 413496759611120779881, 9510425471055777937262
Offset: 0

Views

Author

N. J. A. Sloane

Keywords

Comments

Euler (1809) not only gives the first ten or so terms of the sequence, he also proves both recurrences a(n) = (n-1)*(a(n-1) + a(n-2)) and a(n) = n*a(n-1) + (-1)^n.
a(n) is the permanent of the matrix with 0 on the diagonal and 1 elsewhere. - Yuval Dekel, Nov 01 2003
a(n) is the number of desarrangements of length n. A desarrangement of length n is a permutation p of {1,2,...,n} for which the smallest of all the ascents of p (taken to be n if there are no ascents) is even. Example: a(3) = 2 because we have 213 and 312 (smallest ascents at i = 2). See the J. Désarménien link and the Bona reference (p. 118). - Emeric Deutsch, Dec 28 2007
a(n) is the number of deco polyominoes of height n and having in the last column an even number of cells. A deco polyomino is a directed column-convex polyomino in which the height, measured along the diagonal, is attained only in the last column. - Emeric Deutsch, Dec 28 2007
Attributed to Nicholas Bernoulli in connection with a probability problem that he presented. See Problem #15, p. 494, in "History of Mathematics" by David M. Burton, 6th edition. - Mohammad K. Azarian, Feb 25 2008
a(n) is the number of permutations p of {1,2,...,n} with p(1)!=1 and having no right-to-left minima in consecutive positions. Example a(3) = 2 because we have 231 and 321. - Emeric Deutsch, Mar 12 2008
a(n) is the number of permutations p of {1,2,...,n} with p(n)! = n and having no left to right maxima in consecutive positions. Example a(3) = 2 because we have 312 and 321. - Emeric Deutsch, Mar 12 2008
Number of wedged (n-1)-spheres in the homotopy type of the Boolean complex of the complete graph K_n. - Bridget Tenner, Jun 04 2008
The only prime number in the sequence is 2. - Howard Berman (howard_berman(AT)hotmail.com), Nov 08 2008
From Emeric Deutsch, Apr 02 2009: (Start)
a(n) is the number of permutations of {1,2,...,n} having exactly one small ascent. A small ascent in a permutation (p_1,p_2,...,p_n) is a position i such that p_{i+1} - p_i = 1. (Example: a(3) = 2 because we have 312 and 231; see the Charalambides reference, pp. 176-180.) [See also David, Kendall and Barton, p. 263. - N. J. A. Sloane, Apr 11 2014]
a(n) is the number of permutations of {1,2,...,n} having exactly one small descent. A small descent in a permutation (p_1,p_2,...,p_n) is a position i such that p_i - p_{i+1} = 1. (Example: a(3)=2 because we have 132 and 213.) (End)
For n > 2, a(n) + a(n-1) = A000255(n-1); where A000255 = (1, 1, 3, 11, 53, ...). - Gary W. Adamson, Apr 16 2009
Connection to A002469 (game of mousetrap with n cards): A002469(n) = (n-2)*A000255(n-1) + A000166(n). (Cf. triangle A159610.) - Gary W. Adamson, Apr 17 2009
From Emeric Deutsch, Jul 18 2009: (Start)
a(n) is the sum of the values of the largest fixed points of all non-derangements of length n-1. Example: a(4)=9 because the non-derangements of length 3 are 123, 132, 213, and 321, having largest fixed points 3, 1, 3, and 2, respectively.
a(n) is the number of non-derangements of length n+1 for which the difference between the largest and smallest fixed point is 2. Example: a(3) = 2 because we have 1'43'2 and 32'14'; a(4) = 9 because we have 1'23'54, 1'43'52, 1'53'24, 52'34'1, 52'14'3, 32'54'1, 213'45', 243'15', and 413'25' (the extreme fixed points are marked).
(End)
a(n), n >= 1, is also the number of unordered necklaces with n beads, labeled differently from 1 to n, where each necklace has >= 2 beads. This produces the M2 multinomial formula involving partitions without part 1 given below. Because M2(p) counts the permutations with cycle structure given by partition p, this formula gives the number of permutations without fixed points (no 1-cycles), i.e., the derangements, hence the subfactorials with their recurrence relation and inputs. Each necklace with no beads is assumed to contribute a factor 1 in the counting, hence a(0)=1. This comment derives from a family of recurrences found by Malin Sjodahl for a combinatorial problem for certain quark and gluon diagrams (Feb 27 2010). - Wolfdieter Lang, Jun 01 2010
From Emeric Deutsch, Sep 06 2010: (Start)
a(n) is the number of permutations of {1,2,...,n, n+1} starting with 1 and having no successions. A succession in a permutation (p_1,p_2,...,p_n) is a position i such that p_{i+1} - p_i = 1. Example: a(3)=2 because we have 1324 and 1432.
a(n) is the number of permutations of {1,2,...,n} that do not start with 1 and have no successions. A succession in a permutation (p_1,p_2,...,p_n) is a position i such that p_{i+1} - p_i = 1. Example: a(3)=2 because we have 213 and 321.
(End)
Increasing colored 1-2 trees with choice of two colors for the rightmost branch of nonleave except on the leftmost path, there is no vertex of outdegree one on the leftmost path. - Wenjin Woan, May 23 2011
a(n) is the number of zeros in n-th row of the triangle in A170942, n > 0. - Reinhard Zumkeller, Mar 29 2012
a(n) is the maximal number of totally mixed Nash equilibria in games of n players, each with 2 pure options. - Raimundas Vidunas, Jan 22 2014
Convolution of sequence A135799 with the sequence generated by 1+x^2/(2*x+1). - Thomas Baruchel, Jan 08 2016
The number of interior lattice points of the subpolytope of the n-dimensional permutohedron whose vertices correspond to permutations avoiding 132 and 312. - Robert Davis, Oct 05 2016
Consider n circles of different radii, where each circle is either put inside some bigger circle or contains a smaller circle inside it (no common points are allowed). Then a(n) gives the number of such combinations. - Anton Zakharov, Oct 12 2016
If we partition the permutations of [n+1] in A000240 according to their starting digit, we will get (n+1) equinumerous classes each of size a(n), i.e., A000240(n+1) = (n+1)*a(n), hence a(n) is the size of each class of permutations of [n+1] in A000240. For example, for n = 4 we have 45 = 5*9. - Enrique Navarrete, Jan 10 2017
Call d_n1 the permutations of [n] that have the substring n1 but no substring in {12,23,...,(n-1)n}. If we partition them according to their starting digit, we will get (n-1) equinumerous classes each of size A000166(n-2) (the class starting with the digit 1 is empty since we must have the substring n1). Hence d_n1 = (n-1)*A000166(n-2) and A000166(n-2) is the size of each nonempty class in d_n1. For example, d_71 = 6*44 = 264, so there are 264 permutations in d_71 distributed in 6 nonempty classes of size A000166(5) = 44. (To get permutations in d_n1 recursively from more basic ones see the link "Forbidden Patterns" below.) - Enrique Navarrete, Jan 15 2017
Also the number of maximum matchings and minimum edge covers in the n-crown graph. - Eric W. Weisstein, Jun 14 and Dec 24 2017
The sequence a(n) taken modulo a positive integer k is periodic with exact period dividing k when k is even and dividing 2*k when k is odd. This follows from the congruence a(n+k) = (-1)^k*a(n) (mod k) for all n and k, which in turn is easily proved by induction making use of the recurrence a(n) = n*a(n-1) + (-1)^n. - Peter Bala, Nov 21 2017
a(n) is the number of distinct possible solutions for a directed, no self loop containing graph (not necessarily connected) that has n vertices, and each vertex has an in- and out-degree of exactly 1. - Patrik Holopainen, Sep 18 2018
a(n) is the dimension of the kernel of the random-to-top and random-to-random shuffling operators over a collection of n objects (in a vector space of size n!), as noticed by M. Wachs and V. Reiner. See the Reiner, Saliola and Welker reference below. - Nadia Lafreniere, Jul 18 2019
a(n) is the number of distinct permutations for a Secret Santa gift exchange with n participants. - Patrik Holopainen, Dec 30 2019
a(2*n+1) is even. More generally, a(m*n+1) is divisible by m*n, which follows from a(n+1) = n*(a(n) + a(n-1)) = n*A000255(n-1) for n >= 1. a(2*n) is odd; in fact, a(2*n) == 1 (mod 8). Other divisibility properties include a(6*n) == 1 (mod 24), a(9*n+4) == a(9*n+7) == 0 (mod 9), a(10*n) == 1 (mod 40), a(11*n+5) == 0 (mod 11) and a(13*n+8 ) == 0 (mod 13). - Peter Bala, Apr 05 2022
Conjecture: a(n) with n > 2 is a perfect power only for n = 4 with a(4) = 3^2. This has been verified for n <= 1000. - Zhi-Wei Sun, Jan 09 2025

Examples

			a(2) = 1, a(3) = 2 and a(4) = 9 since the possibilities are {BA}, {BCA, CAB} and {BADC, BCDA, BDAC, CADB, CDAB, CDBA, DABC, DCAB, DCBA}. - _Henry Bottomley_, Jan 17 2001
The Boolean complex of the complete graph K_4 is homotopy equivalent to the wedge of 9 3-spheres.
Necklace problem for n = 6: partitions without part 1 and M2 numbers for n = 6: there are A002865(6) = 4 such partitions, namely (6), (2,4), (3^2) and (2^3) in A-St order with the M2 numbers 5!, 90, 40 and 15, respectively, adding up to 265 = a(6). This corresponds to 1 necklace with 6 beads, two necklaces with 2 and 4 beads respectively, two necklaces with 3 beads each and three necklaces with 2 beads each. - _Wolfdieter Lang_, Jun 01 2010
G.f. = 1 + x^2 + 9*x^3 + 44*x^4 + 265*x^5 + 1854*x^6 + 14833*x^7 + 133496*x^8 + ...

References

  • U. Abel, Some new identities for derangement numbers, Fib. Q., 56:4 (2018), 313-318.
  • M. Bona, Combinatorics of Permutations, Chapman & Hall/CRC, Boca Raton, Florida, 2004.
  • Miklos Bona, editor, Handbook of Enumerative Combinatorics, CRC Press, 2015, page 32.
  • R. A. Brualdi and H. J. Ryser: Combinatorial Matrix Theory, 1992, Section 7.2, p. 202.
  • Ch. A. Charalambides, Enumerative Combinatorics, Chapman & Hall/CRC, Boca Raton, Florida, 2002.
  • L. Comtet, Advanced Combinatorics, Reidel, 1974, p. 182.
  • Florence Nightingale David and D. E. Barton, Combinatorial Chance. Hafner, NY, 1962, p. 168.
  • Florence Nightingale David, Maurice George Kendall, and D. E. Barton, Symmetric Function and Allied Tables, Cambridge, 1966, p. 263, Table 7.5.1, row 1.
  • P. R. de Montmort, On the Game of Thirteen (1713), reprinted in Annotated Readings in the History of Statistics, ed. H. A. David and A. W. F. Edwards, Springer-Verlag, 2001, pp. 25-29.
  • J. M. de Saint-Martin, "Le problème des rencontres" in Quadrature, No. 61, pp. 14-19, 2006, EDP-Sciences Les Ulis (France).
  • H. Doerrie, 100 Great Problems of Elementary Mathematics, Dover, NY, 1965, p. 19.
  • Leonhard Euler, Solution quaestionis curiosae ex doctrina combinationum, Mémoires Académie sciences St. Pétersburg 3 (1809/1810), 57-64; also E738 in his Collected Works, series I, volume 7, pages 435-440.
  • J. M. Gandhi, On logarithmic numbers, Math. Student, 31 (1963), 73-83.
  • A. Hald, A History of Probability and Statistics and Their Applications Before 1750, Wiley, NY, 1990 (Chapter 19).
  • Irving Kaplansky, John Riordan, The problème des ménages. Scripta Math. 12 (1946), 113-124. See Eq(1).
  • Arnold Kaufmann, "Introduction à la combinatorique en vue des applications." Dunod, Paris, 1968. See p. 92.
  • Florian Kerschbaum and Orestis Terzidis, Filtering for Private Collaborative Benchmarking, in Emerging Trends in Information and Communication Security, Lecture Notes in Computer Science, Volume 3995/2006.
  • E. Lozansky and C. Rousseau, Winning Solutions, Springer, 1996; see p. 152.
  • P. A. MacMahon, Combinatory Analysis, 2 vols., Chelsea, NY, 1960, see p. 102.
  • M. S. Petković, "Non-attacking rooks", Famous Puzzles of Great Mathematicians, pp. 265-268, Amer. Math. Soc.(AMS), 2009.
  • V. Reiner, F. Saliola, and V. Welker. Spectra of Symmetrized Shuffling Operators, Memoirs of the American Mathematical Society, vol. 228, Amer. Math. Soc., Providence, RI, 2014, pp. 1-121. See section VI.9.
  • J. Riordan, An Introduction to Combinatorial Analysis, Wiley, 1958, p. 65.
  • H. J. Ryser, Combinatorial Mathematics. Mathematical Association of America, Carus Mathematical Monograph 14, 1963, p. 23.
  • T. Simpson, Permutations with unique fixed and reflected points. Ars Combin. 39 (1995), 97-108.
  • 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).
  • David Wells, The Penguin Dictionary of Curious and Interesting Numbers. Penguin Books, NY, 1986, Revised edition 1987. See p. 122.
  • D. B. West, Combinatorial Mathematics, Cambridge, 2021, p. 82.
  • H. S. Wilf, Generatingfunctionology, Academic Press, NY, 1990, p. 147, Eq. 5.2.9 (q=1).

Links

Crossrefs

Cf. A000142, A002467, A003221, A000522, A000240, A000387, A000449, A000475, A129135, A092582, A000255, A002469, A159610, A068985, A068996, A047865, A038205, A008279, A281682.
For the probabilities a(n)/n!, see A053557/A053556 and A103816/A053556.
A diagonal of A008291 and A068106. Column A008290(n,0).
A001120 has a similar recurrence.
For other derangement numbers see also A053871, A033030, A088991, A088992.
Pairwise sums of A002741 and A000757. Differences of A001277.
Cf. A101560, A101559, A000110, A101033, A101032, A000204, A100492, A099731, A000045, A094216, A094638, A000108.
A diagonal in triangles A008305 and A010027.
a(n)/n! = A053557/A053556 = (N(n, n) of A103361)/(D(n, n) of A103360).
Column k=0 of A086764 and of A334715. Column k=1 of A364068.
Row sums of A216963 and of A323671.

Programs

  • Haskell
    a000166 n = a000166_list !! n
a000166_list = 1 : 0 : zipWith (*) [1..]
                       (zipWith (+) a000166_list $ tail a000166_list)
-- Reinhard Zumkeller, Dec 09 2012
  • Magma
    I:=[0,1]; [1] cat [n le 2 select I[n] else (n-1)*(Self(n-1)+Self(n-2)): n in [1..30]]; // Vincenzo Librandi, Jan 07 2016
  • Maple
    A000166 := proc(n) option remember; if n<=1 then 1-n else (n-1)*(procname(n-1)+procname(n-2)); fi; end;
a:=n->n!*sum((-1)^k/k!, k=0..n): seq(a(n), n=0..21); # Zerinvary Lajos, May 17 2007
ZL1:=[S,{S=Set(Cycle(Z,card>1))},labeled]: seq(count(ZL1,size=n),n=0..21); # Zerinvary Lajos, Sep 26 2007
with (combstruct):a:=proc(m) [ZL,{ZL=Set(Cycle(Z,card>=m))},labeled]; end: A000166:=a(2):seq(count(A000166,size=n),n=0..21); # Zerinvary Lajos, Oct 02 2007
Z := (x, m)->m!^2*sum(x^j/((m-j)!^2), j=0..m): R := (x, n, m)->Z(x, m)^n: f := (t, n, m)->sum(coeff(R(x, n, m), x, j)*(t-1)^j*(n*m-j)!, j=0..n*m): seq(f(0, n, 1), n=0..21); # Zerinvary Lajos, Jan 22 2008
a:=proc(n) if `mod`(n,2)=1 then sum(2*k*factorial(n)/factorial(2*k+1), k=1.. floor((1/2)*n)) else 1+sum(2*k*factorial(n)/factorial(2*k+1), k=1..floor((1/2)*n)-1) end if end proc: seq(a(n),n=0..20); # Emeric Deutsch, Feb 23 2008
G(x):=2*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]/2,n=0..21); # Zerinvary Lajos, Apr 03 2009
seq(simplify(KummerU(-n, -n, -1)), n = 0..23); # Peter Luschny, May 10 2022
  • Mathematica
    a[0] = 1; a[n_] := n*a[n - 1] + (-1)^n; a /@ Range[0, 21] (* Robert G. Wilson v *)
a[0] = 1; a[1] = 0; a[n_] := Round[n!/E] /; n >= 1 (* Michael Taktikos, May 26 2006 *)
Range[0, 20]! CoefficientList[ Series[ Exp[ -x]/(1 - x), {x, 0, 20}], x]
dr[{n_,a1_,a2_}]:={n+1,a2,n(a1+a2)}; Transpose[NestList[dr,{0,0,1},30]][[3]] (* Harvey P. Dale, Feb 23 2013 *)
a[n_] := (-1)^n HypergeometricPFQ[{- n, 1}, {}, 1]; (* Michael Somos, Jun 01 2013 *)
a[n_] := n! SeriesCoefficient[Exp[-x] /(1 - x), {x, 0, n}]; (* Michael Somos, Jun 01 2013 *)
Table[Subfactorial[n], {n, 0, 21}] (* Jean-François Alcover, Jan 10 2014 *)
RecurrenceTable[{a[n] == n*a[n - 1] + (-1)^n, a[0] == 1}, a, {n, 0, 23}] (* Ray Chandler, Jul 30 2015 *)
Subfactorial[Range[0, 20]] (* Eric W. Weisstein, Dec 31 2017 *)
nxt[{n_,a_}]:={n+1,a(n+1)+(-1)^(n+1)}; NestList[nxt,{0,1},25][[All,2]] (* Harvey P. Dale, Jun 01 2019 *)
  • Maxima
    s[0]:1$
s[n]:=n*s[n-1]+(-1)^n$
makelist(s[n],n,0,12); /* Emanuele Munarini, Mar 01 2011 */
  • PARI
    {a(n) = if( n<1, 1, n * a(n-1) + (-1)^n)}; /* Michael Somos, Mar 24 2003 */
  • PARI
    {a(n) = n! * polcoeff( exp(-x + x * O(x^n)) / (1 - x), n)}; /* Michael Somos, Mar 24 2003 */
  • PARI
    {a(n)=polcoeff(sum(m=0,n,m^m*x^m/(1+(m+1)*x+x*O(x^n))^(m+1)),n)} /* Paul D. Hanna */
  • PARI
    A000166=n->n!*sum(k=0,n,(-1)^k/k!) \\ M. F. Hasler, Jan 26 2012
  • PARI
    a(n)=if(n,round(n!/exp(1)),1) \\ Charles R Greathouse IV, Jun 17 2012
  • PARI
    apply( {A000166(n)=n!\/exp(n>0)}, [0..22]) \\ M. F. Hasler, Nov 09 2024
  • Python
    See Hobson link.
  • Python
    A000166_list, m, x = [], 1, 1
for n in range(10*2):
    x, m = x*n + m, -m
    A000166_list.append(x) # Chai Wah Wu, Nov 03 2014

Formula

(A000166 + A000522)/2 = A009179, (A000166 - A000522)/2 = A009628.
a(n) = A008290(n,0).
a(n) + A003048(n+1) = 2*n!. - D. G. Rogers, Aug 26 2006
a(n) = {(n-1)!/exp(1)}, n > 1, where {x} is the nearest integer function. - Simon Plouffe, March 1993 [This uses offset 1, see below for the version with offset 0. - Charles R Greathouse IV, Jan 25 2012]
a(0) = 1, a(n) = round(n!/e) = floor(n!/e + 1/2) for n > 0.
a(n) = n!*Sum_{k=0..n} (-1)^k/k!.
D-finite with recurrence a(n) = (n-1)*(a(n-1) + a(n-2)), n > 0.
a(n) = n*a(n-1) + (-1)^n.
E.g.f.: exp(-x)/(1-x).
a(n) = Sum_{k=0..n} binomial(n, k)*(-1)^(n-k)*k! = Sum_{k=0..n} (-1)^(n-k)*n!/(n-k)!. - Paul Barry, Aug 26 2004
The e.g.f. y(x) satisfies y' = x*y/(1-x).
Inverse binomial transform of A000142. - Ross La Haye, Sep 21 2004
In Maple notation, representation as n-th moment of a positive function on [-1, infinity]: a(n)= int( x^n*exp(-x-1), x=-1..infinity ), n=0, 1... . a(n) is the Hamburger moment of the function exp(-1-x)*Heaviside(x+1). - Karol A. Penson, Jan 21 2005
a(n) = A001120(n) - n!. - Philippe Deléham, Sep 04 2005
a(n) = Integral_{x=0..oo} (x-1)^n*exp(-x) dx. - Gerald McGarvey, Oct 14 2006
a(n) = Sum_{k=2,4,...} T(n,k), where T(n,k) = A092582(n,k) = k*n!/(k+1)! for 1 <= k < n and T(n,n)=1. - Emeric Deutsch, Feb 23 2008
a(n) = n!/e + (-1)^n*(1/(n+2 - 1/(n+3 - 2/(n+4 - 3/(n+5 - ...))))). Asymptotic result (Ramanujan): (-1)^n*(a(n) - n!/e) ~ 1/n - 2/n^2 + 5/n^3 - 15/n^4 + ..., where the sequence [1,2,5,15,...] is the sequence of Bell numbers A000110. - Peter Bala, Jul 14 2008
From William Vaughn (wvaughn(AT)cvs.rochester.edu), Apr 13 2009: (Start)
a(n) = Integral_{p=0..1} (log(1/(1-p)) - 1)^n dp.
Proof: Using the substitutions 1=log(e) and y = e(1-p) the above integral can be converted to ((-1)^n/e) Integral_{y=0..e} (log(y))^n dy.
From CRC Integral tables we find the antiderivative of (log(y))^n is (-1)^n n! Sum_{k=0..n} (-1)^k y(log(y))^k / k!.
Using the fact that e(log(e))^r = e for any r >= 0 and 0(log(0))^r = 0 for any r >= 0 the integral becomes n! * Sum_{k=0..n} (-1)^k / k!, which is line 9 of the Formula section. (End)
a(n) = exp(-1)*Gamma(n+1,-1) (incomplete Gamma function). - Mark van Hoeij, Nov 11 2009
G.f.: 1/(1-x^2/(1-2x-4x^2/(1-4x-9x^2/(1-6x-16x^2/(1-8x-25x^2/(1-... (continued fraction). - Paul Barry, Nov 27 2009
a(n) = Sum_{p in Pano1(n)} M2(p), n >= 1, with Pano1(n) the set of partitions without part 1, and the multinomial M2 numbers. See the characteristic array for partitions without part 1 given by A145573 in Abramowitz-Stegun (A-S) order, with A002865(n) the total number of such partitions. The M2 numbers are given for each partition in A-St order by the array A036039. - Wolfdieter Lang, Jun 01 2010
a(n) = row sum of A008306(n), n > 1. - Gary Detlefs, Jul 14 2010
a(n) = ((-1)^n)*(n-1)*hypergeom([-n+2, 2], [], 1), n>=1; 1 for n=0. - Wolfdieter Lang, Aug 16 2010
a(n) = (-1)^n * hypergeom([ -n, 1], [], 1), n>=1; 1 for n=0. From the binomial convolution due to the e.g.f. - Wolfdieter Lang, Aug 26 2010
Integral_{x=0..1} x^n*exp(x) = (-1)^n*(a(n)*e - n!).
O.g.f.: Sum_{n>=0} n^n*x^n/(1 + (n+1)*x)^(n+1). - Paul D. Hanna, Oct 06 2011
Abs((a(n) + a(n-1))*e - (A000142(n) + A000142(n-1))) < 2/n. - Seiichi Kirikami, Oct 17 2011
G.f.: hypergeom([1,1],[],x/(x+1))/(x+1). - Mark van Hoeij, Nov 07 2011
From Sergei N. Gladkovskii, Nov 25 2011, Jul 05 2012, Sep 23 2012, Oct 13 2012, Mar 09 2013, Mar 10 2013, Oct 18 2013: (Start)
Continued fractions:
In general, e.g.f. (1+a*x)/exp(b*x) = U(0) with U(k) = 1 + a*x/(1-b/(b-a*(k+1)/U(k+1))). For a=-1, b=-1: exp(-x)/(1-x) = 1/U(0).
E.g.f.: (1-x/(U(0)+x))/(1-x), where U(k) = k+1 - x + (k+1)*x/U(k+1).
E.g.f.: 1/Q(0) where Q(k) = 1 - x/(1 - 1/(1 - (k+1)/Q(k+1))).
G.f.: 1/U(0) where U(k) = 1 + x - x*(k+1)/(1 - x*(k+1)/U(k+1)).
G.f.: Q(0)/(1+x) where Q(k) = 1 + (2*k+1)*x/((1+x)-2*x*(1+x)*(k+1)/(2*x*(k+1)+(1+x)/ Q(k+1))).
G.f.: 1/Q(0) where Q(k) = 1 - 2*k*x - x^2*(k + 1)^2/Q(k+1).
G.f.: T(0) where T(k) = 1 - x^2*(k+1)^2/(x^2*(k+1)^2-(1-2*x*k)*(1-2*x-2*x*k)/T(k+1)). (End)
0 = a(n)*(a(n+1) + a(n+2) - a(n+3)) + a(n+1)*(a(n+1) + 2*a(n+2) - a(n+3)) + a(n+2)*a(n+2) if n>=0. - Michael Somos, Jan 25 2014
a(n) = Sum_{k = 0..n} (-1)^(n-k)*binomial(n,k)*(k + x)^k*(k + x + 1)^(n-k) = Sum_{k = 0..n} (-1)^(n-k)*binomial(n,k)*(k + x)^(n-k)*(k + x - 1)^k, for arbitrary x. - Peter Bala, Feb 19 2017
From Peter Luschny, Jun 20 2017: (Start)
a(n) = Sum_{j=0..n} Sum_{k=0..n} binomial(-j-1, -n-1)*abs(Stirling1(j, k)).
a(n) = Sum_{k=0..n} (-1)^(n-k)*Pochhammer(n-k+1, k) (cf. A008279). (End)
a(n) = n! - Sum_{j=0..n-1} binomial(n,j) * a(j). - Alois P. Heinz, Jan 23 2019
Sum_{n>=2} 1/a(n) = A281682. - Amiram Eldar, Nov 09 2020
a(n) = KummerU(-n, -n, -1). - Peter Luschny, May 10 2022
a(n) = (-1)^n*Sum_{k=0..n} Bell(k)*Stirling1(n+1, k+1). - Mélika Tebni, Jul 05 2022

Extensions

Minor edits by M. F. Hasler, Jan 16 2017

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

A002104 Logarithmic numbers.

Original entry on oeis.org

0, 1, 3, 8, 24, 89, 415, 2372, 16072, 125673, 1112083, 10976184, 119481296, 1421542641, 18348340127, 255323504932, 3809950977008, 60683990530225, 1027542662934915, 18430998766219336, 349096664728623336, 6962409983976703337, 145841989688186383359, 3201192743180799343844
Offset: 0

Views

Author

N. J. A. Sloane

Keywords

Comments

Prime p divides a(p+1). - Alexander Adamchuk, Jul 05 2006
Also number of lists of elements from {1,..,n} with (1st element) = (smallest element), where a list means an ordered subset (cf. A000262), see also Haskell program. - Reinhard Zumkeller, Oct 26 2010
a(n+1) = p_n(-1) where p_n(x) is the unique degree-n polynomial such that p_n(k) = A133942(k) for k = 0, 1, ..., n. - Michael Somos, Apr 30 2012
a(n) = A006231(n) + n. - Geoffrey Critzer, Oct 04 2012

Examples

			From _Reinhard Zumkeller_, Oct 26 2010: (Start)
a(3) = #{[1], [1,2], [1,2,3], [1,3], [1,3,2], [2], [2,3], [3]} = 8;
a(4) = #{[1], [1,2], [1,2,3], [1,2,3,4], [1,2,4], [1,2,4,3], [1,3], [1,3,2], [1,3,2,4], [1,3,4], [1,3,4,2], [1,4], [1,4,2], [1,4,2,3], [1,4,3], [1,4,3,2], [2], [2,3], [2,3,4], [2,4], [2,4,3], [3], [3,4], [4]} = 24. (End)
G.f. = x + 3*x^2 + 8*x^3 + 24*x^4 + 89*x^5 + 415*x^6 + 2372*x^7 + ...

References

  • J. M. Gandhi, On logarithmic numbers, Math. Student, 31 (1963), 73-83.
  • 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. A001338, A006231, A007526, A030297, A133942.

Programs

  • Haskell
    import Data.List (subsequences, permutations)
a002104 = length . filter (\xs -> head xs == minimum xs) .
                   tail . choices . enumFromTo 1
   where choices = concat . map permutations . subsequences
-- Reinhard Zumkeller, Feb 21 2012, Oct 25 2010
  • Maple
    a := proc(n) option remember; ifelse(n < 2, n, n*a(n-1) - (n-1)*a(n-2) + 1) end:
seq(a(n), n = 0..23); # Peter Luschny, Dec 05 2023
  • Mathematica
    Table[Sum[Sum[m!/k!,{k,0,m}],{m,0,n-1}],{n,1,30}] (* Alexander Adamchuk, Jul 05 2006 *)
a[n_] = n*(HypergeometricPFQ[{1, 1, 1-n}, {2}, -1]); Table[a[n], {n, 1, 20}] (* Jean-François Alcover, Mar 29 2011 *)
  • PARI
    x='x+O('x^99); concat([0], Vec(serlaplace(-log(1-x)*exp(x)))) \\ Altug Alkan, Dec 17 2017
  • PARI
    {a(n) = sum(k=0, n-1, binomial(n, k) * (n-k-1)!)}; /* Michael Somos, May 08 2019 */

Formula

E.g.f.: -log(1 - x) * exp(x).
a(n) = Sum_{k=1..n} Sum_{i=0..n-k} (n-k)!/i!.
a(n) = Sum_{k=1..n} n(n-1)...(n-k+1)/k = A006231(n) + n - Avi Peretz (njk(AT)netvision.net.il), Mar 24 2001
a(n+1) - a(n) = A000522(n).
a(n) = sum{k=0..n-1, binomial(n, k)*(n-k-1)!}, row sums of A111492. - Paul Barry, Aug 26 2004
a(n) = Sum[Sum[m!/k!,{k,0,m}],{m,0,n-1}]. a(n) = Sum[A000522(m),{m,0,n-1}]. - Alexander Adamchuk, Jul 05 2006
For n > 1, the arithmetic mean of the first n terms is a(n-1) + 1. - Franklin T. Adams-Watters, May 20 2010
a(n) = n * 3F1((1,1,1-n); (2); -1). - Jean-François Alcover, Mar 29 2011
Conjecture: a(n) +(-n-1)*a(n-1) +2*(n-1)*a(n-2) +(-n+2)*a(n-3)=0. - R. J. Mathar, Dec 02 2012
From Emanuele Munarini, Dec 16 2017: (Start)
The generating series A(x) = -exp(x)*log(1-x) satisfies the differential equations:
(1-x)*A'(x) - (1-x)*A(x) = exp(x)
(1-x)*A''(x) - (3-2*x)*A'(x) + (2-x)*A(x) = 0.
From the first one, we have the recurrence reported below by R. R. Forberg. From the second one, we have the recurrence conjectured above. (End)
G.f.: conjecture: T(0)*x/(1-2*x)/(1-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
a(n) ~ exp(1)*(n-1)!. - Vaclav Kotesovec, Mar 10 2014
a(n) = n*a(n-1) - (n-1)*a(n-2) + 1, a(0) = 0, a(1) = 1. - Richard R. Forberg, Dec 15 2014
a(n) = A007526(n) + A006231(n+1) - A030297(n). - Anton Zakharov, Sep 05 2016
0 = +a(n)*(+a(n+1) -4*a(n+2) +4*a(n+3) -a(n+4)) +a(n+1)*(+2*a(n+2) -5*a(n+3) +2*a(n+4)) +a(n+2)*(+2*a(n+2) -a(n+3) -a(n+4)) +a(n+3)*(+a(n+3)) for all n>=0. - Michael Somos, May 08 2019
From Peter Bala, Sep 12 2022: (Start)
For n, m >= 0, a(n) - a(n + m) == ( a(1) - a(m) ) (mod m). The sequence {mod(a(1) - a(m+1), m): m >= 1} begins [0, 1, 1, 0, 1, 5, 1, 0, 3, 7, 1, 4, 1, 9, 8, 0, 1, 15, 1, 4, ...].
Conjectures:
1) for n, m >= 0, k >= 2, a(n + m*2^k) - a(n) is divisible by 2^k.
2) for n >= 0, a(n + m*p^k) - a(n) + m*p^(k-1) is divisible by p^k for all positive integers m and k, and for all odd primes p. The particular case n = m = k = 1 is stated in the Comments section by Adamchuk. (End)
a(n) = Integral_{t=0..oo} ((t + 1)^n - 1)/(t*e^t) dt. - Velin Yanev, Apr 13 2024
a(n) = Gamma(n)*(e - ((-1)^n)*Gamma(1 - n, -1)) + hypergeom([1, 1], [2, n + 2], 1)/(n + 1) - polygamma(n) - 1/n + i*Pi for n > 0, where polygamma is the digamma function and the bivariate gamma function is the upper incomplete gamma function. - Velin Yanev, Apr 13 2024

Extensions

More terms from Larry Reeves (larryr(AT)acm.org), Mar 27 2001

A000757 Number of cyclic permutations of [n] with no i -> i+1 (mod n).

Original entry on oeis.org

1, 0, 0, 1, 1, 8, 36, 229, 1625, 13208, 120288, 1214673, 13469897, 162744944, 2128047988, 29943053061, 451123462673, 7245940789072, 123604151490592, 2231697509543361, 42519034050101745, 852495597142800376
Offset: 0

Views

Author

N. J. A. Sloane

Keywords

Examples

			a(4)=1 because from the 4!/4=6 circular permutations of n=4 elements (1,2,3,4), (1,4,3,2), (1,3,4,2),(1,2,4,3), (1,4,2,3) and (1,3,2,4) only (1,4,3,2) has no successor pair (i,i+1). Note that (4,1) is also a successor pair. - _Wolfdieter Lang_, Jan 21 2008
a(3) = 1 = 2! - 3*1! + 3*0! - 1. a(4) = 1 = 3! - 4*2! + 6*1! - 4*0! + 1. - _Michael Somos_, Mar 28 2011
G.f. = 1 + x^3 + x^4 + 8*x^5 + 36*x^6 + 229*x^7 + 1625*x^8 + 13208*x^9 + ...

References

  • Ch. A. Charalambides, Enumerative Combinatorics, Chapman & Hall/CRC, Boca Raton, Florida, 2002, pp. 182, 183, Table 5.6.
  • 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).
  • R. P. Stanley, Space Programs Summary. Jet Propulsion Laboratory, California Institute of Technology, Pasadena, California, Vol. 37-40-4 (1966), pp. 208-214.
  • R. P. Stanley, Enumerative Combinatorics I, Chap. 2, Exercise 8, p. 88.
  • N. Ya. Vilenkin, Combinatorics, pp. 56-57, Q_n = a(n), n >= 3. Academic Press, 1971. On the Merry Go-Round.

Links

Crossrefs

Cf. A000142, A000166, A002741.

Programs

  • Mathematica
    a[n_] := (-1)^n + Sum[(-1)^k*n!/((n-k)*k!), {k, 0, n-1}]; Table[a[n], {n, 0, 21}] (* Jean-François Alcover, Aug 30 2011, after Michael Somos *)
  • PARI
    {a(n) = if( n<0, 0, (-1)^n + sum( k=0, n-1, (-1)^k * binomial( n, k) * (n - k - 1)!))}; /* Michael Somos, Jun 21 2002 */

Formula

From Michael Somos, Jun 21 2002: (Start)
a(n) = (-1)^n + Sum_{k=0..n-1} (-1)^k*binomial(n, k)*(n-k-1)!;
e.g.f.: (1 - log(1 - x)) / e^x;
a(n) = (n-3) * a(n-1) + (n-2) * (2*a(n-2) + a(n-3)).
a(n) = (n-2) * a(n-1) + (n-1) * a(n-2) - (-1)^n, if n > 0.
a(n) = (-1)^n + A002741(n). (End)
a(n) = n-th forward difference of [1, 1, 1, 2, 6, 24, ...] (factorials A000142 with 1 prepended). - Michael Somos, Mar 28 2011
a(n) = Sum_{j=3..n} (-1)^(n-j)*D(j-1), n >= 3, with the derangements numbers (subfactorials) D(n) = A000166(n).
a(n) + a(n+1) = A000166(n). - Aaron Meyerowitz, Feb 08 2014
a(n) ~ exp(-1)*(n-1)! * (1 - 1/n + 1/n^3 + 1/n^4 - 2/n^5 - 9/n^6 - 9/n^7 + 50/n^8 + 267/n^9 + 413/n^10 + ...), numerators are A000587. - Vaclav Kotesovec, Jul 03 2016

Extensions

Better description from Len Smiley
Additional comments from Michael Somos, Jun 21 2002

A133942 a(n) = (-1)^n * n!.

Original entry on oeis.org

1, -1, 2, -6, 24, -120, 720, -5040, 40320, -362880, 3628800, -39916800, 479001600, -6227020800, 87178291200, -1307674368000, 20922789888000, -355687428096000, 6402373705728000, -121645100408832000, 2432902008176640000
Offset: 0

Views

Author

Michael Somos, Sep 30 2007

Keywords

Comments

A variant of A000142, the factorial numbers. - N. J. A. Sloane, Oct 03 2007
The terms of this sequences form the factorial series which Euler called the divergent series par excellence.
Euler summed this series to 0.596347... (A073003 = Gompertz's constant).
Sum_{n>=0} 1/a(n) = 1/e. - Jaume Oliver Lafont, Mar 03 2009
A002104(n+1) = p(-1) where p(x) is the unique degree-n polynomial such that p(k) = a(k) for k = 0, 1, ..., n. - Michael Somos, Apr 30 2012
a(n) = A048594(2*n+1, n+1). - Reinhard Zumkeller, Mar 02 2014
log(1+x) = Sum_{n>=1} a(n-1)/n!*x^n. - James R. Buddenhagen, May 24 2015
It seems that a(n) is the determinant of n+1 X n+1 matrix whose elements are m(i,j) = quotient(i/j) + remainder(i/j). - Andres Cicuttin, Feb 11 2018

Examples

			G.f. = 1 - x + 2*x^2 - 6*x^3 + 24*x^4 - 120*x^5 + 720*x^6 - 5040*x^7 + ...

References

  • A. N. Khovanskii. The Application of Continued Fractions and Their Generalizations to Problem in Approximation Theory. Groningen: Noordhoff, Netherlands, 1963. See p. 141 (10.19)
  • R. Roy, Sources in the Development of Mathematics, Cambridge University Press, 2011. See p. 186.

Links

Crossrefs

Partial sums are A058006.
Alternating row sums of A048994.
Also, a(n) = A048994(n+1,1).
Cf. A000142, A002104, A002741, A055209, A158882.

Programs

  • GAP
    List([0..20],n->(-1)^n*Factorial(n)); # Muniru A Asiru, Oct 27 2018
  • Haskell
    a133942 n = a133942_list !! n
a133942_list = zipWith (*) a000142_list $ cycle [1, -1]
-- Reinhard Zumkeller, Mar 02 2014
  • Magma
    [(-1)^n * Factorial(n): n in [0..25]]; // Vincenzo Librandi, May 12 2011
  • Maple
    seq((-1)^n*factorial(n),n=0..20); # Muniru A Asiru, Oct 27 2018
  • Mathematica
    nn=20;CoefficientList[Series[1/(1+x),{x,0,nn}],x]Range[0,nn]! (* or *)
RecurrenceTable[{a[0]==1,a[n]==-n*a[n-1]},a[n],{n,20}] (* Harvey P. Dale, May 10 2011 and slightly modified by Robert G. Wilson v, Feb 12 2018 *)
a[n_] := (-1)^n*n!; Array[a, 22, 0] (* Robert G. Wilson v, Feb 11 2018 *)
Times@@@Partition[Riffle[Range[0,30]!,{1,-1}],2] (* Harvey P. Dale, Dec 30 2019 *)
  • PARI
    {a(n) = if( n<0, 0, (-1)^n * n! )};
  • Python
    import math
for n in range(0, 25): print((-1)**n*math.factorial(n), end=', ') # Stefano Spezia, Oct 27 2018

Formula

Sum_{i=0..n} (-1)^i * i^n * binomial(n, i) = (-1)^n * n!. - Yong Kong (ykong(AT)curagen.com), Dec 26 2000
Stirling transform of a(n) = [1, -1, 2, -6, 24, ...] is A000007(n) = [1, 0, 0, 0, 0, ...].
a(n) = -n * a(n-1) unless n=0. a(n) = (-1)^n * A000142(n).
E.g.f.: 1/(1 + x).
G.f.: integral(t=1/x,infinity, (e^-t)/t) e^(1/x)/x = 1/(1 + x/(1 + x/(1 + 2*x/(1 + 2*x/(1 + 3*x/(1 + 3*x/(1 + ...))))))).
Convolution inverse of A158882. HANKEL transform is A055209. PSUM transform is A058006. BIN1 transform is A002741(n+1). - Michael Somos, Apr 30 2012
G.f.: 1 - x/(G(0)+x) where G(k) = 1 + (k+1)*x/(1 + x*(k+2)/G(k+1)), G(0) = W(1,1;x)/W(1,2;x), W(a,b,x) = 1 - a*b*x/1! + a*(a+1)*b*(b+1)*x^2/2! - ... + a*(a+1)*...*(a+n-1)*b*(b+1)*...*(b+n-1)*x^n/n! + ...; see [A. N. Khovanskii, p. 141 (10.19)]; (continued fraction, 2-step). - Sergei N. Gladkovskii, Aug 14 2012
G.f.: 1/U(0) where U(k) = 1 + x*(k+1)/(1 + x*(k+1)/U(k+1)); (continued fraction, 2-step). - Sergei N. Gladkovskii, Oct 15 2012
a(n) = (-1)^n*det(S(i+1,j)|, 1 <= i,j <= n), where S(n,k) are Stirling numbers of the second kind. - Mircea Merca, Apr 06 2013
G.f.: 2/G(0), where G(k)= 1 + 1/(1 - 2*x*(k+1)/(2*x*(k+1) + 1 + 2*x*(k+1)/G(k+1))); (continued fraction). - Sergei N. Gladkovskii, May 30 2013
E.g.f.: 1/(1 + x)= G(0), where G(k) = 1 - x*(k+1)*(k+2)/(1 + (k+1)/G(k+1) ); (continued fraction). - Sergei N. Gladkovskii, Jan 29 2014
For n >= 1, a(n) = round(zeta^(n)(2)), where zeta^(n) is the n-th derivative of the Riemann zeta function. - Iain Fox, Nov 13 2017
a(n) = (n+1)^(n+1) * Integral_{x=0..1} (x*log(x))^n dx. - Peter James Foreman, Oct 27 2018

A238363 Coefficients for the commutator for the logarithm of the derivative operator [log(D),x^n D^n]=d[(xD)!/(xD-n)!]/d(xD) expanded in the operators :xD:^k.

Original entry on oeis.org

1, -1, 2, 2, -3, 3, -6, 8, -6, 4, 24, -30, 20, -10, 5, -120, 144, -90, 40, -15, 6, 720, -840, 504, -210, 70, -21, 7, -5040, 5760, -3360, 1344, -420, 112, -28, 8, 40320, -45360, 25920, -10080, 3024, -756, 168, -36, 9, -362880, 403200, -226800, 86400, -25200, 6048, -1260, 240, -45, 10
Offset: 1

Views

Author

Tom Copeland, Feb 25 2014

Keywords

Comments

Let D=d/dx and [A,B]=A·B-B·A. Then each row corresponds to the coefficients of the operators :xD:^k = x^k D^k in the expansion of the commutator [log(D),:xD:^n]=[-log(x),:xD:^n]=sum(k=0 to n-1, a(n,k) :xD:^k). The e.g.f. is derived from [log(D), exp(t:xD:)]=[-log(x), exp(t:xD:)]= log(1+t)exp(t:xD:), using the shift property exp(t:xD:)f(x)=f((1+t)x).
The reversed unsigned array is A111492.
See the mathoverflow link and link therein to an associated mathstackexchange question for other formulas for log(D). In addition, R_x = log(D) = -log(x) + c - sum[n=1 to infnty, (-1)^n 1/n :xD:^n/n!]=
-log(x) + Psi(1+xD) = -log(x) + c + Ein(:xD:), where c is the Euler-Mascheroni constant, Psi(x), the digamma function, and Ein(x), a breed of the exponential integrals (cf. Wikipedia). The :xD:^k ops. commute; therefore, the commutator reduces to the -log(x) term.
Also the n-th row corresponds to the expansion of d[(xD)!/(xD-n)!]/d(xD) = d[:xD:^n]/d(xD) in the operators :xD:^k, or, equivalently, the coefficients of x in d[z!/(z-n)!]/dz=d[St1(n,z)]]/dz evaluated umbrally with z=St2(.,x), i.e., z^n replaced by St2(n,x), where St1(n,x) and St2(n,x) are the signed and unsigned Stirling polynomials of the first (A008275) and second (A008277) kinds. The derivatives of the unsigned St1 are A028421. See examples. This formalism follows from the relations between the raising and lowering operators presented in the MathOverflow link and the Pincherle derivative. The results can be generalized through the operator relations in A094638, which are related to the celebrated Witt Lie algebra and pseudodifferential operators / symbols, to encompass other integral arrays.
A002741(n)*(-1)^(n+1) (row sums), A002104(n)*(-1)^(n+1) (alternating row sums). Column sequences: A133942(n-1), A001048(n-1), A238474, ... - Wolfdieter Lang, Mar 01 2014
Add an additional head row of zeros to the lower triangular array and denote it as T (with initial indexing in columns and rows being 0). Let dP = A132440, the infinitesimal generator for the Pascal matrix, and I, the identity matrix, then exp(T)=I+dP, i.e., T=log(I+dP). Also, (T_n)^n=0, where T_n denotes the n X n submatrix, i.e., T_n is nilpotent of order n. - Tom Copeland, Mar 01 2014
Any pair of lowering and raising ops. L p(n,x) = n·p(n-1,x) and R p(n,x) = p(n+1,x) satisfy [L,R]=1 which implies (RL)^n = St2(n,:RL:), and since (St2(·,u))!/(St2(·,u)-n)!= u^n, when evaluated umbrally, d[(RL)!/(RL-n)!]/d(RL) = d[:RL:^n]/d(RL) is well-defined and gives A238363 when the LHS is reduced to a sum of :RL:^k terms, exactly as for L=d/dx and R=x above. (Note that R_x above is a raising op. different from x, with associated L_x=-xD.) - Tom Copeland, Mar 02 2014
For relations to colored forests, disposition of flags on flagpoles, and the colorings of the vertices of the complete graphs K_n, encoded in their chromatic polynomials, see A130534. - Tom Copeland, Apr 05 2014
The unsigned triangle, omitting the main diagonal, gives A211603. See also A092271. Related to the infinitesimal generator of A008290. - Peter Bala, Feb 13 2017

Examples

			The first few row polynomials are
p(1,x)=  1
p(2,x)= -1 + 2x
p(3,x)=  2 - 3x + 3x^2
p(4,x)= -6 + 8x - 6x^2 + 4x^3
p(5,x)= 24 -30x +20x^2 -10x^3 + 5x^4
...........
For n=3: z!/(z-3)!=z^3-3z^2+2z=St1(3,z) with derivative 3z^2-6z+2, and
3·St2(2,x)-6·St2(1,x)+2=3(x^2+x)-6x+2=3x^2-3x+2=p(3,x). To see the relation to the operator formalism, note that (xD)^k=St2(k,:xD:) and (xD)!/(xD-k)!=[St2(·,:xD:)]!/[St2(·,:xD:)-k]!= :xD:^k.
The triangle a(n,k) begins:
n\k       0       1       2      3      4     5      6    7   8   9 ...
1:        1
2:       -1       2
3:        2      -3       3
4:       -6       8      -6      4
5:       24     -30      20    -10      5
6:     -120     144     -90     40    -15     6
7:      720    -840     504   -210     70   -21      7
8:    -5040    5760   -3360   1344   -420   112    -28    8
9:    40320  -45360   25920 -10080   3024  -756    168  -36   9
10: -362880  403200 -226800  86400 -25200  6048  -1260  240 -45  10
... formatted by _Wolfdieter Lang_, Mar 01 2014
-----------------------------------------------------------------------

Links

Crossrefs

Cf. A094587, A132013, A132014, A132159, A235706, A238385.
Cf. A008290, A092271, A211603.

Programs

  • Mathematica
    a[n_, k_] := (-1)^(n-k-1)*n!/((n-k)*k!); Table[a[n, k], {n, 1, 10}, {k, 0, n-1}] // Flatten (* Jean-François Alcover, Jul 09 2015 *)

Formula

a(n,k) = (-1)^(n-k-1)*n!/((n-k)*k!) for k=0 to (n-1).
E.g.f.: log(1+t)*exp(x*t).
E.g.f.for unsigned array: -log(1-t)*exp(x*t).
The lowering op. for the row polynomials is L=d/dx, i.e., L p(n,x) = n*p(n-1,x).
An e.g.f. for an unsigned related version is -log(1+t)*exp(x*t)/t= exp(t*s(·,x)) with s(n,x)=(-1)^n * p(n+1,-x)/(n+1). Let L=d/dx and R= x-(1/((1-D)log(1-D))+1/D),then R s(n,x)= s(n+1,x) and L s(n,x)= n*s(n-1,x), defining a special Sheffer sequence of polynomials, an Appell sequence. So, R (-1)^(n-1) p(n,-x)/n = (-1)^n p(n+1,-x)/(n+1).
From Tom Copeland, Apr 17 2014: (Start)
Dividing each diagonal by its first element (-1)^(n-1)*(n-1)! yields the reverse of A104712.
Multiply each n-th diagonal of the Pascal lower triangular matrix by x^n and designate the result as A007318(x) = P(x). Then with dP = A132440, M = padded A238363 = A238385-I, I = identity matrix, and (B(.,x))^n = B(n,x) = the n-th Bell polynomial Bell(n,x) of A008277,
A) P(x)= exp(x*dP) = exp[x*(e^M-I)] = exp[M*B(.,x)] = (I+dP)^B(.,x), and
B) P(:xD:)=exp(dP:xD:)=exp[(e^M-I):xD:]=exp[M*B(.,:xD:)]=exp[M*xD]=
(1+dP)^(xD) with action P(:xD:)g(x) = exp(dP:xD:)g(x) = g[(I+dP)*x].
C) P(x)^m = P(m*x). P(2x) = A038207(x) = exp[M*B(.,2x)], face vectors of n-D hypercubes. (End)
From Tom Copeland, Apr 26 2014: (Start)
M = padded A238363 = A238385-I
A) = [St1]*[dP]*[St2] = [padded A008275]*A132440*A048993
B) = [St1]*[dP]*[St1]^(-1)
C) = [St2]^(-1)*[dP]*[St2]
D) = [St2]^(-1)*[dP]*[St1]^(-1),
where [St1]=padded A008275 just as [St2]=A048993=padded A008277.
E) P(x) = [St2]*exp(x*M)*[St1] = [St2]*(I + dP)^x*[St1].
F) exp(x*M) = [St1]*P(x)*[St2] = (I + dP)^x,
where (I + dP)^x = sum(k>=0, C(x,k)*dP^k).
Let the row vector Rv=(c0 c1 c2 c3 ...) and the column vector Cv(x)=(1 x x^2 x^3 ...)^Transpose. Form the power series V(x)= Rv * Cv(x) and W(y) := V(x.) evaluated umbrally with (x.)^n = x_n = (y)_n = y!/(y-n)!. Then
G) U(:xD:) = dV(:xD:)/d(xD) = dW(xD)/d(xD) evaluated with (xD)^n = Bell(n,:xD:),
H) U(x) = dV(x.)/dy := dW(y)/dy evaluated with y^n=y_n=Bell(n,x), and
I) U(x) = Rv * M * Cv(x). (Cf. A132440, A074909.) (End)
The Bernoulli polynomials Ber_n(x) are related to the polynomials q_n(x) = p(n+1,x) / (n+1) with the e.g.f. [log(1+t)/t] e^(xt) (cf. s_n (x) above) as Ber_n(x) = St2_n[q.(St1.(x))], umbrally, or [St2]*[q]*[St1], in matrix form. Since q_n(x) is an Appell sequence of polynomials, q_n(x) = [log(1+D_x)/D_x]x^n. - Tom Copeland, Nov 06 2016

Extensions

Pincherle formalism added by Tom Copeland, Feb 27 2014

A238385 Shifted lower triangular matrix A238363 with a main diagonal of ones.

Original entry on oeis.org

1, 1, 1, -1, 2, 1, 2, -3, 3, 1, -6, 8, -6, 4, 1, 24, -30, 20, -10, 5, 1, -120, 144, -90, 40, -15, 6, 1, 720, -840, 504, -210, 70, -21, 7, 1, -5040, 5760, -3360, 1344, -420, 112, -28, 8, 1, 40320, -45360, 25920, -10080, 3024, -756, 168, -36, 9, 1, -362880, 403200, -226800, 86400, -25200, 6048, -1260, 240, -45, 10, 1
Offset: 0

Views

Author

Tom Copeland, Feb 25 2014

Keywords

Comments

Shift A238363 and add a main diagonal of ones to obtain this array. The row polynomials form a special Sheffer sequence of polynomials, an Appell sequence.

Examples

			The triangle a(n,k) begins:
n\k       0       1        2      3       4     5      6    7   8   9 10 ...
0:        1
1:        1       1
2:       -1       2        1
3:        2      -3        3      1
4:       -6       8       -6      4       1
5:       24     -30       20    -10       5     1
6:     -120     144      -90     40     -15     6      1
7:      720    -840      504   -210      70   -21      7    1
8:    -5040    5760    -3360   1344    -420   112    -28    8   1
9:    40320  -45360    25920 -10080    3024  -756    168  -36   9   1
10: -362880  403200  -226800  86400  -25200  6048  -1260  240 -45  10  1
... formatted by _Wolfdieter Lang_, Mar 09 2014
----------------------------------------------------------------------------

Crossrefs

Cf. A002741, A007318, A008275, A008277, A008290, A048993, A055137, A074909, A132440, A238363.

Formula

a(n,k) = (-1)^(n+k-1)*n!/((n-k)*k!) for k
Along the n-th diagonal (n>0) Diag(n,k) = a(n+k,k) = (-1)^(n-1)(n-1)! * A007318(n+k,k).
E.g.f.: (log(1+t)+1)*exp(x*t).
E.g.f. for inverse: exp(x*t)/(log(1+t)+1).
The lowering/annihilation and raising/creation operators for the row polynomials are L=D=d/dx and R=x+1/[(1+D)(1+log(1+D))], i.e., L p(n,x)= n*p(n-1,x) and R p(n,x)= p(n+1,x).
E.g.f. of row sums: (log(1+t)+1)*exp(t). Cf. |row sums-1|=|A002741|.
E.g.f. of unsigned row sums: (-log(1-t)+1)*exp(t). Cf. A002104 + 1.
Let dP = A132440, the infinitesimal generator for the Pascal matrix, I, the identity matrix, and T, this entry's lower triangular matrix, then exp(T-I)=I+dP, i.e., T=I+log(I+dP). Also, ((T-I)n)^n=0, where (T-I)_n denotes the n X n submatrix, i.e., (T-I)_n is nilpotent of order n. - _Tom Copeland, Mar 02 2014
Dividing each subdiagonal by its first element (-1)^(n-1)*(n-1)! yields Pascal's triangle A007318. This is equivalent to multiplying the e.g.f. by exp(t)/(log(1+t)+1). - Tom Copeland, Apr 16 2014
From Tom Copeland, Apr 25 2014: (Start)
A) T = [St1]*[dP]*[St2] + I = [padded A008275]*A132440*A048993 + I
B) = [St1]*[dP]*[St1]^(-1) + I
C) = [St2]^(-1)*[dP]*[St2] + I
D) = [St2]^(-1)*[dP]*[St1]^(-1) + I,
where [St1]=padded A008275 just as [St2]=A048993=padded A008277 and I=identity matrix. Cf. A074909. (End)
From Tom Copeland, Jul 26 2017: (Start)
p_n(x) = (1 + log(1+D)) x^n = (1 + D - D^2/2 + D^3/3- ...) x^n = x^n + n! * Sum_(k=1,..,n) (-1)^(k+1) (1/k) x^(n-k)/(n-k)!.
Unsigned T with the first two diagonals nulled gives an exponential infinitesimal generator M (infinigen) for the rencontres numbers A008290, and negated M gives the infinigen for A055137; i.e., with M = |T| - I - dP = -log(I-dP)-dP, then e^M = e^(-dP) / (I-dP) = lower triangular A008290, and e^(-M) = e^dP (I-dP) = A007318 * (I-dP) = lower triangular A055137. The matrix formulation is consistent with the operator relations e^(-D) / (1-D) x^n = n-th row polynomial of A008290 and e^D (1-D) x^n = n-th row polynomial of A055137. (End)

A269953 Triangle read by rows: T(n, k) = Sum_{j=0..n} binomial(-j-1, -n-1)*S1(j, k) where S1 are the Stirling cycle numbers A132393.

Original entry on oeis.org

1, -1, 1, 1, -1, 1, -1, 2, 0, 1, 1, 0, 5, 2, 1, -1, 9, 15, 15, 5, 1, 1, 35, 94, 85, 40, 9, 1, -1, 230, 595, 609, 315, 91, 14, 1, 1, 1624, 4458, 4844, 2779, 924, 182, 20, 1, -1, 13209, 37590, 43238, 26817, 9975, 2310, 330, 27, 1
Offset: 0

Views

Author

Peter Luschny, Apr 12 2016

Keywords

Comments

Replacing the Stirling cycle numbers in the definition by the Stirling set numbers leads to A105794.
From Wolfdieter Lang, Jun 19 2017: (Start)
The triangle t(n, k) = (-1)^(n-k)*T(n, k) is the matrix product of P = A007318 (Pascal) and s1 = A048994 (signed Stirling1). This is Sheffer (exp(t), log(1+t)).
The present triangle T is therefore the Sheffer triangle (exp(-t), -log(1-t)). Note that P is Sheffer (exp(t), t) (of the Appell type). (End)
The triangle T(n,k) is a representative of the parametric family of triangles T(m,n,k), whose columns are the coefficients of the standard expansion of the function f(x) = (-log(1-x))^(k)*exp(-m*x)/k! for the case m=1. See A381082. - Igor Victorovich Statsenko, Feb 14 2025

Examples

			Triangle starts:
   1;
  -1,  1;
   1, -1,  1;
  -1,  2,  0,  1;
   1,  0,  5,  2,  1;
  -1,  9, 15, 15,  5,  1;
   1, 35, 94, 85, 40,  9,  1.

Links

Crossrefs

Columns k=0..4 give A033999, A002741, A381064, A381065, A381066.
Cf. A000166 (row sums), A080956 (diag n,n-1).
Cf. A105793, A105794, A132393, A007318, A048994.
Cf. A001339, A046716, A082030, A095000, A137346.
KummerU(-n,1-n-x,z): this sequence (z=-1), A094816 (z=1), |A137346| (z=2), A327997 (z=3).

Programs

  • Maple
    A269953 := (n,k) -> add(binomial(-j-1,-n-1)*abs(Stirling1(j,k)), j=0..n):
seq(print(seq(A269953(n, k), k=0..n)), n=0..9);
# Alternative:
egf := exp(-t)*(1-t)^(-x): ser := series(egf, t, 12): p := n -> coeff(ser, t, n):
seq(n!*seq(coeff(p(n), x, k), k=0..n), n=0..9); # Peter Luschny, Oct 28 2019
  • Mathematica
    Flatten[Table[Sum[Binomial[-j-1,-n-1] Abs[StirlingS1[j,k]], {j,0,n}], {n,0,9},{k,0,n}]]
(* Or: *)
p [n_] := HypergeometricU[-n, 1 - n - x, -1];
Table[CoefficientList[p[n], x], {n, 0, 9}] (* Peter Luschny, Oct 28 2019 *)

Formula

From Wolfdieter Lang, Jun 19 2017: (Start)
E.g.f. of row polynomials R(n, x) = Sum_{k=0..n} T(n,k)*x^k: exp(-t)/(1 - t)^x.
E.g.f. of column k sequence: exp(-x)*(-log(1-x))^k/k!, k >= 0. (End)
From Peter Bala, Oct 26 2019: (Start)
Let R(n, x) = (-1)^n*Sum_{k >= 0} binomial(n,k)*k!* binomial(-x,k) the n-th row polynomial of this triangle.
R(n, x) = c_n(-x;-1), where c_n(x;a) denotes the n-th Poisson Charlier polynomial.
The series representation e = Sum_{k >= 0} 1/k! is the case n = 0 of the more general result e = n!*Sum_{k >= 0} 1/(k!*R(n,k)*R(n,k+1)), n = 0,2,3,4,.... (End)
R(n, x) = KummerU(-n, 1-n-x, -1). - Peter Luschny, Oct 28 2019

A002745 Sum of logarithmic numbers.

Original entry on oeis.org

1, 5, 20, 96, 469, 3145, 20684, 173544, 1557105, 16215253, 159346604, 2230085528, 26985045333, 368730610729, 5628888393652, 97987283458928, 1475486672174337, 29097611462122437, 505383110562327268, 10970329921706735216
Offset: 1

Views

Author

N. J. A. Sloane

Keywords

References

  • J. M. Gandhi, On logarithmic numbers, Math. Student, 31 (1963), 73-83.
  • Jeffrey Shallit, personal communication.
  • 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. A000203, A002743.

Programs

  • Mathematica
    Table[Sum[Binomial[n,k] * DivisorSigma[1,k] * (k-1)!, {k, 1, n}], {n, 1, 20}] (* Vaclav Kotesovec, Dec 16 2019 *)
  • PARI
    a(n) = sum(k=1, n, sigma(k)*(k-1)!*binomial(n, k)); \\ Michel Marcus, May 13 2020

Formula

a(n) = Sum_{k=1..n} A000203(k)*(k-1)!*binomial(n, k). - Vladeta Jovovic, Feb 09 2003
E.g.f.: exp(x) * Sum_{k>=1} x^k / (k*(1 - x^k)). - Ilya Gutkovskiy, Dec 11 2019
a(p) == -1 (mod p) for prime p. The pseudoprimes of this congruence are 30, 858, 1722, ... - Amiram Eldar, May 13 2020

Extensions

More terms from Vladeta Jovovic, Feb 09 2003

A002746 Sum of logarithmic numbers.

Original entry on oeis.org

1, 4, 13, 50, 203, 1154, 6627, 49356, 403293, 3858376, 33929377, 460614670, 5168544119, 64518640406, 946910125319, 16124114481720, 221243980745433, 4261440137319852, 68524390012831189, 1477309421907315082
Offset: 1

Views

Author

N. J. A. Sloane

Keywords

References

  • J. M. Gandhi, On logarithmic numbers, Math. Student, 31 (1963), 73-83.
  • 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. A000005, A002744, A318249.

Programs

  • Mathematica
    Table[Sum[Binomial[n,k] * DivisorSigma[0,k] * (k-1)!, {k, 1, n}], {n, 1, 20}] (* Vaclav Kotesovec, Dec 16 2019 *)
  • PARI
    a(n) = sum(k=1, n, numdiv(k)*(k-1)!*binomial(n, k)); \\ Michel Marcus, May 13 2020

Formula

a(n) = Sum_{k=1..n} A000005(k)*(k-1)!*binomial(n, k). - Vladeta Jovovic, Feb 09 2003
E.g.f.: -exp(x) * log(Product_{k>=1} (1 - x^k)^(1/k)). - Ilya Gutkovskiy, Dec 11 2019
a(p) == -2 (mod p) for prime p. The pseudoprimes of this congruence are 4, 12, 30, 380, 858, 1722 ... - Amiram Eldar, May 13 2020

Extensions

Corrected and extended by Jeffrey Shallit
More terms from Vladeta Jovovic, Feb 09 2003
Showing 1-10 of 36 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.