A261838 -id:A261838 - 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.

1, 1, 5, 33, 281, 2961, 37277, 546193, 9132865, 171634161, 3581539973, 82171451025, 2055919433081, 55710251353953, 1625385528173693, 50800411296363617, 1693351638586070209, 59966271207156833313, 2248276994650395873861, 88969158875611127548481

Offset: 0

Vladeta Jovovic, Aug 18 2006, Aug 21 2006

nonn

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)

			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)

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

Row sums of A261781.

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

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

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

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

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

A261836 Number T(n,k) of compositions of n into distinct parts where each part i is marked with a word of length i over a k-ary alphabet whose letters appear in alphabetical order and all k letters occur at least once in the composition; triangle T(n,k), n>=0, 0<=k<=n, read by rows.

Original entry on oeis.org

1, 0, 1, 0, 1, 1, 0, 3, 10, 7, 0, 3, 15, 21, 9, 0, 5, 40, 96, 92, 31, 0, 11, 183, 832, 1562, 1305, 403, 0, 13, 266, 1539, 3908, 4955, 3090, 757, 0, 19, 549, 4281, 14791, 26765, 26523, 13671, 2873, 0, 27, 1056, 10902, 50208, 124450, 178456, 148638, 66904, 12607

Offset: 0

Alois P. Heinz, Sep 02 2015

Also number of matrices with k rows of nonnegative integer entries and without zero rows or columns such that the sum of all entries is equal to n and the column sums are distinct.

			T(3,2) = 10: (matrices and corresponding marked compositions are given)
  [2]   [1]   [2 0]  [0 2]  [1 0]  [0 1]  [1 1]  [1 1]  [1 0]  [0 1]
  [1]   [2]   [0 1]  [1 0]  [0 2]  [2 0]  [1 0]  [0 1]  [1 1]  [1 1]
  3aab, 3abb, 2aa1b, 1b2aa, 1a2bb, 2bb1a, 2ab1a, 1a2ab, 2ab1b, 1b2ab.
Triangle T(n,k) begins:
  1;
  0,  1;
  0,  1,   1;
  0,  3,  10,    7;
  0,  3,  15,   21,     9;
  0,  5,  40,   96,    92,    31;
  0, 11, 183,  832,  1562,  1305,   403;
  0, 13, 266, 1539,  3908,  4955,  3090,   757;
  0, 19, 549, 4281, 14791, 26765, 26523, 13671, 2873;

Alois P. Heinz, Rows n = 0..140, flattened

Columns k=0-10 give: A000007, A032020 (for n>0), A261853, A261854, A261855, A261856, A261857, A261858, A261859, A261860, A261861.
Main diagonal gives A032011.
Row sums give A261838.
T(2n,n) gives A261828.
Cf. A261781, A261835.

b:= proc(n, i, p, k) option remember;
      `if`(i*(i+1)/2n, 0, b(n-i, i-1, p+1, k)*binomial(i+k-1, k-1))))
    end:
T:= (n, k)-> add(b(n$2, 0, k-i)*(-1)^i*binomial(k, i), i=0..k):
seq(seq(T(n, k), k=0..n), n=0..12);

b[n_, i_, p_, k_] := b[n, i, p, k] = If[i*(i+1)/2n, 0, b[n-i, i-1, p+1, k]*Binomial[i+k-1, k-1]]]]; T[n_, k_] := Sum[b[n, n, 0, k-i]*(-1)^i*Binomial[k, i], {i, 0, k}]; Table[ Table[T[n, k], {k, 0, n}], {n, 0, 12}] // Flatten (* Jean-François Alcover, Feb 21 2016, after Alois P. Heinz *)

T(n,k) = Sum_{i=0..k} (-1)^i * C(k,i) * A261835(n,k-i).

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.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions