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)n .
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.