Number of ways to put $n_1$ from $A_1$ and $n_2$ from $A_2$ such that a maximum of $k_1$ and $k_2$ stand together.

Question

I have been stuck in this problem for a couple of days now. Suppose we have $n_1$ people from group $A_1$, and $n_2$ people from group $A_2$. We want to count the number of ways to place them in a row such that a maximum of $k_1$ from group $A_1$ stand consecutively and $k_2$ from group $A_2$ stand consecutively.

The way I am trying to think about it is that if we call some one from group $A_1$ as 1, and from group $A_2$ as 2, Then we are counting the number of sequences in the form:

$1^{x_1}2^{x_2}1^{x_3}2^{x_4}...$ with $x_{2k-1} \leq k1$ and $x_{2k} \leq k2$ and also with $x_1+x_3+...=n_1$, $x_2+x_4+...=n_2$. However, I am not sure how I should go around approaching this since I don't know how many of these $x_{2k-1}$ and $x_{2k}$ exist. In other words, I don't know how many variables to solve this equation for, it could have $1$, $2$, or up to $k_1/k_2$ variables.

Answer 1

So after suffering with this problem for a while, I came up with this solution:

We call a bit string of length $n$ valid if it follows the rules defined in the question (i.e. less than $k_1$ $1$s in a row and less than $k_2$ $2$s in a row)

Let $A_{(i,j,b)}$ represent the number of valid bit strings with length $i+j$ where we used $i$ from the $1$s and $j$ from the $2$s in total and with the right most bit (i.e. the $i+j$ bit) being the value $b$ ($b$ is either $1$ or $2$).

Then it follows that we have this recursion relation:

$A_{i,j,1}= \sum_{k=1}^{min(i,k_1)}{(A_{(i-k,j,2)})}$ and $A_{i,j,2}= \sum_{k=1}^{min(j,k_2)}{(A_{(i,j-k,1)})}$.

With the base condition being $A_{(0,0,1)}=A_{(0,0,2)}=1$.

Now all we need to do is to compute $A_{(n1,n2,1)}+A_{(n1,n2,2)}$. I could do the recursion manually, but I thought a code would be more efficient. Here is a C++ code that I wrote to do that. I tested it on multiple test data: for example $n_1=2,n_2=3,k_1=1,k_2=2$ And I got 5 which is the correct number of bitstrings that satisfy these conditions (They are 12122, 12212, 21212, 21221, 22121). I hope this helps someone!

#include <iostream>

using namespace std;

int A[110][110][3]={0}; //Initialize 3D array to all 0s
int main(){
    int n1,n2,k1,k2;
    scanf("%d %d %d %d",&n1,&n2,&k1,&k2); //Inputs n1,n2,k1,k2

    A[0][0][1]=A[0][0][2]=1; //Base cases
    for (int i=0; i<=n1;i++){
        for (int j=0; j<=n2; j++){
            if (i!=0 || j!=0)
            for (int k=1; k<=2; k++){
                if (k==1){
                    for (int z=1; z<=k1; z++){
                        if (i>=z)A[i][j][1]+=A[i-z][j][2];
                    }
                }
                else{
                    for (int z=1; z<=k2; z++){
                        if (j>=z)A[i][j][2]+=A[i][j-z][1];
                    }
                }
            }
        }
    }
    printf(A[n1][n2][1]+A[n1][n2][2]));
}