Give an combinatorial argument

139 Views Asked by At

I need to find the possible value of $R_i$ and prove it by giving combinatorial argument, for following identity.

enter image description here

I was able to give an argument like this.

Consider double counting.

Count number of ways to arrange $n$ labeled balls.

One way of counting is permutation of all balls, which is $n!$.

Second way:

Calculate it by fixing positions of some of them and permute the rest such that none comes at it's original position.

Like choose $i$ balls from $n$ and fix them, find derangement of rest $n-i$ balls.

So in the equation we have $R_i$ is Derangement of $i$ numbers.

Am i missing anything ? Is proof valid and correct ?

If correct, I would love to read more elegant proof in answer. thank you.

1

There are 1 best solutions below

1
On

Your conclusion is correct (see sequence A000166 in OEIS).

I like your proof in terms of it being elegant. Your grammar isn't very good, but I don't see any logically more elegant way to prove that $R_n$ is the number of derangements of $n$ items.