A144085 a(n) is the number of partial bijections (or subpermutations) of an n-element set without fixed points (also called partial derangements).

1, 1, 4, 18, 108, 780, 6600, 63840, 693840, 8361360, 110557440, 1590351840, 24713156160, 412393101120, 7352537512320, 139443752448000, 2802408959750400, 59479486120454400, 1329239028813696000, 31194214921732262400, 766888191387539020800, 19707387644116280908800, 528327710066244459571200

Offset: 0

Author

Abdullahi Umar, Sep 10 2008, Sep 15 2008

Keywords

• nonn

Comments

a(n) is also the number of matchings on the n-crown graph. - Eric W. Weisstein, Jul 11 2011

Examples

			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.
		

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.

Crossrefs

Cf. A144088.

Column k=0 of A369292.

Programs

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 *)

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 */

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