Suppose you have four letters $a,b,c,d$ . the number of $a,b,c,d$ are $n_1,n_2,n_3,n_4$ respectively. you have $n_1+n_2+n_3+n_4$ spaces. How many combinations are possible such that $a$ is not adjacent to $b$ and $c$ is not adjacent to $d$?
I tried arranging a and d first which gives me $(n_1+n_2)!\div(n_1!\times n_2!)$. this leaves me with $n_1+n_2+1$ spaces but i can't seem to find the way in which to arrange b and c such that no bad case is formed.
Looking at other StackExchange questions about permutations with restrictions on adjacent elements, I'm not convinced that there is a closed solution for this. I don't have any proof, it just seems that way from other posts. Most solutions provide a computer algorithm for generating and counting solutions, so that is what I have done below. Essentially, it just builds sequences along the restriction of the question. While I know that it is not as efficient as it probably could be, it will do just find for checking your possible solutions for smaller numbers. Below is some of the output as well.
$$n1,n2,n3,n4\rightarrow\text{total solutions}$$
$$1,1,1,1\rightarrow 8$$ $$2,1,1,1\rightarrow 14$$ $$2,2,1,1\rightarrow 20$$ $$3,1,1,1\rightarrow 20$$ $$2,1,2,1\rightarrow 38$$ $$2,2,2,1\rightarrow 80$$ $$2,2,2,2\rightarrow 248$$
def arrange(n1, n2, n3, n4, seq=""):
total = 0
if any(n < 0 for n in [n1, n2, n3, n4]):
#used one too many characters
return 0
elif n1 + n2 + n3 + n4 == 0:
#all out of characters, this is a working solution
#print seq
return 1
elif n1 + n2 == 0 and (n3 != 0 and n4 != 0):
#All we have left are c and d, no valid solutions
return 0
elif n3 + n4 == 0 and (n1 != 0 and n2 != 0):
#All we have left are a and b, no valid solutions
return 0
elif len(seq) == 0:
#first case
total += arrange(n1-1,n2,n3,n4, "a")
total += arrange(n1,n2-1,n3,n4, "b")
total += arrange(n1,n2,n3-1,n4, "c")
total += arrange(n1,n2,n3,n4-1, "d")
else:
if seq[-1] == 'a':
total += arrange(n1-1,n2,n3,n4, seq + "a")
total += arrange(n1,n2,n3-1,n4, seq + "c")
total += arrange(n1,n2,n3,n4-1, seq + "d")
elif seq[-1] == 'b':
total += arrange(n1,n2-1,n3,n4, seq + "b")
total += arrange(n1,n2,n3-1,n4, seq + "c")
total += arrange(n1,n2,n3,n4-1, seq + "d")
elif seq[-1] == 'c':
total += arrange(n1-1,n2,n3,n4, seq + "a")
total += arrange(n1,n2-1,n3,n4, seq + "b")
total += arrange(n1,n2,n3-1,n4, seq + "c")
elif seq[-1] == 'd':
total += arrange(n1-1,n2,n3,n4, seq + "a")
total += arrange(n1,n2-1,n3,n4, seq + "b")
total += arrange(n1,n2,n3,n4-1, seq + "d")
return total
