An Interesting Counting Problem...

I came across an interesting problem on a video from Shai Simonson about Discrete Math. The question was to count all the possible permutations of a subset drawn from n items.

The count would seem to be direct enough. Just take every possible subset, and count the permutations of that subset. There would only be one subset with n-items and it has n! permutations.. there are n choose k permuations with n items, and they can be permuted in k! ways.. so we could write the whole sum as P(n)= If we enumarate a few we see a pattern: P(0)=1; P(1)=2, P(2) = 5, P(3) = 16, P(4) = 65.... and from that we sense that P(n)= n P(n-1)+1...

Shai had a nice way to show this is true. Here is my illustration of his approach:

can be rewritten as

and here he does something very clever... he factors n out of each of these terms in the new expression to get

which is just 1+ P(n-1)...

But what do you do with P(n)= n P(n-1)+1. It doesn't seem to have a close form expression that lets you calculate the nth term directly.

Once more Simonson gets creative. He points out that the derangements of n follow a similar recursive sequence, except that d(n)= n [d(n-1)] + (-1)ⁿ .

He points out that this is known to be equal to n! (1/1 - 1/1+ 1/2! - 1/3! + 1/4!... 1/n!)

He then suggests that P(n) could be written as n! (1/1 + 1/1+ 1/2! + 1/3! + 1/4!... 1/n!) which matches the values of all the P(n) I checked, and of course, as n goes to infinity, that is just P(n)= n! e .

Ok, pretty interesting, and in fact, it seems that in all the cases I have tried, the actual value of P(n) is just Int(n! e) . It even works at P(1), and gets closer as n increases.

Try a few, tell me if I overlooked something...

I just thought it was a very pretty math. The comparison to d(n) leading to a really clever limiting value... nice job Sir.

http://www.mathvids.com/subtopic/show/116-combinatorics