A120733 -id:A120733 - cp's OEIS frontend

A261838 Number of compositions of n into distinct parts where each part i is marked with a word of length i over a k-ary alphabet (k=1,2,3,...) whose letters appear in alphabetical order and all k letters occur at least once in the composition.

1, 1, 2, 20, 48, 264, 4296, 14528, 89472, 593248, 19115360, 75604544, 599169408, 4141674240, 40147321344, 2159264715776, 10240251475456, 92926573965184, 746025520714112, 7285397378650112, 82900557619046912, 7796186873306241024, 41825012467664893440

Offset: 0

Alois P. Heinz, Sep 02 2015

nonn

Also number of matrices with nonnegative integer entries and without zero rows or columns such that sum of all entries is equal to n and the column sums are distinct.
a(2) = 2:
[1]   [2]
[1]

			a(0) = 1: the empty composition.
a(1) = 1: 1a.
a(2) = 2: 2aa (for k=1), 2ab (for k=2).

Alois P. Heinz, Table of n, a(n) for n = 0..300

Row sums of A261836.

Cf. A120733.

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:
a:= n-> add(add(b(n$2, 0, k-i)*(-1)^i*binomial(k, i), i=0..k), k=0..n):
seq(a(n), n=0..25);

b[n_, i_, p_, k_] := b[n, i, p, k] = If[i*(i+1)/2 < n, 0, If[n == 0, p!, b[n, i-1, p, k] + If[i>n, 0, b[n-i, i-1, p+1, k]*Binomial[i+k-1, k-1]]]]; a[n_] := Sum[b[n, n, 0, k-i]*(-1)^i*Binomial[k, i], {k, 0, n}, {i, 0, k}]; Table[a[n], {n, 0, 25}] (* Jean-François Alcover, Feb 25 2017, translated from Maple *)

A275787 Number of cells in the two-sided Coxeter complex of type B_n.

Original entry on oeis.org

1, 5, 41, 509, 8469, 176217, 4400325, 128203049, 4268957449, 159922273421, 6656731517249, 304797275277365, 15224868078068845, 823874409422614577, 48012621942105876301, 2997884066292303095889, 199666128081901473290833, 14129411123649333432720277, 1058688691179737704258634521, 83732563305101190468369022317, 6971039973751002759723517967941

Offset: 1

Kyle Petersen, Aug 09 2016

nonn

a(n) is the number of nonnegative integer matrices with sum of entries equal to 2*n-2 (or 2*n-1), no zero rows or columns, which are centrally symmetric. - Ludovic Schwob, Feb 17 2024

			The a(2) = 5 matrices whose sum of entries is equal to 2:
  [2] [1 1]
.
  [1] [1 0] [0 1]
  [1] [0 1] [1 0]

Evgeniy Krasko, Counting Unlabelled Chord Diagrams of Maximal Genus, arXiv:1709.00796 [math.CO], 2017.
T. K. Petersen, A two-sided analogue of the Coxeter complex, arXiv:1607.00086 [math.CO], 2016.

Cf. A120733 gives the number of cells for type A_n.

B:=proc(n) local f;
option remember;
if n=1 then 1+s*t;
elif n>1 then
f:=B(n-1);
RETURN(simplify( (2*n*s*t-s*t+1)*f+(2*s*t*(1-s)+s/n*(1-s)*(1-t))*diff(f,s) + (2*s*t*(1-t)+t/n*(1-s)*(1-t))*diff(f,t) + 2/n*s*t*(1-s)*(1-t)*diff( diff(f,s),t) ));
fi;
end:
seq(eval(eval(subs(s=x/(1+x),t=y/(1+y), B(n))*(1+x)^n*(1+y)^n,y=1),x=1), n=1..30);

B[n_] := B[n] = Which[n == 1, 1 + s*t, n > 1, f = B[n - 1]; Return[ Simplify[ (2*n*s*t - s*t + 1)*f + (2*s*t*(1 - s) + s/n*(1 - s)*(1 - t))*D[f, s] + (2*s*t*(1 - t) + t/n*(1 - s)*(1 - t))*D[f, t] + 2/n*s*t*(1 - s)*(1 - t)*D[ D[f, s], t]]]];
Join[{1}, Table[bn = ((B[n] /. {s -> x/(1 + x), t -> y/(1 + y)})*(1 + x)^n*(1 + y)^n /. {y -> 1, x -> 1}); Print[bn]; bn, {n, 1, 20}]] (* Jean-François Alcover, Nov 27 2017, from Maple *)

