3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ what did you try so far? any progress? $\endgroup$ – wonko Jun 12 '17 at 12:38
  • $\begingroup$ 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? $\endgroup$ – 5xum Jun 12 '17 at 12:39
  • $\begingroup$ 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. $\endgroup$ – 5xum Jun 12 '17 at 12:39
  • $\begingroup$ @5xum: I believe OP has shown what he tried and where he got stuck afterwards $\endgroup$ – true blue anil Jun 13 '17 at 11:52
  • $\begingroup$ 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. $\endgroup$ – samerivertwice Jun 13 '17 at 14:49
1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.