A049311 -id:A049311 - cp's OEIS frontend

A323351 Number of ways to fill a (not necessarily square) matrix with n zeros and ones.

1, 2, 8, 16, 48, 64, 256, 256, 1024, 1536, 4096, 4096, 24576, 16384, 65536, 131072, 327680, 262144, 1572864, 1048576, 6291456, 8388608, 16777216, 16777216, 134217728, 100663296, 268435456, 536870912, 1610612736, 1073741824, 8589934592, 4294967296, 25769803776

Offset: 0

Gus Wiseman, Jan 15 2019

nonn

			The a(3) = 16 matrices:
  [000] [001] [010] [011] [100] [101] [110] [111]
.
  [0] [0] [0] [0] [1] [1] [1] [1]
  [0] [0] [1] [1] [0] [0] [1] [1]
  [0] [1] [0] [1] [0] [1] [0] [1]

Cf. A000005, A049311, A120733, A323295, A323300.

Mathematica
```
Table[2^n*DivisorSigma[0,n],{n,10}]
```

a(n) = if (n==0, 1, 2^n*numdiv(n)); \\ Michel Marcus, Jan 15 2019

a(n) = 2^n * A000005(n) for n > 0, a(0) = 1.

G.f.: 1 + Sum_{k>=1} 2^k*x^k/(1 - 2^k*x^k). - Ilya Gutkovskiy, May 23 2019

A057150 Triangle read by rows: T(n,k) = number of k X k binary matrices with n ones, with no zero rows or columns, up to row and column permutation.

Original entry on oeis.org

1, 0, 1, 0, 1, 1, 0, 1, 2, 1, 0, 0, 5, 2, 1, 0, 0, 4, 11, 2, 1, 0, 0, 3, 21, 14, 2, 1, 0, 0, 1, 34, 49, 15, 2, 1, 0, 0, 1, 33, 131, 69, 15, 2, 1, 0, 0, 0, 33, 248, 288, 79, 15, 2, 1, 0, 0, 0, 19, 410, 840, 420, 82, 15, 2, 1, 0, 0, 0, 14, 531, 2144, 1744, 497, 83, 15, 2, 1

Offset: 1

Vladeta Jovovic, Aug 14 2000

Also the number of non-isomorphic set multipartitions (multisets of sets) of weight n with k parts and k vertices. - Gus Wiseman, Nov 14 2018

			[1], [0,1], [0,1,1], [0,1,2,1], [0,0,5,2,1], [0,0,4,11,2,1], ...;
There are 8 square binary matrices with 5 ones, with no zero rows or columns, up to row and column permutation: 5 of size 3 X 3:
[0 0 1] [0 0 1] [0 0 1] [0 0 1] [0 0 1]
[0 0 1] [0 1 0] [0 1 1] [0 1 1] [1 1 0]
[1 1 1] [1 1 1] [1 0 1] [1 1 0] [1 1 0]
2 of size 4 X 4:
[0 0 0 1] [0 0 0 1]
[0 0 0 1] [0 0 1 0]
[0 0 1 0] [0 1 0 0]
[1 1 0 0] [1 0 0 1]
and 1 of size 5 X 5:
[0 0 0 0 1]
[0 0 0 1 0]
[0 0 1 0 0]
[0 1 0 0 0]
[1 0 0 0 0].
From _Gus Wiseman_, Nov 14 2018: (Start)
Triangle begins:
   1
   0   1
   0   1   1
   0   1   2   1
   0   0   5   2   1
   0   0   4  11   2   1
   0   0   3  21  14   2   1
   0   0   1  34  49  15   2   1
   0   0   1  33 131  69  15   2   1
   0   0   0  33 248 288  79  15   2   1
Non-isomorphic representatives of the multiset partitions counted in row 6 {0,0,4,11,2,1} are:
  {{12}{13}{23}}  {{1}{1}{1}{234}}  {{1}{2}{3}{3}{45}}  {{1}{2}{3}{4}{5}{6}}
  {{1}{23}{123}}  {{1}{1}{24}{34}}  {{1}{2}{3}{5}{45}}
  {{13}{23}{23}}  {{1}{1}{4}{234}}
  {{3}{23}{123}}  {{1}{2}{34}{34}}
                  {{1}{3}{24}{34}}
                  {{1}{3}{4}{234}}
                  {{1}{4}{24}{34}}
                  {{1}{4}{4}{234}}
                  {{2}{4}{12}{34}}
                  {{3}{4}{12}{34}}
                  {{4}{4}{12}{34}}
