|
|
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
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
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
|
|
|
FORMULA
|
T(n,k) = (n!/(n-k)!)*Sum_{m=0..k}(-1^m/m!)*binomial(n-m,k-m).
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
|
|
CROSSREFS
|
|
|
KEYWORD
|
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|