A321408 Number of non-isomorphic self-dual multiset partitions of weight n whose parts are aperiodic.

Original entry on oeis.org

1, 1, 1, 2, 5, 9, 18, 35, 75, 153, 318

Offset: 0

Gus Wiseman, Nov 16 2018

A multiset is aperiodic if its multiplicities are relatively prime.
Also the number of nonnegative integer symmetric matrices up to row and column permutations with sum of elements equal to n and no zero rows or columns, in which no row or column has a common divisor > 1.
The dual of a multiset partition has, for each vertex, one part consisting of the indices (or positions) of the parts containing that vertex, counted with multiplicity. For example, the dual of {{1,2},{2,2}} is {{1},{1,2,2}}.
The weight of a multiset partition is the sum of sizes of its parts. Weight is generally not the same as number of vertices.

			Non-isomorphic representatives of the a(1) = 1 through a(6) = 18 multiset partitions:
  {1}  {1}{2}  {2}{12}    {12}{12}      {12}{122}        {112}{122}
               {1}{2}{3}  {2}{122}      {2}{1222}        {12}{1222}
                          {1}{1}{23}    {1}{23}{23}      {2}{12222}
                          {1}{3}{23}    {1}{3}{233}      {12}{13}{23}
                          {1}{2}{3}{4}  {2}{13}{23}      {1}{23}{233}
                                        {3}{3}{123}      {1}{3}{2333}
                                        {1}{2}{2}{34}    {2}{13}{233}
                                        {1}{2}{4}{34}    {3}{23}{123}
                                        {1}{2}{3}{4}{5}  {3}{3}{1233}
                                                         {1}{1}{1}{234}
                                                         {1}{2}{34}{34}
                                                         {1}{2}{4}{344}
                                                         {1}{3}{24}{34}
                                                         {1}{4}{4}{234}
                                                         {2}{4}{12}{34}
                                                         {1}{2}{3}{3}{45}
                                                         {1}{2}{3}{5}{45}
                                                         {1}{2}{3}{4}{5}{6}

Cf. A000219, A007716, A120733, A138178, A316983, A319616.

Cf. A320796, A320797, A320803, A320804, A320805, A320806, A320807, A320809, A320813, A321410, A321411, A321412.

A321409 Number of non-isomorphic self-dual multiset partitions of weight n whose part sizes are relatively prime.

Original entry on oeis.org

1, 1, 1, 3, 6, 16, 27, 71, 135, 309, 621

Offset: 0

Gus Wiseman, Nov 16 2018

Also the number of nonnegative integer symmetric matrices up to row and column permutations with sum of elements equal to n and no zero rows or columns, with relatively prime row sums (or column sums).
The dual of a multiset partition has, for each vertex, one part consisting of the indices (or positions) of the parts containing that vertex, counted with multiplicity. For example, the dual of {{1,2},{2,2}} is {{1},{1,2,2}}.
The weight of a multiset partition is the sum of sizes of its parts. Weight is generally not the same as number of vertices.

			Non-isomorphic representatives of the a(1) = 1 through a(5) = 16 multiset partitions:
  {{1}}  {{1}{2}}  {{1}{22}}    {{1}{222}}      {{11}{122}}
                   {{2}{12}}    {{2}{122}}      {{11}{222}}
                   {{1}{2}{3}}  {{1}{1}{23}}    {{12}{122}}
                                {{1}{2}{33}}    {{1}{2222}}
                                {{1}{3}{23}}    {{2}{1222}}
                                {{1}{2}{3}{4}}  {{1}{22}{33}}
                                                {{1}{23}{23}}
                                                {{1}{2}{333}}
                                                {{1}{3}{233}}
                                                {{2}{12}{33}}
                                                {{2}{13}{23}}
                                                {{3}{3}{123}}
                                                {{1}{2}{2}{34}}
                                                {{1}{2}{3}{44}}
                                                {{1}{2}{4}{34}}
                                                {{1}{2}{3}{4}{5}}

Cf. A000219, A007716, A120733, A138178, A316983, A319616.

Cf. A320796, A320797, A320800, A320805, A320806, A320809, A320811, A320813, A321283, A321410, A321411, A321413.

A321413 Number of non-isomorphic self-dual multiset partitions of weight n with no singletons and relatively prime part sizes.

