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.

%I A120733 #100 Mar 25 2025 02:47:25
%S A120733 1,1,5,33,281,2961,37277,546193,9132865,171634161,3581539973,
%T A120733 82171451025,2055919433081,55710251353953,1625385528173693,
%U A120733 50800411296363617,1693351638586070209,59966271207156833313,2248276994650395873861,88969158875611127548481
%N A120733 Number of matrices with nonnegative integer entries and without zero rows or columns such that sum of all entries is equal to n.
%C A120733 The number of such matrices up to rows/columns permutations are given in A007716.
%C A120733 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
%C A120733 From _Kyle Petersen_, Aug 10 2016: (Start)
%C A120733 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.
%C A120733 Also known as "two-way contingency tables" in the Diaconis-Gangolli reference. (End)
%H A120733 Alois P. Heinz, <a href="/A120733/b120733.txt">Table of n, a(n) for n = 0..400</a>
%H A120733 Sara C. Billey, M. Konvalinka, T. K. Petersen, W. Slofstra, and B. E. Tenner, <a href="http://www.math.washington.edu/~billey/papers/DoubleCosets.pdf">Parabolic double cosets in Coxeter groups</a>, Discrete Mathematics and Theoretical Computer Science, Submitted, 2016.
%H A120733 Thomas Browning, <a href="https://arxiv.org/abs/2010.13256">Counting Parabolic Double Cosets in Symmetric Groups</a>, arXiv:2010.13256 [math.CO], 2020.
%H A120733 Georg Cantor, <a href="https://www.deutsche-digitale-bibliothek.de/item/CPNKIRFILEETQPXCYR5RHGUJCCKBXN5U">Gesammelte Abhandlungen mathematischen und philosophischen Inhalts</a> See IV, 4. Mitteilungen zur Lehre vom Transfiniten, VIII Nr. 13, page 436, Springer, Berlin.
%H A120733 Giulio Cerbai and Anders Claesson, <a href="https://arxiv.org/abs/2310.01270">Caylerian polynomials</a>, arXiv:2310.01270 [math.CO], 2023. Mentions this sequence.
%H A120733 Giulio Cerbai and Anders Claesson, <a href="https://arxiv.org/abs/2411.08426">Enumerative aspects of Caylerian polynomials</a>, arXiv:2411.08426 [math.CO], 2024. See pp. 3, 19.
%H A120733 P. Diaconis and A. Gangolli, <a href="http://dx.doi.org/10.1007/978-1-4612-0801-3_3">Rectangular arrays with fixed margins</a>, Discrete probability and algorithms (Minneapolis, MN, 1993), 15-41, IMA Vol. Math. Appl., 72, Springer, New York, 1995.
%H A120733 G. Duchamp, F. Hivert and J.-Y. Thibon, <a href="https://arxiv.org/abs/math/0105065">Noncommutative symmetric functions VI: Free quasi-symmetric functions and related algebras</a>, arXiv:math/0105065 [math.CO], 2001; Internat. J. Alg. Comp. 12 (2002), 671-717.
%H A120733 Loïc Foissy, Claudia Malvenuto, and Frédéric Patras, <a href="https://arxiv.org/abs/2503.14417">Matrix symmetric and quasi-symmetric functions and noncommutative representation theory</a>, arXiv:2503.14417 [math.CO], 2025. See p. 11.
%H A120733 Masato Kobayashi, <a href="https://arxiv.org/abs/1907.11801">Construction of double coset system of a Coxeter group and its applications to Bruhat graphs</a>, arXiv:1907.11801 [math.CO], 2019.
%H A120733 Vaclav Kotesovec, <a href="/A120733/a120733.pdf">Asymptotics of the sequence A120733</a>
%H A120733 E. Munarini, M. Poneti, and S. Rinaldi, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL12/Rinaldi/rinaldi.html">Matrix compositions</a>, JIS 12 (2009) 09.4.8, Remark 30.
%H A120733 T. K. Petersen, <a href="http://arxiv.org/abs/1607.00086">A two-sided analogue of the Coxeter complex</a>, arXiv:1607.00086 [math.CO], (2016).
%F A120733 a(n) = (1/n!)*Sum_{k=0..n} (-1)^(n-k)*Stirling1(n,k)*A000670(k)^2.
%F A120733 G.f.: Sum_{m>=0,n>=0} Sum_{j=0..n} (-1)^(n-j)*C(n,j)*((1-x)^(-j)-1)^m.
%F A120733 a(n) = Sum_{r>=0,s>=0} binomial(r*s+n-1,n)/2^(r+s+2).
%F A120733 G.f.: Sum_{n>=0} 1/(2-(1-x)^(-n))/2^(n+1). - _Vladeta Jovovic_, Oct 30 2006
%F A120733 a(n) ~ 2^(log(2)/2-2) * n! / (log(2))^(2*n+2). - _Vaclav Kotesovec_, May 07 2014
%e A120733 a(2) = 5:
%e A120733 [1 0]   [0 1]   [1]   [1 1]   [2]
%e A120733 [0 1]   [1 0]   [1]
%e A120733 From _Gus Wiseman_, Nov 14 2018: (Start)
%e A120733 The a(3) = 33 matrices:
%e A120733   [3][21][12][111]
%e A120733 .
%e A120733   [2][20][11][11][110][101][1][10][10][100][02][011][01][01][010][001]
%e A120733   [1][01][10][01][001][010][2][11][02][011][10][100][20][11][101][110]
%e A120733 .
%e A120733   [1][10][10][10][100][100][01][01][010][01][010][001][001]
%e A120733   [1][10][01][01][010][001][10][10][100][01][001][100][010]
%e A120733   [1][01][10][01][001][010][10][01][001][10][100][010][100]
%e A120733 (End)
%p A120733 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
%t A120733 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_ *)
%t A120733 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 *)
%t A120733 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 *)
%Y A120733 Row sums of A261781.
%Y A120733 Cf. A000219, A007322 (partial sums), A007716, A101370, A120732, A261838, A317533, A321515, A321585, A321586.
%K A120733 nonn
%O A120733 0,3
%A A120733 _Vladeta Jovovic_, Aug 18 2006, Aug 21 2006
%E A120733 More terms from _N. J. A. Sloane_, Jan 14 2009