A176120 Triangle read by rows: Sum_{j=0..k} binomial(n, j)*binomial(k, j)*j!.

1, 1, 2, 1, 3, 7, 1, 4, 13, 34, 1, 5, 21, 73, 209, 1, 6, 31, 136, 501, 1546, 1, 7, 43, 229, 1045, 4051, 13327, 1, 8, 57, 358, 1961, 9276, 37633, 130922, 1, 9, 73, 529, 3393, 19081, 93289, 394353, 1441729, 1, 10, 91, 748, 5509, 36046, 207775, 1047376, 4596553, 17572114

Offset: 0

Author

Roger L. Bagula, Apr 09 2010

Keywords

• nonn
• easy
• tabl

Comments

The number of ways of placing any number k = 0, 1, ..., min(n,m) of non-attacking rooks on an n X m chessboard. - R. J. Mathar, Dec 19 2014

Let a be a partial permutation in S the symmetric inverse semigroup on [n] with rank(a) := |image(a)| = m. Then T(n,m) = |aS| where |aS| is the size of the principal right ideal generated by a. - Geoffrey Critzer, Dec 21 2021

Examples

			Triangle begins
  1;
  1,  2;
  1,  3,   7;
  1,  4,  13,   34;
  1,  5,  21,   73,  209;
  1,  6,  31,  136,  501,  1546;
  1,  7,  43,  229, 1045,  4051,  13327;
  1,  8,  57,  358, 1961,  9276,  37633,  130922;
  1,  9,  73,  529, 3393, 19081,  93289,  394353,  1441729;
  1, 10,  91,  748, 5509, 36046, 207775, 1047376,  4596553, 17572114;
  1, 11, 111, 1021, 8501, 63591, 424051, 2501801, 12975561, 58941091, 234662231;
		

References

• O. Ganyushkin and V. Mazorchuk, Classical Finite Transformation Semigroups, Springer, 2009, page 46.

Links

• Seiichi Manyama, Rows n = 0..139, flattened
• Wikipedia, Rook polynomial

Crossrefs

Cf. A086885 (table without column 0), A129833 (row sums).

Cf. A000262, A002061, A002720, A082545, A135859, A343832.

Programs

Magma

A176120:=func< n,k| (&+[Factorial(j)*Binomial(n,j)*Binomial(k,j): j in [0..k]]) >;
[A176120(n,k): k in [0..n], n in [0..12]]; // G. C. Greubel, Aug 11 2022

Maple

A176120 := proc(i,j)
        add(binomial(i,k)*binomial(j,k)*k!,k=0..j) ;
end proc: # R. J. Mathar, Jul 28 2016

Mathematica

T[n_, m_]:= T[n,m]= Sum[Binomial[n, k]*Binomial[m, k]*k!, {k, 0, m}];
Table[T[n, m], {n,0,12}, {m,0,n}]//Flatten

SageMath

def A176120(n,k): return sum(factorial(j)*binomial(n,j)*binomial(k,j) for j in (0..k))
flatten([[A176120(n,k) for k in (0..n)] for n in (0..12)]) # G. C. Greubel, Aug 11 2022

Formula

Sum_{k=0..n} T(n, k) = A129833(n).

T(n,m) = A088699(n, m). - Peter Bala, Aug 26 2013

T(n,m) = A086885(n, m). - R. J. Mathar, Dec 19 2014

From G. C. Greubel, Aug 11 2022: (Start)

T(n, k) = Hypergeometric2F1([-n, -k], [], 1).

T(2*n, n) = A082545(n).

T(2*n+1, n) = A343832(n).

T(n, n) = A002720(n).

T(n, n-1) = A000262(n), n >= 1.

T(n, 1) = A000027(n+1).

T(n, 2) = A002061(n+1).

T(n, 3) = A135859(n+1). (End)