|
| |
|
|
A144084
|
|
T(n,k) is the number of partial bijections of height k (height(alpha) = |Im(alpha)|) of an n-element set.
|
|
19
|
|
|
|
1, 1, 1, 1, 4, 2, 1, 9, 18, 6, 1, 16, 72, 96, 24, 1, 25, 200, 600, 600, 120, 1, 36, 450, 2400, 5400, 4320, 720, 1, 49, 882, 7350, 29400, 52920, 35280, 5040, 1, 64, 1568, 18816, 117600, 376320, 564480, 322560, 40320
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
0,5
|
|
|
COMMENTS
|
T(n,k) is also the number of elements in the Green's J equivalence classes in the symmetric inverse monoid, I sub n.
T(n,k) is also the number of ways to place k nonattacking rooks on an n X n chessboard. It can be obtained by performing P(n,k) permutations of n-columns over each C(n,k) combination of n-rows for the given k-rooks. The rule is also applicable for unequal (m X n) sized rectangular boards. - Antal Pinter, Nov 12 2014
Rows also give the coefficients of the matching-generating polynomial of the complete bipartite graph K_{n,n}. - Eric W. Weisstein, Apr 24 2017
Rows also give the coefficients of the independence polynomial of the n X n rook graph and clique polynomial of the n X n rook complement graph. - Eric W. Weisstein, Jun 13 and Sep 14 2017
T(n,k) is the number of increasing subsequences of length n-k over all permutations of [n]. - Geoffrey Critzer, Jan 08 2023
|
|
|
REFERENCES
|
O. Ganyushkin and V. Mazorchuk, Classical Finite Transformation Semigroups, 2009, page 61.
J. M. Howie, Fundamentals of semigroup theory. Oxford: Clarendon Press, (1995).
Vaclav Kotesovec, Non-attacking chess pieces, 6th ed. (2013), p. 216, p. 218.
|
|
|
LINKS
|
Alois P. Heinz, Rows n = 0..140, flattened
Wayne A. Johnson, Exponential Hilbert series of equivariant embeddings, arXiv:1804.04943 [math.RT], 2018.
W. D. Munn, The characters of the symmetric inverse semigroup, Proc. Cambridge Philos. Soc. 53 (1957), 13-18.
Eric Weisstein's World of Mathematics, Clique Polynomial
Eric Weisstein's World of Mathematics, Complete Bipartite Graph
Eric Weisstein's World of Mathematics, Independence Polynomial
Eric Weisstein's World of Mathematics, Matching-Generating Polynomial
Eric Weisstein's World of Mathematics, Rook Complement Graph
Eric Weisstein's World of Mathematics, Rook Graph
|
|
|
FORMULA
|
T(n,k) = (C(n,k)^2)*k!.
T(n,k) = A007318(n,k) * A008279(n,k). - Antal Pinter, Nov 12 2014
From Peter Bala, Jul 04 2016: (Start)
G.f.: exp(x*t)*I_0(2*sqrt(x)) = 1 + (1 + t)*x/1!^2 + (1 + 4*t + 2*t^2)*x^2/2!^2 + (1 + 9*t + 18*t^2 + 6*t^3)*x^3/3!^2 + ..., where I_0(x) = Sum_{n >= 0} (x/2)^(2*n)/n!^2 is a modified Bessel function of the first kind.
The row polynomials R(n,t) satisfy R(n,t + u) = Sum_{k = 0..n} T(n,k)*t^k*R(n-k,u).
R(n,t) = 1 + Sum_{k = 0..n-1} (-1)^(n-k+1)*n!/k!*binomial(n,k) *t^(n-k)*R(k,t). Cf. A089231. (End)
From Peter Bala, Oct 05 2019: (Start)
E.g.f.: 1/(1 - t*x)*exp(x/(1 - t*x)).
Recurrence for row polynomials: R(n+1,t) = (1 + (2*n+1)*t)R(n,t) - n^2*t^2*R(n-1,t), with R(0,t) = 1 and R(1,t) = 1 + t.
R(n,t) equals the denominator polynomial of the finite continued fraction 1 + n*t/(1 + n*t/(1 + (n-1)*t/(1 + (n-1)*t/(1 + ... + 2*t/(1 + 2*t/(1 + t/(1 + t/(1)))))))). The numerator polynomial is the (n+1)-th row polynomial of A089321. (End)
Sum_{n>=0} Sum_{k=0..n} T(n,k)*y^k*x^n/A001044(n) = exp(y*x)*E(x) where E(x) = Sum_{n>=0} x^n/A001044(n). - Geoffrey Critzer, Jan 08 2023
Sum_{k=0..n} k*T(n,k) = A105219(n). - Alois P. Heinz, Jan 08 2023
|
|
|
EXAMPLE
|
T(3,1) = 9 because there are exactly 9 partial bijections (on a 3-element set) of height 1, namely: (1)->(1), (1)->(2), (1)->(3), (2)->(1), (2)->(2), (2)->(3), (3)->(1), (3)->(2), (3)->(3).
Triangle T(n,k) begins:
1;
1, 1;
1, 4, 2;
1, 9, 18, 6;
1, 16, 72, 96, 24;
1, 25, 200, 600, 600, 120;
1, 36, 450, 2400, 5400, 4320, 720;
...
|
|
|
MAPLE
|
T:= (n, k)-> (binomial(n, k)^2)*k!:
seq(seq(T(n, k), k=0..n), n=0..10); # Alois P. Heinz, Dec 04 2012
|
|
|
MATHEMATICA
|
Table[Table[Binomial[n, k]^2 k!, {k, 0, n}], {n, 0, 6}] // Flatten (* Geoffrey Critzer, Dec 04 2012 *)
Table[ CoefficientList[n!*LaguerreL[n, x], x] // Abs // Reverse, {n, 0, 8}] // Flatten (* Jean-François Alcover, Nov 18 2013 *)
CoefficientList[Table[n! x^n LaguerreL[n, -1/x], {n, 0, 8}], x] // Flatten (* Eric W. Weisstein, Apr 24 2017 *)
CoefficientList[Table[(-x)^n HypergeometricU[-n, 1, -(1/x)], {n, 5}],
x] // Flatten (* Eric W. Weisstein, Jun 13 2017 *)
|
|
|
PROG
|
(Magma) /* As triangle */ [[(Binomial(n, k)^2)*Factorial(k): k in [0..n]]: n in [0.. 10]]; // Vincenzo Librandi, Jun 13 2017
(PARI) T(n, k) = k! * binomial(n, k)^2 \\ Andrew Howroyd, Feb 13 2018
|
|
|
CROSSREFS
|
T(n,k) = |A021010|. Sum of rows of T(n,k) is A002720. T(n,n) is the order of the symmetric group on an n-element set, n!.
Columns k=2..10 are A163102, A179058, A179059, A179060, A179061, A179062, A179063, A179064, A179065.
Cf. A089231, A105219, A295383.
Sequence in context: A338397 A063983 A259985 * A021010 A342088 A193607
Adjacent sequences: A144081 A144082 A144083 * A144085 A144086 A144087
|
|
|
KEYWORD
|
nonn,tabl
|
|
|
AUTHOR
|
Abdullahi Umar, Sep 10 2008, Sep 30 2008
|
|
|
STATUS
|
approved
|
| |
|
|
