Combinatorics, Truncated Permutations

Truncated Permutations

When only the first k elements of an n-element permutation are significant, the number of unique permutations is n!/(n-k)!. As before, there are n elements to choose from, then n-1, then n-2, down to n-k+1. This product is n!/(n-k)!.

Truncated with Repeated Elements

There is no simple formula for a truncated permutation with repeated elements, though one can count them out systematically. Consider arranging 4 letters from ABCDEEE. If you select at most one E, that's a truncated permutation, 4 out of 5, giving 120. With three E's on the shelf, there is one other letter, A B C or D, and it is placed in one of 4 positions, hence 16. Finally 2 E's on the shelf calls for 2 other letters, which can be done in 6 ways. Then we are permuting 4 elements with 2 repeated E's, so 6 times 4!/2! = 72. The sum is 208, and there just isn't a nice formula for that.