A000166 -id:A000166 - cp's OEIS frontend

A100015 Subfactorial primes: primes of the form !k + 1 or !k - 1. Subfactorial or rencontres numbers or derangements !k = A000166(k).

2, 3, 43, 481066515733, 130850092279663

Offset: 1

Jonathan Vos Post, Nov 18 2004

nonn

No additional terms through k <= 2000. - Harvey P. Dale, Feb 17 2023

			a(1) = 2 because !0 = !2 = 1, so !0 + 1 = !2 + 1 = 2.
a(5) = 130850092279663 because the 5th subfactorial prime is !17 - 1 = 130850092279664 - 1 = 130850092279663.

R. A. Brualdi and H. J. Ryser: Combinatorial Matrix Theory, 1992, Section 7.2, p. 202.
H. J. Ryser, Combinatorial Mathematics. Mathematical Association of America, Carus Mathematical Monograph 14, 1963, p. 23.

R. M. Dickau, Derangement diagrams.
H. Fripertinger, The Recontre Numbers, an online calculator.
Mehdi Hassani, Derangements and Applications, Journal of Integer Sequences, Vol. 6 (2003), #03.1.2

Cf. A000166.

Select[Union[Flatten[Table[Subfactorial[n]+{1,-1},{n,20}]]],PrimeQ] (* Harvey P. Dale, Feb 17 2023 *)

A101560 Triangle read by rows giving the coefficients of general sum formulas of n-th Subfactorial numbers (A000166). The k-th row (k>=1) contains T(i,k) for i=1 to 2k-1, where T(i,k) satisfies Subf(n) = Sum_{k=1..n} Sum_{i=1..2k-1} T(i,k) * C(n-k,i-1) * n^(n-k).

Original entry on oeis.org

1, -2, -2, -1, 4, 11, 16, 11, 3, -10, -55, -147, -215, -179, -80, -15, 34, 305, 1247, 2910, 4224, 3904, 2245, 735, 105, -154, -1949, -10971, -35970, -76269, -109554, -108184, -72639, -31780, -8190, -945, 874, 14297, 103679, 443762, 1255671, 2484619, 3535727, 3654132, 2726787, 1434797

Offset: 1

André F. Labossière, Dec 06 2004

			Subf(7) = 7^(7 - 1) - {2 + 2*(7 - 2) + C(7 - 2,2)}*7^(7 - 2) + {4 + 11*(7 - 3) + 16*C(7 - 3,2) + 11*C(7 - 3,3) + 3*C(7 - 3,4)}*7^(7 - 3) - {10 + 55*(7 - 4) + 147*C(7 - 4,2) + 215*C(7 - 4,3)}*7^(7 - 4) + ...
= 7^6 - {2 + 10 + 10}*7^5 + {4 + 44 + 96 + 44 + 3}*7^4 - {10 + 165 + 441 + 215}*7^3 + {34 + 610 + 1247}*7^2 - {154 + 1949}*7 + {874}
= 7^6 - 22*7^5 + 191*7^4 - 831*7^3 + 1891*7^2 - 2103*7 + 874
= 117649 - 369754 + 458591 - 285033 + 92659 - 14721 + 874 = 265.

Cf. A101559, A000166, A000110, A101033, A101032, A000204, A100492, A099731, A000045, A094216, A094638, A000108.

A101800 a(n)= abs(det[A000166(i+j+1)]), i,j=0...n, is the absolute value of the Hankel determinant of order n+1 of the derangements numbers, cf. A000166.

Original entry on oeis.org

0, 1, 16, 2160, 4644864, 220962816000, 126311423016960000, 97655159393202733056000000, 2873961139404949958783139840000000000, 5118723340142578530942677236206891171840000000000

Offset: 0

Karol A. Penson, Dec 17 2004

nonn

a(n) = abs(product( (p!)^2,p=0..n )*(n+1)!*LaguerreL(n+1,0,1)), n=0,1..., where LaguerreL(n,lambda,x) are generalized Laguerre polynomial.

Cf. A000166, A055209, A009940, A101799.

a[n_] := Table[Subfactorial[i+j+1], {i, 0, n}, {j, 0, n}] // Det // Abs;
Table[a[n], {n, 0, 9}] (* Jean-François Alcover, Aug 18 2024 *)

a(n) = abs(A055209(n)*A009940(n+1)). [corrected by Vaclav Kotesovec, Feb 25 2019]

A105926 First differences of A000166.

Original entry on oeis.org

-1, 1, 1, 7, 35, 221, 1589, 12979, 118663, 1201465, 13349609, 161530271, 2114578091, 29780308117, 448995414685, 7215997736011, 123153028027919, 2224451568754289, 42395429898611153, 850263899633257015, 17900292623858042419, 394701452356069835341

