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.