antichains of fixed size

186 days ago by jrp

An ordered multisubset S of B(n) of size k can be encoded as a base 2^k string X with n digits. The ith digit of X encodes which of the k elements of S contain i.

For example if k=3 and the first digit of X is 011, then the first element of S does not contain 1, while the second and third do. So if k=3, n=4, then an example of a corresponding (S,X) pair is S = \{12,124,23\},X=(110,111,001,010).

To ensure that X corresponds to an antichain, we need that for each i,j \le k, some digit of X comes from A_{ij}, the witness set that S_i \le S_j does not hold. For example, if k=3 then A_{12} = \{100,101\} - the third digit is arbitrary here, but the 10 in positions 1 and 2 ensures that S_1 is not a subset of S_2.

After finding the sets A_{ij} we count the intersection with inclusion-exclusion. Remember to divide by k! since we are counting ordered antichains.
import itertools var('n') def As(k): output = [] for i,j in itertools.permutations(range(k),2): factors = [[0,1]]*k factors[i] = [0] factors[j] = [1] output.append(list(itertools.product(*factors))) return output def sizes(k): subsets = list(itertools.product([0,1],repeat=k)) ACs = [set(x for x in subsets if x not in a) for a in As(k)] m = len(ACs) output = [(2**k)**n] for i in range(1,m+1): for x in itertools.combinations(ACs,i): output.append(((-1)**i)*len(set.intersection(*x))**n) return sum(output) 
       
sizes(1) 
        
2^n
2^n
sizes(2) 
        
2^n - 2*3^n + 4^n
2^n - 2*3^n + 4^n
sizes(3) 
        
2*2^n - 6*3^n + 3*4^n + 6*5^n - 6*6^n + 8^n
2*2^n - 6*3^n + 3*4^n + 6*5^n - 6*6^n + 8^n
sizes(4) 
        
6*2^n - 22*3^n + 11*4^n + 36*5^n - 36*6^n + 6*7^n - 18*8^n + 4*9^n +
24*10^n - 12*12^n + 16^n
6*2^n - 22*3^n + 11*4^n + 36*5^n - 36*6^n + 6*7^n - 18*8^n + 4*9^n + 24*10^n - 12*12^n + 16^n