A135589 -id:A135589 - cp's OEIS frontend

A101370 Number of zero-one matrices with n ones and no zero rows or columns.

1, 4, 24, 196, 2016, 24976, 361792, 5997872, 111969552, 2324081728, 53089540992, 1323476327488, 35752797376128, 1040367629940352, 32441861122796672, 1079239231677587264, 38151510015777089280, 1428149538870997774080, 56435732691153773665280

Offset: 1

Peter J. Cameron, Jan 14 2005

a(n) = (1/(4*n!)) * Sum_{r, s>=0} (r*s)_n / 2^(r+s), where (m)_n is the falling factorial m * (m-1) * ... * (m-n+1). [Maia and Mendez]

			a(2)=4:
[1 1] [1] [1 0] [0 1]
..... [1] [0 1] [1 0]
From _Gus Wiseman_, Nov 14 2018: (Start)
The a(3) = 24 matrices:
  [111]
.
  [11][11][110][101][10][100][011][01][010][001]
  [10][01][001][010][11][011][100][11][101][110]
.
  [1][10][10][10][100][100][01][01][010][01][010][001][001]
  [1][10][01][01][010][001][10][10][100][01][001][100][010]
  [1][01][10][01][001][010][10][01][001][10][100][010][100]
(End)

Georg Cantor, Gesammelte Abhandlungen mathematischen und philosophischen Inhalts, p. 435 (IV, 4. Mitteilungen zur Lehre vom Transfiniten, VIII Nr. 13), Springer, Berlin. [Rainer Rosenthal, Apr 10 2007]

Alois P. Heinz, Table of n, a(n) for n = 1..400
P. J. Cameron, D. A. Gewurz and F. Merola, Product action, Discrete Math., 308 (2008), 386-394.
Giulio Cerbai and Anders Claesson, Enumerative aspects of Caylerian polynomials, arXiv:2411.08426 [math.CO], 2024. See pp. 3, 19.
Loïc Foissy, Claudia Malvenuto, and Frédéric Patras, Matrix symmetric and quasi-symmetric functions and noncommutative representation theory, arXiv:2503.14417 [math.CO], 2025. See p. 20.
M. Maia and M. Mendez, On the arithmetic product of combinatorial species, arXiv:math/0503436 [math.CO], 2005.

Cf. A000670 (the sequence P(n)), A049311 (row and column permutations allowed), A120733, A122725, A135589, A283877, A321446, A321587.

P:=function(n) return Sum([1..n],x->Stirling2(n,x)*Factorial(x)); end;

F:=function(n) return Sum([1..n],x->(-1)^(n-x)*Stirling1(n,x)*P(x)^2)/Factorial(n); end;