Offset: 0

N. J. A. Sloane, Apr 27 2005

sign

G. C. Greubel, Table of n, a(n) for n = 0..200

Cf. A000166.

a:=n->sum((-1)^k * (n-k-1) * n!/k!, k=0..n): seq(a(n), n=0..20); # Zerinvary Lajos, Jun 27 2007
A000166:= gfun:-rectoproc({a(0)=1,a(1)=0,a(n) = (n-1)*(a(n-1)+a(n-2))},a(n),remember):
seq(A000166(n+1)-A000166(n),n=0..100); # Robert Israel, Nov 03 2015

Table[Subfactorial[n] - Subfactorial[n - 1], {n, 1, 22}] (* Zerinvary Lajos, Jul 09 2009 *)
Table[n Subfactorial[n] - (-1)^n, {n, 0, 20}] (* Vladimir Reshetnikov, Nov 01 2015 *)
Differences[Table[(-1)^n HypergeometricPFQ[{-n,1},{},1], {n,0,20}]] (* Peter Luschny, Nov 03 2015 *)

a(n) = n*!n - (-1)^n, where !n = A000166(n) is subfactorial. - Vladimir Reshetnikov, Nov 03 2015

(2n + 1) a(n+2) = (2n^2 + 5n + 4) a(n+1) + (2n^2 + 5n + 3) a(n). E.g.f.: exp(-x)*(2*x-1)/(x-1)^2. - Robert Israel, Nov 03 2015

A105927 Let d(n) = A000166(n); then a(n) = ( (n^2+n-1)d(n) + (-1)^(n-1)(n-1) )/2.

Original entry on oeis.org

0, 0, 2, 12, 84, 640, 5430, 50988, 526568, 5940576, 72755370, 961839340, 13656650172, 207316760352, 3351430059614, 57487448630220, 1042952206111440, 19954639072648768, 401578933206288978, 8480263630552747596, 187505565234912994340, 4332318322289242716480

Offset: 0

N. J. A. Sloane, Apr 27 2005

nonn

Wang, Miska, & Mező call these 2-derangement numbers.
Number of permutations p of [n] such that p(k) = k+2 for exactly two k in the range 0Vladeta Jovovic, Dec 14 2007
Number of derangements of the multiset {0,0,1,2,...,n}.  For example a(3)=12 because we have: {1,2,0,3,0}, {1,2,3,0,0}, {1,3,0,0,2}, {1,3,2,0,0}, {2,1,0,3,0}, {2,1,3,0,0}, {2,3,0,0,1}, {2,3,0,1,0}, {3,1,0,0,2}, {3,1,2,0,0}, {3,2,0,0,1}, {3,2,0,1,0}. - Geoffrey Critzer, Jun 02 2014
Number of derangements of a set of n + 2 elements such that the first two elements belong to distinct cycles. - Istvan Mezo, Apr 05 2017

P. A. MacMahon, Combinatory Analysis, 2 vols., Chelsea, NY, 1960, see p. 108.

Alois P. Heinz, Table of n, a(n) for n = 0..300
C.-Y. Wang, P. Miska, I. Mező, The r-derangement numbers, Discrete Mathematics 340.7 (2017): 1681-1692.

Cf. A000153, A018934, A055790.

a:= proc(n) option remember; `if`(n<3, n*(n-1),
       n*(n-1)*(a(n-1)+a(n-2))/(n-2))
    end:
seq(a(n), n=0..25);  # Alois P. Heinz, Jun 03 2014

Table[(Subfactorial[n+2]-2Subfactorial[n+1]-Subfactorial[n])/2,{n,0,21}] (* Geoffrey Critzer, Jun 02 2014 *)

s(n) = if( n<1, 1, n * s(n-1) + (-1)^n);
a(n) = (s(n + 2) - 2*s(n + 1) - s(n))/2; \\ Indranil Ghosh, Apr 06 2017

a(n) = n*(n-1)*(a(n-1) + a(n-2))/(n-2) for n >= 3, a(n) = n*(n-1) for n < 3. - Alois P. Heinz, Jun 03 2014
a(n) ~ sqrt(Pi/2) * n^(n+5/2) / exp(n+1). - Vaclav Kotesovec, Sep 05 2014
a(n) = (n^2 + n + 1) * n!/e + O(1). - Charles R Greathouse IV, Apr 07 2017

A105928 a(n) = ((n^3 - 4n + 1)A000166(n) + (-1)^(n+1)(n-1)^2) / 6.

Original entry on oeis.org

