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,3

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)

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.

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.

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. Rimaldi, 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).

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

Example

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)

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

Crossrefs

Row sums of A261781.

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

Sequence in context: A325153 A129890 A316158 * A218496 A144792 A291846

Adjacent sequences: A120730 A120731 A120732 * A120734 A120735 A120736

Keyword

nonn

Author

Vladeta Jovovic, Aug 18 2006, Aug 21 2006

Extensions

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

Status

approved