A331508 -id:A331508 - 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).

A331461 Array read by antidiagonals: A(n,k) is the number of nonequivalent binary matrices with k columns and any number of nonzero rows with n ones in every column up to permutation of rows and columns.

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 3, 3, 1, 1, 1, 5, 8, 4, 1, 1, 1, 7, 23, 16, 5, 1, 1, 1, 11, 66, 93, 30, 6, 1, 1, 1, 15, 212, 652, 332, 50, 7, 1, 1, 1, 22, 686, 6369, 6414, 1062, 80, 8, 1, 1, 1, 30, 2389, 79568, 226041, 56712, 3117, 120, 9, 1, 1, 1, 42, 8682, 1256425, 12848128, 7295812, 441881, 8399, 175, 10, 1, 1

Offset: 0

Andrew Howroyd, Jan 18 2020

A(n,k) is the number of non-isomorphic set multipartitions (multiset of sets) with k parts each part has size n.

			Array begins:
===========================================================
n\k | 0 1 2   3    4       5          6              7
----+-----------------------------------------------------
  0 | 1 1 1   1    1       1          1              1 ...
  1 | 1 1 2   3    5       7         11             15 ...
  2 | 1 1 3   8   23      66        212            686 ...
  3 | 1 1 4  16   93     652       6369          79568 ...
  4 | 1 1 5  30  332    6414     226041       12848128 ...
  5 | 1 1 6  50 1062   56712    7295812     1817321457 ...
  6 | 1 1 7  80 3117  441881  195486906   200065951078 ...
  7 | 1 1 8 120 8399 3006771 4298181107 17131523059493 ...
  ...
The A(2,3) = 8 matrices are:
  [1 0 0]  [1 1 0]  [1 1 1]  [1 1 0]  [1 1 0]  [1 1 1]  [1 1 0]  [1 1 1]
  [1 0 0]  [1 0 0]  [1 0 0]  [1 1 0]  [1 0 1]  [1 1 0]  [1 0 1]  [1 1 1]
  [0 1 0]  [0 1 0]  [0 1 0]  [0 0 1]  [0 1 0]  [0 0 1]  [0 1 1]
  [0 1 0]  [0 0 1]  [0 0 1]  [0 0 1]  [0 0 1]
  [0 0 1]  [0 0 1]
  [0 0 1]

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

Rows n=0..6 are A000012, A000041, A050535, A050913, A058783, A058784, A058785.
Columns k=0..4 are A000012, A000012, A000027(n+1), A002624, A331720.
Cf. A188392, A262809, A304942, A306018, A330942, A331485, A331508, A331509, A331510.

\\ See A304942 for Blocks
T(n,k)={Blocks(k, n*k, n)}
{ for(n=0, 7, for(k=0, 6, print1(T(n,k), ", ")); print) }

A306018(n) = Sum_{d|n} A(n/d, d).

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

A058790 Number of covers of an unlabeled n-set such that every point of the set is covered by exactly 3 subsets of the cover and that intersection of every 3 subsets of the cover contains at most one point.

Original entry on oeis.org

1, 3, 12, 66, 445, 4279, 53340, 846254, 16333946, 371976963, 9763321109, 290473143807, 9674133467729, 357177322891321, 14503958827502886, 643502334799711633, 31018731336031551119, 1616523352051185316626, 90689288905913623412837, 5456178840303106057314759, 350830170593891706361540379

Offset: 1

Vladeta Jovovic, Nov 30 2000

nonn

Cover may include multiple occurrences of a subset. Also n-rowed binary matrices with distinct rows and all row sums 3.

For labeled case see Goulden I. P., Jackson D. M., Combinatorial Enumeration, John Wiley and Sons, New York, 1983.

Vladeta Jovovic, Formula

Row n=3 of A331508.

Cf. A050535, A050913, A058783, A058784, A058785, A082789, A082790.

More terms from T. Forbes (anthony.d.forbes(AT)googlemail.com), May 24 2003

A331510 Array read by antidiagonals: A(n,k) is the number of nonequivalent binary matrices with k columns and any number of distinct nonzero rows with n ones in every column up to permutation of rows and columns.

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 1, 2, 0, 1, 1, 3, 1, 0, 1, 1, 5, 4, 0, 0, 1, 1, 7, 12, 3, 0, 0, 1, 1, 11, 36, 23, 1, 0, 0, 1, 1, 15, 124, 191, 30, 0, 0, 0, 1, 1, 22, 412, 2203, 837, 23, 0, 0, 0, 1, 1, 30, 1500, 31313, 41664, 2688, 12, 0, 0, 0, 1

