|
%I #91 Oct 03 2023 06:34:23
%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 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. Rimaldi, <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
%O 0,3
%A _Vladeta Jovovic_, Aug 18 2006, Aug 21 2006
%E More terms from _N. J. A. Sloane_, Jan 14 2009
|
