# Homework Help: Forming pairs problem

1. Jun 14, 2010

### dsfranca

1. The problem statement, all variables and given/known data

Suppose we have two decks with n distinct cards each. After we shuffle the decks, what is the probability that k cards are in the same position in the two decks?

2. Relevant equations

3. The attempt at a solution
I have worked out that when n tends to infinity, the probability that 0 cards are in the same position is 1/e but I am having a lot of difficulties with the combinatorics aspect of the problem. Hope you guys could help me with that!
Thanks!

2. Jun 14, 2010

### lanedance

3. Jun 14, 2010

### lanedance

and maybe even one deck - always helps me to start simple, then generalise from there

4. Jun 14, 2010

### lanedance

you'll also have to decide if k cards means "only k cards" or "at least k cards"

5. Jun 14, 2010

### dsfranca

Thanks for the answer lanedance. First of all, the answer I am looking for is only k, and I dont see how this problem would make sense with only one deck, as the most important aspect of it are two cards in the same position.... I am still stuck....

6. Jun 14, 2010

### njama

Let's say there are 4 cards, we are looking for 3 cards.

positions:
1 2 3 4
1st deck.
1 2 3 4
1 2 4 3
1 3 2 4
1 3 4 2
1 4 2 3
1 4 3 2
2 1 3 4
2 1 4 3
2 3 1 4
2 3 4 1
2 4 1 3
2 4 3 1
3 1 2 4
3 1 4 2
3 2 1 4
3 2 4 1
4 1 2 3
4 1 3 2
4 2 1 3
4 2 3 1

So if you shuffle the deck so that the cards are in this order:

2 1 3 4

Then for 2 cards to be same you need:

2 1 3 4
2 1 4 3
2 4 3 1
2 3 1 4
4 1 3 2
3 1 2 4
1 2 3 4

total of 7. so the probability is 7/16

To get the things much clear. Let's say there are 5 cards. You need two cards two match:

2 1 3 4 5

2 1 . . . 3*2*1
2 . 3 . . 2*2+2*2
2 . . 4 . 2*2+1
2 . . . 5 1+1

. 1 3 . . 2*2+2*2
. 1 . 4 . 2*2+1
. 1 . . 5 1+1

. . 3 4 . 2*2+1
. . 3 . 4 1+1

. . . 4 5 1+1
-------------
total: 1*(2*2+2*2+2*2) +2*(2*2+2*2)+3*(2*2+1)+4*(1+1)=45

So the probability is 45/5!

I hope you can follow this pattern and find a formula.

Regards.

Last edited: Jun 14, 2010