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.
Bulat Khaidarov, Enumeration of Certain k-Block Partitions of Barry, J. Int. Seq. 29 (2026), Art. 26.2.8. See p. 6 (Table 2).
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) = [x^(n-k)] (-1)^(n-k)*n!*L_{n}(x) = |A021010(n,k)|, where L_{n}(x) are the Laguerre polynomials.
T(n,n) = n!, the order of the symmetric group on an n-element set.
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 A089231. (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
T(n,k) = Sum_{d=0..2*k} c(k,d)*n^d, where c(k,d) = Sum_{j=max(d-k,0)..k} binomial(k,j)*A008275(k+j,d)/j!. - Eder G. Santos, Jan 23 2025
Conjecture: T(n, k) = Sum_{j=0..k} |Stirling1(n, n-j)| * Stirling2(n-j+1, n-k+1). - Mikhail Kurkov, Jun 23 2026 [The conjecture is true. Both k!*C(n, k)^2 and the claimed sum satisfy the same recurrence relation and the initial condition T(n, 0) = 1, thus they are equal for all 0 <= k <= n by induction. - Peter Luschny, Jun 23 2026]
T(n, k) = (2 * n - k) * T(n - 1, k - 1) + T(n - 1, k) for 0 < k <= n and T(n, 0) = 1. - Peter Luschny, Jun 23 2026
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 *)
(* Alternative: *)
Table[ CoefficientList[n!*LaguerreL[n, x], x] // Abs // Reverse, {n, 0, 8}] // Flatten (* Jean-François Alcover, Nov 18 2013 *)
(* Alternative: *)
CoefficientList[Table[n! x^n LaguerreL[n, -1/x], {n, 0, 8}], x] // Flatten (* Eric W. Weisstein, Apr 24 2017 *)
(* Alternative: *)
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
(Python)
from functools import cache
@cache
def T(n: int, k: int) -> int:
if k < 0 or k > n: return 0
if k == 0: return 1
return (2 * n - k) * T(n - 1, k - 1) + T(n - 1, k)
for n in range(9): print([T(n, k) for k in range(n + 1)]) # Peter Luschny, Jun 23 2026
CROSSREFS
KEYWORD
AUTHOR
Abdullahi Umar, Sep 10 2008, Sep 30 2008
STATUS
approved