How many ways we can find out the strip of N spins contains m "Parallel Pair" out of which m1 of them are "Up Parallel Pair"?

Question

Let us consider a one-dimensional strip containing 8 spins. Spins can be up or down. And spins can be arranged randomly. So the total number of different microstates possible is $2^8$ (Taking Periodic Boundary condition i.e the last spin interacts with the 1st one). One microstate looks like something as: Random Microstate. In the picture the blue spins are called up spins and the red ones are down spins. Now we call two consecutive spins as a pair. If the two consecutive spins have the same direction we call it as "Parallel Pair". Again if a "Parallel Pair" contains both the spins up we call it as "Up Parallel Pair". So one "Up parallel Pair" is $\uparrow \uparrow$ and one "Down Parallel Pair" is $\downarrow \downarrow$.

So how many ways we can find out the strip of 8 spins contains 4 "Parallel Pair" out of which 2 of them are "Up Parallel Pair"?

Can you generalize the problem as: How many ways we can find out the strip of N spins contains m "Parallel Pair" out of which m1 of them are "Up Parallel Pair"?

I have computationally found out that if we denote the number of ways (finding out the strip of N spins contains m "Parallel Pair" out of which m1 of them are "Up Parallel Pair") as $C_{m,m1}^N$ then for N=8 we have the following values. Click on the link.For N=8, all coefficient values (the number of ways)

Answer 1

Let $u(n,k,m)$ be the number of strings of $n$ spins ("microstates"), starting with an "up" spin, that have exactly $k$ "up parallel pairs" and $m$ "down parallel pairs". Define $d(n,k,m)$ to be the number of strings of $n$ spins ("microstates"), starting with a "down" spin, that have exactly $k$ "up parallel pairs" and $m$ "down parallel pairs". So the number we seek is $u(8,2,2) + d(8,2,2)$.

First, note that $u(n,k,m) = d(n,m,k)$. Take any microstate of length $n$ starting with "up" with $k$ up parallel pairs and $m$ down parallel pairs, and flip every state. The result is a microstate starting with "down" and having $k$ down parallel pairs and $m$ up parallel pairs. This process reverses showing the equality. Hence the number we seek is $2 u(8,2,2)$.

Let's note some obvious properties of $u(n,k,m)$. Clearly if $k+m > n-1$, then $u(n,k,m) = 0$, since the string on $n$ states contains only $n-1$ possible parallel pairs. Moreover, if $k+m = n-1$, $u(n,k,m) = 0$ unless $k=n-1$ and $m=0$, in which case the microstate consists of $n$ up spins, and all pairs are up parallel pairs. Finally, for convenience we will define $u(n,k,m) = 0$ if $k<0$ or $m<0$.

So suppose $0 \le k < n-1$, $0 \le m$ and $k+m < n-1$. Every microstate of length $n$, starting with an "up" spin and having $k$ up parallel pairs and $m$ down parallel pairs, must have at least one down spin (since $k < n-1$). Let's count the number of such microstates where the first down spin in the microstate occurs at position $f+1$, meaning $f$ can vary between $1$ and $n-1$.

If the first down spin is at position $f+1$, then the first $f$ spins are all ups, and we have $f-1$ up parallel pairs in the string already. The remaining $n-f$ spins in the microstate form a string with $n-f$ spins, starting with "down", containing $k-(f-1)$ up parallel pairs and $m$ down parallel pairs. There are $d(n-f,k-f+1,m)$ ways to pick such a string, or alternatively, $u(n-f,m,k-f+1)$. Hence, we have the following recurrence for $u(n,k,m)$: $$u(n,k,m) = \displaystyle \sum_{f=1}^{n-1} u(n-f,m,k-f+1)$$

Calculating out with the recurrence, we find that $u(8,2,2) = 9$, so the number of strings the OP requested is $18$. We can also use this terminology to state an "answer" to the more general problem, namely $u(N,m1,m-m1)+u(N,m-m1,m1)$.

I don't see an easy way to get a closed form for this, and I'm out of proofs for the day, but there are some interesting patterns in these numbers. Some searching on OEIS suggests that $u(n,k,0) = {{\left\lfloor\frac{n-1+k}{2}\right\rfloor}\choose{k}}$ (see http://oeis.org/A046854).

There are also some interesting patterns on the diagonals for fixed $k+m$. Examples:

• $k+m=n-2$: $u(n,k,n-2-k) = 1$ for $0 \le k \le n-2$. This one isn't that hard to see...there can only be one transition from up to down, so the microstate has to be $k+1$ ups followed by $n-k-1$ downs.
• $k+m = n-3$: $u(n,k,n-3-k) = k+1$ for $0 \le k \le n-3$.
• $k+m = n-4$: Seems to yield the sequence at http://oeis.org/A003991

ADDENDUM: Details on the calculation of $u(8,2,2)$

For small $n$, we can simply enumerate strings to find these are the only non-zero values for $u(n,k,m)$ for $n \le 4$:

• $u(1,0,0) = 1$
• $u(2,0,0) = 1$, $u(2,1,0) = 1$
• $u(3,0,0) = 1$, $u(3,1,0) = 1$, $u(3,2,0) = 1$, and $u(3,0,1) = 1$
• $u(4,0,0) = 1$, $u(4,1,0) = 2$, $u(4,2,0) = 1$, $u(4,3,0) = 1$, $u(4,0,1) =1$, $u(4,1,1) = 1$, and $u(4,0,2)=1$

To calculate $u(8,2,2)$ via recursion, we have $$\begin{eqnarray*} u(8,2,2) &=& u(7,2,2) + u(6,2,1) + u(5,2,0) \\ &=& u(6,2,2) + u(5,2,1) + u(4,2,0) + \\ && u(5,1,2) + u(4,1,1) + u(3,1,0) + \\ && u(4,0,2) + u(3,0,1) + u(2,0,0)\\ &=& u(6,2,2) + u(5,2,1) + u(5,1,2) + 6 \end{eqnarray*}$$

Using the recursion again gives us: $$\begin{eqnarray*} u(8,2,2) &=& u(5,2,2) + u(4,2,1) + u(3,2,0) +\\ && u(4,1,2) + u(3,1,1) + u(2,1,0) +\\ && u(4,2,1) + u(3,2,0) +6\\ &=& u(5,2,2) + 9\\ &=& u(4,2,2) + u(3,2,1) + u(2,2,0) + 9\\ &=& 9 \end{eqnarray*} $$