OFFSET
0,3
COMMENTS
a(n) is also the number of matchings on the n-crown graph. - Eric W. Weisstein, Jul 11 2011
LINKS
Vincenzo Librandi, Table of n, a(n) for n = 0..200
A. Laradji and A. Umar, Combinatorial results for the symmetric inverse semigroup, Semigroup Forum 75, (2007), 221-236.
A. Laradji and A. Umar, Further combinatorial properties of the symmetric inverse semigroup, 2012. [From N. J. A. Sloane, Dec 25 2012]
A. Umar, Some combinatorial problems in the theory of symmetric ..., Algebra Disc. Math. 9 (2010) 115-126.
Eric Weisstein's World of Mathematics, Crown Graph.
Eric Weisstein's World of Mathematics, Independent Edge Set.
Eric Weisstein's World of Mathematics, Matching.
FORMULA
a(n) = A144088(n,0).
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
a(n) = n! * Sum_{k=0..n} binomial(k,n-k)/(n-k)!. - Seiichi Manyama, Aug 06 2024
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
A144085 := proc(n)
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;
end proc: # R. J. Mathar, Nov 03 2015
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);
Vec(serlaplace(egf)) /* Joerg Arndt, Jul 11 2011 */
CROSSREFS
KEYWORD
nonn
AUTHOR
Abdullahi Umar, Sep 10 2008, Sep 15 2008
STATUS
approved
