A321446 -id:A321446 - 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

A321515 Number of nonnegative integer matrices with sum of entries equal to n, no zero rows or columns, and distinct rows and columns.

Original entry on oeis.org

1, 1, 3, 19, 137, 1209, 12899, 160395, 2276229, 36323217, 643848837, 12551081501, 266868756473, 6146455542737, 152439235077709, 4050427673024753, 114791270281213209, 3456412742412516649, 110191808168628510207, 3708004806262196242699, 131339701217968663631857

Offset: 0

Gus Wiseman, Nov 13 2018

nonn

			The a(3) = 19 matrices:
  [3] [2 1] [1 2]
.
  [2] [2 0] [1 1] [1 1] [1] [1 0] [1 0] [0 2] [0 1] [0 1]
  [1] [0 1] [1 0] [0 1] [2] [1 1] [0 2] [1 0] [2 0] [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..40

Cf. A007716, A120733, A283877, A316980, A319559, A321446, A321586, A321588.

multsubs[set_,k_]:=If[k==0,{{}},Join@@Table[Prepend[#,set[[i]]]&/@multsubs[Drop[set,i-1],k-1],{i,Length[set]}]];
prs2mat[prs_]:=Table[Count[prs,{i,j}],{i,Union[First/@prs]},{j,Union[Last/@prs]}];
Table[Length[Select[multsubs[Tuples[Range[n],2],n],And[Union[First/@#]==Range[Max@@First/@#],Union[Last/@#]==Range[Max@@Last/@#],UnsameQ@@prs2mat[#],UnsameQ@@Transpose[prs2mat[#]]]&]],{n,5}]

\\ Q(m,n,wf) defined in A321588.
seq(n)={my(R=vectorv(n,m,Q(m,n,w->1/(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

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

Original entry on oeis.org

1, 1, 3, 17, 129, 1227, 14123, 190265, 2934359, 50975647, 984801759, 20941104299, 486007744671, 12223797601887, 331190083773701, 9616356919931711, 297887922137531747, 9805965265937326129, 341827167387114704421, 12579123760272833723975, 487315396984696657840761

Offset: 0

Gus Wiseman, Nov 13 2018

nonn

Also number of colored compositions of n using all colors of an initial interval of the color palette such that all parts have different color patterns and the patterns for parts i have i distinct colors in increasing order. a(3) = 17: 2ab1a, 2ab1b, 1a2ab, 1b2ab, 3abc, 2ab1c, 2ac1b, 2bc1a, 1a2bc, 1b2ac, 1c2ab, 1a1b1c, 1a1c1b, 1b1a1c, 1b1c1a, 1c1a1b, 1c1b1a. - Alois P. Heinz, Sep 17 2019

			The a(3) = 17 matrices:
  [1 1 1]
.
  [1 1] [1 1] [1 1 0] [1 0 1] [1 0] [1 0 0] [0 1 1] [0 1] [0 1 0] [0 0 1]
  [1 0] [0 1] [0 0 1] [0 1 0] [1 1] [0 1 1] [1 0 0] [1 1] [1 0 1] [1 1 0]
.
  [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]

Alois P. Heinz, Table of n, a(n) for n = 0..200

Cf. A007716, A049311, A101370, A120733, A283877, A316980, A321446, A321515.

Row sums of A327583, A327584.

C:= binomial:
b:= proc(n, i, k, p) option remember; `if`(n=0, p!, `if`(i<1, 0, add(
      b(n-i*j, min(n-i*j, i-1), k, p+j)*C(C(k, i), j), j=0..n/i)))
    end:
a:= n-> add(add(b(n$2, i, 0)*(-1)^(k-i)*C(k, i), i=0..k), k=0..n):
seq(a(n), n=0..21);  # Alois P. Heinz, Sep 16 2019

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[#]]&]],{n,5}]

a(n) ~ c * d^n * n!, where d = 1.938593839617140963759657977... and c = 0.350862127201784401195038... - Vaclav Kotesovec, Feb 05 2022

a(7)-a(20) from Alois P. Heinz, Sep 16 2019

A321586 Number of nonnegative integer matrices with sum of entries equal to n, no zero rows or columns, and distinct rows (or distinct columns).

Original entry on oeis.org

1, 1, 4, 26, 204, 1992, 23336, 318080, 4948552, 86550424, 1681106080, 35904872576, 836339613984, 21100105791936, 573194015723840, 16681174764033728, 517768654898701120, 17074080118403865856, 596117945858272441408, 21967609729338776864384, 852095613819396775627200

Offset: 0

Gus Wiseman, Nov 13 2018

nonn

			The a(3) = 26 matrices:
  [3][21][12][111]
.
  [2][20][11][11][110][101][1][10][10][100][02][011][01][01][010][001]
  [1][01][10][01][001][010][2][11][02][011][10][100][20][11][101][110]
.
  [100][100][010][010][001][001]
  [010][001][100][001][100][010]
  [001][010][001][100][010][100]

Alois P. Heinz, Table of n, a(n) for n = 0..200

Cf. A007716, A049311, A101370, A120733, A283877, A316980, A321446, A321587.

Row sums of A327245.

C:= binomial:
b:= proc(n, i, k, p) option remember; `if`(n=0, p!, `if`(i<1, 0, add(
      b(n-i*j, min(n-i*j, i-1), k, p+j)*C(C(k+i-1, i), j), j=0..n/i)))
    end:
a:= n-> add(add(b(n$2, i, 0)*(-1)^(k-i)*C(k, i), i=0..k), k=0..n):
seq(a(n), n=0..21);  # Alois P. Heinz, Sep 16 2019

multsubs[set_,k_]:=If[k==0,{{}},Join@@Table[Prepend[#,set[[i]]]&/@multsubs[Drop[set,i-1],k-1],{i,Length[set]}]];
prs2mat[prs_]:=Table[Count[prs,{i,j}],{i,Union[First/@prs]},{j,Union[Last/@prs]}];
Table[Length[Select[multsubs[Tuples[Range[n],2],n],And[Union[First/@#]==Range[Max@@First/@#],Union[Last/@#]==Range[Max@@Last/@#],UnsameQ@@prs2mat[#]]&]],{n,5}]

a(7)-a(20) from Alois P. Heinz, Sep 16 2019

A321588 Number of connected nonnegative integer matrices with sum of entries equal to n, no zero rows or columns, and distinct rows and columns.

Original entry on oeis.org

1, 1, 1, 9, 29, 181, 1285, 10635, 102355, 1118021, 13637175, 184238115, 2727293893, 43920009785, 764389610843, 14297306352937, 286014489487815, 6093615729757841, 137750602009548533, 3293082026520294529, 83006675263513350581, 2200216851785981586729, 61180266502369886181253

Offset: 0

Gus Wiseman, Nov 13 2018

nonn

A matrix is connected if the positions in each row (or each column) of the nonzero entries form a connected hypergraph.

			The a(4) = 29 matrices:
4 31 13
.
3 21 21 20 12 12 11 110 11 110 101 101 1 10 10 02 011 011 01 01
1 10 01 11 10 01 20 101 02 011 110 011 3 21 12 11 110 101 21 12
.
11 11 10 10 01 01
10 01 11 01 11 10
01 10 01 11 10 11

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

Cf. A007718, A056156, A059201, A120733, A283877, A316980, A319557, A319558, A319559, A319565, A319647, A319616-A319629, A321446, A321515, A369285.

prs2mat[prs_]:=Table[Count[prs,{i,j}],{i,Union[First/@prs]},{j,Union[Last/@prs]}];
multsubs[set_,k_]:=If[k==0,{{}},Join@@Table[Prepend[#,set[[i]]]&/@multsubs[Drop[set,i-1],k-1],{i,Length[set]}]];
csm[s_]:=With[{c=Select[Tuples[Range[Length[s]],2],And[OrderedQ[#],UnsameQ@@#,Length[Intersection@@s[[#]]]>0]&]},If[c=={},s,csm[Union[Append[Delete[s,List/@c[[1]]],Union@@s[[c[[1]]]]]]]]];
Table[Length[Select[multsubs[Tuples[Range[n],2],n],And[Union[First/@#]==Range[Max@@First/@#],Union[Last/@#]==Range[Max@@Last/@#],UnsameQ@@prs2mat[#],UnsameQ@@Transpose[prs2mat[#]],Length[csm[Map[Last,GatherBy[#,First],{2}]]]==1]&]],{n,6}]

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}
K(q,t,wf)={prod(j=1, #q, wf(t*q[j]))-1}
Q(m,n,wf=w->2)={my(s=0); forpart(p=m, s+=(-1)^#p*permcount(p)*exp(-sum(t=1, n, (-1)^t*x^t*K(p,t,wf)/t, O(x*x^n))) ); Vec((-1)^m*serchop(serlaplace(s),1), -n)}
ConnectedMats(M)={my([m, n]=matsize(M), R=matrix(m, n)); for(m=1, m, for(n=1, n, R[m, n] = M[m, n] - sum(i=1, m-1, sum(j=1, n-1, binomial(m-1, i-1)*binomial(n, j)*R[i, j]*M[m-i, n-j])))); R}
seq(n)={my(R=vectorv(n,m,Q(m,n,w->1/(1 - y^w) + O(y*y^n)))); for(i=2, #R, R[i] -= i*R[i-1]); Vec(1 + vecsum( vecsum( Vec( ConnectedMats( Mat(R))))))} \\ Andrew Howroyd, Jan 24 2024

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

A369285 Number of connected binary matrices with n ones, no zero rows or columns, and distinct rows and columns.

Original entry on oeis.org

1, 1, 0, 4, 12, 72, 522, 4386, 42360, 465792, 5697552, 77229216, 1145762400, 18485254536, 322206163200, 6033964218720, 120830927523240, 2576515514434920, 58285369894027440, 1394212928447354640, 35160926971256369400, 932396530226753051160, 25936228654879236020640

Offset: 0

Andrew Howroyd, Jan 24 2024

nonn

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

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

Cf. A321446, A321515, A321588.

\\ Q, ConnectedMats 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(Vec(ConnectedMats(Mat(R))))))}

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

A321515 Number of nonnegative integer matrices with sum of entries equal to n, no zero rows or columns, and distinct rows and columns.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Extensions

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A321586 Number of nonnegative integer matrices with sum of entries equal to n, no zero rows or columns, and distinct rows (or distinct columns).

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Extensions

A321588 Number of connected nonnegative integer matrices with sum of entries equal to n, no zero rows or columns, and distinct rows and columns.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Extensions

A369285 Number of connected binary matrices with n ones, no zero rows or columns, and distinct rows and columns.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

PARI