A289312 The number of upper-triangular matrices with integer entries whose absolute sum is equal to n, and each row and column contains at least one nonzero entry.

1, 2, 6, 26, 142, 946, 7446, 67658, 697118, 8031586, 102312486, 1427905658, 21666671534, 355138949394, 6253348428598, 117720540700842, 2359368991571518, 50157679523340994, 1127327559500923974, 26709016625807923418, 665292778385210384078

Offset: 0

Author

Peter Bala, Jul 02 2017

Keywords

• nonn
• easy

Comments

A Fishburn matrix of size n is defined to be an upper-triangular matrix with nonnegative integer entries which sum to n and each row and column contains a nonzero entry. See A022493.

Here we consider generalized Fishburn matrices where we allow the Fishburn matrices to have positive and negative nonzero entries. We define the size of a generalized Fishburn matrix to be the absolute sum of the matrix entries. This sequence gives the number of generalized Fishburn matrices of size n.

Alternatively, this sequence gives the number of 2-colored Fishburn matrices of size n, that is, ordinary Fishburn matrices of size n where each nonzero entry in the matrix can have one of two different colors.

More generally, if F(x) = Sum_{n >= 0} (Product_{i = 1..n} 1 - 1/(1 + x)^i) is the o.g.f. for primitive Fishburn matrices A138265 (i.e., Fishburn matrices with entries restricted to the set {0,1}) and C(x) := c_1*x + c_2*x^2 + ..., where c_i is a sequence of nonnegative integers, then the composition F(C(x)) is the o.g.f. for colored Fishburn matrices where entry i in the matrix can have one of c_i different colors: c_i = 0 for some i means i does not appear as an entry in the Fishburn matrix. This result is an application of Lemma 2.2.22 of Goulden and Jackson.

Examples

			a(2) = 6: The six upper triangular matrices of size 2 with no zero rows or columns are (+-2) and
  /+-1  0\
  |      |.
  \0  +-1/
		

References

• I. P. Goulden and D. M. Jackson, Combinatorial Enumeration, Wiley, N.Y., 1983, p. 42.

Links

• Alois P. Heinz, Table of n, a(n) for n = 0..300
• Ankush Goswami, Abhash Kumar Jha, Byungchan Kim, and Robert Osburn, Asymptotics and sign patterns for coefficients in expansions of Habiro elements, arXiv:2204.02628 [math.NT], 2022.
• Hsien-Kuei Hwang and Emma Yu Jin, Asymptotics and statistics on Fishburn matrices and their generalizations, arXiv:1911.06690 [math.CO], 2019.

Crossrefs

Cf. A022493, A138265, A289313.

Programs

Maple

G:= add(mul(1 - ((1-x)/(1+x))^k, k=1..n),n=0..20):
S:= series(G,x,21):
seq(coeff(S,x,j),j=0..20);
# Peter Bala, Jul 24 2017

Mathematica

m = 21; Sum[Product[1 - ((1-x)/(1+x))^k + O[x]^m, {k, 1, n}], {n, 0, m}] // CoefficientList[#, x]& (* Jean-François Alcover, Feb 28 2020 *)

Formula

G.f.: Sum_{n >= 0} Product_{k = 1..n} 1 - ((1 - x)/(1 + x))^k.

Alternative g.f.: Sum_{n >= 0} ((1 + x)/(1 - x))^(n+1) * Product_{k = 1..n} 1 - ((1 + x)/(1 - x))^k.

G.f.: B(2*x/(1+x)) where B(x) is the g.f. of A022493. - Michael D. Weiner, Feb 28 2019

a(n) ~ 2^(2*n + 5/2) * 3^(n + 3/2) * n^(n+1) / (exp(n) * Pi^(2*n+2)). - Vaclav Kotesovec, Aug 31 2023