Number of ways to cover half of a grid by an orthogonally connected region

Question

Suppose that we have a grid of size $2n$ by $2n$, with $4n^2$ cells in total. How many ways are there to label each cell in the grid using two labels, say zero and one, such that all ones are orthogonally connected and exactly half of the grid contains ones?

For example, there are four ways to label the grid if $n=1$:

1 1 | 0 0 | 1 0 | 0 1
0 0 | 1 1 | 1 0 | 0 1

Brute force search suggests that there are $1474$ ways to label the grid when $n=2$, here are some examples:

1 1 1 1 | 0 0 1 1 | 1 1 1 1
1 1 1 1 | 0 0 1 1 | 0 1 0 0
0 0 0 0 | 0 0 1 1 | 0 1 0 0
0 0 0 0 | 0 0 1 1 | 1 1 0 0

To clarify, this is what I mean by "orthogonally connected". Let $A$ be a $2n$ by $2n$ matrix representing the grid, let $V = \lbrace (i, j) : A[i,j] = 1 \rbrace$ denote the positions of ones and let $E = \lbrace ((i_1, j_1), (i_2, j_2)) \in V \times V: (i_1, j_1) \in \lbrace (i_2 + 1, j_2), (i_2 - 1, j_2), (i_2, j_2 + 1), (i_2, j_2 - 1) \rbrace \rbrace$. All ones are orthogonally connected whenever the graph $(V, E)$ is connected.

In the examples above, ones are orthogonally connected.

In the following examples, ones are not orthogonally connected.

1 0 0 1 | 1 0 0 0
1 0 0 1 | 0 1 0 1
1 0 0 1 | 0 0 1 0
1 0 0 1 | 1 1 1 1

For reference, here is the python code I used to compute the number 1474. It iterates over $2^{(4n^2)}$ possible ways to fill the grid, and uses scipy.ndimage to detect orthgonally connected components. In the problem, I only consider cases where k is even.

import numpy as np
from scipy.ndimage import label

def count_solutions(k, print_patterns=False):
  count = 0
  k2 = k * k
  for i in range(2**k2):
    arr = np.array([int(x) for x in np.binary_repr(i).zfill(k2)]).reshape(k, k)
    if label(arr)[1] == 1 and arr.sum() == k2 // 2:
      if print_patterns: print(arr)
      count += 1
  return count

Answer 1

