mersenneforum.org  

Go Back   mersenneforum.org > Fun Stuff > Puzzles

Reply
 
Thread Tools
Old 2006-04-21, 07:58   #1
Kees
 
Kees's Avatar
 
Dec 2005

22×72 Posts
Default 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 ?
Kees is offline   Reply With Quote
Old 2006-05-03, 11:14   #2
Kees
 
Kees's Avatar
 
Dec 2005

22·72 Posts
Default

In all honesty, for me it is an open question
Kees is offline   Reply With Quote
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
Old 2006-05-09, 08:38   #4
Kees
 
Kees's Avatar
 
Dec 2005

22·72 Posts
Default

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 is offline   Reply With Quote
Old 2006-05-09, 11:53   #5
Kees
 
Kees's Avatar
 
Dec 2005

22·72 Posts
Default

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.
Kees is offline   Reply With Quote
Old 2006-05-12, 19:25   #6
tom11784
 
tom11784's Avatar
 
Aug 2003
Upstate NY, USA

2×163 Posts
Default

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
tom11784 is offline   Reply With Quote
Old 2006-05-13, 06:58   #7
Kees
 
Kees's Avatar
 
Dec 2005

110001002 Posts
Default

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)

Kees is offline   Reply With Quote
Reply

Thread Tools


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

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

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.