m = 17; a670[n_] = Sum[ StirlingS2[n, k]*k!, {k, 0, n}]; Rest[ CoefficientList[ Series[ Sum[ a670[n]^2*(Log[1 + x]^n/n!), {n, 0, m}], {x, 0, m}], x]] (* Jean-François Alcover, Sep 02 2011, after g.f.  *)
Table[Length[Select[Subsets[Tuples[Range[n],2],{n}],And[Union[First/@#]==Range[Max@@First/@#],Union[Last/@#]==Range[Max@@Last/@#]]&]],{n,5}] (* Gus Wiseman, Nov 14 2018 *)

{A000670(n)=sum(k=0,n,stirling(n, k,2)*k!)}
{a(n)=polcoeff(sum(m=0,n,A000670(m)^2*log(1+x+x*O(x^n))^m/m!),n)}
/* Paul D. Hanna, Nov 07 2009 */

a(n) = (Sum s(n, k) * P(k)^2)/n!, where P(n) is the number of labeled total preorders on {1, ..., n} (A000670), s are signed Stirling numbers of the first kind.
G.f.: Sum_{m>=0,n>=0} Sum_{j=0..n} (-1)^(n-j)*binomial(n,j)*((1+x)^j-1)^m. - Vladeta Jovovic, Mar 25 2006
Inverse binomial transform of A007322. - Vladeta Jovovic, Aug 17 2006
G.f.: Sum_{n>=0} 1/(2-(1+x)^n)/2^(n+1). - Vladeta Jovovic, Sep 23 2006
G.f.: Sum_{n>=0} A000670(n)^2*log(1+x)^n/n! where 1/(1-x) = Sum_{n>=0} A000670(n)*log(1+x)^n/n!. - Paul D. Hanna, Nov 07 2009
a(n) ~ n! / (2^(2+log(2)/2) * (log(2))^(2*(n+1))). - Vaclav Kotesovec, Dec 31 2013

A135588 Number of symmetric (0,1)-matrices with exactly n entries equal to 1 and no zero rows or columns.

Original entry on oeis.org

1, 1, 2, 6, 20, 74, 302, 1314, 6122, 29982, 154718, 831986, 4667070, 27118610, 163264862, 1013640242, 6488705638, 42687497378, 288492113950, 1998190669298, 14177192483742, 102856494496050, 762657487965086, 5771613810502002, 44555989658479726, 350503696871063138

Offset: 0

Vladeta Jovovic, Feb 25 2008, Mar 03 2008, Mar 04 2008

nonn

			From _Gus Wiseman_, Nov 14 2018: (Start)
The a(4) = 20 matrices:
  [11]
  [11]
.
  [110][101][100][100][011][010][010][001][001]
  [100][010][011][001][100][110][101][010][001]
  [001][100][010][011][100][001][010][101][110]
.
  [1000][1000][1000][1000][0100][0100][0010][0010][0001][0001]
  [0100][0100][0010][0001][1000][1000][0100][0001][0100][0010]
  [0010][0001][0100][0010][0010][0001][1000][1000][0010][0100]
  [0001][0010][0001][0100][0001][0010][0001][0100][1000][1000]
(End)

Alois P. Heinz, Table of n, a(n) for n = 0..721 (first 51 terms from Vincenzo Librandi)

Row sums of A135589.

Cf. A049311, A054976, A101370, A104601, A104602, A120733, A138178, A283877, A316983, A320796, A321401, A321405.

Table[Sum[SeriesCoefficient[(1+x)^k*(1+x^2)^(k*(k-1)/2)/2^(k+1),{x,0,n}],{k,0,Infinity}],{n,0,20}] (* Vaclav Kotesovec, Jul 02 2014 *)
Join[{1},  Table[Length[Select[Subsets[Tuples[Range[n], 2], {n}], And[Union[First/@#]==Range[Max@@First/@#], Union[Last/@#]==Range[Max@@Last/@#], Sort[Reverse/@#]==#]&]], {n, 5}]] (* Gus Wiseman, Nov 14 2018 *)

G.f.: Sum_{n>=0} (1+x)^n*(1+x^2)^binomial(n,2)/2^(n+1).

G.f.: Sum_{n>=0} (Sum_{k=0..n} (-1)^(n-k)*binomial(n,k)*(1+x)^k*(1+x^2)^binomial(k,2)).

A334548 Array read by antidiagonals: T(n,k) is the number of n X n symmetric binary matrices with no row sum greater than k.

Original entry on oeis.org

1, 1, 1, 1, 2, 1, 1, 2, 5, 1, 1, 2, 8, 14, 1, 1, 2, 8, 45, 43, 1, 1, 2, 8, 64, 315, 142, 1, 1, 2, 8, 64, 809, 2634, 499, 1, 1, 2, 8, 64, 1024, 13846, 25518, 1850, 1, 1, 2, 8, 64, 1024, 28217, 301262, 280257, 7193, 1, 1, 2, 8, 64, 1024, 32768, 1146419, 8035168, 3434595, 29186, 1

Offset: 0

Andrew Howroyd, May 08 2020

			Array begins:
=============================================================
n\k | 0    1      2       3        4         5         6
----|-------------------------------------------------------
  0 | 1    1      1       1        1         1         1 ...
  1 | 1    2      2       2        2         2         2 ...
  2 | 1    5      8       8        8         8         8 ...
  3 | 1   14     45      64       64        64        64 ...
  4 | 1   43    315     809     1024      1024      1024 ...
  5 | 1  142   2634   13846    28217     32768     32768 ...
  6 | 1  499  25518  301262  1146419   1914733   2097152 ...
  7 | 1 1850 280257 8035168 62951431 178499118 254409765 ...
  ...

Column k=0..9 are A000012, A005425, A139678, A139679, A139680, A139681, A139682, A139683, A139684, A139685.

Cf. A006125, A135589, A333157.

T(n,k) = 2^(n*(n+1)/2) = A006125(n+1) for k >= n.

A321446 Number of (0,1)-matrices with n ones, no zero rows or columns, and distinct rows and columns.

Original entry on oeis.org

1, 1, 2, 10, 72, 624, 6522, 80178, 1129368, 17917032, 316108752, 6138887616, 130120838400, 2989026225696, 73964789192400, 1961487062520720, 55495429438186920, 1668498596700706440, 53122020640948010640, 1785467619718933936560, 63175132023953553400440

Offset: 0

Gus Wiseman, Nov 13 2018

nonn

			The a(3) = 10 matrices:
  [1 1] [1 1] [1 0] [0 1]
  [1 0] [0 1] [1 1] [1 1]
.
  [1 0 0] [1 0 0] [0 1 0] [0 1 0] [0 0 1] [0 0 1]
  [0 1 0] [0 0 1] [1 0 0] [0 0 1] [1 0 0] [0 1 0]
  [0 0 1] [0 1 0] [0 0 1] [1 0 0] [0 1 0] [1 0 0]

Andrew Howroyd, Table of n, a(n) for n = 0..50

Cf. A000612, A007716, A049311, A101370, A120733, A135589, A283877, A316980, A319559, A321515, A321586, A321587, A321588, A369285.

prs2mat[prs_]:=Table[Count[prs,{i,j}],{i,Union[First/@prs]},{j,Union[Last/@prs]}];
Table[Length[Select[Subsets[Tuples[Range[n],2],{n}],And[Union[First/@#]==Range[Max@@First/@#],Union[Last/@#]==Range[Max@@Last/@#],UnsameQ@@prs2mat[#],UnsameQ@@Transpose[prs2mat[#]]]&]],{n,6}]

\\ Q(m, n, wf) defined in A321588.
seq(n)={my(R=vectorv(n,m,Q(m,n,w->1 + y^w + O(y*y^n)))); for(i=2, #R, R[i] -= i*R[i-1]); Vec(1 + vecsum(vecsum(R)))} \\ Andrew Howroyd, Jan 24 2024

a(7) onwards from Andrew Howroyd, Jan 20 2024

A138177 Triangle T(n,k) read by rows: number of k X k symmetric matrices with nonnegative integer entries and without zero rows or columns such that sum of all entries is equal to n, n>=1, 1<=k<=n.

Original entry on oeis.org

1, 1, 2, 1, 4, 4, 1, 7, 15, 10, 1, 10, 36, 52, 26, 1, 14, 74, 176, 190, 76, 1, 18, 132, 460, 810, 696, 232, 1, 23, 222, 1060, 2705, 3756, 2674, 764, 1, 28, 347, 2180, 7565, 15106, 17262, 10480, 2620, 1, 34, 525, 4204, 19013, 51162, 83440, 80816, 42732, 9496, 1, 40

Offset: 1

Vladeta Jovovic, Mar 03 2008

See the Brualdi/Ma reference for the connection to A161126. - Joerg Arndt, Nov 02 2014
T(n,k) is also the number of semistandard Young tableaux of size n whose entries span the interval 1..k. See also Gus Wiseman's comment in A138178. The T(4,2) = 7 semi-standard Young tableaux of size 4 spanning the interval 1..2 are:
   11  122  112  111  1222  1122  1112
   22  2    2    2                      . - Jacob Post, Jun 15 2018

			Triangle T(n,k) begins:
  1;
  1,  2;
  1,  4,   4;
  1,  7,  15,   10;
  1, 10,  36,   52,   26;
  1, 14,  74,  176,  190,   76;
  1, 18, 132,  460,  810,  696,  232;
  1, 23, 222, 1060, 2705, 3756, 2674, 764;
  ...

Alois P. Heinz, Rows n = 1..141, flattened
Richard A. Brualdi, Shi-Mei Ma, Enumeration of involutions by descents and symmetric matrices, European Journal of Combinatorics, vol.43, pp.220-228, (January 2015).
FindStat - Combinatorial Statistic Finder, Semistandard Young tableaux
Samantha Dahlberg, Combinatorial Proofs of Identities Involving Symmetric Matrices, arXiv:1410.7356 [math.CO], (27-October-2014)

Cf. (row sums) A138178, A135589, A135588, A161126, A210391.
Main diagonal gives A000085. - Alois P. Heinz, Apr 06 2015
T(2n,n) gives A266305.
T(n^2,n) gives A268309.

gf:= k-> 1/((1-x)^k*(1-x^2)^(k*(k-1)/2)):
A:= (n, k)-> coeff(series(gf(k), x, n+1), x, n):
T:= (n, k)-> add(A(n, k-i)*(-1)^i*binomial(k, i), i=0..k):
seq(seq(T(n, k), k=1..n), n=1..12);  # Alois P. Heinz, Apr 06 2015

gf[k_] := 1/((1-x)^k*(1-x^2)^(k*(k-1)/2)); A[n_, k_] := Coefficient[ Series [gf[k], {x, 0, n+1}], x, n]; T[n_, k_] := Sum[(-1)^j*Binomial[k, j]*A[n, k-j], {j, 0, k}]; Table[T[n, k], {n, 1, 12}, {k, 1, n}] // Flatten (* Jean-François Alcover, Jan 31 2016, after Alois P. Heinz *)

T(n,k) = Sum_{i=0..k} (-1)^i * binomial(k,i) * A210391(n,k-i). - Alois P. Heinz, Apr 06 2015

A137252 Triangle T(n,k) read by rows: number of k X k triangular (0,1)-matrices with exactly n entries equal to 1 and no zero rows or columns.

Original entry on oeis.org

1, 0, 1, 0, 0, 1, 0, 0, 1, 1, 0, 0, 0, 4, 1, 0, 0, 0, 4, 11, 1, 0, 0, 0, 1, 33, 26, 1, 0, 0, 0, 0, 42, 171, 57, 1, 0, 0, 0, 0, 26, 507, 718, 120, 1, 0, 0, 0, 0, 8, 840, 4017, 2682, 247, 1, 0, 0, 0, 0, 1, 865, 12866, 25531, 9327, 502, 1, 0, 0, 0, 0, 0, 584, 26831, 138080, 141904, 30973, 1013, 1

Offset: 0

Vladeta Jovovic, Mar 11 2008

			Triangle T(n,k) begins:
  1;
  0, 1;
  0, 0, 1;
  0, 0, 1, 1;
  0, 0, 0, 4,  1;
  0, 0, 0, 4, 11,   1;
  0, 0, 0, 1, 33,  26,   1;
  0, 0, 0, 0, 42, 171,  57,   1;
  0, 0, 0, 0, 26, 507, 718, 120,  1;
  ...

Alois P. Heinz, Rows n = 0..100, flattened
Matthieu Dien, Antoine Genitrini, and Frederic Peschanski, A Combinatorial Study of Async/Await Processes, Conf.: 19th Int'l Colloq. Theor. Aspects of Comp. (2022), (Analytic) Combinatorics of concurrent systems.
M. Dukes, S. Kitaev, J. Remmel, E. Steingrimsson, Enumerating (2+2)-free posets by indistinguishable elements, J. Combin. 2 (1) (2011) 139-163 doi:10.4310/JOC.2011.v2.n1.a6, Figure 2; arXiv preprint arXiv:1006.2696 [math.CO], 2010-2011.

Cf. A138265 (row sums), A005321 (column sums), A135589.

T(2n,n) gives A357140.

G.f.: Sum(Product(1-1/(1+((1+x)^i-1)*y), i=1..n), n=0..infinity).

A321403 Number of non-isomorphic self-dual set multipartitions (multisets of sets) of weight n.

Original entry on oeis.org

1, 1, 1, 2, 4, 6, 10, 17, 32, 56, 98, 177, 335, 620, 1164, 2231, 4349, 8511, 16870, 33844, 68746, 140894, 291698, 610051, 1288594, 2745916, 5903988, 12805313, 28010036, 61764992, 137281977, 307488896, 693912297, 1577386813, 3611241900, 8324940862, 19321470086

Offset: 0

Gus Wiseman, Nov 15 2018

nonn

Also the number of symmetric (0,1)-matrices up to row and column permutations with sum of elements equal to n and no zero rows or columns.
The dual of a multiset partition has, for each vertex, one part consisting of the indices (or positions) of the parts containing that vertex, counted with multiplicity. For example, the dual of {{1,2},{2,2}} is {{1},{1,2,2}}.
The weight of a multiset partition is the sum of sizes of its parts. Weight is generally not the same as number of vertices.

			Non-isomorphic representatives of the a(1) = 1 through a(7) = 17 set multipartitions:
  {{1}}  {{1},{2}}  {{2},{1,2}}    {{1,2},{1,2}}      {{1},{2,3},{2,3}}
                    {{1},{2},{3}}  {{1},{1},{2,3}}    {{2},{1,3},{2,3}}
                                   {{1},{3},{2,3}}    {{3},{3},{1,2,3}}
                                   {{1},{2},{3},{4}}  {{1},{2},{2},{3,4}}
                                                      {{1},{2},{4},{3,4}}
                                                      {{1},{2},{3},{4},{5}}
.
  {{1,2},{1,3},{2,3}}        {{1,3},{2,3},{1,2,3}}
  {{3},{2,3},{1,2,3}}        {{1},{1},{1,4},{2,3,4}}
  {{1},{1},{1},{2,3,4}}      {{1},{2,3},{2,4},{3,4}}
  {{1},{2},{3,4},{3,4}}      {{1},{4},{3,4},{2,3,4}}
  {{1},{3},{2,4},{3,4}}      {{2},{1,2},{3,4},{3,4}}
  {{1},{4},{4},{2,3,4}}      {{2},{1,3},{2,4},{3,4}}
  {{2},{4},{1,2},{3,4}}      {{3},{4},{1,4},{2,3,4}}
  {{1},{2},{3},{3},{4,5}}    {{4},{4},{4},{1,2,3,4}}
  {{1},{2},{3},{5},{4,5}}    {{1},{1},{5},{2,3},{4,5}}
  {{1},{2},{3},{4},{5},{6}}  {{1},{2},{2},{2},{3,4,5}}
                             {{1},{2},{3},{4,5},{4,5}}
                             {{1},{2},{4},{3,5},{4,5}}
                             {{1},{2},{5},{5},{3,4,5}}
                             {{1},{3},{5},{2,3},{4,5}}
                             {{1},{2},{3},{4},{4},{5,6}}
                             {{1},{2},{3},{4},{6},{5,6}}
                             {{1},{2},{3},{4},{5},{6},{7}}
Inequivalent representatives of the a(6) = 10 matrices:
  [0 0 1] [1 1 0]
  [0 1 1] [1 0 1]
  [1 1 1] [0 1 1]
.
  [1 0 0 0] [1 0 0 0] [1 0 0 0] [1 0 0 0] [0 1 0 0]
  [1 0 0 0] [0 1 0 0] [0 0 1 0] [0 0 0 1] [0 0 0 1]
  [1 0 0 0] [0 0 1 1] [0 1 0 1] [0 0 0 1] [1 1 0 0]
  [0 1 1 1] [0 0 1 1] [0 0 1 1] [0 1 1 1] [0 0 1 1]
.
  [1 0 0 0 0] [1 0 0 0 0]
  [0 1 0 0 0] [0 1 0 0 0]
  [0 0 1 0 0] [0 0 1 0 0]
  [0 0 1 0 0] [0 0 0 0 1]
  [0 0 0 1 1] [0 0 0 1 1]
.
  [1 0 0 0 0 0]
  [0 1 0 0 0 0]
  [0 0 1 0 0 0]
  [0 0 0 1 0 0]
  [0 0 0 0 1 0]
  [0 0 0 0 0 1]

Andrew Howroyd, Table of n, a(n) for n = 0..50

Cf. A007716, A049311, A135588, A135589, A138178, A283877, A316983, A319616.

Cf. A320796, A320797, A321403, A321404, A321405.

permcount(v) = {my(m=1, s=0, k=0, t); for(i=1, #v, t=v[i]; k=if(i>1&&t==v[i-1], k+1, 1); m*=t*k; s+=t); s!/m}
c(p, k)={polcoef((prod(i=2, #p, prod(j=1, i-1, (1 + x^(2*lcm(p[i], p[j])) + O(x*x^k))^gcd(p[i], p[j]))) * prod(i=1, #p, my(t=p[i]); (1 + x^t + O(x*x^k))^(t%2)*(1 + x^(2*t) + O(x*x^k))^(t\2) )), k)}
a(n)={my(s=0); forpart(p=n, s+=permcount(p)*c(p, n)); s/n!} \\ Andrew Howroyd, May 31 2023

Terms a(11) and beyond from Andrew Howroyd, May 31 2023

cp's OEIS Frontend

A101370 Number of zero-one matrices with n ones and no zero rows or columns.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

GAP

GAP

Mathematica

PARI

Formula

A135588 Number of symmetric (0,1)-matrices with exactly n entries equal to 1 and no zero rows or columns.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A334548 Array read by antidiagonals: T(n,k) is the number of n X n symmetric binary matrices with no row sum greater than k.

Views

Author

Keywords

Examples

Crossrefs

Formula

A321446 Number of (0,1)-matrices with n ones, no zero rows or columns, and distinct rows and columns.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Extensions

A138177 Triangle T(n,k) read by rows: number of k X k symmetric matrices with nonnegative integer entries and without zero rows or columns such that sum of all entries is equal to n, n>=1, 1<=k<=n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A137252 Triangle T(n,k) read by rows: number of k X k triangular (0,1)-matrices with exactly n entries equal to 1 and no zero rows or columns.

Views

Author

Keywords

Examples

Links

Crossrefs

Formula

A321403 Number of non-isomorphic self-dual set multipartitions (multisets of sets) of weight n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Extensions