|
|
A259869
|
|
a(0) = -1; for n > 0, number of indecomposable derangements, i.e., no fixed points, and not fixing [1..j] for any 1 <= j < n.
|
|
8
|
|
|
-1, 0, 1, 2, 8, 40, 244, 1736, 14084, 128176, 1292788, 14313272, 172603124, 2252192608, 31620422980, 475350915656, 7618759828388, 129697180826512, 2337145267316500, 44446207287450968, 889595868295057364, 18693361200724345024, 411475140936880082020
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,4
|
|
COMMENTS
|
The derangement characterization would yield a(0) = 1, but -1 is the value given in Martin and Kearney's paper. - Eric M. Schmidt, Jul 10 2015
|
|
LINKS
|
|
|
FORMULA
|
Martin and Kearney (2015) give both a recurrence and a g.f.
The recurrence is a(0)=-1, a(1)=0; a(n) = (n-1)*a(n-1) + (n-3)*a(n-2) + Sum_{j=1..n-1} a(j)*a(n-j).
a(n) ~ n!/exp(1) * (1 - 2/n^2 - 6/n^3 - 29/n^4 - 196/n^5 - 1665/n^6 - 16796/n^7 - 194905/n^8 - 2549468/n^9 - 37055681/n^10), for coefficients see A260578. - Vaclav Kotesovec, Jul 28 2015
G.f.: -1 + x^2/(1 - 2*x - 4*x^2/(1 - 4*x - 9*x^2/(1 - 6*x - 16*x^2/(1 - ...)))), a continued fraction. - Ilya Gutkovskiy, Aug 22 2018
|
|
EXAMPLE
|
There are 9 derangements of 1,2,3,4. All of them are indecomposable except for 2,1,4,3. Thus a(4) = 8. - Eric M. Schmidt, Jul 10 2015
|
|
MATHEMATICA
|
Clear[a]; a[0]=-1; a[1]=0; a[n_]:=a[n]=(n-1)*a[n-1] + (n-3)*a[n-2] + Sum[a[j]*a[n-j], {j, 1, n-1}]; Table[a[n], {n, 0, 20}] (* Vaclav Kotesovec, Jul 29 2015 *)
nmax = 25; CoefficientList[Assuming[Element[x, Reals], Series[-x*E^(1 + 1/x)/ExpIntegralEi[1 + 1/x], {x, 0, nmax}]], x] (* Vaclav Kotesovec, Aug 05 2015 *)
|
|
PROG
|
(Sage)
def a(n) : return -1 if n==0 else 0 if n==1 else (n-1)*a(n-1) + (n-3)*a(n-2) + sum(a(j)*a(n-j) for j in [1..n-1]) # Eric M. Schmidt, Jul 10 2015
|
|
CROSSREFS
|
|
|
KEYWORD
|
sign,easy
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|