A331638 -id:A331638 - cp's OEIS frontend

A330942 Array read by antidiagonals: A(n,k) is the number of binary matrices with k columns and any number of nonzero rows with n ones in every column and columns in nonincreasing lexicographic order.

1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 4, 7, 1, 1, 1, 8, 75, 32, 1, 1, 1, 16, 1105, 2712, 161, 1, 1, 1, 32, 20821, 449102, 116681, 842, 1, 1, 1, 64, 478439, 122886128, 231522891, 5366384, 4495, 1, 1, 1, 128, 12977815, 50225389432, 975712562347, 131163390878, 256461703, 24320, 1, 1

Offset: 0

Andrew Howroyd, Jan 13 2020

The condition that the columns be in nonincreasing order is equivalent to considering nonequivalent matrices up to permutation of columns.

A(n,k) is the number of labeled n-uniform hypergraphs with multiple edges allowed and with k edges and no isolated vertices. When n=2 these objects are multigraphs.

			Array begins:
============================================================
n\k | 0 1    2         3              4                5
----+-------------------------------------------------------
  0 | 1 1    1         1              1                1 ...
  1 | 1 1    2         4              8               16 ...
  2 | 1 1    7        75           1105            20821 ...
  3 | 1 1   32      2712         449102        122886128 ...
  4 | 1 1  161    116681      231522891     975712562347 ...
  5 | 1 1  842   5366384   131163390878 8756434117294432 ...
  6 | 1 1 4495 256461703 78650129124911 ...
  ...
The A(2,2) = 7 matrices are:
   [1 0]  [1 0]  [1 0]  [1 1]  [1 0]  [1 0]  [1 1]
   [1 0]  [0 1]  [0 1]  [1 0]  [1 1]  [0 1]  [1 1]
   [0 1]  [1 0]  [0 1]  [0 1]  [0 1]  [1 1]
   [0 1]  [0 1]  [1 0]

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

Rows n=1..3 are A000012, A121316, A136246.
Columns k=0..3 are A000012, A000012, A226994, A137220.
The version with nonnegative integer entries is A331315.
Other variations considering distinct rows and columns and equivalence under different combinations of permutations of rows and columns are:
All solutions: A262809 (all), A331567 (distinct rows).
Up to row permutation: A188392, A188445, A331126, A331039.
Up to column permutation: this sequence, A331571, A331277, A331569.
Nonisomorphic: A331461, A331510, A331508, A331509.
Cf. A331638.

T[n_, k_] := With[{m = n k}, Sum[Binomial[Binomial[j, n] + k - 1, k] Sum[ (-1)^(i - j) Binomial[i, j], {i, j, m}], {j, 0, m}]];
Table[T[n - k, k], {n, 0, 9}, {k, n, 0, -1}] // Flatten (* Jean-François Alcover, Apr 10 2020, from PARI *)

T(n, k)={my(m=n*k); sum(j=0, m, binomial(binomial(j, n)+k-1, k)*sum(i=j, m, (-1)^(i-j)*binomial(i, j)))}

A(n,k) = Sum_{j=0..n*k} binomial(binomial(j,n)+k-1, k) * (Sum_{i=j..n*k} (-1)^(i-j)*binomial(i,j)).
A(n, k) = Sum_{j=0..k} abs(Stirling1(k, j))*A262809(n, j)/k!.
A(n, k) = Sum_{j=0..k} binomial(k-1, k-j)*A331277(n, j).
A331638(n) = Sum_{d|n} A(n/d, d).

A382429 Number of normal multiset partitions of weight n into sets with a common sum.

Original entry on oeis.org

1, 1, 2, 3, 5, 7, 13, 26, 57, 113, 283, 854, 2401, 6998, 24072, 85061, 308956, 1190518, 4770078, 19949106, 87059592

Offset: 0

Gus Wiseman, Mar 26 2025

