A000166 -id:A000166 - cp's OEIS frontend

A132382 Lower triangular array T(n,k) generator for group of arrays related to A001147 and A102625.

1, -1, 1, -1, -2, 1, -3, -3, -3, 1, -15, -12, -6, -4, 1, -105, -75, -30, -10, -5, 1, -945, -630, -225, -60, -15, -6, 1, -10395, -6615, -2205, -525, -105, -21, -7, 1, -135135, -83160, -26460, -5880, -1050, -168, -28, -8, 1, -2027025, -1216215, -374220, -79380, -13230, -1890, -252, -36, -9, 1

Offset: 0

Tom Copeland, Nov 11 2007, Nov 12 2007, Nov 19 2007, Dec 04 2007, Dec 06 2007

Let b(n) = LPT[ A001147 ] = -A001147(n-1) for n > 0 and 1 for n=0, where LPT represents the action of the list partition transform described in A133314.
Then T(n,k) = binomial(n,k) * b(n-k) .
Form the matrix of polynomials TB(n,k,t) = T(n,k) * t^(n-k) = binomial(n,k) * b(n-k) * t^(n-k) = binomial(n,k) * Pb(n-k,t),
beginning as
     1;
    -1,       1;
    -1*t,    -2,       1;
    -3*t^2,  -3*t,    -3,       1;
   -15*t^3, -12*t^2,  -6*t,    -4,    1;
  -105*t^4, -75*t^3, -30*t^2, -10*t, -5, 1;
Let Pc(n,t) = LPT(Pb(.,t)).
Then [TB(t)]^(-1) = TC(t) = [ binomial(n,k) * Pc(n-k,t) ] = LPT(TB),
whose first column is
Pc(0,t) = 1
Pc(1,t) = 1
Pc(2,t) = 2 + t
Pc(3,t) = 6 + 6*t + 3*t^2
Pc(4,t) = 24 + 36*t + 30*t^2 + 15*t^3
Pc(5,t) = 120 + 240*t + 270*t^2 + 210*t^3 + 105*t^4.
The coefficients of these polynomials are given by the reverse of A102625 with the highest order coefficients given by A001147 with an additional leading 1.
Note this is not the complete matrix TC. The complete matrix is formed by multiplying along the diagonal of the lower triangular Pascal matrix by these polynomials, embedding trees of coefficients in the matrix.
exp[Pb(.,t)*x] = 1 + [(1-2t*x)^(1/2) - 1] / (t-0) = [1 + a finite diff. of [(1-2t*x)^(1/2)] with step t] = e.g.f. of the first column of TB.
exp[Pc(.,t)*x] = 1 / { 1 + [(1-2t*x)^(1/2) - 1] / t } = 1 / exp[Pb(.,t)*x) = e.g.f. of the first column of TC.
TB(t) and TC(t), being inverse to each other, are the generators of an Abelian group.
TB(0) and TC(0) are generators for a subgroup representing the iterated Laguerre operator described in A132013 and A132014.
Let sb(t,m) and sc(t,m) be the associated sequences under the LPT to TB(t)^m = B(t,m) and TC(t)^m = C(t,m).
Let Esb(t,m) and Esc(t,m) be e.g.f.'s for sb(t,m) and sc(t,m), rB(t,m) and rC(t,m) be the row sums of B(t,m) and C(t,m) and aB(t,m) and aC(t,m) be the alternating row sums.
Then B(t,m) is the inverse of C(t,m), Esb(t,m) is the reciprocal of Esc(t,m) and sb(t,m) and sc(t,m) form a reciprocal pair under the LPT. Similar relations hold among the row sums and the alternating sign row sums and associated quantities.
All the group members have the form B(t,m) * C(u,p) = TB(t)^m * TC(u)^p = [ binomial(n,k) * s(n-k) ]
with associated e.g.f. Es(x) = exp[m * Pb(.,t) * x] * exp[p * Pc(.,u) * x] for the first column of the matrix, with terms s(n), so group multiplication is isomorphic to matrix multiplication and to multiplication of the e.g.f.'s for the associated sequences (see examples).
These results can be extended to other groups of integer-valued arrays by replacing the 2 by any natural number in the expression for exp[Pb(.,t)*x].
More generally,
[ G.f. for M = Product_{i=0..j} B[s(i),m(i)] * C[t(i),n(i)] ]
= exp(u*x) * Product_{i=0..j} { exp[m(i) * Pb(.,s(i)) * x] * exp[n(i) * Pc(.,t(i)) * x] }
= exp(u*x) * Product_{i=0..j} { 1 + [ (1 - 2*s(i)*x)^(1/2) - 1 ] / s(i) }^m(i) / { 1 + [ (1 - 2*t(i)*x)^(1/2) - 1 ] / t(i) }^n(i)
= exp(u*x) * H(x)
[ E.g.f. for M ] = I_o[2*(u*x)^(1/2)] * H(x).
M is an integer-valued matrix for m(i) and n(i) positive integers and s(i) and t(i) integers. To invert M, change B to C in Product for M.
H(x) is the e.g.f. for the first column of M and diagonally multiplying the Pascal matrix by the terms of this column generates M. See examples.
The G.f. for M, i.e., the e.g.f. for the row polynomials of M, implies that the row polynomials form an Appell sequence (see Wikipedia and Mathworld). - Tom Copeland, Dec 03 2013

			Some group members and associated arrays are
