login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A144084 T(n,k) is the number of partial bijections of height k (height(alpha) = |Im(alpha)|) of an n-element set. 17
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

REFERENCES

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)

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

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, 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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified April 22 19:11 EDT 2021. Contains 343177 sequences. (Running on oeis4.)