|
%I #62 Jan 25 2024 07:49:11
%S 1,1,4,18,108,780,6600,63840,693840,8361360,110557440,1590351840,
%T 24713156160,412393101120,7352537512320,139443752448000,
%U 2802408959750400,59479486120454400,1329239028813696000,31194214921732262400,766888191387539020800,19707387644116280908800,528327710066244459571200
%N a(n) is the number of partial bijections (or subpermutations) of an n-element set without fixed points (also called partial derangements).
%C a(n) is also the number of matchings on the n-crown graph. - _Eric W. Weisstein_, Jul 11 2011
%H Vincenzo Librandi, <a href="/A144085/b144085.txt">Table of n, a(n) for n = 0..200</a>
%H A. Laradji and A. Umar, <a href="http://dx.doi.org/10.1007/s00233-007-0732-8">Combinatorial results for the symmetric inverse semigroup</a>, Semigroup Forum 75, (2007), 221-236.
%H A. Laradji and A. Umar, <a href="http://www.ibg.uu.se/digitalAssets/121/121877_poster1.pdf">Further combinatorial properties of the symmetric inverse semigroup</a>, 2012. [From _N. J. A. Sloane_, Dec 25 2012]
%H A. Umar, <a href="http://www.mathnet.ru/adm33">Some combinatorial problems in the theory of symmetric ...</a>, Algebra Disc. Math. 9 (2010) 115-126.
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/CrownGraph.html">Crown Graph</a>.
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/IndependentEdgeSet.html">Independent Edge Set</a>.
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/Matching.html">Matching</a>.
%F a(n) = A144088(n,0).
%F a(n) = n! * Sum_{m=0..n} (-1^m/m!) * Sum_{j=0..n-m} binomial(n-m, j)/j!.
%F 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.
%F 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
%F 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
%e 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.
%p A144085 := proc(n)
%p option remember;
%p if n < 0 then
%p 0 ;
%p elif n < 2 then
%p 1;
%p else
%p (2*n-1)*procname(n-1)-(n-1)*(n-3)*procname(n-2)-(n-1)*(n-2)*procname(n-3) ;
%p end if;
%p end proc: # _R. J. Mathar_, Nov 03 2015
%t Table[n! Sum[(-1)^k/k! LaguerreL[n - k, -1], {k, 0, n}], {n, 0, 30}]
%t 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 *)
%o (PARI) x='x+O('x^66);
%o k=0; egf=x^k/k!*exp(x^2/(1-x))/(1-x);
%o Vec(serlaplace(egf)) /* _Joerg Arndt_, Jul 11 2011 */
%Y Cf. A144088.
%Y Column k=0 of A369292.
%K nonn
%O 0,3
%A _Abdullahi Umar_, Sep 10 2008, Sep 15 2008
|
