[EventHorizon]

Hey Braindenizens.

The posts on seem to have stopped, so I thought I would simplify it a little to try and find an eventual solution.

1. Given a well shuffled deck of 8 cards (numbered 1 through 8), what is the probability that when the cards are dealt out that no card's number will reflect the order it was dealt? (i.e., card labelled 1 is not dealt first, card labelled 2 is not dealt second, etc)

2. What is the probability in terms of N, where N is now the number of cards in the deck?

3. What is the probability if we use an infinite deck of cards? (yes, take the limit as N approaches infinity)

[superprismatic]

You didn't simplify the problem a little --

you went all the way to the subfactorials!

The original thread had 4 copies of each number,

making it a much harder problem.

[Guest]

Answer to Number 1: Roughly, 859/2500 actually it is .3436089158, but the calculator won't turn that into a fraction. Answer to number 2: (N-1/N)^N. Answer to Number 3: I'm not sure how to do that.

[Prime]

I did solve question (2) a little while ago, and I didn't see the problem as all that trivial. I got a short function S(N) for the number of arrangements of N objects so that each of them is not in its original position. Then the probability would be S(N)/N! naturally.

My question is: is it a known problem? Has a solution been published before? The problem is so simply stated: "How many arrangements of an ordered set of N objects, so that none is in its original spot are there?"

My way of solving it took a little bit of lateral thinking in addition to strightforward algebra.

[Prime]

P(8) = 14833 / 40320 = 2119 / 5760

[Prime]

lim(S(n)/n!) = 1/e, where n tends to infinity.

[Guest]

40031/40320??

Edited June 14, 2011 by Silver Surfer

[witzar]

My question is: is it a known problem?

http://en.wikipedia.org/wiki/Derangement

[Guest]

Hey all, I'm the OP of the original thread. I love the attention this problem's been getting. However, this simplified version doesn't take into account the fact that in a real deck of cards, there are 4 of each card. The problem isn't quite as simple as "derangement," is it?

In the original thread, I was convinced for awhile that, for a deck of 52 playing cards, the probability of nothing matching is (48/52)^52 = 0.016. This seemed to make sense, since we could lay all the cards face up, and check them in any order we pleased. It didn't MATTER whether all four kings were dealt first, because if we had checked the 13th spot first, the probability of that card not being a king is still 48/52.

BUT let's try a VERY simplified version with duplicates. Say a deck has two queens and two kings. There are 24 ways of ordering these cards:

Q1 Q2 K1 K2 (plus switching the first two, switching the last two, and switching the first two AND last two): these all give the same order

Q1 K1 Q2 K2 (plus switching 1 and 3, switching 2 and 4, and switching 1 3 AND 2 4)

K1 Q1 K2 Q2 (plus three switches as above)

Q1 K1 K2 Q2 (plus three switches)

K1 Q1 Q2 K2 (plus three switches)

K1 K2 Q1 Q2 (plus three switches)

Let's assume the correct order of the deck, like a real deck of cards, is Q K Q K. Out of the possibilities above, the number of orderings that DON'T include at least one match is 4 (K1 Q1 K2 Q2 and all switches). Therefore, the probability is 4/24 = 1/6.

If we use our method for 52 cards, we get a probability of (2/4)^4 = 1/16.

Clearly our original estimation doesn't work.

[Prime]

http://en.wikipedia....iki/Derangement

Thanks, witzar. So Montmort and Bernoulli had beat me to it by 300 years!

Although the reasoning given in the Wikipedia "Counting derangements" paragraph in the point (2) is not all that clear. I can see what they meant, but I would expand on that explanation.

Note the formula has a Fibonacci-like quality.

[Guest]

A suggestion of where to start for the original problem with four suits:

Consider a deck of cards with n (13) cards in each of m (4) suits. There are (mn)! ways of shuffling those cards.

Now consider an n X m grid:

1,1 1,2 1,3 ... 1,n

2,1 2,2 2,3 ... 2,n

.

.

m,1 m,2 m,3 ... m,n