(t,m) :: Array :: Asc. Matrix :: Asc. Sequence :: E.g.f. for sequence
..............................................................................
(0,1).::.B..::..A132013.::.(1,-1,0,0,0,0,...).....::.s(x).=.1-x
(0,1).::.C..::..A094587.::.(0!,1!,2!,3!,...)......::.1./.s(x)
(0,1).::.rB.::.~A055137.::.(1,0,-1,-2,-3,-4,...)..::.exp(x).*.s(x)
(0,1).::.rC.::....-.....::..A000522...............::.exp(x)./.s(x)
(0,1).::.aB.::....-.....::.(1,-2,3,-4,5,-6,...)...::.exp(-x).*.s(x)
(0,1).::.aC.::..A008290.::..A000166...............::.exp(-x)./.s(x)
..............................................................................
(0,2).::.B..::..A132014.::.(1,-2,2,0,0,0,0...)....::.s(x).=.(1-x)^2
(0,2).::.C..::..A132159.::.(1!,2!,3!,4!,...)......::..1./.s(x).
(0,2).::.rB.::...-......::.(1,-1,-1,1,5,11,19,29,)::.exp(x).*.s(x).
(0,2).::.rC.::...-......::..A001339...............::.exp(x)./.s(x).
(0,2).::.aB.::...-......::.(-1)^n.A002061(n+1)....::.exp(-x).*.s(x).
(0,2).::.aC.::...-......::..A000255...............::.exp(-x)./.s(x).
..............................................................................
(1,1).::.B..::..T.......::.(1,-A001147(n-1))......::.s(x).=.(1-2x)^(1/2)
(1,1).::.C..::.~A113278.::..A001147...............::.1./.s(x)...
(1,1).::.rB.::...-......::..A055142...............::.exp(x).*.s(x).
(1,1).::.rC.::...-......::..A084262...............::.exp(x)./.s(x).
(1,1).::.aB.::...-......::.(1,-2,2,-4,-4,-56,...).::.exp(-x).*.s(x).
(1,1).::.aC.::...-......::..A053871...............::.exp(-x)./.s(x).
..............................................................................
(2,1).::.B..::...-......::.(1,-A001813)...........::.s=[1+(1-4x)^(1/2)]/2....
(2,1).::.C..::...-......::..A001761...............::.1./.s(x)..
(2,1).::.rB.::...-......::.(1,0,-3,-20,-183,...)..::.exp(x).*.s(x)..
(2,1).::.rC.::...-......::.(1,2,7,46,485,...).....::.exp(x)./.s(x).
(2,1).::.aB.::...-......::.(1,-2,1,-10,-79,...)...::.exp(-x).*.s(x).
(2,1).::.aC.::...-......::.(1,0,3,20,237,...).....::.exp(-x)./.s(x)
..............................................................................
(1,2).::.B..::.~A134082.::.(1,-2,0,0,0,0,...).....::.s(x).=.1.-.2x
(1,2).::.C..::....-.....::..A000165...............::.1./.s(x)..
(1,2).::.rB.::....-.....::.(1,-1,-3,-5,-7,-9,...).::.exp(x).*.s(x).
(1,2).::.rC.::....-.....::..A010844...............::.exp(x)./.s(x)..
(1,2).::.aB.::....-.....::.(1,-3,5,-7,9,-11,...)..::.exp(-x).*.s(x).
(1,2).::.aC.::....-.....::..A000354...............::.exp(-x)./.s(x).
..............................................................................
(The tilde indicates the match is not exact--specifically, there are differences in signs from the true matrices.)
Note the row sums correspond to binomial transforms of s(x) and the alternating row sums, to inverse binomial transforms, or, finite differences.
Some additional examples:
C(1,2)*B(0,1) = B(1,-2)*C(0,-1) = [ binomial(n,k)*A002866(n-k) ] with asc. e.g.f. (1-x) / (1-2x).
B(1,2)*C(0,1) = C(1,-2)*B(0,-1) = 2I - A094587 with asc. e.g.f. (1-2x) / (1-x).

[G.f. for TB(n,k,t)] = GTB(u,x,t) = exp(u*x) * { 1 + [ (1 - 2t*x)^(1/2) - 1 ] / t } = exp[(u+Pb(.,t))*x] where TB(n,k,t) = (D_x)^n (D_u)^k /k! GTB(u,x,t) eval. at u=x=0.
[G.f. for TC(n,k,t)] = GTC(u,x,t) = exp(u*x) / { 1 + [ (1 - 2t*x)^(1/2) - 1 ] / t } = exp[(u+Pc(.,t))*x] where TC(n,k,t) = (D_x)^n (D_u)^k /k! GTC(u,x,t) eval. at u=x=0.
[E.g.f. for TB(n,k,t)] = I_o[2*(u*x)^(1/2)] * { 1 + [ (1 - 2t*x)^(1/2) - 1 ] / t } and
[E.g.f. for TC(n,k,t)] = I_o[2*(u*x)^(1/2)] / { 1 + [ (1 - 2t*x)^(1/2) - 1 ] / t }
where I_o is the zeroth modified Bessel function of the first kind, i.e.,
I_o[2*(u*x)^(1/2)] = Sum_{j>=0} (u^j/j!) * (x^j/j!).
So [e.g.f. for TB(n,k)] = I_o[2*(u*x)^(1/2)] * (1 - 2x)^(1/2).

More terms from Tom Copeland, Dec 05 2007

A170942 Take the permutations of lengths 1, 2, 3, ... arranged lexicographically, and replace each permutation with the number of its fixed points.

Original entry on oeis.org

1, 2, 0, 3, 1, 1, 0, 0, 1, 4, 2, 2, 1, 1, 2, 2, 0, 1, 0, 0, 1, 1, 0, 2, 1, 0, 0, 0, 1, 1, 2, 0, 0, 5, 3, 3, 2, 2, 3, 3, 1, 2, 1, 1, 2, 2, 1, 3, 2, 1, 1, 1, 2, 2, 3, 1, 1, 3, 1, 1, 0, 0, 1, 2, 0, 1, 0, 0, 1, 1, 0, 2, 1, 0, 0, 0, 1, 1, 2, 0, 0, 2, 0, 1, 0, 0, 1, 3, 1, 2, 1, 1, 2, 1, 0, 1, 0, 0, 0, 0, 1, 0, 1, 0, 0

Offset: 1

Neven Juric (neven.juric(AT)apis-it.hr) and N. J. A. Sloane, Feb 23 2010

Length of n-th row = sum of n-th row = n!; number of zeros in n-th row = A000166(n); number of positive terms in n-th row = A002467(n). [Reinhard Zumkeller, Mar 29 2012]

			123,132,213,231,312,321 (corresponding to 3rd row of triangle A030298) have respectively 3,1,1,0,0,1 fixed points.

Reinhard Zumkeller, Rows n=1..7 of triangle, flattened
FindStat - Combinatorial Statistic Finder, The number of fixed points of a permutation

Cf. A030298, A030299.
Cf. A008290, A000166, A000240, A000387, A000449, A000475, A129135, A129136, A129149, A129153, A129217, A129218, A129238, A129255.
Cf. A008291.

import Data.List (permutations, sort)
a170942 n k = a170942_tabf !! (n-1) (k-1)
a170942_row n = map fps $ sort $ permutations [1..n] where
   fps perm = sum $ map fromEnum $ zipWith (==) perm [1..n]
a170942_tabf = map a170942_row [1..]
-- Reinhard Zumkeller, Mar 29 2012

a(36)-a(105) from John W. Layman, Feb 23 2010

Keyword tabf added by Reinhard Zumkeller, Mar 29 2012

A005001 a(n) = Sum_{k=0..n-1} Bell(k), where the Bell numbers Bell(k) are given in A000110.

Original entry on oeis.org

0, 1, 2, 4, 9, 24, 76, 279, 1156, 5296, 26443, 142418, 820988, 5034585, 32679022, 223578344, 1606536889, 12086679036, 94951548840, 777028354999, 6609770560056, 58333928795428, 533203744952179, 5039919483399502, 49191925338483848, 495150794633289137

Offset: 0

N. J. A. Sloane

Counts rhyme schemes.
Row sums of triangle A137596 starting with offset 1. - Gary W. Adamson, Jan 29 2008
With offset 1 = binomial transform of the Bell numbers, A000110 starting (1, 1, 1, 2, 5, 15, 52, 203, ...). - Gary W. Adamson, Dec 04 2008
a(n) is the number of partitions of the set {1,2,...,n} in which n is either a singleton or it is in a block of consecutive integers. Example: a(3)=4 because we have 123, 1-23, 12-3, and 1-2-3. Deleting the blocks containing n=3, we obtain: empty, 1, 12, 1-2, i.e., all the partitions of the sets: empty, {1}, and {1,2}. - Emeric Deutsch, May 01 2010

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

T. D. Noe, Table of n, a(n) for n = 0..100
J. Riordan, Cached copy of paper
J. Riordan, A budget of rhyme scheme counts, pp. 455 - 465 of Second International Conference on Combinatorial Mathematics, New York, 1978. Edited by Allan Gewirtz and Louis V. Quintas. Annals New York Academy of Sciences, 319, 1979.

Partial sums of A000110, partial sums give A029761.
Equals A024716(n-1) + 1.
Cf. A102735, A094262, A000110, A008277, A102639, A003422, A000166, A000204, A000045, A000108.
Cf. A137596.
Cf. A171859.

with(combinat): seq(add(bell(j), j = 0 .. n-1), n = 0 .. 22); # Emeric Deutsch, May 01 2010

nn=20;Range[0,nn]!CoefficientList[Series[Exp[-1](-Exp[Exp[x]]+Exp[1+x]-Exp[x]ExpIntegralEi[1]+Exp[x]ExpIntegralEi[Exp[x]]),{x,0,nn}],x] (* Geoffrey Critzer, Feb 04 2014 *)
BellB /@ Range[0, 30] // Accumulate // Prepend[#, 0]& (* Jean-François Alcover, Oct 19 2019 *)

# Python 3.2 or higher required.
from itertools import accumulate
A005001_list, blist, a, b = [0,1,2], [1], 2, 1
for _ in range(30):
    blist = list(accumulate([b]+blist))
    b = blist[-1]
    a += b
    A005001_list.append(a) # Chai Wah Wu, Sep 19 2014

a(0) = 0; for n >= 0, a(n+1) = 1 + Sum_{j=1..n} (C(n, j)-C(n, j+1))*a(j).
a(n) = A000110(n) - A171859(n). - Emeric Deutsch, May 01 2010
G.f.: x*( 1 + (G(0)+1)*x/(1-x) ) where G(k) = 1 - 2*x*(k+1)/((2*k+1)*(2*x*k+x-1) - x*(2*k+1)*(2*k+3)*(2*x*k+x-1)/(x*(2*k+3) - 2*(k+1)*(2*x*k+2*x-1)/G(k+1) )); (continued fraction). - Sergei N. Gladkovskii, Dec 20 2012
G.f.: x*G(0)/(1-x^2) where G(k) = 1 - 2*x*(k+1)/((2*k+1)*(2*x*k-1) - x*(2*k+1)*(2*k+3)*(2*x*k-1)/(x*(2*k+3) - 2*(k+1)*(2*x*k+x-1)/G(k+1) )); (continued fraction). - Sergei N. Gladkovskii, Dec 22 2012
G.f.: x*( G(0) - 1 )/(1-x) where G(k) = 1 + (1-x)/(1-x*k)/(1-x/(x+(1-x)/G(k+1) )); (continued fraction). - Sergei N. Gladkovskii, Jan 21 2013
G.f.: (G(0)-1)*x/(1-x^2) where G(k) = 1 + 1/(1-k*x)/(1-x/(x+1/G(k+1))); (continued fraction). - Sergei N. Gladkovskii, Feb 06 2013
G.f.: x/(1-x)/(1-x*Q(0)), where Q(k) = 1 + x/(1 - x + x*(k+1)/(x - 1/Q(k+1))); (continued fraction). - Sergei N. Gladkovskii, May 19 2013
E.g.f. A(x) satisfies: A'(x) = A(x) + exp(exp(x)-1). - Geoffrey Critzer, Feb 04 2014
G.f.: (x/(1 - x)) * Sum_{i>=0} x^i / Product_{j=1..i} (1 - j*x). - Ilya Gutkovskiy, Jun 05 2017
a(n) ~ Bell(n) / (n/LambertW(n) - 1). - Vaclav Kotesovec, Jul 28 2021

A068996 Decimal expansion of 1 - 1/e.

Original entry on oeis.org

6, 3, 2, 1, 2, 0, 5, 5, 8, 8, 2, 8, 5, 5, 7, 6, 7, 8, 4, 0, 4, 4, 7, 6, 2, 2, 9, 8, 3, 8, 5, 3, 9, 1, 3, 2, 5, 5, 4, 1, 8, 8, 8, 6, 8, 9, 6, 8, 2, 3, 2, 1, 6, 5, 4, 9, 2, 1, 6, 3, 1, 9, 8, 3, 0, 2, 5, 3, 8, 5, 0, 4, 2, 5, 5, 1, 0, 0, 1, 9, 6, 6, 4, 2, 8, 5, 2, 7, 2, 5, 6, 5, 4, 0, 8, 0, 3, 5, 6