(End)

Row sums give A057151.
Cf. A049311, A056037, A056079, A056080, A057149, A057151, A057152.
Cf. A007716, A048291, A054976, A101370, A104601, A104602, A120732, A120733, A135588, A319616, A321609, A321615.

permcount[v_List] := Module[{m = 1, s = 0, k = 0, t}, For[i = 1, i <= Length[v], i++, t = v[[i]]; k = If[i > 1 && t == v[[i - 1]], k + 1, 1]; m *= t*k; s += t]; s!/m];
c[p_List, q_List, k_] := SeriesCoefficient[Product[Product[(1 + O[x]^(k + 1) + x^LCM[p[[i]], q[[j]]])^GCD[p[[i]], q[[j]]], {j, 1, Length[q]}], {i, 1, Length[p]}], {x, 0, k}];
M[m_, n_, k_] := M[m, n, k] = Module[{s = 0}, Do[Do[s += permcount[p]* permcount[q]*c[p, q, k], {q, IntegerPartitions[n]}], {p, IntegerPartitions[m]}]; s/(m!*n!)];
T[n_, k_] := M[k, k, n] - 2*M[k, k - 1, n] + M[k - 1, k - 1, n];
Table[T[n, k], {n, 1, 12}, {k, 1, n}] // Flatten (* Jean-François Alcover, Sep 10 2019, after Andrew Howroyd *)

\\ See A321609 for M.
T(n,k) = M(k,k,n) - 2*M(k,k-1,n) + M(k-1,k-1,n); \\ Andrew Howroyd, Nov 14 2018

Duplicate seventh row removed by Gus Wiseman, Nov 14 2018

A293607 Number of unlabeled clutters of weight n.

Original entry on oeis.org

1, 1, 1, 1, 2, 2, 7, 8, 23, 42

Offset: 0

Gus Wiseman, Oct 13 2017

A clutter is a connected antichain of finite sets. The weight of a clutter is the sum of cardinalities of its edges.

			Non-isomorphic representatives of the a(7) = 8 clutters are:
((1234567)),
((12)(13456)), ((123)(1245)), ((123)(1456)),
((12)(13)(145)), ((12)(13)(234)), ((12)(13)(245)), ((13)(24)(125)).

Cf. A006126, A007716, A048143, A049311, A283877, A293606.

A306019 Number of non-isomorphic set-systems of weight n in which all parts have the same size.

Original entry on oeis.org

1, 1, 2, 2, 4, 2, 10, 2, 17, 14, 33, 2, 167, 2, 186, 491, 785, 2, 5839, 2, 11123, 53454, 15229, 2, 1102924, 53537, 193382, 16334183, 12411062, 2, 382413555, 2, 993814248, 9763321547, 53394774, 1778595972, 402119882757, 2, 1111261718, 9674133468473, 16955983996383

Offset: 0

Gus Wiseman, Jun 17 2018

nonn

A set-system of weight n is a finite set of finite nonempty sets whose sizes sum to n.

			Non-isomorphic representatives of the a(6) = 10 set-systems:
{{1,2,3,4,5,6}}
{{1,2,3},{4,5,6}}
{{1,2,5},{3,4,5}}
{{1,3,4},{2,3,4}}
{{1,2},{1,3},{2,3}}
{{1,2},{3,4},{5,6}}
{{1,2},{3,5},{4,5}}
{{1,3},{2,4},{3,4}}
{{1,4},{2,4},{3,4}}
{{1},{2},{3},{4},{5},{6}}

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

Cf. A000005, A001315, A007716, A038041, A049311, A283877, A298422, A306017, A306018, A306020, A306021.

\\ See A331508 for T(n,k).
a(n) = {if(n==0, 1, sumdiv(n, d, if(d==1 || d==n, 1, T(n/d, d))))} \\ Andrew Howroyd, Jan 16 2024

a(p) = 2 for prime p. - Andrew Howroyd, Aug 29 2019

a(n) = Sum_{d|n} A331508(n/d, d) for n > 0. - Andrew Howroyd, Jan 16 2024

Terms a(12) and beyond from Andrew Howroyd, Sep 01 2019

A319778 Number of non-isomorphic set systems of weight n with empty intersection whose dual is also a set system with empty intersection.

Original entry on oeis.org

