Displaying 1-10 of 12 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 n X n (0,1)-matrices with all rows distinct and all columns distinct.
+10
17
1, 2, 10, 264, 33864, 19158720, 44680224960, 413586858182400, 14960200449325582080, 2109063823453947981680640, 1162864344149083760773678387200, 2520991223487759548686737154649702400, 21598422878151131130336454273775859841843200, 734233037731110118818452425552296701963294284185600
FORMULA
a(n) = n! * Sum_{k=0..n} Stirling1(n, k)*binomial(2^k, n). - Vladeta Jovovic, Nov 07 2003 a(n) = Sum_{i=0..n} Sum_{j=0..n} stirling1(n, i) * stirling1(n, j) * 2^(i*j). - Max Alekseyev, Nov 07 2003
EXAMPLE
a(2) = 10: 00/01, 00/10, 01/00, 01/10, 01/11, 10/00, 10/01, 10/11, 11/01, 11/10.
MATHEMATICA
Table[n!*Sum[StirlingS1[n, k]*Binomial[2^k, n], {k, 0, n}], {n, 0, 15}] (* Vaclav Kotesovec, Jul 02 2016 *)
PROG
(Magma)
A088310:= func< n | Factorial(n)*(&+[Binomial(2^k, n)*StirlingFirst(n, k): k in [0..n]]) >;
(SageMath)
@CachedFunction
def A088310(n): return (-1)^n*factorial(n)*sum((-1)^k*binomial(2^k, n)*stirling_number1(n, k) for k in (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
EXTENSIONS
Suggested by Yuval Dekel (dekelyuval(AT)hotmail.com), Nov 06 2003
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
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.012 seconds
| 