Number of ways to sit in a 2XN grid

Question

I had this question in an interview but I was not able to solve it.

We have a grid of 2 rows and n columns. We have to find the number of ways to sit M men and W women given no men can sit adjacent or in front of each other.

I thought of solving it by Dynamic Programming but I'm not sure how to get the recurrence relation.

I know that if I am at (0,i), I can go to (1,i+1) but I don't know how to keep track of counts of men and women so far. Can anybody help me with the recurrence relation or states of dp?

Answer 1

Recurrence relation

Here is one recurrence relation I could thing of.

Let's call n_ways(N, W, M, k) the number of ways to seat:

• W women
• and M men
• in the remaining N columns
• knowing there was k men in the previous column. k can only take values 0 and 1.

n_ways(N, 0, 0, k) = 1
n_ways(N, W, M, k) = 0 if M > N or W+M > 2*N
n_ways(N, W, 0, k) = ((2*N) choose W)
n_ways(N, 0, M, 0) = 2 * (N choose M)
n_ways(N, 0, M, 1) = (N choose M)

n_ways(N, W, M, 0)
    =     n_ways(N-1, W, M, 0)       // put nobody in first column
    + 2 * n_ways(N-1, W-1, M, 0)     // put 1 woman in first column
    +     n_ways(N-1, W-2, M, 0)     // put 2 women in first column
    + 2 * n_ways(N-1, W-1, M-1, 1)   // put 1 woman & 1 man in first column
    + 2 * n_ways(N-1, W, M-1, 1)     // put 1 man in first column

n_ways(N, W, M, 1)
    =     n_ways(N-1, W, M, 0)       // put nobody in first column
    + 2 * n_ways(N-1, W-1, M, 0)     // put 1 woman in first column
    +     n_ways(N-1, W-2, M, 0)     // put 2 women in first column
    +     n_ways(N-1, W-1, M-1, 1)   // put 1 woman & 1 man in first column
    +     n_ways(N-1, W, M-1, 1)     // put 1 man in first column

Testing with python

Since I'm too lazy to implement dynamic programming myself, I instead opted for caching using python's functools.cache.

I implemented the recurrence relation above as a cached recursive function, and got the following results:

Number of ways to seat w women and m men in n columns:
 n,  w,  m --> ways
 0,  0,  0 --> 1
 0,  0,  1 --> 0
 0,  1,  0 --> 0
 1,  2,  0 --> 1
 1,  0,  2 --> 0
 1,  1,  1 --> 2
 2,  2,  2 --> 2
 3,  3,  3 --> 2
 4,  6,  2 --> 18
10, 15,  5 --> 2364
10, 10, 10 --> 2

Here is the python code:

from functools import cache
from math import comb

@cache
def n_ways(n, w, m, k):
    if w == m == 0:
        return 1
    elif m > n or w + m > 2 * n:
        return 0
    elif m == 0:
        return comb(2*n, w)
    elif w == 0:
        return (2-k) * comb(n, m)
    else:
        r_0, r_w, r_ww, r_wm, r_m = (
            n_ways(n-1, w, m, 0),
            n_ways(n-1, w-1, m, 0),
            n_ways(n-1, w-2, m, 0) if w > 1 else 0,
            n_ways(n-1, w-1, m-1, 1),
            n_ways(n-1, w, m-1, 1)
        )
        return (r_0 + r_w + r_w + r_ww + r_wm + r_m) + (1-k) * (r_wm + r_m)

if __name__=='__main__':
    print(f'Number of ways to seat w women and m men in n columns:')
    print(f' n,  w,  m --> ways')
    for w, m in [(0, 0), (0, 1), (1, 0), (2, 0), (0, 2),
                 (1, 1), (2, 2), (3, 3), (6, 2), (15, 5),
                 (10, 10)]:
        n = (w + m) // 2
        print(f'{n:2d}, {w:2d}, {m:2d} --> ', end='')
        print(n_ways(n, w, m, 0))