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,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

Cf. A144088.

Column k=0 of A369292.

Sequence in context: A306003 A214840 A060223 * A375604 A003708 A327679

Adjacent sequences: A144082 A144083 A144084 * A144086 A144087 A144088

Keyword

nonn

Author

Abdullahi Umar, Sep 10 2008, Sep 15 2008

Status

approved