A290823 Irregular triangle read by rows: T(n,k) = number of k-irredundant sets in the n X n rook graph.

1, 1, 1, 1, 4, 6, 1, 9, 36, 48, 1, 16, 120, 416, 632, 1, 25, 300, 1900, 6550, 10930, 400, 1, 36, 630, 6240, 37080, 128592, 240192, 39600, 900, 1, 49, 1176, 16660, 149695, 858774, 3064656, 6354866, 2492385, 229320, 1764

Offset: 0

Author

Andrew Howroyd, Aug 11 2017

Keywords

• nonn
• tabf

Comments

For each row, k lies in the range 0..max(n, 2*n-4). The upper limit is the upper irredundance number of the graph.

Examples

			Triangle begins:
1;
1,  1;
1,  4,   6;
1,  9,  36,   48;
1, 16, 120,  416,   632;
1, 25, 300, 1900,  6550,  10930,    400;
1, 36, 630, 6240, 37080, 128592, 240192, 39600, 900;
...
As polynomials these are 1; 1 + x; 1 + 4*x + 6*x^2; etc.
		

Links

• Andrew Howroyd, Table of n, a(n) for n = 0..846

Crossrefs

Row sums are A290586.

Programs

Mathematica

s[n_, k_]:=Sum[(-1)^i*Binomial[n, i] StirlingS2[n - i, k - i], {i, 0, Min[n, k]}]; c[m_, n_, x_]:=Sum[Binomial[m, i] (n^i - n !*StirlingS2[i, n])*x^i, {i, 0, m - 1}]; p[m_, n_, x_]:=Sum[Sum[Binomial[m, k] Binomial[n, r]* k!*s[r, k]*x^r*c[m - k, n - r, x], {r, 2k, n - 1}], {k,0, m - 1}]; a[n_, x_]:=(2*n^n - n !)x^n + p[n, n, x]; A[n_]:=If[n==0, {1},  Drop[Block[{q=a[n, x]}, CoefficientList[q + x^(Exponent[q, x] + 1), x]], -1]]; Table[A[n], {n, 0, 15}] (* Indranil Ghosh, Aug 12 2017, after PARI code *)

PARI

\\ see A. Howroyd note in A290586 for explanation
s(n,k)=sum(i=0, min(n, k), (-1)^i * binomial(n, i) * stirling(n-i, k-i, 2) );
c(m,n,x)=sum(i=0, m-1, binomial(m, i) * (n^i - n!*stirling(i, n, 2))*x^i);
p(m, n, x)={sum(k=0, m-1, sum(r=2*k, n-1, binomial(m, k) * binomial(n, r) * k! * s(r, k) * x^r * c(m-k, n-r, x) ))}
a(n,x) = (2*n^n - n!)*x^n + p(n,n,x);
for (n=0,8,my(q=a(n,x));print(Vec(q+O(x^(poldegree(q)+1)) )))

Formula

T(n, 0) = 1.

T(n, 1) = n^2.

T(n, 2) = binomial(n^2, 2).

T(n, 3) = binomial(n^2, 3) - n^2*(n-1)^2.

T(n, 2*n-4) = n^2*(n-1)^2 for n > 4.