Solving the Forming Pairs Problem: A Combinatorics Approach | Homework Help

[dsfranca]

Homework Statement

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?

Homework Equations

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!

 

[lanedance]

i would start with k=1 first & see how you go

 

[lanedance]

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

 

[lanedance]

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

 

[dsfranca]

Thanks for the answer lanedance. First of all, the answer I am looking for is only k, and I don't 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...

 

[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.