OFFSET
1,20
LINKS
Peter Bala, A note on A198890
J. Striker, A direct bijection between descending plane partitions with no special parts and permutation matrices, arXiv:1002.3391 [math.CO], 2010-2012.
J. Striker, A direct bijection between descending plane partitions with no special parts and permutation matrices, Discrete Math., 311 (2011).
FORMULA
From Peter Bala, May 29 2022: (Start)
T(0, 0) = 1; T(1, 0) = 1.
T(n, k) = 0 for k < 0 or k > (1/3)*(n+1)*n*(n-1).
T(n, k) = Sum_{j = 0..n-1} T(n-1, k-n*j); T(n, k) = T(n, k-n) + T(n-1, k) - T(n-1, k-n^2).
T(n,k) = T(n, (1/3)*(n+1)*n*(n-1) - k).
Sum_{k = 0..(1/3)*(n+1)*n*(n-1)} T(n, k) = n!.
Sum_{k = 0..(1/3)*(n+1)*n*(n-1)} (-1)^k*T(n, k) = A037223(n).
Sum_{k = 0..(1/3)*(n+1)*n*(n-1)} k*T(n, k) = (1/3)*n!*binomial(n-1,2) = 2*A001754(n) for n >= 1.
n-th row polynomial R(n,x) = Product_{j = 1..n} (1 - x^(j^2))/(1 - x^j).
let k be a nonnegative integer. Let p = p(1)p(2)...p(n) be a permutation of {1,2,...,n}. We define the k-th inversion number of p by inv_k(p) = Sum_{pairs (i,j), 1 <= i < j <= n, such that p(i) > p(j)} (p(i))^k. The n-th row polynomial R(n,x) equals Sum_{permutations p of {1,2,...,n} } x^(inv_1(p)). An example is given below. For the case k = 0 see A008302.
The x-adic limit of R(n,x) as n -> 00 is the g.f. of A087153. (End)
EXAMPLE
Rows 1 through 5 are
1
1, 0, 1
1, 0, 1, 1, 0, 1, 1, 0, 1
1, 0, 1, 1, 1, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 1, 1, 1, 0, 1
1, 0, 1, 1, 1, 2, 2, 2, 3, 2, 4, 3, 4, 4, 4, 5, 4, 5, 5, 4, 6, 4, 5, 5, 4, 5, 4, 4, 4, 3, 4, 2, 3, 2, 2, 2, 1, 1, 1, 0, 1
From Peter Bala, May 29 2022: (Start)
Row 3 generating polynomial:
Permutation p Pairs (p(i),p(j)) with p(i) > p(j) inv_1(p)
123 - 0
132 (3,2) 3
213 (2,1) 2
231 (2,1), (3,1) 5
312 (3,1), (3,2) 6
321 (3,2), (3,1), (2,1) 8
Hence R(3,x) = x^0 + x^2 + x^3 + x^5 + x^6 + x^8 = (1 + x^2)*(1 + x^3 + x^6) = ((1 - x^4)/(1 - x^2)) * (1 - x^9)/(1 - x^3). (End)
MAPLE
s:=(k, q)->add(q^i, i=0..k-1);
f:=n->mul(s(i, q^i), i=1..n);
g:=n->seriestolist(series(f(n), q, 1000));
for n from 1 to 10 do lprint(g(n)); od:
# alternative program
T := proc (n, k) option remember;
if n = 0 or n = 1 and k = 0 then 1
elif k > ((1/3)*n-1/3)*n*(n+1) then 0
elif k < 0 then 0
else T(n, k-n) + T(n-1, k) - T(n-1, k-n^2) fi end:
seq(print(seq(T(n, k), k = 0..(1/3)*(n-1)*n*(n+1))), n = 1..6); # Peter Bala, Jun 07 2022
CROSSREFS
KEYWORD
nonn,tabf
AUTHOR
N. J. A. Sloane, Oct 30 2011
EXTENSIONS
Name clarified by Ludovic Schwob, Jun 15 2023
STATUS
approved