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,2

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.

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.

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

Example

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

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 *)

Crossrefs

Cf. A022493, A138265, A289313.

Sequence in context: A224529 A171151 A177381 * A127116 A107404 A120574

Adjacent sequences: A289309 A289310 A289311 * A289313 A289314 A289315

Keyword

nonn,easy

Author

Peter Bala, Jul 02 2017

Status

approved