A321585 -id:A321585 - cp's OEIS frontend

A120733 Number of matrices with nonnegative integer entries and without zero rows or columns such that sum of all entries is equal to n.

1, 1, 5, 33, 281, 2961, 37277, 546193, 9132865, 171634161, 3581539973, 82171451025, 2055919433081, 55710251353953, 1625385528173693, 50800411296363617, 1693351638586070209, 59966271207156833313, 2248276994650395873861, 88969158875611127548481

Offset: 0

Vladeta Jovovic, Aug 18 2006, Aug 21 2006

nonn

The number of such matrices up to rows/columns permutations are given in A007716.
Dimensions of the graded components of the Hopf algebra MQSym (Matrix quasi-symmetric functions). - Jean-Yves Thibon (jyt(AT)univ-mlv.fr), Oct 23 2006
From Kyle Petersen, Aug 10 2016: (Start)
Number of cells in the two-sided Coxeter complex of the symmetric group. Inclusion of faces corresponds to refinement of matrices, see Section 6 of Petersen paper. The number of cells in the type B analog is given by A275787.
Also known as "two-way contingency tables" in the Diaconis-Gangolli reference. (End)

			a(2) = 5:
[1 0]   [0 1]   [1]   [1 1]   [2]
[0 1]   [1 0]   [1]
From _Gus Wiseman_, Nov 14 2018: (Start)
The a(3) = 33 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]
.
  [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)

Alois P. Heinz, Table of n, a(n) for n = 0..400
Sara C. Billey, M. Konvalinka, T. K. Petersen, W. Slofstra, and B. E. Tenner, Parabolic double cosets in Coxeter groups, Discrete Mathematics and Theoretical Computer Science, Submitted, 2016.
Thomas Browning, Counting Parabolic Double Cosets in Symmetric Groups, arXiv:2010.13256 [math.CO], 2020.
Georg Cantor, Gesammelte Abhandlungen mathematischen und philosophischen Inhalts See IV, 4. Mitteilungen zur Lehre vom Transfiniten, VIII Nr. 13, page 436, Springer, Berlin.
Giulio Cerbai and Anders Claesson, Caylerian polynomials, arXiv:2310.01270 [math.CO], 2023. Mentions this sequence.
Giulio Cerbai and Anders Claesson, Enumerative aspects of Caylerian polynomials, arXiv:2411.08426 [math.CO], 2024. See pp. 3, 19.
P. Diaconis and A. Gangolli, Rectangular arrays with fixed margins, Discrete probability and algorithms (Minneapolis, MN, 1993), 15-41, IMA Vol. Math. Appl., 72, Springer, New York, 1995.
G. Duchamp, F. Hivert and J.-Y. Thibon, Noncommutative symmetric functions VI: Free quasi-symmetric functions and related algebras, arXiv:math/0105065 [math.CO], 2001; Internat. J. Alg. Comp. 12 (2002), 671-717.
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. 11.
Masato Kobayashi, Construction of double coset system of a Coxeter group and its applications to Bruhat graphs, arXiv:1907.11801 [math.CO], 2019.
Vaclav Kotesovec, Asymptotics of the sequence A120733
E. Munarini, M. Poneti, and S. Rinaldi, Matrix compositions, JIS 12 (2009) 09.4.8, Remark 30.
T. K. Petersen, A two-sided analogue of the Coxeter complex, arXiv:1607.00086 [math.CO], (2016).

Row sums of A261781.

Cf. A000219, A007322 (partial sums), A007716, A101370, A120732, A261838, A317533, A321515, A321585, A321586.

t1 := M -> add( add( add( (-1)^(n-j)*binomial(n, j)*((1-x)^(-j)-1)^m, j=0..n), n=0..M), m=0..M); s := series(t1(20),x,20); gfun[seriestolist](%); # N. J. A. Sloane, Jan 14 2009

