A289315 -id:A289315 - cp's OEIS frontend

A005321 Upper triangular n X n (0,1)-matrices with no zero rows or columns.

1, 1, 2, 10, 122, 3346, 196082, 23869210, 5939193962, 2992674197026, 3037348468846562, 6189980791404487210, 25285903982959247885402, 206838285372171652078912306, 3386147595754801373061066905042, 110909859519858523995273393471390010

Offset: 0

N. J. A. Sloane

T. L. Greenough, Enumeration of interval orders without duplicated holdings, Preprint, circa 1976.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Vincenzo Librandi, Table of n, a(n) for n = 0..80
E. Andresen and K. Kjeldsen, On certain subgraphs of a complete transitively directed graph, Discrete Math. 14 (1976), no. 2, 103-119.
William T. Dugan, On the f-vectors of flow polytopes for the complete graph, Sém. Lotharingien Comb., Proc. 36th Conf. Formal Power Series Alg. Comb. (2024) Vol. 91B, Art. No. 101. See p. 3.
T. Lockman Greenough, Representation and enumeration of interval orders and semiorders, Ph.D. Thesis, Dartmouth, 1976.
T. L. Greenough, Enumeration of interval orders without duplicated holdings, Preprint, circa 1976. [Annotated scanned copy]
T. Lockman Greenough, Enumeration of interval orders without duplicated holdings, in Notices of the AMS, February 1976, page A-314.
T. L. Greenough and K. P. Bogart, The Representation and Enumeration of Interval Orders, Preprint, circa 1976. [Annotated scanned copy]
Hsien-Kuei Hwang, Emma Yu Jin, and Michael J. Schlosser, Asymptotics and statistics on Fishburn Matrices: dimension distribution and a conjecture of Stoimenow, arXiv:2012.13570 [math.CO], 2020.
Vít Jelínek, Counting Self-Dual Interval Orders, arXiv:1106.2261 [math.CO], 2011. See Corollary 2.4.
Vít Jelínek, Counting general and self-dual interval orders, Journal of Combinatorial Theory, Series A, Volume 119, Issue 3, April 2012, pp. 599-614. See Corollary 2.4.
J. Longyear, T. Trotter, N. J. A. Sloane, Correspondence
Index entries for sequences related to binary matrices

Cf. A022493, A138265, A289314, A289315.

Column sums of A137252.

max = 14; f[x_] := Sum[ x^n*Product[ (2^i-1) / (1+(2^i-1)*x), {i, 1, n}], {n, 0, max}]; CoefficientList[ Series[ f[x], {x, 0, max}], x] (* Jean-François Alcover, Nov 23 2011, after Vladeta Jovovic *)

a(n) = 1 + sum(k=2, n, binomial(n,k)*sum(i=2, k, (-1)^i*prod(j=i+1, k, 2^j - 1))); \\ Michel Marcus, Oct 13 2019

a(n) = Sum_{k=0..n} binomial(n,k)*A005327(k+1).
G.f.: Sum_{n >= 0} x^n*Product_{i = 1..n} ((2^i-1)/(1 + (2^i-1)*x)). - Vladeta Jovovic, Mar 10 2008
From Peter Bala, Jul 06 2017: (Start)
Two conjectural continued fractions for the o.g.f.:
1/(1 - x/(1 - x/(1 - 6*x/(1 - 9*x/(1 - 28*x/(1 - 49*x/(1 - ... - 2^(n-1)*(2^n - 1)*x/(1 - (2^n - 1)^2*x/(1 - ...)))))))));
1 + x/(1 - 2*x/(1 - 3*x/(1 - 12*x/(1 - 21*x/(1 - ... - 2^n*(2^n - 1)*x/(1 - (2^(n+1) - 1)*(2^n - 1)*x/(1 - ...))))))). Cf. A289314 and A289315. (End)
a(n) = (-1)^n*Sum_{k=0..n} qS2(n,k)*[k]!*(-1)^k, where qS2(n,k) is the triangle A139382, and [k]! is q-factorial, q=2. - Vladimir Kruchinin, Oct 10 2019
a(n) = 1 + Sum_{k=2..n} binomial(n,k)*Sum{i=2..k} (-1)^i*Product_{j=i+1..k} (2^j - 1). See Greenough. - Michel Marcus, Oct 13 2019

More terms from Max Alekseyev, Apr 27 2010

A289314 Number of n X n Fishburn matrices with entries in the set {0,1,2}.

Original entry on oeis.org

1, 2, 12, 264, 19632, 4606752, 3311447232, 7202118117504, 47151987852663552, 927337336972381327872, 54741643544083873448266752, 9696222929066933463021344262144, 5152757080697434799933013959862300672, 8215035458438940398186389046297459974152192

Offset: 0

Peter Bala, Jul 03 2017

A Fishburn matrix is defined to be an upper-triangular matrix with nonnegative integer entries such that each row and column contains a nonzero entry. See A005321 for primitive Fishburn matrices of dimension n, that is, Fishburn matrices of dimension n with entries in the set {0,1}.

The present sequence has an alternative description as the number of primitive Fishburn matrices of dimension n where the 1's may be colored either black or white.

			a(2) = 12: The twelve 2 X 2 Fishburn matrices with entries 0, 1 or 2 are
/1 0\  /1 0\  /2 0\  /2 0\
\0 1/  \0 2/  \0 1/  \0 2/
/1 1\  /1 2\  /1 1\  /1 2\  /2 1\  /2 2\  /2 1\  /2 2\.
\0 1/  \0 1/  \0 2/  \0 2/  \0 1/  \0 1/  \0 2/  \0 2/
Alternatively, the twelve 2-colored primitive Fishburn matrices of dimension 2 (using +1 and -1 for the two different colored versions of 1) are
/+-1  0\ (4 possibilities)
\0  +-1/
   and
/+-1 +-1\ (8 possibilities).
\ 0  +-1/

Robert Israel, Table of n, a(n) for n = 0..64
Hsien-Kuei Hwang, Emma Yu Jin, and Michael J. Schlosser, Asymptotics and statistics on Fishburn Matrices: dimension distribution and a conjecture of Stoimenow, arXiv:2012.13570 [math.CO], 2020.
Vít Jelínek, Counting general and self-dual interval orders, Journal of Combinatorial Theory, Series A, Volume 119, Issue 3, April 2012, pp. 599-614; arXiv preprint, arXiv:1106.2261 [math.CO], 2011.

Cf. A005321, A022493, A138265, A289315.

N:= 20: # to get a(0)..a(N)
g:= add(x^n*mul((3^i-1)/(1+x*(3^i-1)),i=1..n),n=0..N):
S:= series(g,x,N+1):
seq(coeff(S,x,j),j=0..N); # Robert Israel, Jul 11 2017

QP = QPochhammer; nmax = 14;
Sum[(-1)^n (1-x)^(-n-1) x^n QP[3, 3, n]/QP[x/(x-1), 3, n+1], {n, 0, nmax}] + O[x]^nmax // CoefficientList[#, x]& (* Jean-François Alcover, Sep 19 2018 *)

O.g.f.: A(x) = Sum_{n >=0} x^n Product_{i = 1..n} (3^i - 1)/(1 + x*(3^i - 1)) = 1 + 2*x + 12*x^2 + 264*x^3 + ... (use Jelínek, Theorem 2.1 with v = w = x = y = 2).
Two conjectural continued fractions for the o.g.f.:
A(x) = 1/(1 - 2*x/(1 - 4*x/(1 - 24*x/(1 - 64*x/(1 - 234*x/(1 - 676*x/(1 - ... - 3^(n-1)*(3^n - 1)*x/(1 - (3^n - 1)^2*x/(1 - ...))))))))) and
A(x) = 1 + 2*x/(1 - 6*x/(1 - 16*x/(1 - 72*x/(1 - 208*x/(1 - ... - 3^n*(3^n - 1)*x/(1 - (3^(n+1) - 1)*(3^n - 1)*x/(1 - ...))))))).
a(n) ~ c * 3^(n*(n+1)/2), where c = QPochhammer(1/3)^2 = 0.313741223174946734265526469975707962872482170305592991802056615373429729... - Vaclav Kotesovec, Aug 31 2023, updated Mar 17 2024

A369415 Number A(n,k) of n X n Fishburn matrices with entries in the set {0,1,...,k}; square array A(n,k), n>=0, k>=0, read by antidiagonals.

Original entry on oeis.org

1, 1, 0, 1, 1, 0, 1, 2, 2, 0, 1, 3, 12, 10, 0, 1, 4, 36, 264, 122, 0, 1, 5, 80, 2052, 19632, 3346, 0, 1, 6, 150, 9280, 505764, 4606752, 196082, 0, 1, 7, 252, 30750, 5684480, 511718148, 3311447232, 23869210, 0, 1, 8, 392, 83160, 39378750, 17672135680, 2088275673636, 7202118117504, 5939193962, 0

Offset: 0

Alois P. Heinz, Jan 22 2024

Number of upper triangular n X n {0,1,...,k}-matrices with no zero rows or columns.

			A(2,3) = 3*3*4 = 36:
  [10] [10] [10]  [20] [20] [20]  [30] [30] [30]
  [ 1] [ 2] [ 3]  [ 1] [ 2] [ 3]  [ 1] [ 2] [ 3]
