Math Is Fun Forum

Izzy222

Guest

Proof

I'm confused about this problem.  If someone could give me a start, I would really appreciate it!

Suppose n men throw their coats into a closet and later pick them up blindly - one coat per man, uniform probability that any particular coat will go to any particular man.

Let

be the number of ways of permuting n coats so that every coat gets moved (i.e.

since there is one way of switching 2 coats so that both coats get moved).

Let

be the number of permutations. (i.e.

because there are two ways of arranging 2 objects. in general,

).

Prove that:

.

mathsyperson

Moderator

Registered: 2005-06-22

Posts: 4,900

Re: Proof

As you said, C_n  = n!
Then you can replace all the C's in the equation you're trying to prove with factorials, to get n! = (n-2)!(n-1) + (n-1)!(n-1) = (n-1)[(n-2)! + (n-1)!], by factorising.

Rewrite n! as n(n-1)!:
n(n-1)! = (n-1)[(n-2)! + (n-1)!]

Rewrite (n-1)! as (n-1)(n-2)!:
n(n-1)(n-2)! = (n-1)[(n-2)! + (n-1)(n-2)!] = (n-1)(n-2)![(n-1)+1] = (n-1)(n-2)![n]

And so both sides of the equation are the same.

---

Why did the vector cross the road?
It wanted to be normal.

Izzy222

Guest

Re: Proof

Thanks for your response!

Not to bombard you with questions or anything, but you think you could help me with this one (which relates to the previous one)?  I've been stuck on it for several hours now...

Suppose B_n divided by C_n = D_n.

Prove that