A068106 -id:A068106 - cp's OEIS frontend

A000255 a(n) = na(n-1) + (n-1)a(n-2), a(0) = 1, a(1) = 1.

1, 1, 3, 11, 53, 309, 2119, 16687, 148329, 1468457, 16019531, 190899411, 2467007773, 34361893981, 513137616783, 8178130767479, 138547156531409, 2486151753313617, 47106033220679059, 939765362752547227, 19690321886243846661, 432292066866171724421

Offset: 0

N. J. A. Sloane

a(n) counts permutations of [1,...,n+1] having no substring [k,k+1]. - Len Smiley, Oct 13 2001
Also, for n > 0, determinant of the tridiagonal n X n matrix M such that M(i,i)=i and for i=1..n-1, M(i,i+1)=-1, M(i+1,i)=i. - Mario Catalani (mario.catalani(AT)unito.it), Feb 04 2003
Also, for n > 0, maximal permanent of a nonsingular n X n (0,1)-matrix, which is achieved by the matrix with just n-1 0's, all on main diagonal. [For proof, see next entry.] - W. Edwin Clark, Oct 28 2003
Proof from Richard Brualdi and W. Edwin Clark, Nov 15 2003: Let n >= 4. Take an n X n (0,1)-matrix A which is nonsingular. It has t >= n-1, 0's, otherwise there will be two rows of all 1's. Let B be the matrix obtained from A by replacing t-(n-1) of A's 0's with 1's. Let D be the matrix with all 1's except for 0's in the first n-1 positions on the diagonal. This matrix is easily seen to be non-singular. Now we have per(A) < = per(B) < = per (D), where the first inequality follows since replacing 0's by 1's cannot decrease the permanent and the second from Corollary 4.4 in the Brualdi et al. reference, which shows that per(D) is the maximum permanent of ANY n X n matrix with n -1 0's. Corollary 4.4 requires n >= 4. a(n) for n < 4 can be computed directly.
With offset 1, permanent of (0,1)-matrix of size n X (n+d) with d=1 and n zeros not on a line. This is a special case of Theorem 2.3 of Seok-Zun Song et al., Extremes of permanents of (0,1)-matrices, pp. 201-202. - Jaap Spies, Dec 12 2003
Number of fixed-point-free permutations of n+2 that begin with a 2; e.g., for 1234, we have 2143, 2341, 2413, so a(2)=3. Also number of permutations of 2..n+2 that have no agreements with 1..n+1. E.g., for 123 against permutations of 234, we have 234, 342 and 432. Compare A047920. - Jon Perry, Jan 23 2004. [This can be proved by the standard argument establishing that d(n+2) = (n+1)(d(n+1)+d(n)) for derangements A000166 (n+1 choices of where 1 goes, then either 1 is in a transposition, or in a cycle of length at least 3, etc.). - D. G. Rogers, Aug 28 2006]
Stirling transform of A006252(n+1)=[1,1,2,4,14,38,...] is a(n)=[1,3,11,53,309,...]. - Michael Somos, Mar 04 2004
a(n+1) is the sequence of numerators of the self-convergents to 1/(e-2); see A096654. - Clark Kimberling, Jul 01 2004
Euler's interpretation was "fixedpoint-free permutations beginning with 2" and he listed the terms up to 148329 (although he was blind at the time). - Don Knuth, Jan 25 2007
Equals lim_{k->infinity} A153869^k. - Gary W. Adamson, Jan 03 2009
Hankel transform is A059332. - Paul Barry, Apr 22 2009
This sequence appears in the analysis of Euler's divergent series 1 - 1! + 2! - 3! + 4! ... by Lacroix, see Hardy. For information about this and related divergent series see A163940. - Johannes W. Meijer, Oct 16 2009
a(n), n >= 1, enumerates also the ways to distribute n beads, labeled differently from 1 to n, over a set of (unordered) necklaces, excluding necklaces with exactly one bead, and one open cord allowed to have any number of beads. Each beadless necklace as well as the beadless cord contributes a factor 1 in the counting, e.g., a(0):=1*1=1. There are k! possibilities for the cord with k>=0 beads, which means that the two ends of the cord should be considered as fixed, in short: a fixed cord. This produces for a(n) the exponential (aka binomial) convolution of the sequences {n!=A000142(n)} and the subfactorials {A000166(n)}.
See the formula below. Alternatively, the e.g.f. for this problem is seen to be (exp(-x)/(1-x))*(1/(1-x)), namely the product of the e.g.f.s for the subfactorials (from the unordered necklace problem, without necklaces with exactly one bead) and the factorials (from the fixed cord problem). Therefore the recurrence with inputs holds also. 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 02 2010
a(n) = (n-1)a(n-1) + (n-2)a(n-2) gives the same sequence offset by a 1. - Jon Perry, Sep 20 2012
Also, number of reduced 2 X (n+2) Latin rectangles. - A.H.M. Smeets, Nov 03 2013
Second column of Euler's difference table (second diagonal in example of A068106). - Enrique Navarrete, Dec 13 2016
If we partition the permutations of [n+2] in A000166 according to their starting digit, we will get (n+1) equinumerous classes each of size a(n) (the class starting with the digit 1 is empty since no derangement starts with 1). Hence, A000166(n+2)=(n+1)*a(n), so a(n) is the size of each nonempty class of permutations of [n+2] in A000166. For example, for n=3 we have 44=4*11 (see link). - Enrique Navarrete, Jan 11 2017
For n >= 1, the number of circular permutations (in cycle notation) on [n+2] that avoid substrings (j,j+2), 1 <= j <= n.  For example, for n=2, the 3 circular permutations in S4 that avoid substrings {13,24} are (1234),(1423),(1432). Note that each of these circular permutations represent 4 permutations in one-line notation (see link 2017). - Enrique Navarrete, Feb 15 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) holding for all n and k, which in turn is easily proved by induction making use of the given recurrences. - Peter Bala, Nov 21 2017
Number of permutations of [n] where the k-th fixed points are k-colored and all other points are unicolored. - Alois P. Heinz, Apr 28 2025

			a(3)=11: 1 3 2 4; 1 4 3 2; 2 1 4 3; 2 4 1 3; 3 2 1 4; 3 2 4 1; 4 1 3 2; 4 2 1 3; 4 3 2 1; 2 4 3 1; 3 1 4 2. The last two correspond to (n-1)*a(n-2) since they contain a [j,n+1,j+1].
Cord-necklaces problem. For n=4 one considers the following weak two part compositions of 4: (4,0), (2,2), (1,3), and (0,4), where (3,1) does not appear because there are no necklaces with 1 bead. These compositions contribute respectively 4!*1, (binomial(4,2)*2)*sf(2), (binomial(4,1)*1)*sf(3), and 1*sf(4) with the subfactorials sf(n):=A000166(n) (see the necklace comment there). This adds up as 24 + 6*2 + 4*2 + 9 = 53 = a(4). - _Wolfdieter Lang_, Jun 02 2010
G.f. = 1 + x + 3*x^2 + 11*x^3 + 53*x^4 + 309*x^5 + 2119*x^6 + 16687*x^7 + ...

Richard A. Brualdi and Herbert J. Ryser, Combinatorial Matrix Theory, Camb. Univ. Press, 1991, Section 7.2, p. 202.
Charalambos A. Charalambides, Enumerative Combinatorics, Chapman & Hall/CRC, Boca Raton, Florida, 2002, p. 179, Table 5.4 and p. 177 (5.1).
CRC Handbook of Combinatorial Designs, 1996, p. 104.
F. N. David, M. G. Kendall and D. E. Barton, Symmetric Function and Allied Tables, Cambridge, 1966, pp. 263-264. See Table 7.5.1, row 0; also Table 7.6.1, row 0.
John Riordan, An Introduction to Combinatorial Analysis, Wiley, 1958, p. 188.
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).
N. Ya. Vilenkin, Combinatorics, pp. 54 - 56, Academic Press, 1971. Caravan in the Desert, E_n = a(n-1), n >= 1.

