cp's OEIS Frontend

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

%I A290823 #15 Aug 13 2017 02:54:31
%S A290823 1,1,1,1,4,6,1,9,36,48,1,16,120,416,632,1,25,300,1900,6550,10930,400,
%T A290823 1,36,630,6240,37080,128592,240192,39600,900,1,49,1176,16660,149695,
%U A290823 858774,3064656,6354866,2492385,229320,1764
%N A290823 Irregular triangle read by rows: T(n,k) = number of k-irredundant sets in the n X n rook graph.
%C A290823 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.
%H A290823 Andrew Howroyd, <a href="/A290823/b290823.txt">Table of n, a(n) for n = 0..846</a>
%F A290823 T(n, 0) = 1.
%F A290823 T(n, 1) = n^2.
%F A290823 T(n, 2) = binomial(n^2, 2).
%F A290823 T(n, 3) = binomial(n^2, 3) - n^2*(n-1)^2.
%F A290823 T(n, 2*n-4) = n^2*(n-1)^2 for n > 4.
%e A290823 Triangle begins:
%e A290823 1;
%e A290823 1,  1;
%e A290823 1,  4,   6;
%e A290823 1,  9,  36,   48;
%e A290823 1, 16, 120,  416,   632;
%e A290823 1, 25, 300, 1900,  6550,  10930,    400;
%e A290823 1, 36, 630, 6240, 37080, 128592, 240192, 39600, 900;
%e A290823 ...
%e A290823 As polynomials these are 1; 1 + x; 1 + 4*x + 6*x^2; etc.
%t A290823 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 *)
%o A290823 (PARI) \\ see A. Howroyd note in A290586 for explanation
%o A290823 s(n,k)=sum(i=0, min(n, k), (-1)^i * binomial(n, i) * stirling(n-i, k-i, 2) );
%o A290823 c(m,n,x)=sum(i=0, m-1, binomial(m, i) * (n^i - n!*stirling(i, n, 2))*x^i);
%o A290823 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) ))}
%o A290823 a(n,x) = (2*n^n - n!)*x^n + p(n,n,x);
%o A290823 for (n=0,8,my(q=a(n,x));print(Vec(q+O(x^(poldegree(q)+1)) )))
%Y A290823 Row sums are A290586.
%K A290823 nonn,tabf
%O A290823 0,5
%A A290823 _Andrew Howroyd_, Aug 11 2017