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

Question

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.

Answer 1

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

Answer 2

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.