Displaying 1-10 of 16 results found.
Number of zero-one matrices with n ones and no zero rows or columns and with distinct rows, up to permutation of rows.
+10
28
1, 1, 2, 7, 28, 134, 729, 4408, 29256, 210710, 1633107, 13528646, 119117240, 1109528752, 10889570768, 112226155225, 1210829041710, 13640416024410, 160069458445202, 1952602490538038, 24712910192430620, 323964329622503527, 4391974577299578248, 61488854148194151940
COMMENTS
Also the number of labeled hypergraphs spanning an initial interval of positive integers with edge-sizes summing to n. - Gus Wiseman, Dec 18 2018
EXAMPLE
The a(3) = 7 edge-sets:
{{1,2,3}}
{{1},{1,2}}
{{2},{1,2}}
{{1},{2,3}}
{{2},{1,3}}
{{3},{1,2}}
{{1},{2},{3}}
Inequivalent representatives of the a(4) = 28 0-1 matrices:
[1111]
.
[100][1000][010][0100][001][0010][0001][110][110][1100][101][1010][1001]
[111][0111][111][1011][111][1101][1110][101][011][0011][011][0101][0110]
.
[10][100][100][1000][100][100][1000][1000][010][010][0100][0100][0010]
[01][010][010][0100][001][001][0010][0001][001][001][0010][0001][0001]
[11][101][011][0011][110][011][0101][0110][110][101][1001][1010][1100]
.
[1000]
[0100]
[0010]
[0001]
(End)
MAPLE
b:= proc(n, i, k) b(n, i, k):=`if`(n=0, 1, `if`(i<1, 0, add(b(n-i*j,
min(n-i*j, i-1), k)*binomial(binomial(k, i), j), j=0..n/i)))
end:
a:= n-> add(add(b(n$2, i)*(-1)^(k-i)*binomial(k, i), i=0..k), k=0..n):
MATHEMATICA
b[n_, i_, k_] := b[n, i, k] = If[n == 0, 1, If[i < 1, 0, Sum[b[n - i*j, Min[n - i*j, i - 1], k]*Binomial[Binomial[k, i], j], {j, 0, n/i}]]];
a[n_] := Sum[Sum[b[n, n, i]*(-1)^(k-i)*Binomial[k, i], {i, 0, k}], {k, 0, n}];
CROSSREFS
Binary matrices with distinct rows and columns, various versions: A059202, A088309, A088310, A088616, A089673, A089674, A093466, A094000, A094223, A116532, A116539, A181230, A259763
Square array T(m,n) giving the number of m X n (0,1)-matrices with pairwise distinct rows and pairwise distinct columns.
+10
18
2, 2, 2, 0, 10, 0, 0, 24, 24, 0, 0, 24, 264, 24, 0, 0, 0, 1608, 1608, 0, 0, 0, 0, 6720, 33864, 6720, 0, 0, 0, 0, 20160, 483840, 483840, 20160, 0, 0, 0, 0, 40320, 5644800, 19158720, 5644800, 40320, 0, 0, 0, 0, 40320, 57415680, 595506240, 595506240, 57415680, 40320
COMMENTS
Table starts
.2..2.....0...........0...............0..................0
.2.10....24..........24...............0..................0
.0.24...264........1608............6720..............20160
.0.24..1608.......33864..........483840............5644800
.0..0..6720......483840........19158720..........595506240
.0..0.20160.....5644800.......595506240........44680224960
.0..0.40320....57415680.....16388749440......2881362718080
.0..0.40320...518676480....418910083200....172145618789760
.0..0.....0..4151347200..10136835072000...9841604944066560
.0..0.....0.29059430400.233811422208000.546156941728204800
FORMULA
T(m,n) = Sum_{i=0..n} Sum_{j=0..m} stirling1(n,i) * stirling1(m,j) * 2^(i*j) = n! * Sum_{j=0..m} stirling1(m,j) * binomial(2^j,n) = m! * Sum_{i=0..n} stirling1(n,i) * binomial(2^i,m). - Max Alekseyev, Jun 18 2016
CROSSREFS
Binary matrices with distinct rows and columns, various versions: A059202, A088309, A088310, A088616, A089673, A089674, A093466, A094000, A094223, A116532, A116539, A181230, A259763
Triangle T(n,m) of numbers of m-block T_0-covers of a labeled n-set, m = 0..2^n - 1.
+10
17
1, 0, 1, 0, 0, 3, 1, 0, 0, 3, 29, 35, 21, 7, 1, 0, 0, 0, 140, 1015, 2793, 4935, 6425, 6435, 5005, 3003, 1365, 455, 105, 15, 1, 0, 0, 0, 420, 13965, 126651, 661801, 2533135, 7792200, 20085000, 44307120, 84651840, 141113700, 206251500, 265182300
COMMENTS
A cover of a set is a T_0-cover if for every two distinct points of the set there exists a member (block) of the cover containing one but not the other point.
Also, T(n,m) is the number of n X m (0,1)-matrices with pairwise distinct nonzero columns and pairwise distinct nonzero rows, up to permutation of columns.
FORMULA
T(n, m) = (1/m!)*Sum_{1..m + 1} stirling1(m + 1, i)*[2^(i - 1) - 1]_n, where [k]_n := k*(k - 1)*...*(k - n + 1), [k]_0 = 1.
E.g.f: Sum((1+x)^(2^n-1)*log(1+y)^n/n!, n=0..infinity)/(1+y). - Vladeta Jovovic, May 19 2004
Also T(n, m) = Sum_{i=0..n} Stirling1(n+1, i+1)*binomial(2^i-1, m). - Vladeta Jovovic, Jun 04 2004
EXAMPLE
[1],
[0,1],
[0,0,3,1],
[0,0,3,29,35,21,7,1],
...
There are 35 4-block T_0-covers of a labeled 3-set.
MAPLE
with(combinat): for n from 0 to 10 do for m from 0 to 2^n-1 do printf(`%d, `, (1/m!)*sum(stirling1(m+1, i)*product(2^(i-1)-1-j, j=0..n-1), i=1..m+1)) od: od:
MATHEMATICA
T[n_, m_] = Sum[ StirlingS1[n + 1, i + 1]*Binomial[2^i - 1, m], {i, 0, n}]; Table[T[n, m], {n, 0, 5}, {m, 0, 2^n - 1}] (* G. C. Greubel, Dec 28 2016 *)
CROSSREFS
Binary matrices with distinct rows and columns, various versions: A059202, A088309, A088310, A088616, A089673, A089674, A093466, A094000, A094223, A116532, A116539, A181230, A259763
Number of singular n X n rational {0,1}-matrices with no zero rows or columns and with all rows distinct, up to permutation of rows.
+10
17
0, 0, 3, 285, 50820, 23551920, 31898503077, 134251404794199
CROSSREFS
Binary matrices with distinct rows and columns, various versions: A059202, A088309, A088310, A088616, A089673, A089674, A093466, A094000, A094223, A116532, A116539, A181230, A259763
Number of n X n (0,1)-matrices with no zero rows or columns and with all rows distinct and all columns distinct, up to permutation of rows.
+10
16
1, 1, 3, 29, 1015, 126651, 53354350, 74698954306, 350688201987402, 5624061753186933530, 314512139441575825493524, 62498777166571927258267336860, 44831219113504221199415663547412096
REFERENCES
G. Kilibarda and V. Jovovic, "Enumeration of some classes of T_0-hypergraphs", in
FORMULA
a(n) = Sum_{k=0..n+1} Stirling1(n+1, k)*binomial(2^(k-1)-1, n).
MATHEMATICA
f[n_] := Sum[ StirlingS1[n + 1, k] Binomial[2^(k - 1) - 1, n], {k, 0, n + 1}]; Table[ f[n], {n, 0, 12}] (* Robert G. Wilson v, Jun 01 2004 *)
PROG
(PARI) a(n) = sum(k=0, n+1, stirling(n+1, k, 1)*binomial(2^(k-1)-1, n)); \\ Michel Marcus, Dec 17 2022
CROSSREFS
Binary matrices with distinct rows and columns, various versions: A059202, A088309, A088310, A088616, A089673, A089674, A093466, A094000, A094223, A116532, A116539, A181230, A259763
Number of equivalence classes of n X n (0,1)-matrices with all rows distinct and all columns distinct.
+10
15
1, 2, 5, 44, 1411, 159656, 62055868, 82060884560, 371036717493194, 5812014504668066528, 320454239459072905856944, 63156145369562679089674952768, 45090502574837184532027563736271152, 117910805393665959622047902193019284914432, 1139353529410754170844431642119963019965901238144
COMMENTS
Two such matrices are equivalent if they differ just by a permutation of the rows.
FORMULA
a(n) = Sum_{k=0..n} Stirling1(n, k)*binomial(2^k, n). - Vladeta Jovovic, Nov 07 2003
EXAMPLE
a(2) = 5: 00/01, 00/10, 01/10, 01/11, 10/11.
MATHEMATICA
A088309[n_]:= A088309[n]=Sum[Binomial[2^j, n]*StirlingS1[n, j], {j, 0, n}];
PROG
(Magma)
A088309:= func< n | (&+[Binomial(2^k, n)*StirlingFirst(n, k): k in [0..n]]) >;
(SageMath)
@CachedFunction
def A088309(n): return (-1)^n*sum((-1)^k*binomial(2^k, n)*stirling_number1(n, k) for k in (0..n))
(PARI) a(n) = sum(k=0, n, stirling(n, k, 1)*binomial(2^k, n)); \\ Michel Marcus, Dec 16 2022
CROSSREFS
Binary matrices with distinct rows and columns, various versions: A059202, this sequence, A088310, A088616, A089673, A089674, A093466, A094000, A094223, A116532, A116539, A181230, A259763.
EXTENSIONS
Suggested by Yuval Dekel (dekelyuval(AT)hotmail.com), Nov 06 2003
Triangle read by rows: T[n,k] = number of n X n binary matrices with k=0...n^2 ones, distinct up to cyclic shifts of rows and columns; reflection through any vertical or horizontal axis; and reflection through the main diagonal. Also, quasi-n-ominoes on a torus divided into a k X k grid.
+10
14
1, 1, 1, 1, 2, 1, 1, 1, 1, 2, 4, 5, 5, 4, 2, 1, 1, 1, 1, 5, 10, 33, 53, 101, 122, 153, 122, 101, 53, 33, 10, 5, 1, 1, 1, 1, 5, 19, 88, 309, 975, 2537, 5637, 10510, 16740, 22734, 26500, 26500, 22734, 16740, 10510, 5637, 2537, 975, 309, 88, 19, 5, 1, 1
EXAMPLE
[1,1], [1,1,2,1,1], [1,1,2,4,5,5,4,2,1,1] (the last block giving the numbers of 3 X 3 binary matrices with k=0...9 ones, distinct up to the transformations listed above.
CROSSREFS
Binary matrices with distinct rows and columns, various versions: A059202, A088309, A088310, A088616, A089673, A089674, A093466, A094000, A094223, A116532, A116539, A181230, A259763
Number of symmetric n X n (0,1)-matrices with pairwise distinct rows and columns.
+10
14
1, 2, 6, 44, 716, 24416, 1680224, 229468288, 61820527104, 32848197477760, 34502874046006912, 71850629135663531776, 297429744309497638961920, 2452504520881914016303901696, 40340635076928240671195746599936, 1324981038432182976845483456362661888, 86953044949519288083916385603832568137728
FORMULA
a(n) = Sum_{k=0..n} Stirling1(n,k) * 2^(k*(k+1)/2).
MATHEMATICA
Table[Sum[StirlingS1[n, k]*2^Binomial[k+1, 2], {k, 0, n}], {n, 0, 20}] (* G. C. Greubel, Nov 04 2018*)
PROG
(PARI) A259763(n) = sum(k=1, n, stirling(n, k, 1) * 2^(k*(k+1)/2) );
(Magma) [(&+[StirlingFirst(n, k)*2^Binomial(k+1, 2): k in [0..n]]): n in [0..20]]; // G. C. Greubel, Nov 04 2018
CROSSREFS
Binary matrices with distinct rows and columns, various versions: A059202, A088309, A088310, A088616, A089673, A089674, A093466, A094000, A094223, A116532, A116539, A181230, A259763
Number of n-covers of a labeled n-set.
+10
13
1, 1, 3, 32, 1225, 155106, 63602770, 85538516963, 386246934638991, 6001601072676524540, 327951891446717800997416, 64149416776011080449232990868, 45546527789182522411309599498741023, 118653450898277491435912500458608964207578
COMMENTS
Also, number of n X n rational {0,1}-matrices with no zero rows or columns and with all rows distinct, up to permutation of rows.
FORMULA
a(n) = Sum_{k=0..n} (-1)^k*binomial(n, k)*binomial(2^(n-k)-1, n).
a(n) = (1/n!)*Sum_{k=0..n} Stirling1(n+1, k+1)*(2^k-1)^n.
EXAMPLE
Number of ways to choose n nonempty sets with union {1..n}. For example, the a(3) = 32 covers are:
{1}{2}{3} {1}{2}{13} {1}{2}{123} {1}{12}{123} {12}{13}{123}
{1}{2}{23} {1}{3}{123} {1}{13}{123} {12}{23}{123}
{1}{3}{12} {1}{12}{13} {1}{23}{123} {13}{23}{123}
{1}{3}{23} {1}{12}{23} {2}{12}{123}
{2}{3}{12} {1}{13}{23} {2}{13}{123}
{2}{3}{13} {2}{3}{123} {2}{23}{123}
{2}{12}{13} {3}{12}{123}
{2}{12}{23} {3}{13}{123}
{2}{13}{23} {3}{23}{123}
{3}{12}{13} {12}{13}{23}
{3}{12}{23}
{3}{13}{23}
(End)
MATHEMATICA
Join[{1}, Table[Sum[StirlingS1[n+1, k+1]*(2^k - 1)^n, {k, 0, n}]/n!, {n, 1, 15}]] (* Vaclav Kotesovec, Jun 04 2022 *)
Table[Length[Select[Subsets[Rest[Subsets[Range[n]]], {n}], Union@@#==Range[n]&]], {n, 0, 4}] (* Gus Wiseman, Dec 19 2023 *)
PROG
(PARI) a(n) = sum(k=0, n, (-1)^k*binomial(n, k)*binomial(2^(n-k)-1, n)) \\ Andrew Howroyd, Jan 20 2024
CROSSREFS
Covers with any number of edges are counted by A003465, unlabeled A055621.
Connected graphs of this type are counted by A057500, unlabeled A001429.
This is the covering case of A136556.
These set-systems have ranks A367917.
a(n) = number of n X n (0,1) matrices A such that the 2n vectors consisting of the rows and the columns of the matrix A are all distinct.
+10
13
CROSSREFS
Binary matrices with distinct rows and columns, various versions: A059202, A088309, A088310, A088616, A089673, A089674, A093466, A094000, A094223, A116532, A116539, A181230, A259763
AUTHOR
Yuval Dekel and Vladeta Jovovic, Nov 17 2003
EXTENSIONS
What if you also ask that the two main diagonals are also distinct? - N. J. A. Sloane, Jan 03 2004.
Search completed in 0.020 seconds
|