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

Comments

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

Links

Table of n, a(n) for n=0..51.

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

Adjacent sequences: A144086 A144087 A144088 * A144090 A144091 A144092

Keyword

nice,nonn,tabl

Author

Abdullahi Umar, Sep 11 2008

Status

approved