A144090 Triangle read by rows: T(n,k) is the number of partial bijections (or subpermutations) of an n-element set of height k (height(alpha) = |Im(alpha)|) and with exactly 1 fixed point.

1, 2, 0, 3, 6, 3, 4, 24, 36, 8, 5, 60, 210, 220, 45, 6, 120, 780, 1920, 1590, 264, 7, 210, 2205, 9940, 19005, 12978, 1855, 8, 336, 5208, 37520, 130200, 203952, 118664, 14832, 9, 504, 10836, 114408, 630630, 1783656, 2369556, 1201464, 133497

Offset

1,2

Links

Table of n, a(n) for n=1..45.

A. Laradji and A. Umar, Combinatorial results for the symmetric inverse semigroup, Semigroup Forum 75, (2007), 221-236.

Formula

T(n,k) = (n!/(n-k)!)*Sum_{m=0..k-1} ((-1)^m/m!)*C(n-1-m,k-1-m).

Example

T(3,2) = 6 because there are exactly 6 partial bijections (on a 3-element set) with exactly 1 fixed point and of height 2, namely: (1,2)->(1,3), (1,2)->(3,2), (1,3)->(1,2), (1,3)->(2,3), (2,3)->(2,1), (2,3)->(1,3)- the mappings are coordinate-wise.
First six rows:
1
2      0
3      6      3
4     24     36       8
5     60    210     220      45
6    120    780    1920    1590    264

Mathematica

Table[(n!/(n - k)!) Sum[ ((-1)^m/m!) Binomial[n - 1 - m, k - 1 - m], {m, 0, k - 1}], {n, 9}, {k, n}] // Flatten (* Michael De Vlieger, Apr 27 2016 *)

Prog

(PARI) T(n, k) = (n!/(n-k)!)*sum(m=0, k-1, ((-1)^m/m!)*binomial(n-1-m, k-1-m));
for (n=1, 10, for (k=1, n, print1(T(n, k), ", "))) \\ Michel Marcus, Apr 27 2016

Crossrefs

Rows sums are A144086.

Main diagonal gives A000240.

Sequence in context: A226210 A194737 A071089 * A330674 A248966 A021495

Adjacent sequences: A144087 A144088 A144089 * A144091 A144092 A144093

Keyword

nonn,tabl

Author

Abdullahi Umar, Sep 11 2008

Status

approved