T. D. Noe, Table of n, a(n) for n=0..100
M. H. Albert, M. D. Atkinson, and Robert Brignall, Permutation Classes of Polynomial Growth, arXiv:math/0603315 [math.CO], 2006-2007; Annals of Combinatorics 11 (2007) 249-264.
Per Alexandersson and Frether Getachew, An involution on derangements, arXiv:2105.08455 [math.CO], 2021.
Roland Bacher, Counting Packings of Generic Subsets in Finite Groups, Electr. J. Combinatorics, Vol. 19 (2012), Article P7. - From _N. J. A. Sloane_, Feb 06 2013
Barry Balof and Helen Jenne, Tilings, Continued Fractions, Derangements, Scramblings, and e, Journal of Integer Sequences, Vol. 17 (2014), Article 14.2.7.
Robert Brignall, Vít Jelínek, Jan Kynčl, and David Marchant, Zeros of the Möbius function of permutations, arXiv:1810.05449 [math.CO], 2018.
Richard A. Brualdi, John L. Goldwasser, and T. S. Michael, Maximum permanents of matrices of zeros and ones, J. Combin. Theory Ser. A 47 (1988), 207-245.
Giulio Cerbai and Luca Ferrari, Permutation patterns in genome rearrangement problems, arXiv:1808.02653 [math.CO], 2018. See p. 126.
Shane Chern, Lin Jiu, and Italo Simonelli, A central limit theorem for a card shuffling problem, arXiv:2309.08841 [math.PR], 2023.
Leonhard Euler, Recherches sur une nouvelle espèce des quarrés magiques, Verhandelingen uitgegeven door het zeeuwsch Genootschap der Wetenschappen te Vlissingen, 9 (1782), 85-239, on page 235 in section 152. This is paper E530 in Enestrom's index of Euler's works. The sequence appears on page 389 of Euler's Opera Omnia, series I, volume 7. [From D. E. Knuth]
Uriel Feige, Tighter bounds for online bipartite matching, 2018.
Philip Feinsilver and John McSorley, Zeons, Permanents, the Johnson Scheme, and Generalized Derangements, International Journal of Combinatorics, Volume 2011, Article ID 539030, 29 pages; doi:10.1155/2011/539030.
Philippe Flajolet and Robert Sedgewick, Analytic Combinatorics, 2009; see page 373.
Hannah Golab, Pattern avoidance in Cayley permutations, Master's Thesis, Northern Arizona Univ. (2024). See p. 36.
G. H. Hardy, Divergent Series, Oxford University Press, 1949. p. 29.
Florian Herzig, Problem 2330, Crux Mathematicorum, Vol. 24, No. 3 (1998), p. 176; Solution to Problem 2330, by Con Amore Problem Group, ibid., Vol. 25, No. 3 (1999), pp. 183-185.
F. Hivert, J.-C. Novelli and J.-Y. Thibon, Commutative combinatorial Hopf algebras, arXiv:math/0605262 [math.CO], 2006.
Brian Hopkins, Euler's Enumerations, Enumerative Combinatorics and Applications, Vol. 1, No. 1 (2021), Article #S1H1.
Helen K. Jenne, Proofs you can count on, Honors Thesis, Math. Dept., Whitman College, 2013.
G. Kreweras, The number of more or less "regular" permutations, Fib. Quart., Vol. 18, No. 3 (1980), pp. 226-229.
Ajay Kumar and Chanchal Kumar, Monomial ideals induced by permutations avoiding patterns, 2018.
Toufik Mansour and Mark Shattuck, Counting permutations by the number of successors within cycles, Discr. Math., Vol. 339, No. 4 (2016), pp. 1368-1376.
A. N. Myers, Counting permutations by their rigid patterns, J. Combin. Theory, Series A, Vol. 99, No. 2 (2002), pp. 345-357.
Enrique Navarrete, Forbidden Patterns and the Alternating Derangement Sequence, arXiv:1610.01987 [math.CO], 2016.
Enrique Navarrete, Forbidden Substrings in Circular K-Successions, arXiv:1702.02637 [math.CO], 2017.
Luis Manuel Rivera, Integer sequences and k-commuting permutations, arXiv preprint arXiv:1406.3081 [math.CO], 2014.
D. P. Roselle, Permutations by number of rises and successions, Proc. Amer. Math. Soc., Vol. 19, No. 1 (1968), pp. 8-16.
D. P. Roselle, Permutations by number of rises and successions, Proc. Amer. Math. Soc., Vol. 19, No. 1 (1968), pp. 8-16. [Annotated scanned copy]
Max Rumney and E. J. F. Primrose, A sequence connected with the subfactorial sequence, Note 3207, Math. Gaz., Vol. 52, No. 382 (1968), pp. 381-382.
Max Rumney and E. J. F. Primrose, A sequence connected with the subfactorial sequence, Note 3207, Math. Gaz., Vol. 52, No. 382 (1968), pp. 381-382. [Annotated scanned copy]
Isaac Sofair, Derangement revisited, Math. Gazette, Vol. 97, No. 540 (2013), pp. 435-440.
Seok-Zun Song et al., Extremes of permanents of (0,1)-matrices, Lin. Algebra and its Applic., Vol. 373 (2003), pp. 197-210.
Jun Yan, Results on pattern avoidance in parking functions, arXiv:2404.07958 [math.CO], 2024. See p. 5.

Row sums of triangle in A046740. A diagonal of triangle in A068106.
Cf. A000153, A000166, A000261, A001909, A001910, A055790.
Cf. A090010, A090012, A090013, A090014, A090015, A090016.
A052655 gives occurrence count for non-singular (0, 1)-matrices with maximal permanent, A089475 number of different values of permanent, A089480 occurrence counts for permanents all non-singular (0, 1)-matrices, A087982, A087983.
A diagonal in triangle A010027.
Cf. A153869, A159610, A002469.
a(n) = A086764(n+1,1).

a000255 n = a000255_list !! n
a000255_list = 1 : 1 : zipWith (+) zs (tail zs) where
   zs = zipWith (*) [1..] a000255_list
-- Reinhard Zumkeller, Dec 05 2011

I:=[1, 3]; [1] cat  [n le 2 select I[n] else n*Self(n-1)+(n-1)*Self(n-2): n in [1..30]]; // Vincenzo Librandi, Aug 09 2018

a := n -> hypergeom([2,-n], [], 1)*(-1)^n:
seq(simplify(a(n)), n=0..19); # Peter Luschny, Sep 20 2014
seq(simplify(KummerU(-n, -n-1, -1)), n=0..21); # Peter Luschny, May 10 2022

