cp's OEIS Frontend

A144089 T(n,k) is the number of partial bijections (or subpermutations) of an n-element set of height k (height(alpha) = |Im(alpha)|) and without fixed points.

%I A144089 #35 Feb 16 2025 08:33:08
%S A144089 1,1,0,1,2,1,1,6,9,2,1,12,42,44,9,1,20,130,320,265,44,1,30,315,1420,
%T A144089 2715,1854,265,1,42,651,4690,16275,25494,14833,1854,1,56,1204,12712,
%U A144089 70070,198184,263284,133496,14833,1,72,2052,29904,240534,1076544,2573508
%N A144089 T(n,k) is the number of partial bijections (or subpermutations) of an n-element set of height k (height(alpha) = |Im(alpha)|) and without fixed points.
%C A144089 Rows also give coefficients of the matching-generating polynomial of the n-crown graph. - _Eric W. Weisstein_ May 19 2017
%H A144089 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 A144089 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/CrownGraph.html">Crown Graph</a>
%H A144089 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/Matching-GeneratingPolynomial.html">Matching-Generating Polynomial</a>
%F A144089 T(n,k) = (n!/(n-k)!)*Sum_{m=0..k}(-1^m/m!)*binomial(n-m,k-m).
%F A144089 T(n,n-1) = A000166(n+1) and T(n,n) = A000166(n).
%F A144089 E.g.f.:  exp(log(1/(1-y*x))-y*x)*exp(x/(1 - y*x)). - _Geoffrey Critzer_, Feb 18 2022
%e A144089 T(3,2) = 9 because there are exactly 9 partial bijections (on a 3-element set) without fixed points and of height 2, namely: (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),- the mappings are coordinate-wise.
%e A144089 Triangle starts:
%e A144089   1;
%e A144089   1,  0;
%e A144089   1,  2,   1;
%e A144089   1,  6,   9,   2;
%e A144089   1, 12,  42,  44,   9;
%e A144089   1, 20, 130, 320, 265, 44;
%t A144089 t[n_, k_] := n!^2*Hypergeometric1F1[-k, -n, -1]/(k!*(n-k)!^2); Flatten[ Table[ t[n, k], {n, 0, 7}, {k, 0, n}]] (* _Jean-François Alcover_, Oct 13 2011 *)
%t A144089 CoefficientList[Table[x^n n! Sum[(-1)^k/k! LaguerreL[n - k, -1/x], {k, 0, n}], {n, 2, 10}], x] // Flatten (* _Eric W. Weisstein_, May 19 2017 *)
%o A144089 (Sage)
%o A144089 def A144089_triangle(dim): # computes rows in reversed order
%o A144089     M = matrix(ZZ,dim,dim)
%o A144089     for n in (0..dim-1): M[n,n] = 1
%o A144089     for n in (1..dim-1):
%o A144089         for k in (0..n-1):
%o A144089             M[n,k] = M[n-1,k-1]+(2*k)*M[n-1,k]+(k+1)^2*M[n-1,k+1]
%o A144089     return M
%o A144089 A144089_triangle(9) # _Peter Luschny_, Sep 19 2012
%Y A144089 Row sums give A144085.
%Y A144089 Cf. A000166.
%K A144089 nice,nonn,tabl
%O A144089 0,5
%A A144089 _Abdullahi Umar_, Sep 11 2008