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

%I #15 Jan 25 2020 17:54:45

%S 1,1,1,0,1,1,0,1,0,1,0,1,1,0,1,0,1,5,0,0,1,0,1,43,5,0,0,1,0,1,518,175,

%T 1,0,0,1,0,1,8186,9426,272,0,0,0,1,0,1,163356,751365,64453,205,0,0,0,

%U 1,0,1,3988342,84012191,23553340,248685,80,0,0,0,1

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

%C An n-regular set-system is a finite set of nonempty sets in which each element appears in n blocks.

%C A set-system is T_0 if for every two distinct elements there exists a block containing one but not the other element.

%C A(n,k) is the number of binary matrices with k distinct columns and any number of distinct nonzero rows with n ones in every column and rows in decreasing lexicographic order.

%H Andrew Howroyd, <a href="/A331039/b331039.txt">Table of n, a(n) for n = 0..209</a>

%F A(n, k) = Sum_{j=1..k} Stirling1(k, j)*A188445(n, j) for n, k >= 1.

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

%F A331654(n) = Sum_{d|n} A(n/d, d).

%e Array begins:

%e ==========================================================

%e n\k | 0 1 2 3 4 5 6 7

%e ----+-----------------------------------------------------

%e 0 | 1 1 0 0 0 0 0 0 ...

%e 1 | 1 1 1 1 1 1 1 1 ...

%e 2 | 1 0 1 5 43 518 8186 163356 ...

%e 3 | 1 0 0 5 175 9426 751365 84012191 ...

%e 4 | 1 0 0 1 272 64453 23553340 13241130441 ...

%e 5 | 1 0 0 0 205 248685 421934358 1176014951129 ...

%e 6 | 1 0 0 0 80 620548 5055634889 69754280936418 ...

%e 7 | 1 0 0 0 15 1057989 43402628681 2972156676325398 ...

%e ...

%e The A(2,3) = 5 matrices are:

%e [1 1 1] [1 1 0] [1 1 0] [1 0 1] [1 1 0]

%e [1 0 0] [1 0 1] [1 0 0] [1 0 0] [1 0 1]

%e [0 1 0] [0 1 0] [0 1 1] [0 1 1] [0 1 1]

%e [0 0 1] [0 0 1] [0 0 1] [0 1 0]

%e The corresponding set-systems are:

%e {{1,2,3}, {1}, {2}, {3}},

%e {{1,2}, {1,3}, {2,3}},

%e {{1,2}, {1,3}, {2}, {3}},

%e {{1,2}, {1}, {2,3}, {3}},

%e {{1,3}, {1}, {2,3}, {2}}.

%o (PARI)

%o WeighT(v)={Vec(exp(x*Ser(dirmul(v, vector(#v, n, (-1)^(n-1)/n))))-1, -#v)}

%o D(p, n, k)={my(v=vector(n)); for(i=1, #p, v[p[i]]++); binomial(WeighT(v)[n], k)*k!/prod(i=1, #v, i^v[i]*v[i]!)}

%o T(n, k)={my(m=n*k+1, q=Vec(exp(intformal(O(x^m) - x^n/(1-x)))/(1+x))); if(n==0, k<=1, (-1)^m*sum(j=0, m, my(s=0); forpart(p=j, s+=(-1)^#p*D(p, n, k), [1, n]); s*q[#q-j])/2)}

%Y Rows n=1..4 are A000012, A060053, A060070, A331655.

%Y Cf. A188445, A330942, A330964, A331126, A331160, A331161, A331569, A331654.

%K nonn,tabl

%O 0,18

%A _Andrew Howroyd_, Jan 08 2020