a[n_] := Sum[2^(-2-r-s)*Binomial[n+r*s-1, n], {r, 0, Infinity}, {s, 0, Infinity}]; Table[Print[an = a[n]]; an, {n, 0, 19}] (* Jean-François Alcover, May 15 2012, after Vladeta Jovovic *)
Flatten[{1,Table[1/n!*Sum[(-1)^(n-k)*StirlingS1[n,k]*Sum[m!*StirlingS2[k, m],{m,k}]^2,{k,n}],{n,20}]}] (* Vaclav Kotesovec, May 07 2014 *)
multsubs[set_,k_]:=If[k==0,{{}},Join@@Table[Prepend[#,set[[i]]]&/@multsubs[Drop[set,i-1],k-1],{i,Length[set]}]]; Table[Length[Select[multsubs[Tuples[Range[n],2],n],And[Union[First/@#]==Range[Max@@First/@#],Union[Last/@#]==Range[Max@@Last/@#]]&]],{n,5}] (* Gus Wiseman, Nov 14 2018 *)

a(n) = (1/n!)*Sum_{k=0..n} (-1)^(n-k)*Stirling1(n,k)*A000670(k)^2.
G.f.: Sum_{m>=0,n>=0} Sum_{j=0..n} (-1)^(n-j)*C(n,j)*((1-x)^(-j)-1)^m.
a(n) = Sum_{r>=0,s>=0} binomial(r*s+n-1,n)/2^(r+s+2).
G.f.: Sum_{n>=0} 1/(2-(1-x)^(-n))/2^(n+1). - Vladeta Jovovic, Oct 30 2006
a(n) ~ 2^(log(2)/2-2) * n! / (log(2))^(2*n+2). - Vaclav Kotesovec, May 07 2014

More terms from N. J. A. Sloane, Jan 14 2009

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

Original entry on oeis.org

1, 1, 2, 6, 27, 159, 1154, 9968, 99861, 1138234, 14544650, 205927012, 3199714508, 54131864317, 990455375968, 19488387266842, 410328328297512, 9205128127109576, 219191041679766542, 5521387415218119528, 146689867860276432637, 4099255234885039058842, 120199458455807733040338

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) = 27 matrices:
  [1111]
.
  [111][111][111][11][110][110][101][101][100][011][011][010][001]
  [100][010][001][11][101][011][110][011][111][110][101][111][111]
.
  [11][11][11][11][10][10][10][10][01][01][01][01]
  [10][10][01][01][11][11][10][01][11][11][10][01]
  [10][01][10][01][10][01][11][11][10][01][11][11]
.
  [1]
  [1]
  [1]
  [1]

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

Cf. A007716, A007718, A049311, A056156, A101370, A104602, A120733, A283877, A319557, A319647, A319616-A319629, A321585.

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[Subsets[Tuples[Range[n],2],{n}],And[Union[First/@#]==Range[Max@@First/@#],Union[Last/@#]==Range[Max@@Last/@#],Length[csm[Map[Last,GatherBy[#,First],{2}]]]==1]&]],{n,6}] (* Mathematica 7.0+ *)

NonZeroCols(M)={my(C=Vec(M)); Mat(vector(#C, n, sum(k=1, n, (-1)^(n-k)*binomial(n,k)*C[k])))}
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(M=matrix(n,n,i,j,sum(k=1, n, binomial(i*j,k)*x^k, O(x*x^n) ))); Vec(1 + vecsum(vecsum(Vec( ConnectedMats( NonZeroCols( NonZeroCols(M)~)) ))))} \\ Andrew Howroyd, Jan 17 2024

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

A321680 Number of non-isomorphic weight-n connected antichains (not necessarily strict) of multisets with multiset density -1.

Original entry on oeis.org

1, 1, 3, 4, 9, 14, 39, 80, 216, 538, 1460

Offset: 0

Gus Wiseman, Nov 16 2018

The multiset density of a multiset partition is the sum of the numbers of distinct vertices in each part minus the number of parts minus the number of vertices.

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(5) = 14 multiset trees:
  {{1}}  {{1,1}}    {{1,1,1}}      {{1,1,1,1}}        {{1,1,1,1,1}}
         {{1,2}}    {{1,2,2}}      {{1,1,2,2}}        {{1,1,2,2,2}}
         {{1},{1}}  {{1,2,3}}      {{1,2,2,2}}        {{1,2,2,2,2}}
                    {{1},{1},{1}}  {{1,2,3,3}}        {{1,2,2,3,3}}
                                   {{1,2,3,4}}        {{1,2,3,3,3}}
                                   {{1,1},{1,1}}      {{1,2,3,4,4}}
                                   {{1,2},{2,2}}      {{1,2,3,4,5}}
                                   {{1,3},{2,3}}      {{1,1},{1,2,2}}
                                   {{1},{1},{1},{1}}  {{1,2},{2,2,2}}
                                                      {{1,2},{2,3,3}}
                                                      {{1,3},{2,3,3}}
                                                      {{1,4},{2,3,4}}
                                                      {{3,3},{1,2,3}}
                                                      {{1},{1},{1},{1},{1}}

Cf. A006126, A007718, A056156, A096827, A285572, A293993, A293994, A305052, A319719, A319721, A321194, A321585, A321681.

A321681 Number of non-isomorphic weight-n connected strict antichains of multisets with multiset density -1.

Original entry on oeis.org

1, 1, 2, 3, 7, 13, 35, 77, 205, 517, 1399

Offset: 0

Gus Wiseman, Nov 16 2018

The multiset density of a multiset partition is the sum of the numbers of distinct vertices in each part minus the number of parts minus the number of vertices.

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(5) = 13 trees:
  {{1}}  {{1,1}}  {{1,1,1}}  {{1,1,1,1}}    {{1,1,1,1,1}}
         {{1,2}}  {{1,2,2}}  {{1,1,2,2}}    {{1,1,2,2,2}}
                  {{1,2,3}}  {{1,2,2,2}}    {{1,2,2,2,2}}
                             {{1,2,3,3}}    {{1,2,2,3,3}}
                             {{1,2,3,4}}    {{1,2,3,3,3}}
                             {{1,2},{2,2}}  {{1,2,3,4,4}}
                             {{1,3},{2,3}}  {{1,2,3,4,5}}
                                            {{1,1},{1,2,2}}
                                            {{1,2},{2,2,2}}
                                            {{1,2},{2,3,3}}
                                            {{1,3},{2,3,3}}
                                            {{1,4},{2,3,4}}
                                            {{3,3},{1,2,3}}

Cf. A006126, A007718, A056156, A096827, A285572, A293993, A293994, A305052, A319557, A319565, A319719, A319721, A321585, A321680.

A321484 Number of non-isomorphic self-dual connected multiset partitions of weight n.

Original entry on oeis.org

1, 1, 1, 2, 3, 6, 9, 20, 35, 78, 141

Offset: 0

Gus Wiseman, Nov 16 2018

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(6) = 9 multiset partitions:
  {{1}}  {{11}}  {{111}}    {{1111}}    {{11111}}      {{111111}}
                 {{2}{12}}  {{12}{12}}  {{11}{122}}    {{112}{122}}
                            {{2}{122}}  {{12}{122}}    {{12}{1222}}
                                        {{2}{1222}}    {{2}{12222}}
                                        {{2}{13}{23}}  {{22}{1122}}
                                        {{3}{3}{123}}  {{12}{13}{23}}
                                                       {{2}{13}{233}}
                                                       {{3}{23}{123}}
                                                       {{3}{3}{1233}}

Cf. A007718, A056156, A138178, A316983, A319565, A319616, A319647, A319719, A321194, A321585, A321680, A321681.

cp's OEIS Frontend

A120733 Number of matrices with nonnegative integer entries and without zero rows or columns such that sum of all entries is equal to n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Extensions

A321680 Number of non-isomorphic weight-n connected antichains (not necessarily strict) of multisets with multiset density -1.

Views

Author

Keywords

Comments

Examples

Crossrefs

A321681 Number of non-isomorphic weight-n connected strict antichains of multisets with multiset density -1.

Views

Author

Keywords

Comments

Examples

Crossrefs

A321484 Number of non-isomorphic self-dual connected multiset partitions of weight n.

Views

Author

Keywords

Comments

Examples

Crossrefs