Offset: 0

Andrew Howroyd, Jan 18 2020

			Array begins:
=================================
n\k | 0 1 2 3  4   5    6   7
----+----------------------------
  0 | 1 1 1 1  1   1    1   1 ...
  1 | 1 1 2 3  5   7   11  15 ...
  2 | 1 0 1 4 12  36  124 412 ...
  3 | 1 0 0 3 23 191 2203 ...
  4 | 1 0 0 1 30 837 ...
  5 | 1 0 0 0 23 ...
  ...
The A(2,3) = 4 matrices are:
  [1 1 1]  [1 1 0]  [1 1 1]  [1 1 0]
  [1 0 0]  [1 0 1]  [1 1 0]  [1 0 1]
  [0 1 0]  [0 1 0]  [0 0 1]  [0 1 1]
  [0 0 1]  [0 0 1]

Rows n=1..3 are A000041, A331717, A331718.
Column k=5 is A331719.
Cf. A188445, A330942, A331461, A331508, A331509.

A(n,k) = 0 for k > 0, n > 2^(k-1).

A(n,k) = A(2^(k-1) - n, k) for k > 0, n <= 2^(k-1).

a(58)-a(65) from Andrew Howroyd, Feb 08 2020

A331509 Array read by antidiagonals: A(n,k) is the number of nonisomorphic T_0 n-regular set-systems on a k-set.

Original entry on oeis.org

1, 1, 1, 0, 1, 1, 0, 1, 0, 1, 0, 1, 1, 0, 1, 0, 1, 3, 0, 0, 1, 0, 1, 6, 3, 0, 0, 1, 0, 1, 15, 19, 1, 0, 0, 1, 0, 1, 42, 141, 29, 0, 0, 0, 1, 0, 1, 109, 1571, 769, 23, 0, 0, 0, 1, 0, 1, 320

Offset: 0

Andrew Howroyd, Jan 18 2020

An n-regular set-system is a finite set of nonempty sets in which each element appears in n blocks.
A set-system is T_0 if for every two distinct elements there exists a block containing one but not the other element.
A(n,k) is the number of nonequivalent binary matrices with k distinct columns and any number of distinct nonzero rows with n ones in every column up to permutation of rows and columns.

			Array begins:
=================================
n\k | 0 1 2 3  4   5    6   7
----+----------------------------
  0 | 1 1 0 0  0   0    0   0 ...
  1 | 1 1 1 1  1   1    1   1 ...
  2 | 1 0 1 3  6  15   42 109 ...
  3 | 1 0 0 3 19 141 1571 ...
  4 | 1 0 0 1 29 769 ...
  5 | 1 0 0 0 23 ...
  ...
The A(2,3) = 3 matrices are:
  [1 1 1]    [1 1 0]    [1 1 0]
  [1 0 0]    [1 0 1]    [1 0 1]
  [0 1 0]    [0 1 0]    [0 1 1]
  [0 0 1]    [0 0 1]

Row 2 appears to be A005368. Row 3 is A331716.

Cf. A330942, A331039, A331461, A331508, A331510.

A058791 Number of covers of an unlabeled n-set such that every point of the set is covered by exactly 4 subsets of the cover and that intersection of every 4 subsets of the cover contains at most one point.

Original entry on oeis.org

1, 4, 25, 278, 5532, 200589, 11662671, 981458725, 111213730857, 16212510876591, 2947663429595884, 653299790376494253, 173373367472722467460, 54295204354760461199529, 19822683467350158062736540

Offset: 1

Vladeta Jovovic, Nov 30 2000

Cover may include multiple occurrences of a subset. Also n-rowed binary matrices with distinct rows and all row sums 4.

Vladeta Jovovic, Formula

Row n=4 of A331508.

Cf. A050535, A050913, A058783, A058784, A058785.

a(8)-a(12) from Andrew Howroyd, Jan 29 2020

a(13)-a(15) from Sean A. Irvine, Aug 26 2022

A058792 Number of covers of an unlabeled n-set such that every point of the set is covered by exactly 5 subsets of the cover and that intersection of every 5 subsets of the cover contains at most one point.

Original entry on oeis.org

1, 5, 44, 966, 53535, 7043925, 1775617861, 738134963014, 461550358993886, 409321620633426443, 493892363593918906465

Offset: 1

Vladeta Jovovic, Nov 30 2000

Cover may include multiple occurrences of a subset. Also n-rowed binary matrices with distinct rows and all row sums 5.

Vladeta Jovovic, Formula

Row n=5 of A331508.

