1 ⋅ 1! + 2 ⋅ 2! + … + n ⋅ n! = (n + 1)! - 1

It is easy to prove this using the principle of mathematical induction. Some ways to interpret this formula.

  1. For values of k from 1 to n - 1, the number of possible permutations of n items where the kth item is the first one to be moved from its original position is equal to the number of possible permutations of the sequence where at least one element has moved from its original position. This gives us the formula: 1 ⋅ 1! + 2 ⋅ 2! + … + (n - 1) ⋅ (n - 1)! = n! - 1. In other words, k ⋅ k! is the number of permutations in which (n - k)th item is the first one to be moved from its original position.
  2. The largest factoradic number that can be represented using n digits is 1 ⋅ 1! + 2 ⋅ 2! + … + n ⋅ n! = (n + 1)! - 1.
Update 1: Realized that interpretation 1 can be made simpler if we consider kth item as the last one to be moved from its original position. The number of permutations in which kth item is the last one to be moved from its original position is: (k - 1)(k - 1)!. In this case, the interpretation becomes: For values of k from 2 to n, the number of possible permutations of n items where the kth item is the last one to be moved from its original position is 1 ⋅ 1! + 2 ⋅ 2! + … + (n - 1) ⋅ (n - 1)!.

No comments

Post a comment

RSS