login
Rencontres numbers: number of permutations of [n] with exactly 4 fixed points.
(Formerly M4969 N2132)
12

%I M4969 N2132 #59 Jul 06 2023 05:29:03

%S 1,0,15,70,630,5544,55650,611820,7342335,95449640,1336295961,

%T 20044438050,320711010620,5452087178160,98137569209940,

%U 1864613814984984,37292276299704525,783137802293789040,17229031650463366195,396267727960657413630

%N Rencontres numbers: number of permutations of [n] with exactly 4 fixed points.

%D J. Riordan, An Introduction to Combinatorial Analysis, Wiley, 1958, p. 65.

%D N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).

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

%H T. D. Noe, <a href="/A000475/b000475.txt">Table of n, a(n) for n=4..100</a>

%H FindStat - Combinatorial Statistic Finder, <a href="http://www.findstat.org/St000022">The number of fixed points of a permutation</a>

%H <a href="/index/Per#IntegerPermutationCatAuto">Index entries for sequences related to permutations with fixed points</a>

%F a(n) = sum((-1)^j*n!/(4!*j!), j=2..n-4) = A008290(n,4).

%F a(n) = A000166(n)*binomial(n+4, 4). - Robert Goodhand (robert(AT)rgoodhand.fsnet.co.uk), Nov 08 2001

%F E.g.f.: (exp(-x)/(1-x))*(x^4/4!). In general, for k fixed points:(exp(-x)/(1-x)) * (x^k/k!). - _Wenjin Woan_, Nov 22 2008

%F a(n) ~ n! * exp(-1)/24, in general a(n) ~ n! * exp(-1)/k!. - _Vaclav Kotesovec_, Mar 16 2014

%F a(n) = n*a(n-1) + (-1)^n*binomial(n,4) with a(n) = 0 for n = 0,1,2,3. - _Chai Wah Wu_, Nov 01 2014

%F D-finite with recurrence (-n+4)*a(n) +n*(n-5)*a(n-1) +n*(n-1)*a(n-2)=0. - _R. J. Mathar_, Nov 02 2015

%F O.g.f.: (1/24)*Sum_{k>=4} k!*x^k/(1 + x)^(k+1). - _Ilya Gutkovskiy_, Apr 13 2017

%p a:=n->sum(n!*sum((-1)^k/(k-3)!, j=0..n), k=3..n): seq(-a(n)/4!, n=3..22); # _Zerinvary Lajos_, May 25 2007

%p G(x):=exp(-x)/(1-x)*(x^4/4!): f[0]:=G(x): for n from 1 to 26 do f[n]:=diff(f[n-1],x) od: x:=0: seq(f[n],n=4..23); # _Zerinvary Lajos_, Apr 03 2009

%t Table[Subfactorial[n - 4]*Binomial[n, 4], {n, 4, 23}] (* _Zerinvary Lajos_, Jul 10 2009 *)

%o (PARI) x='x+O('x^66); Vec( serlaplace(exp(-x)/(1-x)*(x^4/4!)) ) \\ _Joerg Arndt_, Feb 19 2014

%o (Python)

%o from sympy import binomial

%o A000475_list, m, x = [], 1, 0

%o for n in range(4,100):

%o x, m = x*n + m*binomial(n,4), -m

%o A000475_list.append(x) # _Chai Wah Wu_, Nov 01 2014

%Y Cf. A008290.

%Y A diagonal of A008291.

%Y Cf. A170942.

%K nonn

%O 4,3

%A _N. J. A. Sloane_

%E Formula corrected by _Sean A. Irvine_, Oct 26 2010