A144084 - OEIS

%I #79 Jan 14 2024 23:45:00

%S 1,1,1,1,4,2,1,9,18,6,1,16,72,96,24,1,25,200,600,600,120,1,36,450,

%T 2400,5400,4320,720,1,49,882,7350,29400,52920,35280,5040,1,64,1568,

%U 18816,117600,376320,564480,322560,40320

%N T(n,k) is the number of partial bijections of height k (height(alpha) = |Im(alpha)|) of an n-element set.

%C T(n,k) is also the number of elements in the Green's J equivalence classes in the symmetric inverse monoid, I sub n.

%C 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

%C Rows also give the coefficients of the matching-generating polynomial of the complete bipartite graph K_{n,n}. - _Eric W. Weisstein_, Apr 24 2017

%C 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

%C T(n,k) is the number of increasing subsequences of length n-k over all permutations of [n]. - _Geoffrey Critzer_, Jan 08 2023

%D O. Ganyushkin and V. Mazorchuk, Classical Finite Transformation Semigroups, 2009, page 61.

%D J. M. Howie, Fundamentals of semigroup theory. Oxford: Clarendon Press, (1995).

%D Vaclav Kotesovec, Non-attacking chess pieces, 6th ed. (2013), p. 216, p. 218.

%H Alois P. Heinz, <a href="/A144084/b144084.txt">Rows n = 0..140, flattened</a>

%H Wayne A. Johnson, <a href="https://arxiv.org/abs/1804.04943">Exponential Hilbert series of equivariant embeddings</a>, arXiv:1804.04943 [math.RT], 2018.

%H W. D. Munn, <a href="http://dx.doi.org/10.1017/S0305004100031947">The characters of the symmetric inverse semigroup</a>, Proc. Cambridge Philos. Soc. 53 (1957), 13-18.

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/CliquePolynomial.html">Clique Polynomial</a>

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/CompleteBipartiteGraph.html">Complete Bipartite Graph</a>

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/IndependencePolynomial.html">Independence Polynomial</a>

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/Matching-GeneratingPolynomial.html">Matching-Generating Polynomial</a>

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/RookComplementGraph.html">Rook Complement Graph</a>

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/RookGraph.html">Rook Graph</a>

%F T(n,k) = (C(n,k)^2)*k!.

%F T(n,k) = A007318(n,k) * A008279(n,k). - _Antal Pinter_, Nov 12 2014

%F From _Peter Bala_, Jul 04 2016: (Start)

%F 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.

%F The row polynomials R(n,t) satisfy R(n,t + u) = Sum_{k = 0..n} T(n,k)*t^k*R(n-k,u).

%F 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)

%F From _Peter Bala_, Oct 05 2019: (Start)

%F E.g.f.: 1/(1 - t*x)*exp(x/(1 - t*x)).

%F 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.

%F 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)

%F 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

%F Sum_{k=0..n} k*T(n,k) = A105219(n). - _Alois P. Heinz_, Jan 08 2023

%e 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).

%e Triangle T(n,k) begins:

%e   1;

%e   1,  1;

%e   1,  4,   2;

%e   1,  9,  18,    6;

%e   1, 16,  72,   96,   24;

%e   1, 25, 200,  600,  600,  120;

%e   1, 36, 450, 2400, 5400, 4320, 720;

%e   ...

%p T:= (n, k)-> (binomial(n, k)^2)*k!:

%p seq(seq(T(n, k), k=0..n), n=0..10);  # _Alois P. Heinz_, Dec 04 2012

%t Table[Table[Binomial[n, k]^2 k!,{k, 0, n}], {n, 0, 6}] // Flatten (* _Geoffrey Critzer_, Dec 04 2012 *)

%t Table[ CoefficientList[n!*LaguerreL[n, x], x] // Abs // Reverse, {n, 0, 8}] // Flatten (* _Jean-François Alcover_, Nov 18 2013 *)

%t CoefficientList[Table[n! x^n LaguerreL[n, -1/x], {n, 0, 8}], x] // Flatten (* _Eric W. Weisstein_, Apr 24 2017 *)

%t CoefficientList[Table[(-x)^n HypergeometricU[-n, 1, -(1/x)], {n, 5}],

%t   x] // Flatten (* _Eric W. Weisstein_, Jun 13 2017 *)

%o (Magma) /* As triangle */ [[(Binomial(n,k)^2)*Factorial(k): k in [0..n]]: n in [0.. 10]]; // _Vincenzo Librandi_, Jun 13 2017

%o (PARI) T(n,k) = k! * binomial(n,k)^2 \\ _Andrew Howroyd_, Feb 13 2018

%Y 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!.

%Y Columns k=2..10 are A163102, A179058, A179059, A179060, A179061, A179062, A179063, A179064, A179065.

%Y Cf. A089231, A105219, A295383.

%K nonn,tabl

%O 0,5

%A _Abdullahi Umar_, Sep 10 2008, Sep 30 2008