We call a multiset or multiset partition normal iff it covers an initial interval of positive integers. The weight of a multiset partition is the sum of sizes of its blocks.

			The a(1) = 1 through a(6) = 13 partitions:
  {1} {12}   {123}     {1234}       {12345}         {123456}
      {1}{1} {3}{12}   {12}{12}     {24}{123}       {123}{123}
             {1}{1}{1} {14}{23}     {34}{124}       {125}{134}
                       {3}{3}{12}   {3}{12}{12}     {135}{234}
                       {1}{1}{1}{1} {5}{14}{23}     {145}{235}
                                    {3}{3}{3}{12}   {12}{12}{12}
                                    {1}{1}{1}{1}{1} {14}{14}{23}
                                                    {14}{23}{23}
                                                    {16}{25}{34}
                                                    {3}{3}{12}{12}
                                                    {5}{5}{14}{23}
                                                    {3}{3}{3}{3}{12}
                                                    {1}{1}{1}{1}{1}{1}
The corresponding factorizations:
  2  6    30     210      2310       30030
     2*2  5*6    6*6      21*30      30*30
          2*2*2  14*15    35*42      6*6*6
                 5*5*6    5*6*6      66*70
                 2*2*2*2  5*5*5*6    110*105
                          11*14*15   154*165
                          2*2*2*2*2  5*5*6*6
                                     14*14*15
                                     14*15*15
                                     26*33*35
                                     5*5*5*5*6
                                     11*11*14*15
                                     2*2*2*2*2*2

Without the common sum we have A116540 (normal set multipartitions).
Twice-partitions of this type are counted by A279788.
For common sizes instead of sums we have A317583.
Without strict blocks we have A326518, non-strict blocks A326517.
For a common length instead of sum we have A331638.
For distinct instead of equal block-sums we have A381718.
Factorizations of this type are counted by A382080.
For distinct block-sums and constant blocks we have A382203.
For constant instead of strict blocks we have A382204.
A000670 counts patterns, ranked by A055932 and A333217, necklace A019536.
A001055 count multiset partitions of prime indices, strict A045778.
A321469 counts multiset partitions with distinct block-sums, ranks A326535.
Normal multiset partitions: A035310, A255906, A304969, A317532.
Set multipartitions: A089259, A116539, A270995, A296119, A318360.
Set multipartitions with distinct sums: A279785, A381806, A381870.
Constant blocks with distinct sums: A381635, A381636, A381716.
Cf. A000110, A034691, A038041, A050320, A255903, A326520, A381633, A381996, A382214, A382216.

