A144084 T(n,k) is the number of partial bijections of height k (height(alpha) = |Im(alpha)|) of an n-element set.
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
Offset: 0
Examples
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; ...
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
Crossrefs
Programs
-
Magma
/* As triangle */ [[(Binomial(n,k)^2)*Factorial(k): k in [0..n]]: n in [0.. 10]]; // Vincenzo Librandi, Jun 13 2017
-
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 *) -
PARI
T(n,k) = k! * binomial(n,k)^2 \\ Andrew Howroyd, Feb 13 2018
Formula
T(n,k) = (C(n,k)^2)*k!.
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
Comments