Number of ways to keep two decks of cards in front of each other with no matching cards facing each other.

Question

A deck of 52 cards are placed face up in a row. We have another similar deck with 52 cards. In how many ways can we place the cards in this new deck in front of the row of 52 cards such that

1. there is exactly one card in front of each card of the row, and,
2. no two similar cards are in front of each other (so, ace of spades cannot be kept in front of ace of spades)?

---

My attempt

I attempted this question with a smaller deck consisting of 4 identical cards in each deck. Each deck contains cards numbered 1,2,3 and 4. The cards of the first deck are laid down in a row in increasing order ( card 1 is the first card followed by card 2 and so on).

Now, when we open the second deck, then at the first position, there are 3 possibilities to place a card( cards 2,3 and 4). At the second position, there are 2 cases.

Case1: If card 2 from the new deck is placed at the first position, then we can have cards 1,3 or 4 in the second position. Thus, case 1 gives us 3 permutations for the first 2 positions

Case 2: Card 3 or 4 is placed from the new deck in front of the first position. In this case, if card 3 is placed at the first position then we can place 1 or 4 at the second position. If card 4 is placed at the first position then we can place cards 1 or 3 at the second position. Thus, case 2 gives us 2*2=4 permutations for placing the first 2 cards from the new deck.

Total possible permutations for the cards from the new deck for the first 2 positions= case 1+case2 = 7

I then calculate all the permutations for the first 3 positions followed by all the permutations for all the 4 positions. While this mechanical approach can give me the answer for 4 cards, it will be tough to do so for 52 cards. Also, I am looking for a more elegant approach than mechanically calculating all the permutations recursively.

Answer 1

Yes you are working through it correctly but as you said, you cannot work this manually for large numbers. As you saw the comments above, this is a standard derangement question. For $4$ cards, it is $\frac {4!}{2!} - \frac {4!}{3!} + \frac {4!}{4!} = 9$.

You first find number of ways to get at least one card in the right place using P.I.E and then subtract from total number of permutations which is $4!$.

If you choose one card that has to be put in right place, the rest $3$ can be in whichever place. Also, you can choose any of the cards to be in the right place.

So number of ways $= \, ^4C_1 \times 3!$

Now this will have duplicates. For example when you choose card $1$ to be its correct place and do all permutations of the rest $3$, card $2$ will be in the right place in some permutation. When you choose card $2$ to be in its correct place and do permutations of $1, 3, 4$, there will be permutation when the previous case will repeat. So, applying PIE you get to -

$= \, ^4C_1 \times 3! - \, ^4C_2 \times 2! + \, ^4C_3 \times 1! - \, ^4C_4 \times 0!= 15$

Total number of permutations $= 4! = 24$. You subtract all cases where at least one card is in its right place then you get $9$ which is the answer you are looking for.

Now here is the formula for derangement of $n$ objects (represented as $!n$).

$!n = n! \sum \limits_{i=0}^n \frac{(-1)^i}{i!}$

In your case, it is $!52 = 52! \sum \limits_{i=0}^{52} \frac{(-1)^i}{i!}$. You can put this expression in WolframAlpha to get the value. It will more than one third of $52!$.

Please read wiki page https://en.wikipedia.org/wiki/Derangement for details.