Original entry on oeis.org

1, 0, 0, 0, 0, 3, 0, 14, 13, 50, 65

Offset: 0

Gus Wiseman, Nov 16 2018

Also the number of nonnegative integer symmetric matrices up to row and column permutations with sum of elements equal to n and no zero rows or columns, with relatively prime row sums (or column sums) and no row (or column) summing to 1.
The dual of a multiset partition has, for each vertex, one part consisting of the indices (or positions) of the parts containing that vertex, counted with multiplicity. For example, the dual of {{1,2},{2,2}} is {{1},{1,2,2}}.
The weight of a multiset partition is the sum of sizes of its parts. Weight is generally not the same as number of vertices.

			Non-isomorphic representatives of the a(5) = 3, a(7) = 14, and a(8) = 13 multiset partitions:
  {{11}{122}}  {{111}{1222}}    {{111}{11222}}
  {{11}{222}}  {{111}{2222}}    {{111}{22222}}
  {{12}{122}}  {{112}{1222}}    {{112}{12222}}
               {{11}{22222}}    {{122}{11222}}
               {{12}{12222}}    {{11}{122}{233}}
               {{122}{1122}}    {{11}{122}{333}}
               {{22}{11222}}    {{11}{222}{333}}
               {{11}{12}{233}}  {{11}{223}{233}}
               {{11}{22}{233}}  {{12}{122}{333}}
               {{11}{22}{333}}  {{12}{123}{233}}
               {{11}{23}{233}}  {{13}{112}{233}}
               {{12}{12}{333}}  {{13}{122}{233}}
               {{12}{13}{233}}  {{23}{123}{123}}
               {{13}{23}{123}}

Cf. A000219, A007716, A120733, A138178, A302545, A316983, A319616.

Cf. A320796, A320797, A320806, A320813, A321283, A321409, A321410, A321411.

A321584 Number of connected (0,1)-matrices with n ones and no zero rows or columns.

Original entry on oeis.org

1, 1, 2, 6, 27, 159, 1154, 9968, 99861, 1138234, 14544650, 205927012, 3199714508, 54131864317, 990455375968, 19488387266842, 410328328297512, 9205128127109576, 219191041679766542, 5521387415218119528, 146689867860276432637, 4099255234885039058842, 120199458455807733040338

Offset: 0

Gus Wiseman, Nov 13 2018

nonn

A matrix is connected if the positions in each row (or each column) of the nonzero entries form a connected hypergraph.

			The a(4) = 27 matrices:
  [1111]
.
  [111][111][111][11][110][110][101][101][100][011][011][010][001]
  [100][010][001][11][101][011][110][011][111][110][101][111][111]
.
  [11][11][11][11][10][10][10][10][01][01][01][01]
  [10][10][01][01][11][11][10][01][11][11][10][01]
  [10][01][10][01][10][01][11][11][10][01][11][11]
.
  [1]
  [1]
  [1]
  [1]

Andrew Howroyd, Table of n, a(n) for n = 0..100

Cf. A007716, A007718, A049311, A056156, A101370, A104602, A120733, A283877, A319557, A319647, A319616-A319629, A321585.