Cf. A050535, A050913, A058783, A058784, A058785.

a(7)-a(10) from Andrew Howroyd, Jan 29 2020

a(11) from Sean A. Irvine, Aug 27 2022

A058793 Number of covers of an unlabeled n-set such that every point of the set is covered by exactly 6 subsets of the cover and that intersection of every 6 subsets of the cover contains at most one point.

Original entry on oeis.org

1, 6, 73, 2957, 431805, 193413963, 198914729182, 389238347659505, 1292594846197639190, 6753309741099683530616

Offset: 1

Vladeta Jovovic, Nov 30 2000

Cover may include multiple occurrences of a subset. Also n-rowed binary matrices with distinct rows and all row sums 6.

Vladeta Jovovic, Formula

Row n=6 of A331508.

Cf. A050535, A050913, A058783, A058784, A058785.

a(6)-a(10) from Andrew Howroyd, Jan 29 2020

A302129 Number of unlabeled uniform connected hypergraphs of weight n.

Original entry on oeis.org

1, 1, 1, 1, 2, 1, 6, 1, 9, 10, 17, 1, 108, 1, 86, 401, 482, 1, 4469, 1, 8435, 47959, 8082, 1, 1007342, 52414, 112835, 15338453, 11899367, 1, 362657533, 1, 977129970, 9349593479, 35787684, 1771297657, 390347162497, 1, 779945988, 9360467497257, 16838238535445

Offset: 0

Gus Wiseman, Jun 20 2018

nonn

A hypergraph is uniform if all edges have the same size. The weight of a hypergraph is the sum of cardinalities of the edges. Weight is generally not the same as number of vertices.

			Non-isomorphic representatives of the a(8) = 9 uniform connected hypergraphs:
  {{1,2,3,4,5,6,7,8}}
  {{1,2,3,7}, {4,5,6,7}}
  {{1,2,5,6}, {3,4,5,6}}
  {{1,3,4,5}, {2,3,4,5}}
  {{1,2}, {1,3}, {2,4}, {3,4}}
  {{1,3}, {2,4}, {3,5}, {4,5}}
  {{1,4}, {2,3}, {2,4}, {3,4}}
  {{1,4}, {2,5}, {3,5}, {4,5}}
  {{1,5}, {2,5}, {3,5}, {4,5}}

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

Cf. A000005, A007716, A038041, A038041, A048143, A299353, A301481, A301920, A301924, A306019, A306021, A331508.

\\ See A331508 for T(n, k).
InvEulerT(v)={my(p=log(1+x*Ser(v))); dirdiv(vector(#v,n,polcoef(p,n)), vector(#v,n,1/n))}
a(n) = {if(n==0, 1, sumdiv(n, d, if(d==1 || d==n, d==1, InvEulerT(vector(d, i, T(n/d, i)))[d] )))} \\ Andrew Howroyd, Jan 16 2024

a(p) = 1 for prime p. - Andrew Howroyd, Jan 16 2024

a(11) onwards from Andrew Howroyd, Jan 16 2024

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

A331461 Array read by antidiagonals: A(n,k) is the number of nonequivalent binary matrices with k columns and any number of nonzero rows with n ones in every column up to permutation of rows and columns.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula

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

A058790 Number of covers of an unlabeled n-set such that every point of the set is covered by exactly 3 subsets of the cover and that intersection of every 3 subsets of the cover contains at most one point.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Extensions

A331510 Array read by antidiagonals: A(n,k) is the number of nonequivalent binary matrices with k columns and any number of distinct nonzero rows with n ones in every column up to permutation of rows and columns.

Views

Author

Keywords

Examples

Crossrefs

Formula

Extensions

A331509 Array read by antidiagonals: A(n,k) is the number of nonisomorphic T_0 n-regular set-systems on a k-set.

Views

Author

Keywords

Comments

Examples

Crossrefs

A058791 Number of covers of an unlabeled n-set such that every point of the set is covered by exactly 4 subsets of the cover and that intersection of every 4 subsets of the cover contains at most one point.

Views

Author

Keywords

Comments

Links

Crossrefs

Extensions

A058792 Number of covers of an unlabeled n-set such that every point of the set is covered by exactly 5 subsets of the cover and that intersection of every 5 subsets of the cover contains at most one point.

Views

Author

Keywords

Comments

Links

Crossrefs

Extensions

A058793 Number of covers of an unlabeled n-set such that every point of the set is covered by exactly 6 subsets of the cover and that intersection of every 6 subsets of the cover contains at most one point.

Views

Author

Keywords