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

Author

Vladeta Jovovic, Aug 18 2006, Aug 21 2006

Keywords

• nonn

Comments

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)

Examples

			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)
		

Links

• 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).

Crossrefs

Row sums of A261781.

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

Programs

Maple

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

Mathematica

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 *)

Formula

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

Extensions

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