0, 0, 0, 6, 72, 780, 8520, 97650, 1189104, 15441048, 213816240, 3152287710, 49369524600, 819340272036, 14373198453432, 265869427695690, 5173710021214560, 105683257864542000, 2261482144869433824, 50598160483438733238, 1181568482279829616680, 28750554997809594831420

Offset: 0

N. J. A. Sloane, Apr 27 2005

nonn

Wang, Miska, & Mező call these 3-derangement numbers. a(n) counts the fixed point free permutations (derangements) on n + 3 elements such that the first 3 elements belong to distinct cycles. - Istvan Mezo, Apr 05 2017

P. A. MacMahon, Combinatory Analysis, 2 vols., Chelsea, NY, 1960, see p. 108.

Vincenzo Librandi, Table of n, a(n) for n = 0..200
C.-Y. Wang, P. Miska, I. Mező, The r-derangement numbers, Discrete Mathematics 340.7 (2017): 1681-1692.

Table[((n^3 - 4 n + 1) Subfactorial[n] + (-1)^(n + 1) (n - 1)^2)/ 6, {n, 0, 21}] (* Michael De Vlieger, Apr 05 2017 *)

s(n) = if( n<1, 1, n * s(n-1) + (-1)^n);
a(n) = ((n^3 - 4*n + 1) * s(n) + (-1)^(n + 1) * (n - 1)^2)/6; \\ Indranil Ghosh, Apr 06 2017

G.f.: (2*x-1)*hypergeom([1,2],[],x/(1+x))/(3*(1+x)^2) - (5*x-1)*hypergeom([2,3],[],x/(1+x))/(3*(1+x)^3). - Mark van Hoeij, Nov 19 2011

E.g.f.: x^3*exp(-x)/(1-x)^4. - Istvan Mezo, Apr 05 2017

A334716 a(n) = !n + n * n!, where !n = A000166(n) is subfactorial of n.

Original entry on oeis.org

1, 1, 5, 20, 105, 644, 4585, 37134, 337393, 3399416, 37622961, 453769370, 5924234041, 83242063332, 1252567177849, 20096182035734, 342461702459745, 6177536369911664, 117598028364137953, 2356007639327453106, 49553054794725702121, 1091705092860949184540

Offset: 0

Alois P. Heinz, May 08 2020

nonn

Alois P. Heinz, Table of n, a(n) for n = 0..448
Wikipedia, Derangement

Main diagonal of A334715.

Cf. A000142, A000166, A001563.

a:= proc(n) option remember; `if`(n<3, [1, 1, 5][n+1],
      ((2*n+1)*(n-1)*a(n-1)-(n-1)*(n^2-2*n-2)*a(n-2)
       -(n+1)*(n-1)*(n-2)*a(n-3))/n)
    end:
seq(a(n), n=0..23);

a[n_] := Subfactorial[n] + n n!;
a /@ Range[0, 23] (* Jean-François Alcover, Apr 26 2021 *)

E.g.f.: x/(x-1)^2 - exp(-x)/(x-1).

a(n) = A000166(n) + A001563(n) = !n + n * n!.

A335691 A000166(n)^2.

Original entry on oeis.org

1, 0, 1, 4, 81, 1936, 70225, 3437316, 220017889, 17821182016, 1782120871521, 215636596084900, 31051670188655281, 5247732257301156624, 1028555522495168900401, 231424992560450869558756, 59244798095490816735545025, 17121746649596584336387952896

Offset: 0

N. J. A. Sloane, Jul 20 2020

nonn

I. Kaplansky and J. Riordan, The problème des ménages, Scripta Math. 12, (1946), 113-124. See p. 115.

I. Kaplansky and J. Riordan, The problème des ménages, Scripta Math. 12, (1946), 113-124. [Scan of annotated copy]

Cf. A000166, A335692, A335693.

A337986 Prime numbers p such that v_p(A000166(k)) = v_p(k-1) for all k > 1, where v_p(k) is the p-adic valuation of k.

Original entry on oeis.org

2, 5, 7, 17, 19, 23, 29, 43, 59, 61, 71, 73, 107, 113, 131, 137, 149, 157, 173, 181, 191, 197, 199, 229, 233, 239, 241, 251, 257, 311, 317, 331, 349, 383, 401, 409, 421, 461, 491, 499, 541, 547, 557, 599, 601, 613, 619, 641, 653, 673, 719, 751, 761, 787, 797, 809

Offset: 1

Amiram Eldar, Jan 29 2021

nonn

Miska (2016) proved that the complement of this sequence within the primes is infinite, and conjectured that this sequence is also infinite, and that its asymptotic density within the primes is 1/e (A068985). Numerically, he found that there are 28990 terms below 10^6, which are about 37% of all the primes less than 10^6.

			2 is a term since A007814(A000166(k)) = A007814(k-1) for all k > 1.

Amiram Eldar, Table of n, a(n) for n = 1..1000
Piotr Miska, Arithmetic properties of the sequence of derangements, Journal of Number Theory, Vol. 163 (2016), pp. 114-145; arXiv preprint, arXiv:1508.01987 [math.NT], 2015.

Cf. A000166, A000255, A007814, A068985.

e[n_] := e[n] = Subfactorial[n]/(n - 1); q[p_] := PrimeQ[p] && AllTrue[Table[e[n], {n, 2, p + 1}], ! Divisible[#, p] &]; Select[Range[1000], q]

A prime p is a term if and only if p does not divide any of the numbers A000255(k), k in {2, ..., p+1}.

A378158 Numbers k such that lpf(!k) < lpf(k-1), where lpf(k) = A020639(k) and !k = A000166(k).

Original entry on oeis.org

20, 38, 42, 60, 90, 104, 108, 110, 114, 132, 138, 152, 164, 170, 174, 192, 194, 198, 240, 242, 258, 284, 294, 324, 338, 350, 360, 368, 390, 398, 434, 438, 450, 462, 482, 488, 500, 504, 510, 522, 524, 528, 542, 548, 564, 570, 588, 600, 602, 614, 618, 632, 642, 644, 648

Offset: 1

Amiram Eldar, Nov 18 2024

nonn

Since (k-1) | !k, we have lpf(!k) <= lpf(k-1). This sequence gives the values of k for which the inequality holds.

Amiram Eldar, Table of n, a(n) for n = 1..10000

Cf. A000166, A020639, A337986, A378157.

okQ[k_, p_] := Module[{q = 2}, While[q < p && !Divisible[k, q], q = NextPrime[q]]; q < p]; q[k_] := okQ[Subfactorial[k], FactorInteger[k-1][[1, 1]]]; Select[Range[3, 650], q]

ok(k, p) = {my(q = 2); while(q < p && k % q, q = nextprime(q+1)); q < p;}
lista(kmax) = {my(s = 1); for(k = 3, kmax, s = k * s + (-1)^k; if(ok(s, factor(k-1)[1,1]), print1(k, ", ")));}

cp's OEIS Frontend

A100015 Subfactorial primes: primes of the form !k + 1 or !k - 1. Subfactorial or rencontres numbers or derangements !k = A000166(k).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

A101560 Triangle read by rows giving the coefficients of general sum formulas of n-th Subfactorial numbers (A000166). The k-th row (k>=1) contains T(i,k) for i=1 to 2*k-1, where T(i,k) satisfies Subf(n) = Sum_{k=1..n} Sum_{i=1..2*k-1} T(i,k) * C(n-k,i-1) * n^(n-k).

Views

Author

Keywords

Examples

Crossrefs

A101800 a(n)= abs(det[A000166(i+j+1)]), i,j=0...n, is the absolute value of the Hankel determinant of order n+1 of the derangements numbers, cf. A000166.

Views

Author

Keywords

Comments

Crossrefs

Programs

Mathematica

Formula

A105926 First differences of A000166.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A105927 Let d(n) = A000166(n); then a(n) = ( (n^2+n-1)*d(n) + (-1)^(n-1)*(n-1) )/2.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

A105928 a(n) = ((n^3 - 4n + 1)*A000166(n) + (-1)^(n+1)*(n-1)^2) / 6.

Views

Author

Keywords

Comments

References

Links

Programs

Mathematica

PARI

Formula

A334716 a(n) = !n + n * n!, where !n = A000166(n) is subfactorial of n.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A335691 A000166(n)^2.

Views

Author

Keywords

References

Links

Crossrefs

A337986 Prime numbers p such that v_p(A000166(k)) = v_p(k-1) for all k > 1, where v_p(k) is the p-adic valuation of k.

Views

A101560 Triangle read by rows giving the coefficients of general sum formulas of n-th Subfactorial numbers (A000166). The k-th row (k>=1) contains T(i,k) for i=1 to 2k-1, where T(i,k) satisfies Subf(n) = Sum_{k=1..n} Sum_{i=1..2k-1} T(i,k) * C(n-k,i-1) * n^(n-k).

A105927 Let d(n) = A000166(n); then a(n) = ( (n^2+n-1)d(n) + (-1)^(n-1)(n-1) )/2.

A105928 a(n) = ((n^3 - 4n + 1)A000166(n) + (-1)^(n+1)(n-1)^2) / 6.