# combinatorics and permutations of adjacency

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.

• what did you try so far? any progress? – wonko Jun 12 '17 at 12:38
• Hi and welcome to the site! Since this is a site that encourages and helps with learning, it is best if you show your own ideas and efforts in solving the question. Can you edit your question to add your thoughts and ideas about it? – 5xum Jun 12 '17 at 12:39
• Also, don't get discouraged by the downvote. I downvoted the question and voted to close it because at the moment, it is not up to site standards (you have shown no work you did on your own). If you edit your question so that you show what you tried and how far you got, I will not only remove the downvote, I will add an upvote. – 5xum Jun 12 '17 at 12:39
• @5xum: I believe OP has shown what he tried and where he got stuck afterwards – true blue anil Jun 13 '17 at 11:52
• I think a reasonable approach might be to start with the smallest $n$, lets say it's $n_1$ for arguments sake and you have at least $n_1$ of every letter. You can then arrange those. Then take the next smallest, lets say it's $n_2$. Now you have at least $n_2-n_1$ of the remaining $3$ letters which can be arranged around them and so on. – samerivertwice Jun 13 '17 at 14:49

$$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