Thread: Combinatorics
View Single Post
Old 2006-05-04, 01:02   #3
jebeagles
 
jebeagles's Avatar
 
Jun 2004
Chicago

22·7 Posts
Default

Given a k-element subset, remove any of the k elements, this clearly is a permutation of k-1 elements.

Take a set (k-1)-element subsets of the same k-1 elements. There are k! remaining elements that can be placed back into the (k-1)-element subsets. Now, there are exactly k repeated k-element subsets doing this process, so there are only (k-1)! that can be added to each set of permutations. Now there are (k-1)! permutations, and (k-1)! elements that can be added to those permutations, adding an element to each permutation out of the possible (k-1)! elements gives a distinct k-element subset.

Therefore, bijection.
---
is that what you were looking for, or am I off?

Last fiddled with by jebeagles on 2006-05-04 at 01:04
jebeagles is offline   Reply With Quote