1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Do you need an exact answer, or will an approximation of some sort do? $\endgroup$ – saulspatz Jul 12 at 15:25
  • $\begingroup$ An exact answer is the best, but an approximation will be also appreciated. $\endgroup$ – SeokBeom Kim Jul 12 at 23:19
0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thanks for your effort. Will it be possible to share your python code for me? $\endgroup$ – SeokBeom Kim Jul 13 at 8:03
  • $\begingroup$ @SeokBeomKim Sure, glad to. $\endgroup$ – saulspatz Jul 13 at 12:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.