csm[s_]:=With[{c=Select[Tuples[Range[Length[s]],2],And[OrderedQ[#],UnsameQ@@#,Length[Intersection@@s[[#]]]>0]&]},If[c=={},s,csm[Union[Append[Delete[s,List/@c[[1]]],Union@@s[[c[[1]]]]]]]]];
Table[Length[Select[Subsets[Tuples[Range[n],2],{n}],And[Union[First/@#]==Range[Max@@First/@#],Union[Last/@#]==Range[Max@@Last/@#],Length[csm[Map[Last,GatherBy[#,First],{2}]]]==1]&]],{n,6}] (* Mathematica 7.0+ *)

NonZeroCols(M)={my(C=Vec(M)); Mat(vector(#C, n, sum(k=1, n, (-1)^(n-k)*binomial(n,k)*C[k])))}
ConnectedMats(M)={my([m,n]=matsize(M), R=matrix(m,n)); for(m=1, m, for(n=1, n, R[m,n] = M[m,n] - sum(i=1, m-1, sum(j=1, n-1, binomial(m-1,i-1)*binomial(n,j)*R[i,j]*M[m-i,n-j])))); R}
seq(n)={my(M=matrix(n,n,i,j,sum(k=1, n, binomial(i*j,k)*x^k, O(x*x^n) ))); Vec(1 + vecsum(vecsum(Vec( ConnectedMats( NonZeroCols( NonZeroCols(M)~)) ))))} \\ Andrew Howroyd, Jan 17 2024

a(7) onwards from Andrew Howroyd, Jan 17 2024

A260700 Number of distinct parabolic double cosets of the symmetric group S_n.

Original entry on oeis.org

1, 3, 19, 167, 1791, 22715, 334031, 5597524, 105351108, 2200768698, 50533675542, 1265155704413, 34300156146805, 1001152439025205, 31301382564128969, 1043692244938401836, 36969440518414369896, 1386377072447199902576, 54872494774746771827248, 2285943548113541477123970

Offset: 1

Kyle Petersen, Nov 16 2015

nonn

This is closely related to the number of contingency tables on n elements (see A120733), but many contingency tables correspond to the same parabolic double coset, e.g., for n=2, there are 5 contingency tables, but only 3 distinct cosets.

			For n=2, there are three parabolic double cosets: {12}, {21}, and {12, 21}.

Thomas Browning, Table of n, a(n) for n = 1..400
Sara Billey, Matjaz Konvalinka, T. Kyle Petersen, William Slofstra, and Bridget Tenner, Parabolic double cosets in Coxeter groups, Discrete Mathematics and Theoretical Computer Science, Submitted, 2016.
Sara Billey, Matjaz Konvalinka, T. Kyle Petersen, William Slofstra, and Bridget Tenner, Parabolic double cosets in Coxeter groups, Electron. J. Combin., Volume 25, Issue 1 (2018) P1.23.
Thomas Browning, Counting Parabolic Double Cosets in Symmetric Groups, arXiv:2010.13256 [math.CO], 2020.
Masato Kobayashi, Construction of double coset system of a Coxeter group and its applications to Bruhat graphs, arXiv:1907.11801 [math.CO], 2019.

Cf. A120733.

a(n) is asymptotic to n! / (2^(log(2)/2 + 2) * log(2)^(2*n + 2)). [Conjectured Vaclav Kotesovec Sep 08 2020, proved Thomas Browning Oct 26 2020]

More terms from Thomas Browning, Sep 07 2020

A321412 Number of non-isomorphic self-dual multiset partitions of weight n with no singletons and with aperiodic parts.

Original entry on oeis.org

1, 0, 0, 0, 1, 1, 3, 4, 12, 20, 42

Offset: 0

Gus Wiseman, Nov 16 2018

A multiset is aperiodic if its multiplicities are relatively prime.
Also the number of nonnegative integer symmetric matrices up to row and column permutations with sum of elements equal to n and no zero rows or columns, with no row or column having a common divisor > 1 or summing to 1.
The dual of a multiset partition has, for each vertex, one part consisting of the indices (or positions) of the parts containing that vertex, counted with multiplicity. For example, the dual of {{1,2},{2,2}} is {{1},{1,2,2}}.
The weight of a multiset partition is the sum of sizes of its parts. Weight is generally not the same as number of vertices.

			Non-isomorphic representatives of the a(5) = 1 through a(8) = 12 multiset partitions:
{{12}{12}}  {{12}{122}}  {{112}{122}}    {{112}{1222}}    {{1112}{1222}}
                         {{12}{1222}}    {{12}{12222}}    {{112}{12222}}
                         {{12}{13}{23}}  {{12}{13}{233}}  {{12}{122222}}
                                         {{13}{23}{123}}  {{122}{11222}}
                                                          {{12}{123}{233}}
                                                          {{12}{13}{2333}}
                                                          {{13}{112}{233}}
                                                          {{13}{122}{233}}
                                                          {{13}{23}{1233}}
                                                          {{23}{123}{123}}
                                                          {{12}{12}{34}{34}}
                                                          {{12}{13}{24}{34}}

Cf. A000219, A007716, A120733, A138178, A302545, A316983, A319616.

Cf. A320796, A320797, A320803, A320806, A320809, A320813, A321408, A321410, A321411.

A323303 Number of ways to arrange the prime indices of n into a matrix with equal column-sums.

Original entry on oeis.org

1, 1, 1, 2, 1, 2, 1, 2, 2, 2, 1, 3, 1, 2, 2, 3, 1, 3, 1, 3, 2, 2, 1, 4, 2, 2, 2, 3, 1, 6, 1, 2, 2, 2, 2, 10, 1, 2, 2, 4, 1, 6, 1, 3, 3, 2, 1, 5, 2, 3, 2, 3, 1, 4, 2, 4, 2, 2, 1, 12, 1, 2, 3, 4, 2, 6, 1, 3, 2, 6, 1, 10, 1, 2, 3, 3, 2, 6, 1, 5, 3, 2, 1, 12, 2, 2

Offset: 1

Gus Wiseman, Jan 17 2019

nonn

A prime index of n is a number m such that prime(m) divides n. The multiset of prime indices of n is row n of A112798.

			The a(90) = 16 matrix-arrangements of (3,2,2,1) with equal column-sums:
  [1 2] [2 1] [2 3] [3 2]
  [3 2] [2 3] [2 1] [1 2]
.
  [1] [1] [1] [2] [2] [2] [2] [2] [2] [3] [3] [3]
  [2] [2] [3] [1] [1] [2] [2] [3] [3] [1] [2] [2]
  [2] [3] [2] [2] [3] [1] [3] [1] [2] [2] [1] [2]
  [3] [2] [2] [3] [2] [3] [1] [2] [1] [2] [2] [1]

Cf. A006052, A008480, A056239, A112798, A118914, A120733, A319056, A321719.

Cf. A323295, A323300, A323302, A323305, A323306, A323347, A323349.

primeMS[n_]:=If[n==1,{},Flatten[Cases[FactorInteger[n],{p_,k_}:>Table[PrimePi[p],{k}]]]];
facs[n_]:=If[n<=1,{{}},Join@@Table[Map[Prepend[#,d]&,Select[facs[n/d],Min@@#>=d&]],{d,Rest[Divisors[n]]}]];
ptnmats[n_]:=Union@@Permutations/@Select[Union@@(Tuples[Permutations/@#]&/@Map[primeMS,facs[n],{2}]),SameQ@@Length/@#&];
Table[Length[Select[ptnmats[n],SameQ@@Total/@Transpose[#]&]],{n,100}]

A383256 Number of n X n matrices of nonnegative entries with all columns summing to n and no horizontally adjacent zeros.

Original entry on oeis.org

1, 1, 7, 343, 125465, 366908001, 8698468668251, 1708834003295306868, 2810884261025802145414705, 39088555382409783097546399456477, 4626844513673581956954679383115038810744, 4688191496359773864437279635019555242588548880831

Offset: 0

John Tyler Rascoe, Apr 21 2025

nonn

			a(1) = 1: [1]
a(2) = 7: [1,1]   [1,0]   [1,2]   [0,1]   [2,1]   [0,2]   [2,0]
          [1,1],  [1,2],  [1,0],  [2,1],  [0,1],  [2,0],  [0,2].

John Tyler Rascoe, Python program.

Cf. A008300, A120733, A145839, A261780, A382923.

Python
```
# see links
```

a(10)-a(11) from Bert Dobbelaere, Apr 23 2025

cp's OEIS Frontend

A261838 Number of compositions of n into distinct parts where each part i is marked with a word of length i over a k-ary alphabet (k=1,2,3,...) whose letters appear in alphabetical order and all k letters occur at least once in the composition.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

A275787 Number of cells in the two-sided Coxeter complex of type B_n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

A321408 Number of non-isomorphic self-dual multiset partitions of weight n whose parts are aperiodic.

Views

Author

Keywords

Comments

Examples

Crossrefs

A321409 Number of non-isomorphic self-dual multiset partitions of weight n whose part sizes are relatively prime.

Views

Author

Keywords

Comments

Examples

Crossrefs

A321413 Number of non-isomorphic self-dual multiset partitions of weight n with no singletons and relatively prime part sizes.

Views

Author

Keywords

Comments

Examples

Crossrefs

A321584 Number of connected (0,1)-matrices with n ones and no zero rows or columns.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Extensions

A260700 Number of distinct parabolic double cosets of the symmetric group S_n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

Extensions

A321412 Number of non-isomorphic self-dual multiset partitions of weight n with no singletons and with aperiodic parts.

Views

Author

Keywords

Comments

Examples

Crossrefs

A323303 Number of ways to arrange the prime indices of n into a matrix with equal column-sums.

Views

Author

Keywords

Comments

Examples

Crossrefs