A198890 Irregular triangle read by rows: row n gives expansion of g.f. for descending plane partitions of order n with no special parts and weight equal to sum of the parts.

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, 1, 0, 1, 1, 1, 2, 3, 2, 4, 3, 5, 5, 7, 6, 8, 8, 9, 10, 12, 10, 14, 12, 14, 15, 16, 15, 18, 16, 18, 18, 20, 17, 21, 18, 20, 20, 20, 18, 21, 17, 20, 18, 18, 16, 18, 15, 16, 15, 14, 12, 14, 10, 12, 10, 9, 8, 8, 6, 7, 5, 5, 3, 4, 2, 3, 2, 1, 1, 1, 0, 1

Offset

1,20

Links

Table of n, a(n) for n=1..146.

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

Row sums give A000142 (factorial numbers).

Cf. A001754, A008302, A037223, A087153.

Sequence in context: A140195 A196564 A196563 * A305831 A022927 A063435

Adjacent sequences: A198887 A198888 A198889 * A198891 A198892 A198893

Keyword

nonn,tabf

Author

N. J. A. Sloane, Oct 30 2011

Extensions

Name clarified by Ludovic Schwob, Jun 15 2023

Status

approved