cp's OEIS Frontend

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

%I A144084 #89 Feb 16 2025 08:33:08
%S A144084 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 A144084 2400,5400,4320,720,1,49,882,7350,29400,52920,35280,5040,1,64,1568,
%U A144084 18816,117600,376320,564480,322560,40320
%N A144084 T(n,k) is the number of partial bijections of height k (height(alpha) = |Im(alpha)|) of an n-element set.
%C A144084 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 A144084 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 A144084 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 A144084 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 A144084 T(n,k) is the number of increasing subsequences of length n-k over all permutations of [n]. - _Geoffrey Critzer_, Jan 08 2023
%D A144084 O. Ganyushkin and V. Mazorchuk, Classical Finite Transformation Semigroups, 2009, page 61.
%D A144084 J. M. Howie, Fundamentals of semigroup theory. Oxford: Clarendon Press, (1995).
%D A144084 Vaclav Kotesovec, Non-attacking chess pieces, 6th ed. (2013), p. 216, p. 218.
%H A144084 Alois P. Heinz, <a href="/A144084/b144084.txt">Rows n = 0..140, flattened</a>
%H A144084 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 A144084 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 A144084 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/CliquePolynomial.html">Clique Polynomial</a>
%H A144084 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/CompleteBipartiteGraph.html">Complete Bipartite Graph</a>
%H A144084 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/IndependencePolynomial.html">Independence Polynomial</a>
%H A144084 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/Matching-GeneratingPolynomial.html">Matching-Generating Polynomial</a>
%H A144084 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/RookComplementGraph.html">Rook Complement Graph</a>
%H A144084 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/RookGraph.html">Rook Graph</a>
%F A144084 T(n,k) = (C(n,k)^2)*k!.
%F A144084 T(n,k) = A007318(n,k) * A008279(n,k). - _Antal Pinter_, Nov 12 2014
%F A144084 From _Peter Bala_, Jul 04 2016: (Start)
%F A144084 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 A144084 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 A144084 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 A144084 From _Peter Bala_, Oct 05 2019: (Start)
%F A144084 E.g.f.: 1/(1 - t*x)*exp(x/(1 - t*x)).
%F A144084 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 A144084 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)
%F A144084 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 A144084 Sum_{k=0..n} k*T(n,k) = A105219(n). - _Alois P. Heinz_, Jan 08 2023
%F A144084 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
%e A144084 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 A144084 Triangle T(n,k) begins:
%e A144084   1;
%e A144084   1,  1;
%e A144084   1,  4,   2;
%e A144084   1,  9,  18,    6;
%e A144084   1, 16,  72,   96,   24;
%e A144084   1, 25, 200,  600,  600,  120;
%e A144084   1, 36, 450, 2400, 5400, 4320, 720;
%e A144084   ...
%p A144084 T:= (n, k)-> (binomial(n, k)^2)*k!:
%p A144084 seq(seq(T(n, k), k=0..n), n=0..10);  # _Alois P. Heinz_, Dec 04 2012
%t A144084 Table[Table[Binomial[n, k]^2 k!,{k, 0, n}], {n, 0, 6}] // Flatten (* _Geoffrey Critzer_, Dec 04 2012 *)
%t A144084 Table[ CoefficientList[n!*LaguerreL[n, x], x] // Abs // Reverse, {n, 0, 8}] // Flatten (* _Jean-François Alcover_, Nov 18 2013 *)
%t A144084 CoefficientList[Table[n! x^n LaguerreL[n, -1/x], {n, 0, 8}], x] // Flatten (* _Eric W. Weisstein_, Apr 24 2017 *)
%t A144084 CoefficientList[Table[(-x)^n HypergeometricU[-n, 1, -(1/x)], {n, 5}],
%t A144084   x] // Flatten (* _Eric W. Weisstein_, Jun 13 2017 *)
%o A144084 (Magma) /* As triangle */ [[(Binomial(n,k)^2)*Factorial(k): k in [0..n]]: n in [0.. 10]]; // _Vincenzo Librandi_, Jun 13 2017
%o A144084 (PARI) T(n,k) = k! * binomial(n,k)^2 \\ _Andrew Howroyd_, Feb 13 2018
%Y A144084 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 A144084 Columns k=2..10 are A163102, A179058, A179059, A179060, A179061, A179062, A179063, A179064, A179065.
%Y A144084 Cf. A089231, A105219, A295383.
%K A144084 nonn,tabl
%O A144084 0,5
%A A144084 _Abdullahi Umar_, Sep 10 2008, Sep 30 2008