Offset: 0

N. J. A. Sloane, Apr 08 2002

From the "derangements" problem: this is the probability that if a large number of people are given their hats at random, at least one person gets their own hat.
1-1/e is the limit to which (1 - !n/n!) {= 1 - A000166(n)/A000142(n) = A002467(n)/A000142(n)} converges as n tends to infinity. - Lekraj Beedassy, Apr 14 2005
Also, this is lim_{n->inf} P(n), where P(n) is the probability that a random rooted forest on [n] is not connected. - Washington Bomfim, Nov 01 2010
Also equals the mode of a Gompertz distribution when the shape parameter is less than 1. - Jean-François Alcover, Apr 17 2013
The asymptotic density of numbers with an even number of trailing zeros in their factorial base representation (A232744). - Amiram Eldar, Feb 26 2021

			0.6321205588285576784044762...

Steven R. Finch, Mathematical Constants, Cambridge, 2003, Section 1.3, pp. 12-17.
Anders Hald, A History of Probability and Statistics and Their Applications before 1750, Wiley, NY, 1990 (Chapter 19).
John Riordan, An Introduction to Combinatorial Analysis, Wiley, 1958, p. 65.

Brian Conrey and Tom Davis, Derangements.
Brady Haran and Tom Crawford, A Problem with Infinite Hotel Keys, YouTube Numberphile video, 2025.
MathOverflow, What is the effect of adding 1/2 to a continued fraction?.
Jonathan Sondow and Eric Weisstein, e, MathWorld.
Bala Subramanian, Why time constant is 63.2% not a 50 or 70%? (2018).
Index entries for transcendental numbers

Cf. A000166, A068985, A091131, A185393, A232744.

evalf[140](1-exp(-1));  # Alois P. Heinz, May 16 2025

RealDigits[1 - 1/E, 10, 100][[1]] (* Alonso del Arte, Jul 06 2012 *)

1 - exp(-1) \\ Michel Marcus, Mar 04 2016

Equals Integral_{x = 0 .. 1} exp(-x) dx. - Alonso del Arte, Jul 06 2012
Equals -Sum_{k>=1} (-1)^k/k!. - Bruno Berselli, May 13 2013
Equals Sum_{k>=0} 1/((2*k+2)*(2*k)!). - Fred Daniel Kline, Mar 03 2016
From Peter Bala, Nov 27 2019: (Start)
1 - 1/e =  Sum_{n >= 0} n!/(A(n)*A(n+1)), where A(n) = A000522(n).
Continued fraction expansion: [0; 1, 1, 1, 2, 1, 1, 4, 1, 1, 6, 1, 1, 8, ...].
Related continued fraction expansions include
2*(1 - 1/e) = [1; 3, 1, 3, 1, 1, 1, 3, 3, 3, 1, 3, 1, 3, 5, 3, 1, 5, ..., 1, 3, 2*n + 1, 3, 1, 2*n + 1, ...];
(1/2)*(1 - 1/e) = [0; 3, 6, 10, 14, 18, ..., 4*n + 2, ...];
4*(1 - 1/e) = [2; 1, 1, 8, 3, 1, 1, 1, 1, 7, 1, 1, 2, 1, 1, 1, 2, 7, 1, 2, 2, 1, 1, 1, 3, ..., 7, 1, n, 2, 1, 1, 1, n+1, ...];
(1/4)*(1 - 1/e) = [0; 6, 3, 20, 7, 36, 11, 52, 15, ..., 16*n + 4, 4*n + 3, ...]. (End)
Equals Integral_{x=0..1} x * cosh(x) dx. - Amiram Eldar, Aug 14 2020
Equals A091131/e. - Hugo Pfoertner, Aug 20 2024

A000459 Number of multiset permutations of {1, 1, 2, 2, ..., n, n} with no fixed points.

Original entry on oeis.org

1, 0, 1, 10, 297, 13756, 925705, 85394646, 10351036465, 1596005408152, 305104214112561, 70830194649795010, 19629681235869138841, 6401745422388206166420, 2427004973632598297444857, 1058435896607583305978409166, 526149167104704966948064477665

Offset: 0

N. J. A. Sloane

Original definition: Number of permutations with no hits on 2 main diagonals. (Identical to definition of A000316.) - M. F. Hasler, Sep 27 2015
Card-matching numbers (Dinner-Diner matching numbers): A deck has n kinds of cards, 2 of each kind. The deck is shuffled and dealt in to n hands with 2 cards each. A match occurs for every card in the j-th hand of kind j. A(n) is the number of ways of achieving no matches. The probability of no matches is A(n)/((2n)!/2!^n).
Also, Penrice's Christmas gift numbers (see Penrice 1991).
a(n) is the maximal number of totally mixed Nash equilibria in games of n players, each with 3 pure options. - Raimundas Vidunas, Jan 22 2014

			There are 297 ways of achieving zero matches when there are 2 cards of each kind and 4 kinds of card so a(4)=297.
From _Peter Bala_, Jul 08 2014: (Start)
a(3) = 10: the 10 permutations of the multiset {1,1,2,2,3,3} that have no fixed points are
{2,2,3,3,1,1}, {3,3,1,1,2,2}
{2,3,1,3,1,2}, {2,3,1,3,2,1}
{2,3,3,1,1,2}, {2,3,3,1,2,1}
{3,2,1,3,1,2}, {3,2,1,3,2,1}
{3,2,3,1,1,2}, {3,2,3,1,2,1}
(End)

F. N. David and D. E. Barton, Combinatorial Chance, Hafner, NY, 1962, Ch. 7 and Ch. 12.
J. Riordan, An Introduction to Combinatorial Analysis, Wiley, 1958, pp. 174-178.
R. P. Stanley, Enumerative Combinatorics Volume I, Cambridge University Press, 1997, p. 71.
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).