Start with one of the suits. Apply the basic derangement problem on the first row. There are !n ways to shuffle that suit. There are an additional !n ways to shuffle the remaining suits. Total: m(!n). Simple, but wrong. Each column has one card from each suit, and each row has one card from each rank. We can shuffle the suits of cards of the same rank any way we like, and we also can shuffle the cards in a column any way we like. There are m! ways to do each of these for each of the n ranks and rows, but these combinations are not exclusive, because it is possible to have more than one card of the same rank in the same column. So, if somebody can figure out how many of those combinations overlap, I think we're done.

[EventHorizon]

It looks like Prime got the answers to these first.

1. 14833/8!

2. sum from i=2 to N of ( ((-1)^i) * (1/i!) )

So for N=1, it's 0.

For N=2, it's 1/2.

For N=3, it's 1/2 - 1/6 = 1/3.

For N=4, it's 1/2 - 1/6 + 1/24 = 5/8.

etc.

3. Looking at the series I noticed it was the tailor series for e^x where x = -1.

Tailor series for e^x = 1 + x + (x^2)/2! + (x^3)/3! + (x^4)/4! + ...

Substituting x=-1 gives 1 - 1 + 1/2 - 1/3! + 1/4! + ...

So the series must converge to e^-1 = 1/e.

------------------------------

Yup, looks like I did go to subfactorials. I didn't know what they were before this, but they are simpler than the original problem.

It looks like harpuzzler's equation has the right limit, but is not exact.

Looking at the wikipedia entry for the inclusion-exclusion principle it shows that the number of derangements is the closest integer to n!/e.

-----------------------------

As for the original problem, looking at the wikipedia entry for derangement under generalizations, it looks like the anagram for a word is equivalent to the original problem. It is a problem where the word is 52 letters long and has 4 each of 13 unique letters. The form for the answer looks rather ugly.

Looking at sacohen0326's example with 2 queens and 2 kings, if you ignore suit it is 4!/(2!*2!) = 6 possible orderings and only 1 that works, so 1/6. The equation for those who don't know is obtained by taking the total permutations and dividing by the number of permutations of each card number.

So the solution is easy when you have 1 suit or if you only have 1 or 2 different ranks of cards.

Perhaps the next step would be to find the derangements for when there are N ranks and 2 suits. Or even if there are 1 suit for all N ranks + one duplicate.

Perhaps d3k3's grid organization will prove useful.

I'll look around a bit for that anagram problem.

[Prime]

Actually, what I derived for the question (2) was a short recursive form of that series where each next member is derived from its two predecessors.

Let's designate S(n) as a function yielding the number of complete out of order arrangements for n objects.

S(1) = 0

S(2) = 1

S(n) = (n - 1) * (S(n-1) + S(n-2))

For example:

S(3) = 2 * (1 + 0) = 2

S(4) = 3 * (2 + 1) = 9

S(5) = 4 * (9 + 2) = 44

and so on... Easy to set up in a spreadsheet application.

The probability for n ojbects to be all out of place is S(n) / n!. I.e. probability for 4 objects to be all out of order is 9 / 4! = 9 / 24 = 3 / 8.

I derived the formula like so:

For n objects to be all out of order there can be n - 1 different objects in the first position. Suppose, there is object k in the first position. Then the next position to consider is position k. There are two possibilities:

1). There is object 1 in the position k. In that case we are left with n - 2 objects to arrange, or S(n-2).

2). There is any other of the remaining n - 2 objects in position k (except 1, or k). Let's say, it is object j. Then the next position to look at is position j, for which again there are two possibilities: 1) there is object 1 in j, leaving S(n-3); or any other of the remaining n - 3 objects.

And so on...

This yields a series S(n) = (n - 1) * S(n - 2) + (n - 1) * (n - 2) * S(n-3) + ... + (n - 1)! = (n - 1) * (S(n-2) + (n - 2) * S(n-3) + ... + (n - 2)!) = (n - 1) * (S(n-2) + S(n-1))

As for the problem with a full deck of cards, it seems out of grasp for the time being.