(Here I'm assuming an $n\times n$ grid rather than $2n\times 2n$, to more easily talk about odd-sized grids.)

I've written a program to compute a few more of these numbers (source code below). Using dynamic programming, it is possible to compute the answer in $O(n! 2^{n})$ time, which is a bit better than the $O(2^{n^2})$ naive enumeration. The basic idea is to work one row of the grid at a time: the possible states of each row can be encoded by (1) whether each entry of the row is a $0$ or a $1$; (2) one color for each of the $1$s, where two $1$s have the same color if they are connected by an orthogonal path of $1$s contained in rows $1\leq j \leq i$.

The number of valid ways to fill the grid is thus the number of ways to fill $j$ rows ($j \leq n$) with $n^2/2$ ones that all have the same color in the final row.

• $n=2$: $4$
• $n=4$: $1474$
• $n=6$: $71969832$
• $n=8$: $528144170884375$

I'm not seeing any patterns and the sequence is not in OEIS, so I'm rather pessimistic there's a nice closed form.

Here are some numbers for $n$ odd, if we requires $\lfloor n^2/2\rfloor$ ones:

• $n = 1$: $1$
• $n = 3$: $36$
• $n = 5$: $136217$
• $n = 7$: $78614780347$

Source code:

#include <iostream>
#include <vector>
#include <map>

struct UnionFind
{
    UnionFind(int n)
    {
        parent.resize(n);
        for (int i = 0; i < n; i++)
            parent[i] = i;
    }

    int find(int i)
    {
        int p = parent[i];
        if (parent[p] != p)
        {
            p = find(p);
            parent[i] = p;
        }
        return p;
    }

    void takeUnion(int a, int b)
    {
        parent[find(a)] = find(b);
    }

    std::vector<int> parent;
};

struct Row
{
    std::vector<int> groups;
    int64_t totalones;

    bool operator<(const Row& other) const
    {
        if (totalones < other.totalones)
            return true;
        if (totalones > other.totalones)
            return false;
        int n = groups.size();
        for (int i = 0; i < n; i++)
        {
            if (groups[i] < other.groups[i])
                return true;
            if (groups[i] > other.groups[i])
                return false;
        }
        return false;
    }
};

Row buildTopRow(uint64_t top, int n)
{
    Row result;
    result.groups.resize(n);
    result.totalones = 0;
    bool prevset = false;
    int curgroup = 1;
    for (int i = 0; i < n; i++)
    {
        bool curset = top & (1ULL << i);
        if(!curset)
        { 
            if (prevset)
            {
                curgroup++;
            }
            result.groups[i] = 0;
        }
        else
        {
            result.groups[i] = curgroup;
            result.totalones++;
        }
        prevset = curset;
    }

    return result;
}

bool stitch(const Row& top, uint64_t bottom, Row &result)
{
    int n = top.groups.size();

    result.totalones = top.totalones;
    result.groups.resize(n);

    UnionFind uf(2*n);

    bool prevset = false;
    int curgroup = 0;
    for (int i = 0; i < n; i++)
    {
        bool curset = bottom & (1ULL << i);
        if (!curset)
        {
            result.groups[i] = 0;
        }
        else
        {
            if (prevset)
            {
                int nextgroup = top.groups[i];
                if (nextgroup != 0)
                {
                    uf.takeUnion(curgroup, nextgroup);
                }                
            }
            else
            {
                int nextgroup = top.groups[i];
                if (nextgroup != 0)
                {
                    curgroup = nextgroup;
                }
                else
                {
                    curgroup = n + i;
                }
            }

            result.groups[i] = curgroup;
            result.totalones++;
        }

        prevset = curset;
    }

    std::map<int, int> relabeling;
    int curidx = 1;

    for (int i = 0; i < n; i++)
    {
        if (result.groups[i] != 0)
        {
            int canonical = uf.find(result.groups[i]);
            auto it = relabeling.find(canonical);
            if (it == relabeling.end())
            {
                relabeling[canonical] = curidx++;
            }
            result.groups[i] = relabeling[canonical];
        }
    }

    // check if we've irrecoverably disconnected the 1s

    for (int i = 0; i < n; i++)
    {
        if (top.groups[i] != 0)
        {
            auto it = relabeling.find(uf.find(top.groups[i]));
            if (it == relabeling.end())
                return false;
        }
    }

    return true;
}

void doCase(int n)
{
    std::map<Row, int64_t> ways;
    uint64_t options = (1ULL << n);
    for (uint64_t way = 0; way < options; way++)
    {
        ways[buildTopRow(way, n)] = 1;
    }

    int64_t answer = 0;

    for (int row = 0; row < n - 1; row++)
    {
        std::map<Row, int64_t> nextways;
        for (auto& w : ways)
        {
            for (uint64_t way = 0; way < options; way++)
            {
                Row nextrow;
                if (stitch(w.first, way, nextrow))
                {
                    nextways[nextrow] += w.second;
                }
            }

            // are we done?
            if (w.first.totalones == n * n / 2)
            {
                bool ok = true;
                for (int i = 0; i < n; i++)
                {
                    if (w.first.groups[i] > 1)
                        ok = false;
                }
                if (ok)
                {
                    answer += w.second;
                }
            }
        }    
        ways = nextways;
    }

    for (auto it : ways)
    {
        if (it.first.totalones != n * n / 2)
            continue;
        bool ok = true;
        for (int i = 0; i < n; i++)
        {
            if (it.first.groups[i] > 1)
                ok = false;
        }
        if (ok)
        {
            answer += it.second;
        }
    }
    std::cout << n << ": " << answer << std::endl;
}


int main()
{
    for (int i = 2; i <= 62; i += 2)
    {
        doCase(i);
    }
}
```