.
  [11] [11] [11]  [21] [21] [21]  [31] [31] [31]
  [ 1] [ 2] [ 3]  [ 1] [ 2] [ 3]  [ 1] [ 2] [ 3]
.
  [12] [12] [12]  [22] [22] [22]  [32] [32] [32]
  [ 1] [ 2] [ 3]  [ 1] [ 2] [ 3]  [ 1] [ 2] [ 3]
.
  [13] [13] [13]  [23] [23] [23]  [33] [33] [33]
  [ 1] [ 2] [ 3]  [ 1] [ 2] [ 3]  [ 1] [ 2] [ 3]
.
Square array A(n,k) begins:
  1,    1,       1,         1,           1,            1, ...
  0,    1,       2,         3,           4,            5, ...
  0,    2,      12,        36,          80,          150, ...
  0,   10,     264,      2052,        9280,        30750, ...
  0,  122,   19632,    505764,     5684480,     39378750, ...
  0, 3346, 4606752, 511718148, 17672135680, 305416893750, ...
  ...

Alois P. Heinz, Antidiagonals n = 0..53, flattened
Hsien-Kuei Hwang, Emma Yu Jin, and Michael J. Schlosser, Asymptotics and statistics on Fishburn Matrices: dimension distribution and a conjecture of Stoimenow, arXiv:2012.13570 [math.CO], 2020.
Vít Jelínek, Counting general and self-dual interval orders, Journal of Combinatorial Theory, Series A, Volume 119, Issue 3, April 2012, pp. 599-614; arXiv preprint, arXiv:1106.2261 [math.CO], 2011.
Wikipedia, Peter C. Fishburn

Columns k=0-3 give: A000007, A005321, A289314, A289315.
Rows n=0-3 give: A000012, A001477, A011379, A369423.
Main diagonal gives A369336.

A:= (n, k)-> coeff(series(add(x^j*mul(((k+1)^i-1)/(1+x*
           ((k+1)^i-1)), i=1..j), j=0..n), x, n+1), x, n):
seq(seq(A(n, d-n), n=0..d), d=0..10);

A(n,k) = [x^n] Sum_{j=0..n} x^j * Product_{i=1..j} ((k+1)^i-1)/(1+x*((k+1)^i-1)).

A289316 The number of upper-triangular matrices whose nonzero entries are positive odd numbers summing to n and each row contains a nonzero entry.

Original entry on oeis.org

1, 1, 2, 8, 37, 219, 1557, 12994, 124427, 1344506, 16178891, 214522339, 3107144562, 48805300668, 826268787588, 14998055299920, 290550119360174, 5983278021430064, 130512410617529321, 3006012061455129053, 72900477505718600661

Offset: 0

Peter Bala, Jul 24 2017

A row-Fishburn matrix of size n is defined to be an upper-triangular matrix with nonnegative integer entries which sum to n and each row contains a nonzero entry. See A158691. Here we are considering row-Fishburn matrices where the nonzero entries are all odd.

The g.f. F(x) for primitive row_Fishburn matrices (i.e., row_Fishburn matrices with entries restricted to the set {0,1}), is F(x) = Sum_{n>=0} Product_{k=1..n} ( (1 + x)^k - 1 ). See A179525. Let C(x) = x/(1 - x^2) = x + x^3 + x^5 + x^7 + .... Then appplying Lemma 2.2.22 of Goulden and Jackson gives the g.f. for the present sequence as the composition F(C(x)).

			a(3) = 8: The eight row-Fishburn matrices of size 3 with odd nonzero entries are
(3) /1 1\
    \0 1/
/1 0 0\  /0 1 0\  /0 0 1\
|0 1 0|  |0 1 0|  |0 1 0|
\0 0 1/  \0 0 1/  \0 0 1/
/1 0 0\  /0 1 0\  /0 0 1\
|0 0 1|  |0 0 1|  |0 0 1|
\0 0 1/  \0 0 1/  \0 0 1/

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

Seiichi Manyama, Table of n, a(n) for n = 0..200
Hsien-Kuei Hwang, Emma Yu Jin, Asymptotics and statistics on Fishburn matrices and their generalizations, arXiv:1911.06690 [math.CO], 2019.

Cf. A158691, A179525, A289312, A289313, A289314, A289315, A289317.

C:= x -> x/(1 - x^2):
G:= add(mul( (1 + C(x))^k - 1, k=1..n),n=0..20):
S:= series(G,x,21):
seq(coeff(S,x,j),j=0..20);

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

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

A289317 The number of upper-triangular matrices whose nonzero entries are positive odd numbers summing to n and each row and each column contains a nonzero entry.