allnorm[n_Integer]:=Function[s,Array[Count[s,y_/;y<=#]+1&,n]]/@Subsets[Range[n-1]+1];
sps[{}]:={{}};sps[set:{i_,_}]:=Join@@Function[s,Prepend[#,s]&/@sps[Complement[set,s]]]/@Cases[Subsets[set],{i,_}];
mps[mset_]:=Union[Sort[Sort/@(#/.x_Integer:>mset[[x]])]&/@sps[Range[Length[mset]]]];
Table[Length[Join@@(Select[mps[#],SameQ@@Total/@#&&And@@UnsameQ@@@#&]&/@allnorm[n])],{n,0,5}]

a(11) from Robert Price, Mar 30 2025

a(12)-a(20) from Christian Sievers, Apr 06 2025

A382428 Number of normal multiset partitions of weight n into sets with distinct sizes.

Original entry on oeis.org

1, 1, 1, 6, 8, 35, 292, 673, 2818, 16956, 219772, 636748, 3768505, 20309534, 183403268, 3227600747, 12272598308, 81353466578, 561187259734, 4416808925866, 50303004612136, 1238783066956740, 5566249468690291, 44970939483601100, 330144217684933896, 3131452652308459402

Offset: 0

Gus Wiseman, Mar 29 2025

nonn

We call a multiset or multiset partition normal iff it covers an initial interval of positive integers. The weight of a multiset partition is the sum of sizes of its blocks.

			The a(1) = 1 through a(4) = 8 multiset partitions:
  {{1}}  {{1,2}}  {{1,2,3}}    {{1,2,3,4}}
                  {{1},{1,2}}  {{1},{1,2,3}}
                  {{1},{2,3}}  {{1},{2,3,4}}
                  {{2},{1,2}}  {{2},{1,2,3}}
                  {{2},{1,3}}  {{2},{1,3,4}}
                  {{3},{1,2}}  {{3},{1,2,3}}
                               {{3},{1,2,4}}
                               {{4},{1,2,3}}

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

For distinct sums instead of sizes we have A116539, see A050326.
Without distinct lengths we have A116540 (normal set multipartitions).
Without strict blocks we have A326517, for sum instead of size A326519.
For equal instead of distinct sizes we have A331638.
Twice-partitions of this type are counted by A358830.
For distinct sums instead of sizes we have A381718.
For equal instead of distinct sizes we have A382429.
A000670 counts patterns, ranked by A055932 and A333217, necklace A019536.
A001055 count factorizations, strict A045778.
Normal multiset partitions: A034691, A035310, A255906.
Set multipartitions: A089259, A270995, A296119, A318360.
Cf. A000110, A007716, A050320, A255903, A275780, A279785, A317532, A326518, A381633, A382214, A382216.

allnorm[n_Integer]:=Function[s,Array[Count[s,y_/;y<=#]+1&,n]]/@Subsets[Range[n-1]+1];
sps[{}]:={{}};sps[set:{i_,_}]:=Join@@Function[s,Prepend[#,s]&/@sps[Complement[set,s]]]/@Cases[Subsets[set],{i,_}];
mps[mset_]:=Union[Sort[Sort/@(#/.x_Integer:>mset[[x]])]&/@sps[Range[Length[mset]]]];
Table[Length[Join@@(Select[mps[#],UnsameQ@@Length/@#&&And@@UnsameQ@@@#&]&/@allnorm[n])],{n,0,5}]

R(n, k)={Vec(prod(j=1, n, 1 + binomial(k, j)*x^j + O(x*x^n)))}
seq(n)={sum(k=0, n, R(n, k)*sum(r=k, n, binomial(r, k)*(-1)^(r-k)))} \\ Andrew Howroyd, Mar 31 2025

a(10) onwards from Andrew Howroyd, Mar 31 2025

A331639 Number of binary matrices with nonzero rows, a total of n ones and distinct columns each with the same number of ones and columns in decreasing lexicographic order.

Original entry on oeis.org

1, 2, 2, 8, 2, 95, 2, 1062, 2651, 17667, 2, 946585, 2, 10422801, 126470568, 555727036, 2, 61345560608, 2, 1559456567421, 28383861400820, 19815939349521, 2, 30118264353296169, 8755909495925859, 49334805652369611, 21097628287362414244, 98053701052228556867, 2, 27303813269345643163251

Offset: 1

Andrew Howroyd, Jan 23 2020

nonn

The condition that the columns be in decreasing order is equivalent to considering nonequivalent matrices with distinct columns up to permutation of columns.

Andrew Howroyd, Table of n, a(n) for n = 1..200

Cf. A331277, A331638.

a(n) = Sum_{d|n} A331277(n/d, d).

a(p) = 2 for prime p.

cp's OEIS Frontend

A330942 Array read by antidiagonals: A(n,k) is the number of binary matrices with k columns and any number of nonzero rows with n ones in every column and columns in nonincreasing lexicographic order.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A382429 Number of normal multiset partitions of weight n into sets with a common sum.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Extensions

A382428 Number of normal multiset partitions of weight n into sets with distinct sizes.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Extensions

A331639 Number of binary matrices with nonzero rows, a total of n ones and distinct columns each with the same number of ones and columns in decreasing lexicographic order.

Views

Author

Keywords

Comments

Links

Crossrefs

Formula