cp's OEIS Frontend

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

%I A144085 #66 Feb 16 2025 08:33:08
%S A144085 1,1,4,18,108,780,6600,63840,693840,8361360,110557440,1590351840,
%T A144085 24713156160,412393101120,7352537512320,139443752448000,
%U A144085 2802408959750400,59479486120454400,1329239028813696000,31194214921732262400,766888191387539020800,19707387644116280908800,528327710066244459571200
%N A144085 a(n) is the number of partial bijections (or subpermutations) of an n-element set without fixed points (also called partial derangements).
%C A144085 a(n) is also the number of matchings on the n-crown graph. - _Eric W. Weisstein_, Jul 11 2011
%H A144085 Vincenzo Librandi, <a href="/A144085/b144085.txt">Table of n, a(n) for n = 0..200</a>
%H A144085 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 A144085 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 A144085 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 A144085 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/CrownGraph.html">Crown Graph</a>.
%H A144085 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/IndependentEdgeSet.html">Independent Edge Set</a>.
%H A144085 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/Matching.html">Matching</a>.
%F A144085 a(n) = A144088(n,0).
%F A144085 a(n) = n! * Sum_{m=0..n} (-1^m/m!) * Sum_{j=0..n-m} binomial(n-m, j)/j!.
%F A144085 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 A144085 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 A144085 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
%F A144085 a(n) = n! * Sum_{k=0..n} binomial(k,n-k)/(n-k)!. - _Seiichi Manyama_, Aug 06 2024
%e A144085 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 A144085 := proc(n)
%p A144085     option remember;
%p A144085     if n < 0 then
%p A144085         0 ;
%p A144085     elif n < 2 then
%p A144085         1;
%p A144085     else
%p A144085         (2*n-1)*procname(n-1)-(n-1)*(n-3)*procname(n-2)-(n-1)*(n-2)*procname(n-3) ;
%p A144085     end if;
%p A144085 end proc: # _R. J. Mathar_, Nov 03 2015
%t A144085 Table[n! Sum[(-1)^k/k! LaguerreL[n - k, -1], {k, 0, n}], {n, 0, 30}]
%t A144085 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 A144085 (PARI) x='x+O('x^66);
%o A144085 k=0; egf=x^k/k!*exp(x^2/(1-x))/(1-x);
%o A144085 Vec(serlaplace(egf)) /* _Joerg Arndt_, Jul 11 2011 */
%Y A144085 Cf. A144088.
%Y A144085 Column k=0 of A369292.
%K A144085 nonn
%O A144085 0,3
%A A144085 _Abdullahi Umar_, Sep 10 2008, Sep 15 2008