c = CoefficientList[Series[Exp[ -z]/(1 - z)^2, {z, 0, 30}], z]; For[n = 0, n < 31, n++; Print[c[[n]]*(n - 1)! ]]
Table[Subfactorial[n] + Subfactorial[n + 1], {n, 0, 20}] (* Zerinvary Lajos, Jul 09 2009 *)
RecurrenceTable[{a[n]==n a[n-1]+(n-1)a[n-2],a[0]==1,a[1]==1},a[n], {n,20}] (* Harvey P. Dale, May 10 2011 *)
a[ n_] := If[ n < 0, 0, Round[ n! (n + 2) / E]] (* Michael Somos, Jun 01 2013 *)
a[ n_] := If[ n < 0, 0, n! SeriesCoefficient[ Exp[ -x] / (1 - x)^2, {x, 0, n}]] (* Michael Somos, Jun 01 2013 *)
a[ n_] := If[ n < 0, 0, (-1)^n HypergeometricPFQ[ {- n, 2}, {}, 1]] (* Michael Somos, Jun 01 2013 *)
sa[k_Integer]/;k>=2 := SparseArray[{{i_, i_} -> i, Band[{2, 1}] -> -1, {i_, j_} /; (i == j - 1) :> i}, {k, k}]; {1, 1}~Join~Array[Det[sa[#]] &, 20, 2] (* Shenghui Yang, Oct 15 2024 *)

{a(n) = if( n<0, 0, contfracpnqn( matrix( 2, n, i, j, j - (i==1)))[1, 1])};

{a(n) = if( n<0, 0, n! * polcoeff( exp( -x + x * O(x^n)) / (1 - x)^2, n))};

from sage.combinat.sloane_functions import ExtremesOfPermanentsSequence2
e = ExtremesOfPermanentsSequence2()
it = e.gen(1,1,1)
[next(it) for i in range(20)]
# Zerinvary Lajos, May 15 2009

E.g.f.: exp(-x)/(1-x)^2.
a(n) = Sum_{k=0..n} (-1)^k * (n-k+1) * n!/k!. - Len Smiley
Inverse binomial transform of (n+1)!. - Robert A. Stump (bee_ess107(AT)yahoo.com), Dec 09 2001
a(n-2) = !n/(n - 1) where !n is the subfactorial of n, A000166(n). - Lekraj Beedassy, Jun 18 2002
a(n) = floor((1/e)*n!*(n+2)+1/2). - Benoit Cloitre, Jan 15 2004
Apparently lim_{n->infinity} log(n) - log(a(n))/n = 1. - Gerald McGarvey, Jun 12 2004
a(n) = (n*(n+2)*a(n-1) + (-1)^n)/(n+1) for n >= 1, a(0)=1. See the Charalambides reference.
a(n) = GAMMA(n+3,-1)*exp(-1)/(n+1) (incomplete Gamma function). - Mark van Hoeij, Nov 11 2009
a(n) = A000166(n) + A000166(n+1).
A002469(n) = (n-2)*a(n-1) + A000166(n). - Gary W. Adamson, Apr 17 2009
If we take b(n) = (-1)^(n+1)*a(n) for n > 0, then for n > 1 the arithmetic mean of the first n terms is -b(n-1). - Franklin T. Adams-Watters, May 20 2010
a(n) = hypergeometric([2,-n],[],1)*(-1)^n = KummerU(2,3+n,-1)*(-1)^n. See the Abramowitz-Stegun handbook (for the reference see e.g. A103921) p. 504, 13.1.10, and for the recurrence p. 507, 13.4.16. - Wolfdieter Lang, May 20 2010
a(n) = n!*(1 + Sum_{k=0..n-2} sf(n-k)/(n-k)!) with the subfactorials sf(n):= A000166(n) (this follows from the exponential convolution). - Wolfdieter Lang, Jun 02 2010
a(n) = 1/(n+1)*floor(((n+1)!+1)/e). - Gary Detlefs, Jul 11 2010
a(n) = (Subfactorial(n+2))/(n+1). - Alexander R. Povolotsky, Jan 26 2011
G.f.: 1/(1-x-2x^2/(1-3x-6x^2/(1-5x-12x^2/(1-7x-20x^2/(1-.../(1-(2n+1)x-(n+1)(n+2)x^2/(1-... (continued fraction). - Paul Barry, Apr 11 2011
G.f.: hypergeom([1,2],[],x/(x+1))/(x+1). - Mark van Hoeij, Nov 07 2011
From Sergei N. Gladkovskii, Sep 24 2012 - Feb 05 2014: (Start)
Continued fractions:
E.g.f. 1/E(0) where E(k) = 1 - 2*x/(1 + x/(2 - x - 2/(1 + x*(k+1)/E(k+1)))).
G.f.: S(x)/x - 1/x = Q(0)/x - 1/x where S(x) = Sum_{k>=0} k!*(x/(1+x))^k, 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 + x - x*(k+2)/(1 - x*(k+1)/Q(k+1)).
G.f.: 1/x/Q(0) where Q(k) = 1/x - (2*k+1) - (k+2)*(k+1)/Q(k+1).
G.f.: (1+x)/(x*Q(0)) - 1/x where Q(k) = 1 - 2*k*x - x^2*(k + 1)^2/Q(k+1).
G.f.: 2/x/G(0) - 1/x where G(k) = 1 + 1/(1 - x*(2*k+2)/(x*(2*k+1) - 1 + x*(2*k+2)/ G(k+1))).
G.f.: ((Sum_{k>=0} k!*(x/(1+x))^k) - 1)/x = Q(0)/(2*x) - 1/x where Q(k) = 1 + 1/(1 - x*(k+1)/(x*(k+1) + (1+x)/Q(k+1))).
G.f.: W(0) where W(k) = 1 - x*(k+1)/(x*(k+1) - 1/(1 - x*(k+2)/(x*(k+1) - 1/W(k+1)))).
G.f.: G(0)/(1-x) where G(k) = 1 - x^2*(k+1)*(k+2)/(x^2*(k+1)*(k+2) - (1-x*(1+2*k))*(1-x*(3+2*k))/G(k+1)). (End)
From Peter Bala, Sep 20 2013: (Start)
The sequence b(n) := n!*(n + 2) satisfies the defining recurrence for a(n) but with the starting values b(0) = 2 and b(1) = 3. This leads to the finite continued fraction expansion a(n) = n!*(n+2)*( 1/(2 + 1/(1 + 1/(2 + 2/(3 + ... + (n-1)/n)))) ), valid for n >= 2.
Also a(n) = n!*(n+2)*( Sum_{k = 0..n} (-1)^k/(k+2)! ). Letting n -> infinity gives the infinite continued fraction expansion 1/e = 1/(2 + 1/(1 + 1/(2 + 2/(3 + ... + (n-1)/(n + ...)))) ) due to Euler. (End)
0 = a(n)*(+a(n+1) + 2*a(n+2) - a(n+3)) + a(n+1)*(+2*a(n+2) - a(n+3)) + a(n+2)*(+a(n+2)) if n >= 0. - Michael Somos, May 06 2014
a(n-3) = (n-2)*A000757(n-2) + (2*n-5)*A000757(n-3) + (n-3)*A000757(n-4), n >= 3. - Luis Manuel Rivera Martínez, Mar 14 2015
a(n) = A000240(n) + A000240(n+1), n >= 1. Let D(n) = A000240(n) be the permutations of [n] having no substring in {12,23,...,(n-1)n,n1}. Let d(n) = a(n-1) be the permutations of [n] having no substring in {12,23,...,(n-1)n}. Let d_n1 = A000240(n-1) be the permutations of [n] that have the substring n1 but no substring in {12,23,...,(n-1)n}. Then the link "Forbidden Patterns" shows the bijection d_n1 ~ D(n-1) and since dn = d_n1 U D(n), we get dn = D(n-1) U D(n). Taking cardinalities we get the result for n-1, i.e., a(n-1) = A000240(n-1) + A000240(n). For example, for n=4 in this last equation, we get a(4) = 11 = 3+8. - Enrique Navarrete, Jan 16 2017
a(n) = (n+1)!*hypergeom([-n], [-n-1], -1). - Peter Luschny, Nov 02 2018
Sum_{n>=0} (-1)^n*n!/(a(n)*a(n+1)) = e - 2 (Herzig, 1998). - Amiram Eldar, Mar 07 2022
a(n) = KummerU(-n, -n - 1, -1). - Peter Luschny, May 10 2022

A002467 The game of Mousetrap with n cards (given n letters and n envelopes, how many ways are there to fill the envelopes so that at least one letter goes into its right envelope?).

Original entry on oeis.org

0, 1, 1, 4, 15, 76, 455, 3186, 25487, 229384, 2293839, 25232230, 302786759, 3936227868, 55107190151, 826607852266, 13225725636255, 224837335816336, 4047072044694047, 76894368849186894, 1537887376983737879, 32295634916658495460, 710503968166486900119

Offset: 0

N. J. A. Sloane, Jeffrey Shallit

a(n) is the number of permutations in the symmetric group S_n that have a fixed point, i.e., they are not derangements (A000166). - Ahmed Fares (ahmedfares(AT)my-deja.com), May 08 2001
a(n+1)=p(n+1) where p(x) is the unique degree-n polynomial such that p(k)=k! for k=0,1,...,n. - Michael Somos, Oct 07 2003
The termwise sum of this sequence and A000166 gives the factorial numbers. - D. G. Rogers, Aug 26 2006, Jan 06 2008
a(n) is the number of deco polyominoes of height n and having in the last column an odd 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. Example: a(2)=1 because the horizontal domino is the only deco polyomino of height 2 having an odd number of cells in the last column. - Emeric Deutsch, May 08 2008
Starting (1, 4, 15, 76, 455, ...) = eigensequence of triangle A127899 (unsigned). - Gary W. Adamson, Dec 29 2008
(n-1) | a(n), hence a(n) is never prime. - Jonathan Vos Post, Mar 25 2009
a(n) is the number of permutations of [n] that have at least one fixed point = number of positive terms in n-th row of the triangle in A170942, n > 0. - Reinhard Zumkeller, Mar 29 2012
Numerator of partial sum of alternating harmonic series, provided that the denominator is n!. - Richard Locke Peterson, May 11 2020
a(n) is the number of terms in the polynomial expansion of the determinant of a n X n matrix that contains at least one diagonal element. - Adam Wang, May 28 2025

			G.f. = x + x^2 + 4*x^3 + 15*x^4 + 76*x^5 + 455*x^6 + 3186*x^7 + 25487*x^8 + ...

R. K. Guy, Unsolved Problems Number Theory, E37.
R. K. Guy and R. J. Nowakowski, "Mousetrap," in D. Miklos, V. T. Sos and T. Szonyi, eds., Combinatorics, Paul Erdős is Eighty. Bolyai Society Math. Studies, Vol. 1, pp. 193-206, 1993.
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).

Alois P. Heinz, Table of n, a(n) for n = 0..450 (first 101 terms from T. D. Noe)
E. Barcucci, A. Del Lungo and R. Pinzani, "Deco" polyominoes, permutations and random generation, Theoretical Computer Science, 159, 1996, 29-42.
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.
Sergi Elizalde, Bijections for restricted inversion sequences and permutations with fixed points, arXiv:2006.13842 [math.CO], 2020.
R. K. Guy, Letter to N. J. A. Sloane, Feb 10 1993
R. K. Guy and R. J. Nowakowski, Mousetrap, Preprint, Feb 10 1993 [Annotated scanned copy]
R. K. Guy and S. Washburn, Correspondence, Nov. - Dec. 1991
T. Kotek, J. A. Makowsky, Recurrence Relations for Graph Polynomials on Bi-iterative Families of Graphs, arXiv preprint arXiv:1309.4020 [math.CO], 2013.
J. Metzger, Email to N. J. A. Sloane, Apr 30 1991
Daniel J. Mundfrom, A problem in permutations: the game of 'Mousetrap', European J. Combin. 15 (1994), no. 6, 555-560.
Alexsandar Petojevic, The Function vM_m(s; a; z) and Some Well-Known Sequences, Journal of Integer Sequences, Vol. 5 (2002), Article 02.1.7.
Simon Plouffe, Exact formulas for Integer Sequences.
A. Steen, Some formulas respecting the game of mousetrap, Quart. J. Pure Applied Math., 15 (1878), 230-241.
L. Takacs, The Problem of Coincidences, Archive for History of Exact Sciences, Volume 21, No. 3, Sept. 1980. pp 229-244, paragraphs 5 and 7.
Eric Weisstein's World of Mathematics, Mousetrap

Cf. A002468, A002469, A028306, A047920, A052169, A127899, A276975.
Row sums of A068106.
Column k=1 of A293211.
Column k=0 of A299789, A306234, and of A324362.

a := proc(n) -add((-1)^i*binomial(n, i)*(n-i)!, i=1..n) end;
a := n->-n!*add((-1)^k/k!, k=1..n): seq(a(n), n=0..20); # Zerinvary Lajos, May 25 2007
a := n -> simplify(GAMMA(n+1) - GAMMA(n+1, -1)*exp(-1)):
seq(a(n), n=0..20); # Peter Luschny, Feb 28 2017

Denominator[k=1; NestList[1+1/(k++ #1)&,1,12]] (* Wouter Meeussen, Mar 24 2007 *)
a[ n_] := If[ n < 0, 0, n! - Subfactorial[n]] (* Michael Somos, Jan 25 2014 *)
a[ n_] := If[ n < 1, 0, n! - Round[ n! / E]] (* Michael Somos, Jan 25 2014 *)
a[ n_] := If[ n < 0, 0, n! - (-1)^n HypergeometricPFQ[ {- n, 1}, {}, 1]](* Michael Somos, Jan 25 2014 *)
a[ n_] := If[ n < 0, 0, n! SeriesCoefficient[ (1 - Exp[ -x] ) / (1 - x), {x, 0, n}]] (* Michael Somos, Jan 25 2014 *)
RecurrenceTable[{a[n] == (n - 1) ( a[n - 1] + a[n - 2]), a[0] == 0, a[1] == 1}, a[n], {n, 20}] (* Ray Chandler, Jul 30 2015 *)

{a(n) = if( n<1, 0, n * a(n-1) - (-1)^n)} /* Michael Somos, Mar 24 2003 */

{a(n) = if( n<0, 0, n! * polcoeff( (1 - exp( -x + x * O(x^n))) / (1 - x), n))} /* Michael Somos, Mar 24 2003 */

a(n) = if(n<1,0,subst(polinterpolate(vector(n,k,(k-1)!)),x,n+1))

A002467(n) = if(n<1, 0, n*A002467(n-1)-(-1)^n); \\ Joerg Arndt, Apr 22 2013

a(n) = n! - A000166(n) = A000142(n) - A000166(n).
E.g.f.: (1 - exp(-x)) / (1 - x). - Michael Somos, Aug 11 1999
a(n) = (n-1)*(a(n-1) + a(n-2)), n > 1; a(1) = 1. - Michael Somos, Aug 11 1999
a(n) = n*a(n-1) - (-1)^n. - Michael Somos, Aug 11 1999
a(0) = 0, a(n) = floor(n!(e-1)/e + 1/2) for n > 0. - Michael Somos, Aug 11 1999
a(n) = - n! * Sum_{i=1..n} (-1)^i/i!. Limit_{n->infinity} a(n)/n! = 1 - 1/e. - Gerald McGarvey, Jun 08 2004
Inverse binomial transform of A002627. - Ross La Haye, Sep 21 2004
a(n) = (n-1)*(a(n-1) + a(n-2)), n > 1. - Gary Detlefs, Apr 11 2010
a(n) = n! - floor((n!+1)/e), n > 0. - Gary Detlefs, Apr 11 2010
For n > 0, a(n) = {(1-1/exp(1))*n!}, where {x} is the nearest integer. - Simon Plouffe, conjectured March 1993, added Feb 17 2011
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) = Gamma(n+1) - Gamma(n+1, -1)*exp(-1). - Peter Luschny, Feb 28 2017
a(n) = Sum_{k=0..n-1} A047920(n-1,k). - Alois P. Heinz, Sep 01 2021

A047920 Triangular array formed from successive differences of factorial numbers.

Original entry on oeis.org

1, 1, 0, 2, 1, 1, 6, 4, 3, 2, 24, 18, 14, 11, 9, 120, 96, 78, 64, 53, 44, 720, 600, 504, 426, 362, 309, 265, 5040, 4320, 3720, 3216, 2790, 2428, 2119, 1854, 40320, 35280, 30960, 27240, 24024, 21234, 18806, 16687, 14833, 362880, 322560

Offset: 0

N. J. A. Sloane

Number of permutations of 1,2,...,k,n+1,n+2,...,2n-k that have no agreements with 1,...,n. For example, consider 1234 and 1256, then n=4 and k=2, so T(4,2)=14. Compare A000255 for the case k=1. - Jon Perry, Jan 23 2004
From Emeric Deutsch, Apr 21 2009: (Start)
T(n-1,k-1) is the number of non-derangements of {1,2,...,n} having smallest fixed point equal to k. Example: T(3,1)=4 because we have 4213, 4231, 3214, and 3241 (the permutations of {1,2,3,4} having smallest fixed equal to 2).
Row sums give the number of non-derangement permutations of {1,2,...,n} (A002467).
Mirror image of A068106.
Closely related to A134830, where each row has an extra term (see the Charalambides reference).
(End)
T(n,k) is the number of permutations of {1..n} that don't fix the points 1..k. - Robert FERREOL, Aug 04 2016

			Triangle begins:
    1;
    1,  0;
    2,  1,  1;
    6,  4,  3,  2;
   24, 18, 14, 11,  9;
  120, 96, 78, 64, 53, 44;
  ...
The left-hand column is the factorial numbers (A000142). The other numbers in the row are calculated by subtracting the numbers in the previous row. For example, row 4 is 6, 4, 3, 2, so row 5 is 4! = 24, 24 - 6 = 18, 18 - 4 = 14, 14 - 3 = 11, 11 - 2 = 9. - _Michael B. Porter_, Aug 05 2016

Ch. A. Charalambides, Enumerative Combinatorics, Chapman & Hall/CRC, Boca Raton, Florida, 2002, p. 176, Table 5.3. [From Emeric Deutsch, Apr 21 2009]

Reinhard Zumkeller, Rows n = 0..150 of triangle, flattened
E. Deutsch and S. Elizalde, The largest and the smallest fixed points of permutations, arXiv:0904.2792 [math.CO], 2009.
J. D. H. Dickson, Discussion of two double series arising from the number of terms in determinants of certain forms, Proc. London Math. Soc., 10 (1879), 120-122. [Annotated scanned copy]
J. D. H. Dickson, Discussion of two double series arising from the number of terms in determinants of certain forms, Proc. London Math. Soc., 10 (1879), 120-122.
Ira M. Gessel, Symmetric inclusion-exclusion, Séminaire Lotharingien de Combinatoire, B54b (2005).
Peter Kagey, Ranking and Unranking Restricted Permutations, arXiv:2210.17021 [math.CO], 2022.
Index entries for sequences related to factorial numbers

Columns give A000142, A001563, A001564, etc. Cf. A047922.
See A068106 for another version of this triangle.
Orthogonal columns: A000166, A000255, A055790. Main diagonal A033815.
Cf. A002467, A068106, A134830. - Emeric Deutsch, Apr 21 2009
Cf. A155521.
T(n+2,n) = 2*A000153(n+1). T(n+3,n) = 6*A000261(n+2). T(n+4,n) = 24*A001909(n+3). T(n+5, n) = 120*A001910(n+4). T(n+6,n) = 720*A176732(n).
T(n+7,n) = 5040*A176733(n) - Richard R. Forberg, Dec 29 2013

a047920 n k = a047920_tabl !! n !! k
a047920_row n = a047920_tabl !! n
a047920_tabl = map fst $ iterate e ([1], 1) where
   e (row, n) = (scanl (-) (n * head row) row, n + 1)
-- Reinhard Zumkeller, Mar 05 2012

d[0] := 1: for n to 15 do d[n] := n*d[n-1]+(-1)^n end do: T := proc (n, k) if k <= n then sum(binomial(n-k, j)*d[n-j], j = 0 .. n-k) else 0 end if end proc: for n from 0 to 9 do seq(T(n, k), k = 0 .. n) end do; # yields sequence in triangular form - Emeric Deutsch, Jul 17 2009
# second Maple program:
T:= proc(n, k) option remember;
     `if`(k=0, n!, T(n, k-1)-T(n-1, k-1))
    end:
seq(seq(T(n, k), k=0..n), n=0..12);  # Alois P. Heinz, Sep 01 2021

t[n_, k_] = Sum[(-1)^j*Binomial[k, j]*(n-j)!, {j, 0, n}]; Flatten[Table[t[n, k], {n, 0, 9}, {k, 0, n}]][[1 ;; 47]] (* Jean-François Alcover, May 17 2011, after Philippe Deléham *)
T[n_, k_] := n! Hypergeometric1F1[-k, -n, -1];
Table[T[n, k], {n, 0, 7}, {k, 0, n}] // Flatten  (* Peter Luschny, Jul 28 2024 *)

row(n) = vector(n+1, k, k--; sum(j=0, n, (-1)^j * binomial(k, j)*(n-j)!)); \\ Michel Marcus, Sep 04 2021

t(n, k) = t(n, k-1) - t(n-1, k-1) = t(n, k+1) - t(n-1, k) = n*t(n-1, k) + k*t(n-2, k-1) = (n-1)*t(n-1, k-1) + (k-1)*t(n-2, k-2) = A060475(n, k)*(n-k)!. - Henry Bottomley, Mar 16 2001
T(n, k) = Sum_{j>=0} (-1)^j * binomial(k, j)*(n-j)!. - Philippe Deléham, May 29 2005
T(n,k) = Sum_{j=0..n-k} d(n-j)*binomial(n-k,j), where d(i)=A000166(i) are the derangement numbers. - Emeric Deutsch, Jul 17 2009
Sum_{k=0..n} (k+1)*T(n,k) = A155521(n+1). - Emeric Deutsch, Jul 18 2009
T(n, k) = n!*hypergeom([-k], [-n], -1). - Peter Luschny, Jul 28 2024

A055790 a(n) = na(n-1) + (n-2)a(n-2), a(0) = 0, a(1) = 2.

Original entry on oeis.org

0, 2, 4, 14, 64, 362, 2428, 18806, 165016, 1616786, 17487988, 206918942, 2657907184, 36828901754, 547499510764, 8691268384262, 146725287298888, 2624698909845026, 49592184973992676, 986871395973226286, 20630087248996393888, 451982388752415571082

Offset: 0

Henry Bottomley, Jul 13 2000

nonn

With offset 1, permanent of (0,1)-matrix of size n X (n+d) with d=1 and n-1 zeros not on a line. This is a special case of Theorem 2.3 of Seok-Zun Song et al. Extremes of permanents of (0,1)-matrices, p. 201-202. - Jaap Spies, Dec 12 2003
With a(0) = 1, number of degree-(n+1) permutations p such that p(i) != i+2 for each i=1,2,...,n+1. - Vladeta Jovovic, Jan 03 2003
Equivalently number of degree-(n+1) permutations p such that p(i) != i-2 for each i=1,2,...,n+1.
With a(0) = 1, number of degree-(n+1) permutations without fixed points between 2 and n. - Olivier Gérard, Jul 29 2016
Also column 3 of Euler's difference table (third diagonal in example of A068106). - Enrique Navarrete, Oct 31 2016
For n>=2, the number of circular permutations (in cycle notation) on [n+2] that avoid substrings (j,j+3), 1<=j<=n-1.  For example, for n=2, the 4 circular permutations in S4 that avoid the substring {14} are (1234),(1243),(1324),(1342). Note that each of these circular permutations represent 4 permutations in one-line notation (see link 2017). - Enrique Navarrete, Feb 15 2017

			G.f. = 2*x + 4*x^2 + 14*x^3 + 64*x^4 + 362*x^5 + 2428*x^6 + ...
a(3) = 3*a(2)+(3-2)*a(1) = 12+2 = 14.
for n=1, the 2 permutations of [2] matches:
12, 21
for n=2, the 4 permutations of [3] without 2 as a fixed point are
132, 213, 231, 312.
for n=3, the 14 permutations of [4] without fixed point at 2 or 3 are
1324 1342 1423    2143 2314 2341 2413
3124 3142 3412 3421    4123 4312 4321

Brualdi, Richard A. and Ryser, Herbert J., Combinatorial Matrix Theory, Cambridge NY (1991), Chapter 7.

Reinhard Zumkeller, Table of n, a(n) for n = 0..250
T. Mansour and M. Shattuck, Counting permutations by the number of successors within cycles, Discr. Math., 339 (2016), 1368-1376.
Enrique Navarrete, Generalized K-Shift Forbidden Substrings in Permutations, arXiv:1610.06217 [math.CO], 2016.
Enrique Navarrete, Forbidden Substrings in Circular K-Successions, arXiv:1702.02637 [math.CO], 2017.
Seok-Zun Song et al., Extremes of permanents of (0,1)-matrices, Special issue on the Combinatorial Matrix Theory Conference (Pohang, 2002). Linear Algebra Appl. 373 (2003), pp. 197-210.

Cf. A000166 (Derangements, permutations without fixed points ).
Cf. A000255 (permutations with p(i)!=i+1, same type of recurrence).
Cf. A000153, A000261, A001909, A001910, A090010, A090012-A090016.
Apart from first term, appears in triangles A047920 or A068106 of differences of factorials, i.e. as third term of A000142, A001563, A001564, A001565 etc.

a055790 n = a055790_list !! n
a055790_list = 0 : 2 : zipWith (+)
   (zipWith (*) [0..] a055790_list) (zipWith (*) [2..] $ tail a055790_list)
-- Reinhard Zumkeller, Mar 05 2012

f := proc(n) option remember; if n <= 1 then 2*n else n*f(n-1)+(n-2)*f(n-2); fi; end;

a[0] = 0; a[1] = 2; a[n_] := a[n] = a[n] = n*a[n - 1] + (n - 2)*a[n - 2];
Table[a[n], {n, 0, 21}] (* Jean-François Alcover, Nov 14 2017 *)
RecurrenceTable[{a[0]==0,a[1]==2,a[n]==n*a[n-1]+(n-2)a[n-2]},a,{n,30}] (* Harvey P. Dale, May 07 2018 *)

a(n) = if(n==0, 0, round((n+3+1/n)*n!/exp(1))) \\ Felix Fröhlich, Jul 29 2016

For n > 0, a(n) = round[(n+3+1/n)*n!/e] = 2*A000153(n) = A000255(n-1)+A000255(n) = A000166(n-1)+2*A000166(n)+A000166(n+1).
G.f.: Q(0)*(1+x)/x - 1/x - 2, 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))); (continued fraction). - Sergei N. Gladkovskii, May 08 2013
G.f.: (1+x)^2/x/Q(0) - 1/x - 2, where Q(k)= 1 - 2*k*x - x^2*(k + 1)^2/Q(k+1); (continued fraction). - Sergei N. Gladkovskii, May 08 2013
G.f.: 2*(1+x)/G(0) - 1-x, where G(k)= 1 + 1/(1 - x*(2*k+2)/(x*(2*k+1) - 1 + x*(2*k+2)/G(k+1))); (continued fraction). - Sergei N. Gladkovskii, May 31 2013
G.f.: W(0) -1, where W(k) = 1 - x*(k+2)/( x*(k+1) - 1/(1 - x*(k+1)/( x*(k+1) - 1/W(k+1) ))); (continued fraction). - Sergei N. Gladkovskii, Aug 26 2013
a(n) ~ sqrt(Pi/2)*n^n*sqrt(n)*(12*n + 37)/(6*exp(n+1)). - Ilya Gutkovskiy, Jul 29 2016
0 = a(n)*(+a(n+1) + 3*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)) for n>=0. - Michael Somos, Nov 01 2016

Comments corrected, new interpretation and examples by Olivier Gérard, Jul 29 2016

A033815 Number of standard permutations of [ a_1..a_n b_1..b_n ] (b_i is not immediately followed by a_i, for all i).

Original entry on oeis.org

1, 1, 14, 426, 24024, 2170680, 287250480, 52370755920, 12585067447680, 3854801333416320, 1465957162768492800, 677696237345719468800, 374281829360322587827200, 243388909697235614324812800, 184070135024053703140543027200, 160192129141963141211280644352000

Offset: 0

N. J. A. Sloane

Also turns up as the solution to Problem #18, p. 326 of Alan Tucker's Applied Combinatorics, 4th ed, Wiley NY 2002 [Tucker's `n' is the `2n' here]. - John L Leonard, Sep 15 2003
Number of acyclic orientations of the Turán graph T(2n,n). - Alois P. Heinz, Jan 13 2016
n-th term of the n-th forward differences of n!. - Alois P. Heinz, Feb 22 2019

R. P. Stanley, Enumerative Combinatorics I, Chap.2, Exercise 10, p. 89.

Reinhard Zumkeller, Table of n, a(n) for n = 0..200
Leo Chao, Paul DesJarlais and John L Leonard, A binomial identity, via derangements, Math. Gaz. 89 (2005), 268-270.
Ira Gessel, Enumerative applications of symmetric functions, Séminaire Lotharingien de Combinatoire, B17a (1987), 17 pp.

Main diagonal of array in A068106 and of A047920.
Cf. A000142, A002119, A116854, A267383.
Column k=2 of A372326.

a033815 n = a116854 (2 * n + 1) (n + 1)
-- Reinhard Zumkeller, Aug 31 2014

A033815 := proc(n) local i; add(binomial(n, i)*(-1)^i*(2*n - i)!, i = 0 .. n) end;
# second Maple program:
A:= proc(n, k) A(n, k):= `if`(k=0, n!, A(n+1, k-1) -A(n, k-1)) end:
a:= n-> A(n$2):
seq(a(n), n=0..23);  # Alois P. Heinz, Feb 22 2019

a[n_] := (2n)!*Hypergeometric1F1[-n, -2n, -1]; Table[a[n], {n, 0, 14}] (* Jean-François Alcover, Jun 13 2012, after Vladimir Reshetnikov *)

a(n) = A002119(n)*n!*(-1)^n.
D-finite with recurrence a(n) = 2n*(2n-1)*a(n-1) + n*(n-1)*a(n-2).
a(n) = Sum_{i=0..n} binomial(n, i)*(-1)^i*(2*n-i)!.
From John L Leonard, Sep 15 2003: (Start)
a(n) = Sum_{i=0..n} C(n, i)*(2n-i)!*Sum_{j=0..2n-i} (-1)^j/j!.
a(n) = n!*Sum_{i=0..n} C(n, i)*n!/(n-i)!*Sum_{j=0..n-i} (-1)^j*C(n-i, j)*(n-j)!/i!. (End)
a(n) = Sum_{k=0..n} binomial(n,k)*A000166(n+k). - Vladeta Jovovic, Sep 04 2006
a(n) = A116854(2*n+1,n+1). - Reinhard Zumkeller, Aug 31 2014
a(n) = A267383(2n,n). - Alois P. Heinz, Jan 13 2016
a(n) ~ sqrt(Pi) * 2^(2*n + 1) * n^(2*n + 1/2) / exp(2*n + 1/2). - Vaclav Kotesovec, Feb 18 2017
a(n) = n!*exp(-1/2)*((-1)^n * BesselI(n+1/2,1/2)*Pi^(1/2) + BesselK(n+1/2,1/2)/Pi^(1/2) ). - Mark van Hoeij, Jul 15 2022

A161131 Number of permutations of {1,2,...,n} that have no odd fixed points.

Original entry on oeis.org

1, 0, 1, 3, 14, 64, 426, 2790, 24024, 205056, 2170680, 22852200, 287250480, 3597143040, 52370755920, 760381337520, 12585067447680, 207863095910400, 3854801333416320, 71370457471716480, 1465957162768492800, 30071395843421184000, 677696237345719468800

Offset: 0

Emeric Deutsch, Jul 18 2009

nonn

			a(3)=3 because we have 312, 231, and 321.

Alois P. Heinz, Table of n, a(n) for n = 0..450

Cf. A000166, A068106, A161132.

d[0] := 1: for n to 25 do d[n] := n*d[n-1]+(-1)^n end do: a := proc (n) options operator, arrow: add(d[n-j]*binomial(floor((1/2)*n), j), j = 0 .. floor((1/2)*n)) end proc; seq(a(n), n = 0 .. 22);
a := proc (n) options operator, arrow: add((-1)^j*binomial(ceil((1/2)*n), j)*factorial(n-j), j = 0 .. ceil((1/2)*n)) end proc; seq(a(n), n = 0 .. 22); # Emeric Deutsch, Jul 18 2009
# next Maple program:
a:= proc(n) option remember; `if`(n<4, [1, 0, 1, 3][n+1],
      (8*(n-1)*(2*n-5)*a(n-1)+2*(8*n^4-48*n^3+102*n^2-90*n+29)*a(n-2)
       -2*(2*n-1)*(n-2)*a(n-3)+(2*n-1)*(2*n-3)*(n-2)*(n-3)*a(n-4))
       /(4*(2*n-3)*(2*n-5)))
    end:
seq(a(n), n=0..30);  # Alois P. Heinz, Jul 15 2022
a := n -> n!*hypergeom([-ceil(n/2)], [-n], -1):
seq(simplify(a(n)), n = 0..22);  # Peter Luschny, Jul 15 2022

Table[Sum[(-1)^j*Binomial[Ceiling[n/2], j]*(n-j)!, {j, 0, Ceiling[n/2]}], {n, 0, 30}] (* Vaclav Kotesovec, Feb 18 2017 *)

for(n=0, 30, print1(sum(j=0, ceil(n/2), (-1)^j*binomial(ceil(n/2), j)*(n - j)!),", ")) \\ Indranil Ghosh, Mar 08 2017

a(n) = Sum_{j=0..floor(n/2)} d(n-j)*binomial(floor(n/2), j), where d(i)=A000166(i) are the derangement numbers.
a(n) = Sum_{j=0..ceiling(n/2)} (-1)^j*binomial(ceiling(n/2), j)*(n-j)!. - Emeric Deutsch, Jul 18 2009
a(n) ~ exp(-1/2) * n!. - Vaclav Kotesovec, Feb 18 2017
From Peter Luschny, Jul 15 2022: (Start)
a(n) = n!*hypergeom([-ceiling(n/2)], [-n], -1).
a(n) = A068106(n, floor(n/2)). (End)
D-finite with recurrence +16*a(n) -24*a(n-1) -4*(2*n-1)*(2*n-3)*a(n-2) +4*(2*n^2-10*n+15)*a(n-3) +2*(-10*n+29)*a(n-4) +2*(n-2)*(n-4)*a(n-5) +(n-4)*(n-5)*a(n-6)=0. - R. J. Mathar, Jul 26 2022

A161132 Number of permutations of {1,2,...,n} that have no even fixed points.

Original entry on oeis.org

1, 1, 1, 4, 14, 78, 426, 3216, 24024, 229080, 2170680, 25022880, 287250480, 3884393520, 52370755920, 812752093440, 12585067447680, 220448163358080, 3854801333416320, 75225258805132800, 1465957162768492800, 31537353006189676800, 677696237345719468800

Offset: 0

Emeric Deutsch, Jul 18 2009

nonn

			a(3)=4 because we have 132, 312, 213, and 231.

Alois P. Heinz, Table of n, a(n) for n = 0..450

Cf. A000166, A033815, A068106, A161131, A267383.

d[0] := 1: for n to 25 do d[n] := n*d[n-1]+(-1)^n end do: a := proc (n) options operator, arrow: add(d[n-j]*binomial(ceil((1/2)*n), j), j = 0 .. ceil((1/2)*n)) end proc: seq(a(n), n = 0 .. 22);
a := proc (n) options operator, arrow: add((-1)^j*binomial(floor((1/2)*n), j)*factorial(n-j), j = 0 .. floor((1/2)*n)) end proc; seq(a(n), n = 0 .. 22); # Emeric Deutsch, Jul 18 2009
a := n -> n!*hypergeom([-floor(n/2)], [-n], -1):
seq(simplify(a(n)), n = 0..22);  # Peter Luschny, Jul 15 2022

a[n_] := Sum[Subfactorial[n-j]*Binomial[Ceiling[n/2], j], {j, 0, Ceiling[ n/2]}]; Table[a[n], {n, 0, 22}] (* Jean-François Alcover, Feb 19 2017 *)

for (n=0, 30, print1(sum(j=0, floor(n/2), (-1)^j*binomial(floor(n/2),j)*(n - j)!),", ")) \\ Indranil Ghosh, Mar 08 2017

import math
f=math.factorial
def C(n, r): return f(n)/ f(r)/ f(n - r)
def A161132(n):
    s=0
    for j in range(0, (n/2)+1):
        s += (-1)**j*C(n/2, j)*f(n - j)
    return s # Indranil Ghosh, Mar 08 2017

a(n) = Sum_{j=0..ceiling(n/2)} d(n-j)*binomial(ceiling(n/2), j), where d(i) = A000166(i) are the derangement numbers.
a(n) = Sum_{j=0..floor(n/2)} (-1)^j*binomial(floor(n/2),j)*(n-j)!.
a(n) = A267383(n,ceiling(n/2)). - Alois P. Heinz, Jan 13 2016
a(n) ~ exp(-1/2) * n!. - Vaclav Kotesovec, Feb 18 2017
From Mark van Hoeij, Jul 15 2022: (Start)
a(2*n) = A033815(n),
a(2*n+1) = (A033815(n) + A033815(n+1)/(n+1))/2. (End)
From Peter Luschny, Jul 15 2022: (Start)
a(n) = n!*hypergeom([-floor(n/2)], [-n], -1).
a(n) = A068106(n, ceiling(n/2)). (End)
D-finite with recurrence +16*a(n) -24*a(n-1) +4*(-4*n^2+8*n+3)*a(n-2) +4*(2*n^2-10*n+9)*a(n-3) +2*(-4*n^2+22*n-31)*a(n-4) +2*(n-2)*(n-4)*a(n-5) -(n-4)*(n-5)*a(n-6)=0. - R. J. Mathar, Jul 26 2022

A129867 Row sums of triangular array T: T(j,k) = k*(j-k)! for k < j, T(j,k) = 1 for k = j; 1 <= k <= j.

Original entry on oeis.org

1, 2, 5, 14, 47, 200, 1073, 6986, 53219, 462332, 4500245, 48454958, 571411271, 7321388384, 101249656697, 1502852293010, 23827244817323, 401839065437636, 7182224591785949, 135607710526966262, 2696935204638786575

Offset: 1

Paul Curtz, May 24 2007

nonn

T read by rows is in A130469.
First differences are 1, 3, 9, 33, 153, 873, 5913, ... (see A007489), second differences are 2, 6, 24, 120, 720, 5040, ... (see A000142 ).
First terms of the sequences of m-th differences are 1, 2, 4, 14, 64, ... (see A055790, A047920, A068106).
Antidiagonal sums are 1, 1, 3, 8, 29, 135, ... (see A130470) with first differences 0, 2, 5, 21, 106, ... (see A130471).
Equals the row sums of irregular triangle A182961. - Paul D. Hanna, Mar 05 2012

			First seven rows of T are
[   1 ]
[   1,   1 ]
[   2,   2,   1 ]
[   6,   4,   3,   1 ]
[  24,  12,   6,   4,   1 ]
[ 120,  48,  18,   8,   5,   1 ]
[ 720, 240,  72,  24,  10,   6,   1 ]

Vincenzo Librandi, Table of n, a(n) for n = 1..100

Cf. A130469, A007489, A000142, A055790, A047920, A068106, A130470, A130471.

Cf. A182961.

m:=21; [ &+([ k*Factorial(j-k): k in [1..j-1] ] cat [ 1 ]): j in [1..m] ]; // Klaus Brockhaus, May 28 2007

Edited and extended by Klaus Brockhaus, May 28 2007

A116853 Difference triangle of factorial numbers read by upward diagonals.

Original entry on oeis.org

1, 1, 2, 3, 4, 6, 11, 14, 18, 24, 53, 64, 78, 96, 120, 309, 362, 426, 504, 600, 720, 2119, 2428, 2790, 3216, 3720, 4320, 5040, 16687, 18806, 21234, 24024, 27240, 30960, 35280, 40320

Offset: 1

Gary W. Adamson, Feb 24 2006

This is a subsequence of Euler's difference table A068106 and of A047920 (in a different ordering), since 0! = 1 was left out here. - Georg Fischer, Mar 23 2019

			Starting with 1, 2, 6, 24, 120 ... we take the first difference row (A001563), second, third, etc. Reorient into a flush left format, getting:
[1]    1;
[2]    1,   2;
[3]    3,   4,   6;
[4]   11,  14,  18,  24;
[5]   53,  64,  78,  96, 120;
[6]  309, 362, 426, 504, 600, 720;
...

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

Cf. A000142 (factorial numbers).
Cf. A000255 (first column and inverse binomial transform of A000142).
N-th forward differences of A000142: A001563 (1st), A001564 (2nd), A001565 (3rd), A001688 (4th), A001689 (5th).
Cf. A047920 (with 0!, different order), A068106 (with 0!), A180191 (row sums), A246606 (central terms).

a116853 n k = a116853_tabl !! (n-1) !! (k-1)
a116853_row n = a116853_tabl !! (n-1)
a116853_tabl = map reverse $ f (tail a000142_list) [] where
   f (u:us) vs = ws : f us ws where ws = scanl (-) u vs
-- Reinhard Zumkeller, Aug 31 2014

rows = 8;
rr = Range[rows]!;
dd = Table[Differences[rr, n], {n, 0, rows-1}];
T = Array[t, {rows, rows}];
Do[Thread[Evaluate[Diagonal[T, -k+1]] = dd[[k, ;;rows-k+1]]], {k, rows}];
Table[t[n, k], {n, 1, rows}, {k, 1, n}] // Flatten (* Jean-François Alcover, Dec 21 2019 *)

Take successive difference rows of factorial numbers n! starting with n=1. Reorient into a triangle format.

A163770 Triangle read by rows interpolating the swinging subfactorial (A163650) with the swinging factorial (A056040).

Original entry on oeis.org

1, 0, 1, 1, 1, 2, 2, 3, 4, 6, -9, -7, -4, 0, 6, 44, 35, 28, 24, 24, 30, -165, -121, -86, -58, -34, -10, 20, 594, 429, 308, 222, 164, 130, 120, 140, -2037, -1443, -1014, -706, -484, -320, -190, -70, 70, 6824, 4787, 3344, 2330, 1624, 1140, 820, 630, 560, 630

Offset: 0

Peter Luschny, Aug 05 2009

An analog to the derangement triangle (A068106).

			1
0, 1
1, 1, 2
2, 3, 4, 6
-9, -7, -4, 0, 6
44, 35, 28, 24, 24, 30
-165, -121, -86, -58, -34, -10, 20

G. C. Greubel, Table of n, a(n) for the first 50 rows, flattened
Peter Luschny, Die schwingende Fakultät und Orbitalsysteme, August 2011.
Peter Luschny, Swinging Factorial.
M. Z. Spivey and L. L. Steil, The k-Binomial Transforms and the Hankel Transform, J. Integ. Seqs. Vol. 9 (2006), #06.1.1.

Row sums are A163773.

Cf. A056040, A163650, A163771, A163772, A068106.

DiffTria := proc(f,n,display) local m,A,j,i,T; T:=f(0);
for m from 0 by 1 to n-1 do A[m] := f(m);
for j from m by -1 to 1 do A[j-1] := A[j-1] - A[j] od;
for i from 0 to m do T := T,(-1)^(m-i)*A[i] od;
if display then print(seq(T[i],i=nops([T])-m..nops([T]))) fi;
od; subsop(1=NULL,[T]) end:
swing := proc(n) option remember; if n = 0 then 1 elif
irem(n, 2) = 1 then swing(n-1)*n else 4*swing(n-1)/n fi end:
Computes n rows of the triangle.
A163770 := n -> DiffTria(k->swing(k),n,true);
A068106 := n -> DiffTria(k->factorial(k),n,true);

sf[n_] := n!/Quotient[n, 2]!^2; t[n_, k_] := Sum[(-1)^(n - i)*Binomial[n - k, n - i]*sf[i], {i, k, n}]; Table[t[n, k], {n, 0, 9}, {k, 0, n}] // Flatten (* Jean-François Alcover, Jun 28 2013 *)

T(n,k) = Sum_{i=k..n} (-1)^(n-i)*binomial(n-k,n-i)*i$ where i$ denotes the swinging factorial of i (A056040).

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Haskell

Magma

Maple

Mathematica

PARI

PARI

Sage

Formula

A002467 The game of Mousetrap with n cards (given n letters and n envelopes, how many ways are there to fill the envelopes so that at least one letter goes into its right envelope?).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

PARI

PARI

PARI

Formula

A047920 Triangular array formed from successive differences of factorial numbers.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

Formula

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

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

Formula

Extensions

A033815 Number of standard permutations of [ a_1..a_n b_1..b_n ] (b_i is not immediately followed by a_i, for all i).

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

Formula

A000255 a(n) = na(n-1) + (n-1)a(n-2), a(0) = 1, a(1) = 1.

A055790 a(n) = na(n-1) + (n-2)a(n-2), a(0) = 0, a(1) = 2.