# In how many ways can $n$ dogs and $k$ cats be arranged in a row so that no two cats are adjacent?

There are $$n$$ dogs and $$k$$ cats. In how many ways can we arrange them in a row so there are no $$2$$ cats are adjacent?

I thought about trying to calculate the number of possibilities without any constraints and subtract the number of ways we can arrange them so there is at least $$1$$ pair of adjacent cats.

Would like to understand how to approach this problem correctly (and if there are multiple ways I would love to hear them).

Edit: Sorry, I didn't make myself clear.

What I meant was that the cats and dogs are different(each dog is different than the other and so are the cats).

And the row doesn't have to start with dogs - the only requirement is that we can't have $$2$$ or more cats in a row.

But the other question (if the cats and dogs are the same) is good too. If you have more ways to solve in case they are indistinguishable I would love to read and understand it too.

So, basically this 1 question turned to two:

Case 1: the cats are indistinguishable and the dogs too.

Case 2: they are distinguishable.

And $$n$$ is large enough for it to be possible.

What is the minimal $$n$$? A bit confused.

If we start with a cat, then $$n=k-1$$ seems enough (cat first, cat last).

If we start with a dog, $$n=k$$. So in general we need $$n$$ at least $$k$$ to arrange them properly? Am I right?

Again sorry for the confusion!

Edit 2: My 2 questions were answered - thank you!

If you have any other ways to approach the problem or wish to add anything - please do, I would gladly read it!

In particular, if you know how to place the cats first and then the dogs, I would like to hear it.

• Is there any information given about $n$ and $k$? – Prakhar Nagpal Nov 16 '18 at 17:40
• Are the cats distinguishable? What about the dogs? – darij grinberg Nov 16 '18 at 18:00
• There are two slightly different questions here. It is possible for no two cats to be adjacent if the row begins or ends with a cat that is adjacent to a dog. On the other hand, if you stipulate that there must be a dog on each side of each cat, the row must begin and end with a dog. Which problem did you have in mind? – N. F. Taussig Nov 16 '18 at 18:33
• @darijgrinberg I am sure that, unless you have identical twins, you should be able to distinguish different cats and dogs. The problem does not say anything about the amount of time you are allowed to learn about the differences between the animals. – Batominovski Nov 16 '18 at 18:57

Okay now, to solve this, we need a couple of constraints, the minimum value of $$n$$ has to be $$n=k-1$$ if it is more then also it doesn't make a difference. Now, let us say we keep the $$n$$ dogs in a row with space between each one. So clearly there will be $$n+1$$ spaces, now these $$n+1$$ spaces have to be occupied by $$k$$ cats. Thus we get $$\binom {n+1}{k}$$ This is assuming that the cats are all identical as are the dogs.
If not, then we get, $$\binom {n+1}{k}\cdot n! \cdot k!$$ The reason this works is to let us say, take an example where $$k=5$$ and $$n=5$$. Now we put the $$5$$ dogs in a line with space between them. Then out of the $$6$$ spots between the dogs, we have to put $$5$$ cats and this can be done in $$\binom{6}{5}$$ ways. Now in these $$6$$ ways, we will all sorts of combinations, one where say the $$2$$nd spot is not occupied, another where the $$3$$rd is left empty. As you do this you will realize why this is such a great method. It allows all possible combinations of boys together and apart while ensuring that the condition is met.

• The minimum value of $n$ is $k-1$. You can have $C,D,C,D,\ldots,C,D,C$ for example. (Here, $C$ is a cat and $D$ is a dog.) – Batominovski Nov 16 '18 at 18:58
• Yes, you are right, I have changed that now. Thank you – Prakhar Nagpal Nov 16 '18 at 18:59
• Thanks for your answer. 1 thing I would like to clarify is why n=k-1 is the min. Am I correct: case 1:If we start with cats then k-1 dogs are enough to cover them. case2: If we start with dogs then k-1 dogs are not enough and here we need at least k dogs. And because of case 2 we need at least k dogs? – Johnny Nov 16 '18 at 19:01
• This method requires you to start with dogs and lets us say you have $5$ cats and $4$ dogs. Now you put the dogs and leave spaces between them, giving you $5$ spaces which means you have to put each cat in one space, the sequence will be $C,D,C,D,C,D,C,D,C$ using the formula we derived you get $\binom{5}{5}=1$ which is indeed true as there is only one way to arrange them. – Prakhar Nagpal Nov 16 '18 at 19:03
• I see. thanks a lot! Are there other ways to approach this problem? For example can I start with cats and then place the dogs? – Johnny Nov 16 '18 at 19:15

If $$n\leq k-1$$, then it is impossible to do so, as even with sitting them alternately, you will not have sufficient number of dogs to do so. However, if we assume that's not the case, then there are $$n+1$$ places around dogs to put the cats.

Assuming that the dogs and cats are indistinguishable respectively, then all we have to do is pick out $$k$$ places for the cats out of $$n+1$$. So number of ways to do that is

$$N = {{n+1}\choose k}$$

If we assume that the dogs are all different and so are the cats, we multiply the above with the number of permutations for cats and dogs respectively.

$$N = {{n+1}\choose k} * n! * k!$$

• Thanks for your answer. 1 thing I would like to clarify is why n=k is the min. Am I correct: case 1:If we start with cats then k-1 dogs are enough to cover them. case2: If we start with dogs then k-1 dogs are not enough and here we need at least k dogs. And because of case 2 we need at least k dogs? – Johnny Nov 16 '18 at 19:02
• Firstly, as you can see in my $1st$ line, minimum is not $k$, $k-1$ dogs are enough. Secondly, in your case $2$ also $k-1$ dogs will be enough because we consider all the alternate positions including both the ends which gives us $k$ places for the cats – Sauhard Sharma Nov 16 '18 at 19:11