login
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.
1
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, 2715, 1854, 265, 1, 42, 651, 4690, 16275, 25494, 14833, 1854, 1, 56, 1204, 12712, 70070, 198184, 263284, 133496, 14833, 1, 72, 2052, 29904, 240534, 1076544, 2573508
OFFSET
0,5
COMMENTS
Rows also give coefficients of the matching-generating polynomial of the n-crown graph. - Eric W. Weisstein May 19 2017
LINKS
A. Laradji and A. Umar, Combinatorial results for the symmetric inverse semigroup, Semigroup Forum 75, (2007), 221-236.
Eric Weisstein's World of Mathematics, Crown Graph
Eric Weisstein's World of Mathematics, Matching-Generating Polynomial
FORMULA
T(n,k) = (n!/(n-k)!)*Sum_{m=0..k}(-1^m/m!)*binomial(n-m,k-m).
T(n,n-1) = A000166(n+1) and T(n,n) = A000166(n).
E.g.f.: exp(log(1/(1-y*x))-y*x)*exp(x/(1 - y*x)). - Geoffrey Critzer, Feb 18 2022
EXAMPLE
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.
Triangle starts:
1;
1, 0;
1, 2, 1;
1, 6, 9, 2;
1, 12, 42, 44, 9;
1, 20, 130, 320, 265, 44;
MATHEMATICA
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 *)
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 *)
PROG
(Sage)
def A144089_triangle(dim): # computes rows in reversed order
M = matrix(ZZ, dim, dim)
for n in (0..dim-1): M[n, n] = 1
for n in (1..dim-1):
for k in (0..n-1):
M[n, k] = M[n-1, k-1]+(2*k)*M[n-1, k]+(k+1)^2*M[n-1, k+1]
return M
A144089_triangle(9) # Peter Luschny, Sep 19 2012
CROSSREFS
Row sums give A144085.
Cf. A000166.
Sequence in context: A137376 A039761 A196073 * A172107 A349226 A165891
KEYWORD
nice,nonn,tabl
AUTHOR
Abdullahi Umar, Sep 11 2008
STATUS
approved