T. D. Noe, Table of n, a(n) for n = 0..100
Per Alexandersson and Frether Getachew, An involution on derangements, arXiv:2105.08455 [math.CO], 2021.
Shalosh B. Ekhad, Christoph Koutschan, and Doron Zeilberger, There are EXACTLY 1493804444499093354916284290188948031229880469556 Ways to Derange a Standard Deck of Cards (ignoring suits) [and many other such useful facts], arXiv:2101.10147 [math.CO], 2021.
F. F. Knudsen and I. Skau, On the Asymptotic Solution of a Card-Matching Problem, Mathematics Magazine 69 (1996), 190-197.
P. A. MacMahon, Combinatory Analysis Cambridge: The University Press 1915-1916
B. H. Margolius, The Dinner-Diner Matching Problem, Mathematics Magazine, 76 (2003), 107-118.
B. H. Margolius, Dinner-Diner Matching Probabilities
R. D. McKelvey and A. McLennan, The maximal number of regular totally mixed Nash equilibria, J. Economic Theory, 72:411--425, 1997.
L. I. Nicolaescu, Derangements and asymptotics of the Laplace transforms of large powers of a polynomial, New York J. Math. 10 (2004) 117-131.
S. G. Penrice, Derangements, permanents and Christmas presents, The American Mathematical Monthly 98 (1991), 617-620.
John Riordan and N. J. A. Sloane, Correspondence, 1974
R. Vidunas, Counting derangements and Nash equilibria, arXiv preprint arXiv:1401.5400 [math.CO], 2014-2016.
Raimundas Vidunas, Counting derangements and Nash equilibria Ann. Comb. 21, No. 1, 131-152 (2017).
Wikipedia, Permutations of multisets
Index entries for sequences related to card matching

Cf. A000166, A008290, A059056-A059071, A033581, A059073.

Row n=2 of A372307.

I:=[0,1]; [n le 2 select I[n] else n*(2*n-1)*Self(n-1)+2*n*(n-1)*Self(n-2)-(2*n-1): n in [1..30]]; // Vincenzo Librandi, Sep 28 2015

p := (x,k)->k!^2*sum(x^j/((k-j)!^2*j!),j=0..k); R := (x,n,k)->p(x,k)^n; f := (t,n,k)->sum(coeff(R(x,n,k),x,j)*(t-1)^j*(n*k-j)!,j=0..n*k); seq(f(0,n,2)/2!^n,n=0..18);

RecurrenceTable[{(2*n+3)*a[n+3]==(2*n+5)^2*(n+2)*a[n+2]+(2*n+3)*(n+2)*a[n+1]-2*(2*n+5)*(n+1)*(n+2)*a[n],a[1]==0,a[2]==1,a[3]==10},a,{n,1,25}] (* Vaclav Kotesovec, Aug 31 2012 *)
a[n_] := a[n] = n*(2*n-1)*a[n-1] + 2*n*(n-1)*a[n-2] - (2*n-1); a[0] = 1; a[1] = 0; a[2] = 1; Table[a[n], {n, 0, 14}] (* Jean-François Alcover, Mar 04 2013 *)
a[n_] := Sum[(2*(n-m))! / 2^(n-m) Binomial[n, m] Hypergeometric1F1[m-n, 2*(m - n), -4], {m, 0, n}]; Table[a[n], {n, 0, 16}] (* Peter Luschny, Nov 15 2023 *)

a(n) = (2^n*round(2^(n/2+3/4)*Pi^(-1/2)*exp(-2)*n!*besselk(1/2+n,2^(1/2))))/2^n;
vector(15, n, a(n))\\ Altug Alkan, Sep 28 2015

{ A000459(n) = sum(m=0,n, sum(k=0,n-m, (-1)^k * binomial(n,k) * binomial(n-k,m) * 2^(2*k+m-n) * (2*n-2*m-k)! )); } \\ Max Alekseyev, Oct 06 2016

