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, 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

Author

Abdullahi Umar, Sep 11 2008

Keywords

• nice
• nonn
• tabl

Comments

Rows also give coefficients of the matching-generating polynomial of the n-crown graph. - Eric W. Weisstein May 19 2017

Examples

			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;
		

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

Crossrefs

Row sums give A144085.

Cf. A000166.

Programs

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 *)

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

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