Original entry on oeis.org

1, 1, 1, 3, 7, 23, 84, 364, 1792, 9953, 61455, 417720, 3098515, 24902930, 215538825, 1998518430, 19761943208, 207571259703, 2307812703419, 27075591512866, 334263981931669

Offset: 0

Peter Bala, Jul 25 2017

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 each column contains a nonzero entry. See A022493. Here we are considering Fishburn matrices where the nonzero entries are all odd.

The g.f. for primitive Fishburn matrices (i.e., Fishburn matrices with entries restricted to the set {0,1}), is F(x) = Sum_{n>=0} Product_{k=1..n} ( 1 - 1/(1 + x)^k ). See A138265. Let C(x) = x/(1 - x^2) = x + x^3 + x^5 + x^7 + .... Then applying Lemma 2.2.22 of Goulden and Jackson gives the g.f. for this sequence as the composition F(C(x)).

			a(4) = 7: The Fishburn matrices of size 4 with odd nonzero entries are
/3 0\ /1 0\
\0 1/ \0 3/
/1 1 0\ /1 0 1\ /1 0 0\
|0 1 0| |0 1 0| |0 1 1|
\0 0 1/ \0 0 1/ \0 0 1/
/1 1 0\
|0 0 1|
\0 0 1/
/1 0 0 0\
|0 1 0 0|
|0 0 1 0|
\0 0 0 1/

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

Seiichi Manyama, Table of n, a(n) for n = 0..200
Hsien-Kuei Hwang, Emma Yu Jin, Asymptotics and statistics on Fishburn matrices and their generalizations, arXiv:1911.06690 [math.CO], 2019.

Cf. A022493, A138265, A289312, A289313, A289314, A289315, A289316.

C:= x -> x/(1 - x^2):
G:= add(mul( 1 - 1/(1 + C(x))^k, k=1..n), n=0..20):
S:= series(G,x,21):
seq(coeff(S,x,j),j=0..20);

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

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

A369336 Number of n X n Fishburn matrices with entries in the set {0,1,...,n}.

Original entry on oeis.org

1, 1, 12, 2052, 5684480, 305416893750, 391129148721673152, 14286237711414132094989064, 17309880507327972883933887341789184, 792117985317303404452447777723478865406570410, 1534214120588806182890487155420702132205591283310000000000

Offset: 0

Alois P. Heinz, Jan 20 2024

nonn

Number of upper triangular n X n {0,1,...,n}-matrices with no zero rows or columns.

			a(0) = 1: [].
a(1) = 1: [1].
a(2) = 12:
  [10] [10] [20] [20]  [11] [11] [21] [21]  [12] [12] [22] [22]
  [ 1] [ 2] [ 1] [ 2]  [ 1] [ 2] [ 1] [ 2]  [ 1] [ 2] [ 1] [ 2].

Alois P. Heinz, Table of n, a(n) for n = 0..35
Hsien-Kuei Hwang, Emma Yu Jin, and Michael J. Schlosser, Asymptotics and statistics on Fishburn Matrices: dimension distribution and a conjecture of Stoimenow, arXiv:2012.13570 [math.CO], 2020.
Vít Jelínek, Counting general and self-dual interval orders, Journal of Combinatorial Theory, Series A, Volume 119, Issue 3, April 2012, pp. 599-614; arXiv preprint, arXiv:1106.2261 [math.CO], 2011.
Wikipedia, Peter C. Fishburn

Cf. A000007, A005321, A289314, A289315.

Main diagonal of A369415.

a:= n-> coeff(series(add(x^j*mul(((n+1)^i-1)/(1+x*
    ((n+1)^i-1)), i=1..j), j=0..n), x, n+1), x, n):
seq(a(n), n=0..10);

a(n) = [x^n] Sum_{j=0..n} x^j * Product_{i=1..j} ((n+1)^i-1)/(1+x*((n+1)^i-1)).

cp's OEIS Frontend

A005321 Upper triangular n X n (0,1)-matrices with no zero rows or columns.

Views

Author

Keywords

References

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A289314 Number of n X n Fishburn matrices with entries in the set {0,1,2}.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A369415 Number A(n,k) of n X n Fishburn matrices with entries in the set {0,1,...,k}; square array A(n,k), n>=0, k>=0, read by antidiagonals.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Formula

A289316 The number of upper-triangular matrices whose nonzero entries are positive odd numbers summing to n and each row contains a nonzero entry.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Formula

A289317 The number of upper-triangular matrices whose nonzero entries are positive odd numbers summing to n and each row and each column contains a nonzero entry.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Formula

A369336 Number of n X n Fishburn matrices with entries in the set {0,1,...,n}.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Formula