Number of Unbalanced Incomplete Block Design

Question

I'm studying the combinatorial design theory related to graph theory. While studying, I met a problem related to block design, but not BIBD.

I have to find the number of possible block designs with its parameter $v=2n$ and $r=k=n$, where $v$ denotes the number of elements, $r$ denotes the number of blocks containing each element and $k$ denotes the size of a block. The problem comes from that this design is not balanced since it does not satisfy the equality $\lambda(v-1)=r(k-1)$.

Actually, this is same as coloring an $2n \times 2n$ grid with two colors, where each row and column are colored exactly half and half.

Is there any way to approach this problem? Any comment or idea is fine to me.

Answer 1

Here are the numbers for $n=1,2,3,4,$ computed by brute-force search, taking advantage of all the symmetry I could think of.

$$\begin{array}{r|r} n & f(n)\\ \hline 1 &2\\ \hline 2 &90\\ \hline 3&297,200\\ \hline 4&116,963,796,250\\ \hline \end{array}$$

I did this in python, and it might be possible to extend to $n=5$ by switching to a systems programming language and taking advantage of multicore, but I doubt it's worth the trouble.

from itertools import combinations
from collections import defaultdict, Counter
from math import factorial
from functools import reduce

def product(seq):
    return reduce(lambda x,y: x*y, seq, 1)

def multinomial(seq):
    n = sum(seq)
    return factorial(n) // product(factorial(k) for k in seq)

def designs(n):
    if n == 1: 
        return 2
    possible = list(combinations(range(1,2*n+1), n))
    counts = { }
    rows = { }
    counts[1] = defaultdict(int)
    available = { }
    level = 1
    rows[level] = possible[-1]
    for r in rows[level]:
        counts[level][r] += 1
    answers = 0
    level = 2
    available[level] = possible[:]
    while level > 1:
        while available[level]:
            counts[level] = counts[level-1].copy()
            rows[level] = available[level][-1]
            for r in rows[level]:
                counts[level][r] += 1
            if level == 2*n:
                vals = (rows[i] for i in range(2,2*n+1))
                uniq = Counter(vals)
                answers += multinomial(uniq.values())
            cnt = counts[level]
            available[level+1] = [p for p in available[level] if
                                  max(cnt[a] for a in p) < n]
            available[level].pop()
            level += 1
        level -= 1
    return len(possible) * answers

for n in range(2,5):
    print(n,designs(n))

The code fixes the first row, and multiplies the answer by ${2n\choose n}.$ It generates only the solutions with the rows in reverse lexicographical order. For each such solution, it calculates the permutations of the rows other than the first, taking account of repetitions.