login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A144085 a(n) is the number of partial bijections (or subpermutations) of an n-element set without fixed points (also called partial derangements). 8
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

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

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.

Sequence in context: A306003 A214840 A060223 * A003708 A327679 A330353

Adjacent sequences:  A144082 A144083 A144084 * A144086 A144087 A144088

KEYWORD

nonn

AUTHOR

Abdullahi Umar, Sep 10 2008, Sep 15 2008

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified September 21 01:52 EDT 2020. Contains 337266 sequences. (Running on oeis4.)