A008608 Number of n X n upper triangular matrices A of nonnegative integers such that a_1i + a_2i + ... + a_{i-1,i} - a_ii - a_{i,i+1} - ... - a_in = -1.

1, 2, 7, 40, 357, 4820, 96030, 2766572, 113300265, 6499477726, 515564231770, 55908184737696, 8203615387086224, 1613808957720017838, 422045413500096791377, 145606442599303799948900, 65801956684134601408784992, 38698135339344702725297294600, 29437141738828506134939056167071, 28800381656420765181010517468370560

Offset

1,2

Comments

Garsia and Haglund call these Tesler matrices. - N. J. A. Sloane, Jul 04 2014

This is also the value of the type A_n Kostant partition function evaluated at (1,1,...,1,-n) in ZZ^(n+1). This is the number of ways of writing the vector (1,1,...,1,-n) in ZZ^(n+1) as a linear combination with nonnegative integer coefficients of the vectors e_i - e_j, for 1 <= i<j <= n+1. - Alejandro H. Morales, Mar 11 2014

Links

Joel B. Lewis, Table of n, a(n) for n = 1..26 (first 23 terms from Jay Pantone)

D. Armstrong, A. Garsia, J. Haglund, B. Rhoades and B. Sagan, Combinatorics of Tesler matrices in the theory of parking functions and diagonal harmonics, J. of Combin., 3(3):451-494, 2012.

W. Baldoni and M. Vergne, Kostant partitions functions and flow polytopes, Transform. Groups, 13(3-4):447-469, 2008.

J. Haglund, A polynomial expression for the Hilbert series of the quotient ring of diagonal coinvariants.

J. Haglund and A. Garsia, A polynomial expression for the character of diagonal harmonics, 2013.

A. Garsia and J. Haglund, A polynomial expression for the character of diagonal harmonics, 2014.

Ricky I. Liu, K. Mészáros, and A. H. Morales, Flow polytopes and the space of diagonal harmonics, arXiv preprint arXiv:1610.08370 [math.CO], 2016.

K. Mészáros, A. H. Morales, and B. Rhoades, The polytope of Tesler matrices, arXiv preprint arXiv:1409.8566 [math.CO], 2014.

Jason O'Neill, On the poset and asymptotics of Tesler Matrices, arXiv:1702.00866 [math.CO], 2017.

Michèle Vergne et al., Maple programs for efficient computation of the Kostant partition function.

Example

For n = 3 there are seven matrices: [[1,0,0],[0,1,0],[0,0,1]], [[1,0,0],[0,0,1],[0,0,2]], [[0,0,1],[0,1,0],[0,0,2]], [[0,0,1],[0,0,1],[0,0,3]], [[0,1,0],[0,2,0],[0,0,1]], [[0,1,0],[0,1,1],[0,0,2]], [[0,1,0],[0,0,2],[0,0,3]], so a(3) = 7. - Alejandro H. Morales, Jul 03 2015

Maple

multcoeff:=proc(n, f, coeffv, k)
   local i, currcoeff;
   currcoeff:=f;
   for i from 1 to n do
      currcoeff:=`if`(coeffv[i]=0, coeff(series(currcoeff, x[i], k), x[i], 0), coeff(series(currcoeff, x[i], k), x[i]^coeffv[i]));
   end do;
   return currcoeff;
end proc:
F:=n->mul(mul((1-x[i]*x[j]^(-1))^(-1), j=i+1..n), i=1..n):
a := n -> multcoeff(n+1, F(n+1), [seq(1, i=1..n), -n], n+2):
seq(a(i), i=2..7) # Alejandro H. Morales, Mar 11 2014, Jun 28 2015
# second Maple program:
b:= proc(n, i, l) option remember; (m-> `if`(m=0, 1,
      `if`(i=0, b(l[1]+1, m-1, subsop(1=NULL, l)), add(
      b(n-j, i-1, subsop(i=l[i]+j, l)), j=0..n))))(nops(l))
    end:
a:= n-> b(1, n-1, [0$(n-1)]):
seq(a(n), n=1..14);  # Alois P. Heinz, Jul 05 2015

Mathematica

b[n_, i_, l_List] := b[n, i, l] = Function[{m}, If[m==0, 1, If[i==0, b[l[[1]]+1, m-1, ReplacePart[l, 1 -> Sequence[]]], Sum[b[n-j, i-1, ReplacePart[l, i -> l[[i]] + j]], {j, 0, n}]]]][Length[l]]; a[n_] := b[1, n-1, Array[0&, n-1]]; Table[a[n], {n, 1, 14}] (* Jean-François Alcover, Jul 16 2015, after Alois P. Heinz *)

Crossrefs

Cf. A259485, A259666.

Row sums of A259786.

Main diagonal (shifted) of A259841.

Column k=1 of A259844.

Sequence in context: A064626 A137731 A363004 * A028441 A006455 A130715

Adjacent sequences: A008605 A008606 A008607 * A008609 A008610 A008611

Keyword

nonn

Author

Glenn P. Tesler (gptesler(AT)euclid.ucsd.edu)

Extensions

a(7)-a(13) from Alejandro H. Morales, Mar 12 2014

a(14) from Alejandro H. Morales, Jun 04 2015

a(15)-a(22) from Alois P. Heinz, Jul 05 2015

Status

approved