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

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

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

A327583 Number T(n,k) of colored compositions of n using all colors of a k-set such that all parts have different color patterns and the patterns for parts i have i distinct colors in increasing order; triangle T(n,k), n>=0, min(j:A001787(j)>=n)<=k<=n, read by rows.

Original entry on oeis.org

1, 1, 3, 4, 13, 6, 48, 75, 150, 536, 541, 300, 2820, 6320, 4683, 666, 11144, 50150, 81012, 47293, 936, 41346, 308080, 903210, 1134952, 545835, 1824, 131304, 1689040, 7805080, 16914786, 17346352, 7087261, 2520, 420084, 8279640, 58728660, 194051060, 333027016

Offset: 0

Alois P. Heinz, Sep 17 2019

T(n,k) is defined for all n>=0 and k>=0. The triangle displays only positive terms. All other terms are zero.

			T(3,2) = 4: 2ab1a, 2ab1b, 1a2ab, 1b2ab.
T(3,3) = 13: 3abc, 2ab1c, 2ac1b, 2bc1a, 1a2bc, 1b2ac, 1c2ab, 1a1b1c, 1a1c1b, 1b1a1c, 1b1c1a, 1c1a1b, 1c1b1a.
T(4,2) = 6: 2ab1a1b, 1a2ab1b, 1a1b2ab, 2ab1b1a, 1b2ab1a, 1b1a2ab.
Triangle T(n,k) begins:
  1;
     1;
        3;
        4,  13;
        6,  48,    75;
           150,   536,    541;
           300,  2820,   6320,   4683;
           666, 11144,  50150,  81012,   47293;
           936, 41346, 308080, 903210, 1134952, 545835;
           ...

Alois P. Heinz, Rows n = 0..150, flattened

Main diagonal gives A000670.
Row sums give A321587.
Column sums give A327585.
Cf. A001787, A326914, A327584 (this triangle read by columns).

C:= binomial:
g:= proc(n) option remember; n*2^(n-1) end:
h:= proc(n) option remember; local k; for k from
      `if`(n=0, 0, h(n-1)) do if g(k)>=n then return k fi od
    end:
b:= proc(n, i, k, p) option remember; `if`(n=0, p!,
      `if`(i<1 or k add(b(n$2, i, 0)*(-1)^(k-i)*C(k, i), i=0..k):
seq(seq(T(n, k), k=h(n)..n), n=0..12);

c = Binomial;
g[n_] := g[n] = n*2^(n - 1);
h[n_] := h[n] = Module[{k}, For[k = If[n == 0, 0,
     h[n - 1]], True, k++, If[g[k] >= n, Return[k]]]];
b[n_, i_, k_, p_] := b[n, i, k, p] = If[n == 0, p!,
     If[i < 1 || k < h[n], 0, Sum[b[n - i*j, Min[n - i*j, i - 1],
     k, p + j]*c[c[k, i], j], {j, 0, n/i}]]];
T[n_, k_] := Sum[b[n, n, i, 0]*(-1)^(k - i)*c[k, i], {i, 0, k}];
Table[Table[T[n, k], {k, h[n], n}], {n, 0, 12}] // Flatten (* Jean-François Alcover, Feb 22 2021, after Alois P. Heinz *)

A327584 Number T(n,k) of colored compositions of n using all colors of a k-set such that all parts have different color patterns and the patterns for parts i have i distinct colors in increasing order; triangle T(n,k), k>=0, k<=n<=k*2^(k-1), read by columns.

Original entry on oeis.org

1, 1, 3, 4, 6, 13, 48, 150, 300, 666, 936, 1824, 2520, 2160, 5040, 75, 536, 2820, 11144, 41346, 131304, 420084, 1191552, 3427008, 9207456, 23466720, 61522560, 141553560, 345346560, 777152160, 1635096960, 3700806480, 6998261760, 14211912960, 27442437120

Offset: 0

Alois P. Heinz, Sep 17 2019

T(n,k) is defined for all n>=0 and k>=0. The triangle displays only positive terms. All other terms are zero.

			T(3,2) = 4: 2ab1a, 2ab1b, 1a2ab, 1b2ab.
T(3,3) = 13: 3abc, 2ab1c, 2ac1b, 2bc1a, 1a2bc, 1b2ac, 1c2ab, 1a1b1c, 1a1c1b, 1b1a1c, 1b1c1a, 1c1a1b, 1c1b1a.
T(4,2) = 6: 2ab1a1b, 1a2ab1b, 1a1b2ab, 2ab1b1a, 1b2ab1a, 1b1a2ab.
Triangle T(n,k) begins:
  1;
     1;
        3;
        4,  13;
        6,  48,    75;
           150,   536,    541;
           300,  2820,   6320,   4683;
           666, 11144,  50150,  81012,   47293;
           936, 41346, 308080, 903210, 1134952, 545835;
           ...

Alois P. Heinz, Columns k = 0..7, flattened

Main diagonal gives A000670.
Row sums give A321587.
Column sums give A327585.
Cf. A001787, A326962, A327583 (this triangle read by rows).

C:= binomial:
g:= proc(n) option remember; n*2^(n-1) end:
h:= proc(n) option remember; local k; for k from
      `if`(n=0, 0, h(n-1)) do if g(k)>=n then return k fi od
    end:
b:= proc(n, i, k, p) option remember; `if`(n=0, p!,
      `if`(i<1 or k add(b(n$2, i, 0)*(-1)^(k-i)*C(k, i), i=0..k):
seq(seq(T(n, k), n=k..k*2^(k-1)), k=0..5);

c = Binomial;
g[n_] := g[n] = n*2^(n - 1);
h[n_] := h[n] = Module[{k}, For[k = If[n == 0, 0,
     h[n - 1]], True, k++, If[g[k] >= n, Return[k]]]];
b[n_, i_, k_, p_] := b[n, i, k, p] = If[n == 0, p!,
     If[i < 1 || k < h[n], 0, Sum[b[n - i*j, Min[n - i*j, i - 1],
     k, p + j]*c[c[k, i], j], {j, 0, n/i}]]];
T[n_, k_] := Sum[b[n, n, i, 0]*(-1)^(k - i)*c[k, i], {i, 0, k}];
Table[Table[T[n, k], {n, k, k*2^(k - 1)}], {k, 0, 5}] // Flatten (* Jean-François Alcover, Feb 22 2021, after Alois P. Heinz *)

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

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

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

A327583 Number T(n,k) of colored compositions of n using all colors of a k-set such that all parts have different color patterns and the patterns for parts i have i distinct colors in increasing order; triangle T(n,k), n>=0, min(j:A001787(j)>=n)<=k<=n, read by rows.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

A327584 Number T(n,k) of colored compositions of n using all colors of a k-set such that all parts have different color patterns and the patterns for parts i have i distinct colors in increasing order; triangle T(n,k), k>=0, k<=n<=k*2^(k-1), read by columns.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica