A120733 - OEIS

%I #96 Nov 18 2024 15:59:19

%S 1,1,5,33,281,2961,37277,546193,9132865,171634161,3581539973,

%T 82171451025,2055919433081,55710251353953,1625385528173693,

%U 50800411296363617,1693351638586070209,59966271207156833313,2248276994650395873861,88969158875611127548481

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

%C The number of such matrices up to rows/columns permutations are given in A007716.

%C 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 From _Kyle Petersen_, Aug 10 2016: (Start)

%C 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 Also known as "two-way contingency tables" in the Diaconis-Gangolli reference. (End)

%H Alois P. Heinz, <a href="/A120733/b120733.txt">Table of n, a(n) for n = 0..400</a>

%H 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 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 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 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 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 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 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 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 Vaclav Kotesovec, <a href="/A120733/a120733.pdf">Asymptotics of the sequence A120733</a>

%H 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 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 a(n) = (1/n!)*Sum_{k=0..n} (-1)^(n-k)*Stirling1(n,k)*A000670(k)^2.

%F G.f.: Sum_{m>=0,n>=0} Sum_{j=0..n} (-1)^(n-j)*C(n,j)*((1-x)^(-j)-1)^m.

%F a(n) = Sum_{r>=0,s>=0} binomial(r*s+n-1,n)/2^(r+s+2).

%F G.f.: Sum_{n>=0} 1/(2-(1-x)^(-n))/2^(n+1). - _Vladeta Jovovic_, Oct 30 2006

%F a(n) ~ 2^(log(2)/2-2) * n! / (log(2))^(2*n+2). - _Vaclav Kotesovec_, May 07 2014

%e a(2) = 5:

%e [1 0]   [0 1]   [1]   [1 1]   [2]

%e [0 1]   [1 0]   [1]

%e From _Gus Wiseman_, Nov 14 2018: (Start)

%e The a(3) = 33 matrices:

%e   [3][21][12][111]

%e .

%e   [2][20][11][11][110][101][1][10][10][100][02][011][01][01][010][001]

%e   [1][01][10][01][001][010][2][11][02][011][10][100][20][11][101][110]

%e .

%e   [1][10][10][10][100][100][01][01][010][01][010][001][001]

%e   [1][10][01][01][010][001][10][10][100][01][001][100][010]

%e   [1][01][10][01][001][010][10][01][001][10][100][010][100]

%e (End)

%p 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 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 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 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 Row sums of A261781.

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

%K nonn,changed

%O 0,3

%A _Vladeta Jovovic_, Aug 18 2006, Aug 21 2006

%E More terms from _N. J. A. Sloane_, Jan 14 2009