Combinatorics

Kees · 2006-04-21, 07:58

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 ?

Kees · 2006-05-03, 11:14

In all honesty, for me it is an open question

jebeagles · 2006-05-04, 01:02

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?

Kees · 2006-05-09, 08:38

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 ?

Kees · 2006-05-09, 11:53

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.

tom11784 · 2006-05-12, 19:25

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

Kees · 2006-05-13, 06:58

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)

2006-04-21, 07:58	#1
Kees Dec 2005 2²×7² 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-04, 01:02	#3
jebeagles Jun 2004 Chicago 28₁₀ 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

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Combinatorics news	Nick	Combinatorics & Combinatorial Number Theory	7	2019-12-14 15:25
Stacking boxes - combinatorics?	Ken_g6	Puzzles	15	2010-08-04 23:30

2006-05-03, 11:14	#2
Kees Dec 2005 2²·7² Posts	In all honesty, for me it is an open question

2006-05-09, 08:38	#4
Kees Dec 2005 2²·7² 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 2²×7² 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 2²×7² 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)