 mersenneforum.org Combinatorics
 Register FAQ Search Today's Posts Mark Forums Read 2006-04-21, 07:58 #1 Kees   Dec 2005 22×72 Posts Combinatorics You have a set of k!+k-1 elements (k>1), numbered 1, 2,..., k!+k-1 . Let A be the set of subsets with exactly k elements. Let B be the set of subsets with exactly k-1 elements, which includes also all the permutations of such a subset (so if for instance k=4 then the subsets {1,2,3},{1,3,2},{2,3,1},{2,1,3},{3,1,2}{3,2,1} are all in B. Evidently #A=#B Can you construct a bijection f such that f(A_i)=B_i and such that for all i A_i contains B_i ?   2006-05-03, 11:14 #2 Kees   Dec 2005 22·72 Posts In all honesty, for me it is an open question   2006-05-04, 01:02 #3 jebeagles   Jun 2004 Chicago 22×7 Posts 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   2006-05-09, 08:38 #4 Kees   Dec 2005 22·72 Posts At least you are trying for a solution. I wonder however whether I should accept this solution. It seems all right, but it silently assumes the following: if during the process of 'adding' an element out of the (k-1)! available to one of the (k-1)! permutations we get a k-subset twice, this would mean that another k-subset does not get attributed and we should be able to settle that. There is yet another snag: for the moment we have only looked at one subset of k-1 elements.There are however quite some subsets of k-1 elements. Are we still getting distinct k-subsets ?   2006-05-09, 11:53 #5 Kees   Dec 2005 22·72 Posts you are right, the second part of my answer is gibberish at best...  what jebeagles is showing is the following: we have the set {1,...,k!+k-1} and we take some subset of k-1 elements. say {1,...,k-1}. To this subset we can 'add' k! different elements. Here we have our first problem. The number of sets {1,...,k-1} including permutations is (k-1)! How to add the remaining elements? (we had k!=(k-1)! * k elements remaining after selecting k-1 elements). So which do we select ? And what happens to the selectionprocedures for other subsets (for instance {1,...,k-2,k}) after this selection. Can we still fill. I am not really satisfied with the answer, actually. All that seems to be shown is that the two sets have the same size (which I offered at the beginning of the problem). If that was the end to it, we would obviously have a bijection. But the extra condition makes this unclear for me.   2006-05-12, 19:25 #6 tom11784   Aug 2003 Upstate NY, USA 2×163 Posts If you number the subsets by ranking from least to greatest for first term, then second term, then third term, then fourth i.e. A1={1,2,3,4} A2={1,2,4,3} A3={1,3,2,4} A4={1,3,4,2} ... and f({a,b,c,d})={a,b,c} then B1={1,2,3} B2={1,2,4} B3={1,3,2} B4={1,3,4} ... which I believe meets your requirements, but I may be reading something incorrectly   2006-05-13, 06:58 #7 Kees   Dec 2005 110001002 Posts The problem is that the subsets in A do not have permutations of themselves A1=(1,2,3,4), A2=(1,2,3,5) B1=(1,2,3), B2=(1,3,2)   Thread Tools Show Printable Version Email this Page Similar Threads Thread Thread Starter Forum Replies Last Post Nick Combinatorics & Combinatorial Number Theory 7 2019-12-14 15:25 Ken_g6 Puzzles 15 2010-08-04 23:30

All times are UTC. The time now is 11:40.

Sun Sep 20 11:40:57 UTC 2020 up 10 days, 8:51, 0 users, load averages: 2.01, 1.66, 1.44