|
|
A144085
|
|
a(n) is the number of partial bijections (or subpermutations) of an n-element set without fixed points (also called partial derangements).
|
|
9
|
|
|
1, 1, 4, 18, 108, 780, 6600, 63840, 693840, 8361360, 110557440, 1590351840, 24713156160, 412393101120, 7352537512320, 139443752448000, 2802408959750400, 59479486120454400, 1329239028813696000, 31194214921732262400, 766888191387539020800, 19707387644116280908800, 528327710066244459571200
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,3
|
|
COMMENTS
|
a(n) is also the number of matchings on the n-crown graph. - Eric W. Weisstein, Jul 11 2011
|
|
LINKS
|
Eric Weisstein's World of Mathematics, Matching.
|
|
FORMULA
|
a(n) = n! * Sum_{m=0..n} (-1^m/m!) * Sum_{j=0..n-m} binomial(n-m, j)/j!.
a(n) = (2*n-1)*a(n-1) - (n-1)*(n-3)*a(n-2) - (n-1)*(n-2)*a(n-3), a(0)=1, a(n)=0 if n < 0.
E.g.f. for number of partial bijections of an n-element set with exactly k fixed points is (x^k/k!)*exp(x^2/(1-x))/(1-x). - Vladeta Jovovic, Nov 09 2008
a(n) ~ exp(2*sqrt(n)-n-3/2)*n^(n+1/4)/sqrt(2) * (1+79/(48*sqrt(n))). - Vaclav Kotesovec, Aug 11 2013
|
|
EXAMPLE
|
a(3) = 18 because there are exactly 18 partial derangements (on a 3-element set), namely: the empty map, (1)->(2), (1)->(3), (2)->(1), (2)->(3), (3)->(1), (3)->(2), (1,2)->(2,1), (1,2)->(2,3), (1,2)->(3,1), (1,3)->(2,1), (1,3)->(3,1), (1,3)->(3,2), (2,3)->(1,2), (2,3)->(3,1), (2,3)->(3,2), (1,2,3)->(2,3,1), (1,2,3)->(3,1,2) - the mappings are coordinate-wise.
|
|
MAPLE
|
option remember;
if n < 0 then
0 ;
elif n < 2 then
1;
else
(2*n-1)*procname(n-1)-(n-1)*(n-3)*procname(n-2)-(n-1)*(n-2)*procname(n-3) ;
end if;
|
|
MATHEMATICA
|
Table[n! Sum[(-1)^k/k! LaguerreL[n - k, -1], {k, 0, n}], {n, 0, 30}]
RecurrenceTable[{n (1 + n) a[n] + (-1 + n^2) a[1 + n] + a[3 + n] == (3 + 2 n) a[2 + n], a[1] == 1, a[2] == 1, a[3] == 4}, a, {n, 20}] (* Eric W. Weisstein, Sep 30 2017 *)
|
|
PROG
|
(PARI) x='x+O('x^66);
k=0; egf=x^k/k!*exp(x^2/(1-x))/(1-x);
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|