1, 0, 1, 1, 2, 5, 13, 28, 72, 181, 483

Offset: 0

Gus Wiseman, Sep 27 2018

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 dual of a multiset partition has empty intersection iff no part contains all the vertices.

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(2) = 1 through a(6) = 13 multiset partitions:
2: {{1},{2}}
3: {{1},{2},{3}}
4: {{1},{3},{2,3}}
   {{1},{2},{3},{4}}
5: {{1},{2,4},{3,4}}
   {{2},{1,3},{2,3}}
   {{1},{2},{3},{2,3}}
   {{1},{2},{4},{3,4}}
   {{1},{2},{3},{4},{5}}
6: {{3},{1,4},{2,3,4}}
   {{1,2},{1,3},{2,3}}
   {{1,3},{2,4},{3,4}}
   {{1},{2},{1,3},{2,3}}
   {{1},{2},{3,5},{4,5}}
   {{1},{3},{4},{2,3,4}}
   {{1},{3},{2,4},{3,4}}
   {{1},{4},{2,4},{3,4}}
   {{2},{3},{1,3},{2,3}}
   {{2},{4},{1,2},{3,4}}
   {{1},{2},{3},{4},{3,4}}
   {{1},{2},{3},{5},{4,5}}
   {{1},{2},{3},{4},{5},{6}}

Cf. A007716, A049311, A281116, A283877, A316980, A317752, A317755, A317757.

Cf. A319775, A319779, A319781, A319783.

A104601 Triangle T(r,n) read by rows: number of n X n (0,1)-matrices with exactly r entries equal to 1 and no zero row or columns.

Original entry on oeis.org

1, 0, 2, 0, 4, 6, 0, 1, 45, 24, 0, 0, 90, 432, 120, 0, 0, 78, 2248, 4200, 720, 0, 0, 36, 5776, 43000, 43200, 5040, 0, 0, 9, 9066, 222925, 755100, 476280, 40320, 0, 0, 1, 9696, 727375, 6700500, 13003620, 5644800, 362880, 0, 0, 0, 7480, 1674840

Offset: 1

Ralf Stephan, Mar 27 2005

			1
0,2
0,4,6
0,1,45,24
0,0,90,432,120
0,0,78,2248,4200,720
0,0,36,5776,43000,43200,5040
0,0,9,9066,222925,755100,476280,40320
0,0,1,9696,727375,6700500,13003620,5644800,362880
0,0,0,7480,1674840,37638036,179494350,226262400,71850240,3628800

M. Maia and M. Mendez, On the arithmetic product of combinatorial species, arXiv:math/0503436 [math.CO], 2005.

Right-edge diagonals include A000142, A055602, A055603. Row sums are in A104602.
Column sums are in A048291. The triangle read by columns = A055599.
Cf. A049311, A054976, A057150, A057151, A101370, A120732, A120733, A138178, A316983, A319616.

t[r_, n_] := Sum[ Sum[ (-1)^(2n - d - k/d)*Binomial[n, d]*Binomial[n, k/d]*Binomial[k, r], {d, Divisors[k]}], {k, r, n^2}]; Flatten[ Table[t[r, n], {r, 1, 10}, {n, 1, r}]] (* Jean-François Alcover, Jun 27 2012, from formula *)
Table[Length[Select[Subsets[Tuples[Range[n],2],{n}],Union[First/@#]==Union[Last/@#]==Range[k]&]],{n,6},{k,n}] (* Gus Wiseman, Nov 14 2018 *)

T(r, n) = Sum{l>=r, Sum{d|l, (-1)^(2n-d-l/d)*C(n, d)*C(n, l/d)*C(l, r) }}.

E.g.f.: Sum(((1+x)^n-1)^n*exp((1-(1+x)^n)*y)*y^n/n!,n=0..infinity). - Vladeta Jovovic, Feb 24 2008

A135588 Number of symmetric (0,1)-matrices with exactly n entries equal to 1 and no zero rows or columns.

Original entry on oeis.org

1, 1, 2, 6, 20, 74, 302, 1314, 6122, 29982, 154718, 831986, 4667070, 27118610, 163264862, 1013640242, 6488705638, 42687497378, 288492113950, 1998190669298, 14177192483742, 102856494496050, 762657487965086, 5771613810502002, 44555989658479726, 350503696871063138

Offset: 0

Vladeta Jovovic, Feb 25 2008, Mar 03 2008, Mar 04 2008

nonn

			From _Gus Wiseman_, Nov 14 2018: (Start)
The a(4) = 20 matrices:
  [11]
  [11]
.
  [110][101][100][100][011][010][010][001][001]
  [100][010][011][001][100][110][101][010][001]
  [001][100][010][011][100][001][010][101][110]
.
  [1000][1000][1000][1000][0100][0100][0010][0010][0001][0001]
  [0100][0100][0010][0001][1000][1000][0100][0001][0100][0010]
  [0010][0001][0100][0010][0010][0001][1000][1000][0010][0100]
  [0001][0010][0001][0100][0001][0010][0001][0100][1000][1000]
(End)

Alois P. Heinz, Table of n, a(n) for n = 0..721 (first 51 terms from Vincenzo Librandi)

Row sums of A135589.

Cf. A049311, A054976, A101370, A104601, A104602, A120733, A138178, A283877, A316983, A320796, A321401, A321405.

Table[Sum[SeriesCoefficient[(1+x)^k*(1+x^2)^(k*(k-1)/2)/2^(k+1),{x,0,n}],{k,0,Infinity}],{n,0,20}] (* Vaclav Kotesovec, Jul 02 2014 *)
Join[{1},  Table[Length[Select[Subsets[Tuples[Range[n], 2], {n}], And[Union[First/@#]==Range[Max@@First/@#], Union[Last/@#]==Range[Max@@Last/@#], Sort[Reverse/@#]==#]&]], {n, 5}]] (* Gus Wiseman, Nov 14 2018 *)

G.f.: Sum_{n>=0} (1+x)^n*(1+x^2)^binomial(n,2)/2^(n+1).

G.f.: Sum_{n>=0} (Sum_{k=0..n} (-1)^(n-k)*binomial(n,k)*(1+x)^k*(1+x^2)^binomial(k,2)).

A303547 Number of non-isomorphic periodic multiset partitions of weight n.

Original entry on oeis.org

0, 1, 1, 4, 1, 13, 1, 33, 10, 94, 1, 327, 1, 913, 100, 3017, 1, 10233, 1, 34236, 919, 119372, 1, 432234, 91, 1574227, 9945, 5916177, 1, 22734231, 1, 89003059, 119378, 356058543, 1000, 1453509039, 1, 6044132797, 1574233, 25612601420, 1, 110509543144, 1, 485161348076

Offset: 1

Gus Wiseman, Apr 26 2018

nonn

A multiset is periodic if its multiplicities have a common divisor greater than 1. For this sequence neither the parts nor their multiset union are required to be periodic, only the multiset of parts.

			Non-isomorphic representatives of the a(4) = 4 multiset partitions are {{1,1},{1,1}}, {{1,2},{1,2}}, {{1},{1},{1},{1}}, {{1},{1},{2},{2}}.

Cf. A000740, A000837, A001055, A007716, A007916, A049311, A100953, A255906, A269134, A275024, A293993, A301700, A303386, A303431, A303546.

a(n) = 1 if n is prime.

a(n) = A007716(n) - A303546(n).

More terms from Jinyuan Wang, Jun 21 2020

A306018 Number of non-isomorphic set multipartitions of weight n in which all parts have the same size.

Original entry on oeis.org

1, 1, 3, 4, 9, 8, 24, 16, 51, 47, 115, 57, 420, 102, 830, 879, 2962, 298, 15527, 491, 41275, 80481, 133292, 1256, 2038182, 58671, 2386862, 24061887, 23570088, 4566, 600731285, 6843, 1303320380, 14138926716, 1182784693, 1820343112, 542834549721, 21638, 31525806080

Offset: 0

Gus Wiseman, Jun 17 2018

nonn

A set multipartition of weight n is a finite multiset of finite nonempty sets whose cardinalities sum to n.

Number of distinct binary matrices with all row sums equal and total sum n, up to row and column permutations. - Andrew Howroyd, Sep 05 2018

			Non-isomorphic representatives of the a(6) = 24 set multipartitions in which all parts have the same size:
{{1,2,3,4,5,6}}
{{1,2,3},{1,2,3}}
{{1,2,3},{4,5,6}}
{{1,2,5},{3,4,5}}
{{1,3,4},{2,3,4}}
{{1,2},{1,2},{1,2}}
{{1,2},{1,3},{2,3}}
{{1,2},{3,4},{3,4}}
{{1,2},{3,4},{5,6}}
{{1,2},{3,5},{4,5}}
{{1,3},{2,3},{2,3}}
{{1,3},{2,4},{3,4}}
{{1,4},{2,4},{3,4}}
{{1},{1},{1},{1},{1},{1}}
{{1},{1},{1},{2},{2},{2}}
{{1},{1},{2},{2},{2},{2}}
{{1},{1},{2},{2},{3},{3}}
{{1},{2},{2},{2},{2},{2}}
{{1},{2},{2},{3},{3},{3}}
{{1},{2},{3},{3},{3},{3}}
{{1},{2},{3},{3},{4},{4}}
{{1},{2},{3},{4},{4},{4}}
{{1},{2},{3},{4},{5},{5}}
{{1},{2},{3},{4},{5},{6}}

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

Cf. A000005, A000041, A001315, A007716, A038041, A049311, A283877, A298422, A304942, A306017, A306019, A306020, A306021, A331461.

\\ See A304942 for Blocks
a(n)={sumdiv(n, d, Blocks(n/d, n, d))} \\ Andrew Howroyd, Sep 05 2018

a(p) = A000041(p) + 1 for prime p. - Andrew Howroyd, Sep 06 2018

a(n) = Sum_{d|n} A331461(n/d, d). - Andrew Howroyd, Feb 09 2020

Terms a(11) and beyond from Andrew Howroyd, Sep 05 2018

A306020 a(n) is the number of set-systems using nonempty subsets of {1,...,n} in which all sets have the same size.

Original entry on oeis.org

1, 2, 5, 16, 95, 2110, 1114237, 68723671292, 1180735735906024030715, 170141183460507917357914971986913657850, 7237005577335553223087828975127304179197147198604070555943173844710572689401

Offset: 0

Gus Wiseman, Jun 17 2018

nonn

A058673(n) <= a(n). - Lorenzo Sauras Altuzarra, Aug 10 2023

			a(3) = 16 set-systems in which all sets have the same size:
  {}
  {{1}}
  {{2}}
  {{3}}
  {{1,2}}
  {{1,3}}
  {{2,3}}
  {{1,2,3}}
  {{1},{2}}
  {{1},{3}}
  {{2},{3}}
  {{1,2},{1,3}}
  {{1,2},{2,3}}
  {{1,3},{2,3}}
  {{1},{2},{3}}
  {{1,2},{1,3},{2,3}}

Index entries for sequences related to matroids

Cf. A000005, A001315, A007716, A038041, A049311, A058673 (labeled matroids), A283877, A298422, A306017, A306018, A306019, A306021.

Row sums of A059328.

a := n -> 1-n+add(2^binomial(n, d), d = 1 .. n):
seq(a(n), n = 0 .. 10); # Lorenzo Sauras Altuzarra, Aug 11 2023

Table[1+Sum[2^Binomial[n,d]-1,{d,n}],{n,10}]

a(n) = 1 - n + sum(d = 1, n, 2^binomial(n, d)); \\ Michel Marcus, Aug 10 2023

a(n) = 1 - n + Sum_{d = 1..n} 2^binomial(n, d).

cp's OEIS Frontend

A323351 Number of ways to fill a (not necessarily square) matrix with n zeros and ones.

Views

Author

Keywords

Examples

Crossrefs

Programs

Mathematica

PARI

Formula

A057150 Triangle read by rows: T(n,k) = number of k X k binary matrices with n ones, with no zero rows or columns, up to row and column permutation.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

PARI

Extensions

A293607 Number of unlabeled clutters of weight n.

Views

Author

Keywords

Comments

Examples

Crossrefs

A306019 Number of non-isomorphic set-systems of weight n in which all parts have the same size.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula

Extensions

A319778 Number of non-isomorphic set systems of weight n with empty intersection whose dual is also a set system with empty intersection.

Views

Author

Keywords

Comments

Examples

Crossrefs

A104601 Triangle T(r,n) read by rows: number of n X n (0,1)-matrices with exactly r entries equal to 1 and no zero row or columns.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A135588 Number of symmetric (0,1)-matrices with exactly n entries equal to 1 and no zero rows or columns.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A303547 Number of non-isomorphic periodic multiset partitions of weight n.

Views

Author

Keywords

Comments

Examples

Crossrefs

Formula

Extensions

A306018 Number of non-isomorphic set multipartitions of weight n in which all parts have the same size.

Views

Author