a(n) = A000316(n)/2^n.
a(n) = Sum_{k=0..n} Sum_{m=0..n-k} (-1)^k * n!/(k!*m!*(n-k-m)!) * 2^(2*k+m-n) * (2*n-2*m-k)!. - Max Alekseyev, Oct 06 2016
G.f.: Sum_{j=0..n*k} coeff(R(x, n, k), x, j)*(t-1)^j*(n*k-j)! where n is the number of kinds of cards, k is the number of cards of each kind (2 in this case) and coeff(R(x, n, k), x, j) is the coefficient of x^j of the rook polynomial R(x, n, k) = (k!^2*sum(x^j/((k-j)!^2*j!))^n (see Riordan or Stanley).
D-finite with recurrence a(n) = n*(2*n-1)*a(n-1)+2*n*(n-1)*a(n-2)-(2*n-1), a(1) = 0, a(2) = 1.
a(n) = round(2^(n/2 + 3/4)*Pi^(-1/2)*exp(-2)*n!*BesselK(1/2+n,2^(1/2))). - Mark van Hoeij, Oct 30 2011
(2*n+3)*a(n+3)=(2*n+5)^2*(n+2)*a(n+2)+(2*n+3)*(n+2)*a(n+1)-2*(2*n+5)*(n+1)*(n+2)*a(n). - Vaclav Kotesovec, Aug 31 2012
Asymptotic: a(n) ~ n^(2*n)*2^(n+1)*sqrt(Pi*n)/exp(2*n+2), Vaclav Kotesovec, Aug 31 2012
a(n) = (1/2^n)*A000316(n) = int_{0..inf} exp(-x)*(1/2*x^2 - 2*x + 1)^n dx. Asymptotic: a(n) ~ ((2*n)!/2^n)*exp(-2)*( 1 - 1/(2*n) - 23/(96*n^2) + O(1/n^3) ). See Nicolaescu. - Peter Bala, Jul 07 2014
Let S = x_1 + ... + x_n. a(n) equals the coefficient of (x_1*...*x_n)^2 in the expansion of product {i = 1..n} (S - x_i)^2 (MacMahon, Chapter III). - Peter Bala, Jul 08 2014
Conjecture: a(n+k) - a(n) is divisible by k. - Mark van Hoeij, Nov 15 2023

More terms and edited by Barbara Haas Margolius (margolius(AT)math.csuohio.edu), Dec 22 2000
Edited by M. F. Hasler, Sep 27 2015
a(0)=1 prepended by Max Alekseyev, Oct 06 2016

A008305 Triangle read by rows: a(n,k) = number of permutations of [n] allowing i->i+j (mod n), j=0..k-1.

Original entry on oeis.org

1, 1, 2, 1, 2, 6, 1, 2, 9, 24, 1, 2, 13, 44, 120, 1, 2, 20, 80, 265, 720, 1, 2, 31, 144, 579, 1854, 5040, 1, 2, 49, 264, 1265, 4738, 14833, 40320, 1, 2, 78, 484, 2783, 12072, 43387, 133496, 362880, 1, 2, 125, 888, 6208, 30818, 126565, 439792, 1334961, 3628800

Offset: 1

N. J. A. Sloane

The point is, we are counting permutations of [n] = {1,2,...,n} with the restriction that i cannot move by more than k places. Hence the phrase "permutations with restricted displacements". - N. J. A. Sloane, Mar 07 2014

The triangle could have been defined as an infinite square array by setting a(n,k) = n! for k >= n.

			a(4,3) = 9 because 9 permutations of {1,2,3,4} are allowed if each i can be placed on 3 positions i+0, i+1, i+2 (mod 4): 1234, 1423, 1432, 3124, 3214, 3412, 4123, 4132, 4213.
Triangle begins:
  1,
  1, 2,
  1, 2,   6,
  1, 2,   9,  24,
  1, 2,  13,  44,  120,
  1, 2,  20,  80,  265,   720,
  1, 2,  31, 144,  579,  1854,   5040,
  1, 2,  49, 264, 1265,  4738,  14833,  40320,
  1, 2,  78, 484, 2783, 12072,  43387, 133496,  362880,
  1, 2, 125, 888, 6208, 30818, 126565, 439792, 1334961, 3628800,
  ...

H. Minc, Permanents, Encyc. Math. #6, 1978, p. 48

Alois P. Heinz, Rows n = 1..23, flattened
Henry Beker and Chris Mitchell, Permutations with restricted displacement, SIAM J. Algebraic Discrete Methods 8 (1987), no. 3, 338--363. MR0897734 (89f:05009)
N. S. Mendelsohn, Permutations with confined displacement, Canad. Math. Bull., 4 (1961), 29-38.
N. Metropolis, M. L. Stein, P. R. Stein, Permanents of cyclic (0,1) matrices, J. Combin. Theory, 7 (1969), 291-321.
Wikipedia, Permanent (mathematics)

Diagonals (from the right): A000142, A000166, A000179, A000183, A004307, A189389, A184965.
Diagonals (from the left): A000211 or A048162, 4*A000382 or A004306 or A000803, A000804, A000805.
a(n,ceiling(n/2)) gives A306738.
Cf. A002467, A306714.

with(LinearAlgebra):
a:= (n, k)-> Permanent(Matrix(n,
             (i, j)-> `if`(0<=j-i and j-i

a[n_, k_] := Permanent[Table[If[0 <= j-i && j-i < k || j-i < k-n, 1, 0], {i, 1,n}, {j, 1, n}]]; Table[Table[a[n, k], {k, 1, n}], {n, 1, 10}] // Flatten (* Jean-François Alcover, Mar 10 2014, after Alois P. Heinz *)

a(n,k) = per(sum(P^j, j=0..k-1)), where P is n X n, P[ i, i+1 (mod n) ]=1, 0's otherwise.

a(n,n) - a(n,n-1) = A002467(n). - Alois P. Heinz, Mar 06 2019

Comments and more terms from Len Smiley
More terms from Vladeta Jovovic, Oct 02 2003
Edited by Alois P. Heinz, Dec 18 2010

A046739 Triangle read by rows, related to number of permutations of [n] with 0 successions and k rises.

Original entry on oeis.org

0, 1, 1, 1, 1, 7, 1, 1, 21, 21, 1, 1, 51, 161, 51, 1, 1, 113, 813, 813, 113, 1, 1, 239, 3361, 7631, 3361, 239, 1, 1, 493, 12421, 53833, 53833, 12421, 493, 1, 1, 1003, 42865, 320107, 607009, 320107, 42865, 1003, 1, 1, 2025, 141549, 1704693, 5494017

Offset: 1

N. J. A. Sloane

From Emeric Deutsch, May 25 2009: (Start)
T(n,k) is the number of derangements of [n] having k excedances. Example: T(4,2)=7 because we have 3*14*2, 3*4*12, 4*3*12, 2*14*3, 2*4*13, 3*4*21, 4*3*21, each with two excedances (marked). An excedance of a permutation p is a position i such that p(i) > i.
Sum_{k>=1} k*T(n,k) = A000274(n+1). (End)
The triangle 1;1,1;1,7,1;... has general term T(n,k) = Sum_{j=0..n+2} (-1)^(n-j)*C(n+2,j)*A123125(j,k+2) and bivariate g.f. ((1-y)*(y*exp(2*x*y) + exp(x*(y+1))(y^2 - 4*y + 1) + y*exp(2*x)))/(exp(x*y) - y*exp(x))^3. - Paul Barry, May 10 2011
The n-th row is the local h-vector of the barycentric subdivision of a simplex, i.e., the Coxeter complex of type A. See Proposition 2.4 of Stanley's paper below. - Kyle Petersen, Aug 20 2012
T(n,k) is the k-th coefficient of the local h^*-polynomial, or box polynomial, of the s-lecture hall n-simplex with s=(2,3,...,n+1).  See Theorem 4.1 of the paper by N. Gustafsson and L. Solus below. - Liam Solus, Aug 23 2018

			Triangle starts:
  0;
  1;
  1,   1;
  1,   7,   1;
  1,  21,  21,   1;
  1,  51, 161,  51,   1;
  1, 113, 813, 813, 113, 1;
  ...
From _Peter Luschny_, Sep 17 2021: (Start)
The triangle shows the coefficients of the following bivariate polynomials:
  [1] 0;
  [2] x*y;
  [3] x^2*y +     x*y^2;
  [4] x^3*y +   7*x^2*y^2 +     x*y^3;
  [5] x^4*y +  21*x^3*y^2 +  21*x^2*y^3 +     x*y^4;
  [6] x^5*y +  51*x^4*y^2 + 161*x^3*y^3 +  51*x^2*y^4 +     x*y^5;
  [7] x^6*y + 113*x^5*y^2 + 813*x^4*y^3 + 813*x^3*y^4 + 113*x^2*y^5 + x*y^6;
  ...
These polynomials are the permanents of the n X n matrices with all entries above the main antidiagonal set to 'x' and all entries below the main antidiagonal set to 'y'. The main antidiagonals consist only of zeros. Substituting x <- 1 and y <- -1 generates the Euler secant numbers A122045. (Compare with A081658.)
(End)

Robert Israel, Table of n, a(n) for n = 1..10012 (rows 0 to 142, flattened)
L. Carlitz, Richard Scoville, and Theresa Vaughan, Enumeration of pairs of permutations and sequences, Bulletin of the American Mathematical Society 80.5 (1974): 881-884. [Annotated scanned copy]
L. Carlitz, N. J. A. Sloane, and C. L. Mallows, Correspondence, 1975
N. Gustafsson and L. Solus. Derangements, Ehrhart theory, and local h-polynomials, arXiv:1807.05246 [math.CO], 2018.
R. Mantaci and F. Rakotondrajao, Exceedingly deranging!, Advances in Appl. Math., 30 (2003), 177-188. [_Emeric Deutsch_, May 25 2009]
Lili Mu and Volkmar Welker, On a question about real rooted polynomials and f-polynomials of simplicial complexes, arXiv:2503.24076 [math.CO], 2025. See p. 8.
D. P. Roselle, Permutations by number of rises and successions, Proc. Amer. Math. Soc., 19 (1968), 8-16. [Annotated scanned copy]
D. P. Roselle, Permutations by number of rises and successions, Proc. Amer. Math. Soc., 20 (1968), 8-16.
R. P. Stanley, Subdivisions and local h-vectors, J. Amer. Math. Soc., 5 (1992), 805-851.
John D. Wiltshire-Gordon, Alexander Woo, and Magdalena Zajaczkowska, Specht Polytopes and Specht Matroids, arXiv:1701.05277 [math.CO], 2017. [See Conjecture 6.2]

Cf. A046740.
Row sums give A000166.
Diagonals give A070313, A070315.
T(2n,n) gives A320337.
Cf. A000274, A081658, A122045, A271697.

G := (1-t)*exp(-t*z)/(1-t*exp((1-t)*z)): Gser := simplify(series(G, z = 0, 15)): for n to 13 do P[n] := sort(expand(factorial(n)*coeff(Gser, z, n))) end do: 0; for n to 11 do seq(coeff(P[n], t, j), j = 1 .. n-1) end do; # yields sequence in triangular form # Emeric Deutsch, May 25 2009

max = 12; f[t_, z_] := (1-t)*(Exp[-t*z]/(1 - t*Exp[(1-t)*z])); se = Series[f[t, z], {t, 0, max}, {z, 0, max}];
coes = Transpose[ #*Range[0, max]! & /@ CoefficientList[se, {t, z}]]; Join[{0}, Flatten[ Table[ coes[[n, k]], {n, 2, max}, {k, 2, n-1}]]] (* Jean-François Alcover, Oct 24 2011, after g.f. *)
E1[n_ /; n >= 0, 0] = 1; (* E1(n,k) are the Eulerian numbers *)
E1[n_, k_] /; k < 0 || k > n = 0;
E1[n_, k_] := E1[n, k] = (n-k) E1[n-1, k-1] + (k+1) E1[n-1, k];
T[n_, k_] := Sum[Binomial[-j-1, -n-1] E1[j, k], {j, 0, n}];
Table[T[n, k], {n, 1, 100}, {k, 1, n-1}] /. {} -> {0} // Flatten (* Jean-François Alcover, Oct 31 2020, after Peter Luschny in A271697 *)
Table[Expand[n!Factor[SeriesCoefficient[(x-y)/(x Exp[y t]-y Exp[x t]),{t,0,n}]]],{n,0,12}]//TableForm (* Mamuka Jibladze, Nov 26 2024 *)

T(n)={my(x='x+O('x^(n+1))); concat([[0]], [Vecrev(p/y) | p<-Vec(-1+serlaplace((y-1)/(y*exp(x)-exp(x*y))))])}
{ my(A=T(10));for(i=1,#A,print(A[i])) } \\ Andrew Howroyd, Nov 13 2024

a(n+1, r) = r*a(n, r) + (n+1-r)*a(n, r-1) + n*a(n-1, r-1).
exp(-t)/(1 - exp((x-1)t)/(x-1)) = 1 + x*t^2/2! + (x+x^2)*t^3/3! + (x+7x^2+x^3)*t^4/4! + (x+21x^2+21x^3+x^4)*t^5/5! + ... - Philippe Deléham, Jun 11 2004
E.g.f.: (y-1)/(y*exp(x) - exp(x*y)). - Mamuka Jibladze, Nov 08 2024

More terms from Larry Reeves (larryr(AT)acm.org), Apr 07 2000

A073701 a(n) = n^2*a(n-1)+(-1)^n.

Original entry on oeis.org

1, 0, 1, 8, 129, 3224, 116065, 5687184, 363979777, 29482361936, 2948236193601, 356736579425720, 51370067437303681, 8681541396904322088, 1701582113793247129249, 382855975603480604081024, 98011129754491034644742145, 28325216499047909012330479904, 9177370145691522519995075488897

Offset: 0

Vladeta Jovovic, Aug 30 2002

nonn

The sequence b(n) := n!^2 satisfies the same recurrence below for a(n) with the initial conditions b(0) = 1, b(1) = 1. It follows that, for n >=3, a(n) = n!^2*(1/(4 + 4/(8 + 9/(15 +...+ (n-1)^2/(n^2-1))))). Hence BesselJ(0,2) := sum {k = 0..inf} (-1)^k/k!^2 = 1/(4 + 4/(8 + 9/(15 + ...+(n-1)^2/(n^2+1 + ...)))) = 0.22388 90779 ... . Cf. A006040. - Peter Bala, Jul 09 2008

Seiichi Manyama, Table of n, a(n) for n = 0..253

Cf. A000166, A006040.

[1] cat [ n eq 1 select 0 else n^2*Self(n-1)+(-1)^n:n in [1..15]]; // Marius A. Burtea, Feb 13 2020

Join[{a = 1}, Table[a = a*n^2 + (-1)^n, {n, 15}]] (* Jayanta Basu, Jul 08 2013 *)

a(n) = n!^2*Sum_{k=0..n} (-1)^k/k!^2.
BesselJ(0, 2*sqrt(x))/(1-x) = Sum_{n>=0} a(n)*x^n/n!^2.
a(n) = round(n!^2*BesselJ(0, 2)), n>0.
Recurrence: a(0) = 1, a(1) = 0, a(n) = (n^2-1)*a(n-1) + (n-1)^2*a(n-2), n >= 2. - Peter Bala, Jul 09 2008, corrected by Georg Fischer, Feb 13 2020
a(n) = Sum_{k=0..n} (-1)^(n-k)*(k!*binomial(n,k))^2. - Ridouane Oudra, Jul 11 2025

A352828 Number of strict integer partitions y of n with no fixed points y(i) = i.

Original entry on oeis.org

1, 0, 1, 2, 2, 2, 2, 3, 4, 6, 8, 10, 12, 14, 16, 19, 22, 26, 32, 38, 46, 56, 66, 78, 92, 106, 123, 142, 162, 186, 214, 244, 280, 322, 368, 422, 484, 552, 630, 718, 815, 924, 1046, 1180, 1330, 1498, 1682, 1888, 2118, 2372, 2656, 2972, 3322, 3712, 4146, 4626

Offset: 0

Gus Wiseman, May 15 2022

nonn

			The a(0) = 1 through a(12) = 12 partitions (A-C = 10..12; empty column indicated by dot; 0 is the empty partition):
   0  .  2  3    4    5    6    7    8     9     A      B      C
            21   31   41   51   43   53    54    64     65     75
                                61   71    63    73     74     84
                                     431   81    91     83     93
                                           432   532    A1     B1
                                           531   541    542    642
                                                 631    632    651
                                                 4321   641    732
                                                        731    741
                                                        5321   831
                                                               5421
                                                               6321

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

The version for permutations is A000166, complement A002467.
The reverse version is A025147, complement A238395, non-strict A238394.
The non-strict version is A064428 (unproved, ranked by A352826 or A352873).
The version for compositions is A238351, complement A352875.
The complement is A352829, non-strict A001522 (unproved, ranked by A352827 or A352874).
A000041 counts partitions, strict A000009.
A000700 counts self-conjugate partitions, ranked by A088902.
A008290 counts permutations by fixed points, unfixed A098825.
A115720 and A115994 count partitions by their Durfee square.
A238349 counts compositions by fixed points, complement A352523.
A238352 counts reversed partitions by fixed points, rank statistic A352822.
A352833 counts partitions by fixed points.
Cf. A008292, A064410, A111133, A114088, A118199, A188674, A257990, A352824, A352825, A352830, A352872.

pq[y_]:=Length[Select[Range[Length[y]],#==y[[#]]&]];
Table[Length[Select[IntegerPartitions[n],UnsameQ@@#&&pq[#]==0&]],{n,0,30}]

G.f.: Sum_{n>=0} q^(n*(3*n+1)/2)*Product_{k=1..n} (1+q^k)/(1-q^k). - Jeremy Lovejoy, Sep 26 2022

A024000 a(n) = 1 - n.

Original entry on oeis.org

1, 0, -1, -2, -3, -4, -5, -6, -7, -8, -9, -10, -11, -12, -13, -14, -15, -16, -17, -18, -19, -20, -21, -22, -23, -24, -25, -26, -27, -28, -29, -30, -31, -32, -33, -34, -35, -36, -37, -38, -39, -40, -41, -42, -43, -44, -45, -46, -47, -48, -49, -50, -51, -52, -53, -54, -55, -56

Offset: 0

N. J. A. Sloane

a(n) is the weighted sum over all derangements (permutations with no fixed points) of n elements where each permutation with an odd number of cycles has weight +1 and each with an even number of cycles has weight -1. [Michael Somos, Jan 19 2011]

			a(4) = -3 because there are 6 derangements with one 4-cycle with weight -1 and 3 derangements with two 2-cycles with weight +1. - _Michael Somos_, Jan 19 2011

Vincenzo Librandi, Table of n, a(n) for n = 0..1000
Tanya Khovanova, Recursive Sequences
Index entries for linear recurrences with constant coefficients, signature (2,-1).

Cf. A000007, A000166, A087981, A137775. - Michael Somos, Jan 19 2011
Cf. A001489, A094816.
A022958 shifted left.

[1-n: n in [0..50]]; // Vincenzo Librandi, Apr 29 2011

A024000:=n->1-n: seq(A024000(n), n=0..100); # Wesley Ivan Hurt, Mar 02 2016

CoefficientList[Series[(1 - 2 x)/(1 - x)^2, {x, 0, 60}], x] Range[0, 60]!
CoefficientList[Series[Exp[x] (1 - x), {x, 0, 60}], x]
1-Range[0,60] (* Harvey P. Dale, Sep 18 2013 *)
Flatten[NestList[(#/.x_/;x>1->Sequence[x,2x])-1&,{1},60]]
(* Robert G. Wilson v, Mar 02 2016 *)

{a(n) = 1 - n} /* Michael Somos, Jan 19 2011 */

E.g.f.: (1-x)*exp(x).
a(n) = Sum_{k=0..n} A094816(n,k)*(-1)^k (alternating row sums of Poisson-Charlier coefficient matrix).
O.g.f.: (1-2*x)/(1-x)^2. a(n+1) = A001489(n). - R. J. Mathar, May 28 2008
a(n) = 2*a(n-1)-a(n-2) for n>1. - Wesley Ivan Hurt, Mar 02 2016

cp's OEIS Frontend

A132382 Lower triangular array T(n,k) generator for group of arrays related to A001147 and A102625.

Views

Author

Keywords

Comments

Examples

Formula

Extensions

A170942 Take the permutations of lengths 1, 2, 3, ... arranged lexicographically, and replace each permutation with the number of its fixed points.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Extensions

A005001 a(n) = Sum_{k=0..n-1} Bell(k), where the Bell numbers Bell(k) are given in A000110.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Maple

Mathematica

Python

Formula

A068996 Decimal expansion of 1 - 1/e.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

A000459 Number of multiset permutations of {1, 1, 2, 2, ..., n, n} with no fixed points.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

PARI

Formula

Extensions

A008305 Triangle read by rows: a(n,k) = number of permutations of [n] allowing i->i+j (mod n), j=0..k-1.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A046739 Triangle read by rows, related to number of permutations of [n] with 0 successions and k rises.

Views