Discrete Math Advanced Counting Problem

gizmoguy19 · 2012-07-03 17:32:36

Hi
I have this question from Discrete Math class, which has been bugging me for sometime now.

Q: A group of 4 people from different parts of the world decide to swap their homes with each for a week so they can all travel. What is the number of way this can be done?

Thanks

William F · 2012-07-03 17:45:37

If I understand the question right, the answer is 6 ways. If you label the homes as A,B,C and D you will have:

AB BC
AC BD
AD CD

These are the 6 possible combinations.

Bob · 2012-07-03 18:55:02

hi gizmoguy19

Welcome to the forum.

William's idea is good but, take care to answer the question as asked ... that's three ways of doing it not six.

But what do you mean by swap? ie. Could A takes B's home, B takes C's, C takes D's and D takes A's be allowed?

If I call that 4-cycle ABCD then add on ABDC, ACBD, ACDB, ADBC, ADCB.

So you then have three ways of doing a pair of 2-cycles plus six ways of doing the 4-cycles.

You can dismiss 1-cycles as everybody stays at home, and any 3-cycle as the 4th person doesn't swap.

Bob

anonimnystefy · 2012-07-04 01:33:37

I would say that this is another derangement problem with n=4. The solution is !4=9 ways.

careless25 · 2012-07-04 02:55:43

can you solve this using the K5 complete graph, as in a graph with 5 vertices connected to all other vertices. So wouldnt the total number of edges be 10?
sum of all degree of all vertices = 2 * edges.
so each vertex has degree 4. there are 5 vertices. 20 = 2 * edges. therefore 10 edges in total.

anonimnystefy · 2012-07-04 03:11:52

Hi careless

I don't see how that is connected to this problem. Could you explain?

suresh74 · 2012-07-04 03:14:42

I have this problem please solve it
(x+a)(x+b)(x+c)

bobbym · 2012-07-04 03:15:25

Hi careless25;

I think your graph is showing the 10 permutations. But the answer is 1 less because abcd is the start position of the people and is not a derangement.

careless25 · 2012-07-04 03:40:43

hi bobbym, actually what anonimystefy said is true, the way I am solving it doesnt make sense since there are 5 vertices in mine but the OP said only 4 people.

You listed out all the permutations which does make sense.

Anonimystefy how many ways would it be with 5 peolpe? !5 = 44 ways?

bobbym · 2012-07-04 03:42:37

Hi;

Yes, 44 is the next derangement number.

careless25 · 2012-07-04 03:50:49

I also need help with this counting problem.

John ordered some boots from an online store. He was sent a crate containing 200 boots of size 7, 200 boots of size 9, 200 boots of size 11, and 300 boots are for the left boot, 300 boots are for the right foot. Prove John has at least 100 correct pairs of boots.

bobbym · 2012-07-04 03:54:10

Hi careless25;

Okay, I am looking at it.

In the meantime check this out:

http://mathforum.org/advanced/robertd/derangements.html

careless25 · 2012-07-04 03:58:06

hi bobbym,
I see where I went wrong in my thinking. Instad of counting the number of edges I have to count the different arrangements of the edges in a 5 vertices graph. Thanks for the link!

bobbym · 2012-07-04 04:10:46

Hi careless25;

It is kind of complicated isn't it?

careless25 · 2012-07-04 04:12:42

Yeah it is, I cant find a good way to have a union of those sets.

careless25 · 2012-07-04 04:15:53

Lets say we have a set A containing 600 elements = {7,9,11,7,9,11,......,11}
and another way of describing that se would be = {l,r,l,r,l,r,l,r,l.....l} where l and r are right and left shoes respectively. Then if we map them 1 to 1 we have exactly 100 pairs of size 7 shoes, size 9 shoes and size 11 shoes. This means we have a total of 300 correct pairs if arranged this way. Would this work?

Last edited by careless25 (2012-07-04 04:18:47)

bobbym · 2012-07-04 04:23:20

Why not use a pigeonhole principle?

anonimnystefy · 2012-07-04 09:05:18

suresh74 wrote:

I have this problem please solve it
(x+a)(x+b)(x+c)

Hi suresh74

What do you have to do with that? Expand it?

bobbym · 2012-07-04 22:27:33

Hi suresh74;

Please repost your problem in "Help Me" and start a new thread.

Math Is Fun Forum

#1 2012-07-03 17:32:36

Discrete Math Advanced Counting Problem

#2 2012-07-03 17:45:37

Re: Discrete Math Advanced Counting Problem

#3 2012-07-03 18:55:02

Re: Discrete Math Advanced Counting Problem

#4 2012-07-04 01:33:37

Re: Discrete Math Advanced Counting Problem

#5 2012-07-04 02:55:43

Re: Discrete Math Advanced Counting Problem

#6 2012-07-04 03:11:52

Re: Discrete Math Advanced Counting Problem

#7 2012-07-04 03:14:42

Re: Discrete Math Advanced Counting Problem

#8 2012-07-04 03:15:25

Re: Discrete Math Advanced Counting Problem

#9 2012-07-04 03:40:43

Re: Discrete Math Advanced Counting Problem

#10 2012-07-04 03:42:37

Re: Discrete Math Advanced Counting Problem

#11 2012-07-04 03:50:49

Re: Discrete Math Advanced Counting Problem

#12 2012-07-04 03:54:10

Re: Discrete Math Advanced Counting Problem

#13 2012-07-04 03:58:06

Re: Discrete Math Advanced Counting Problem

#14 2012-07-04 04:10:46

Re: Discrete Math Advanced Counting Problem

#15 2012-07-04 04:12:42

Re: Discrete Math Advanced Counting Problem

#16 2012-07-04 04:15:53

Re: Discrete Math Advanced Counting Problem

#17 2012-07-04 04:23:20

Re: Discrete Math Advanced Counting Problem

#18 2012-07-04 09:05:18

Re: Discrete Math Advanced Counting Problem

#19 2012-07-04 22:27:33

Re: Discrete Math Advanced Counting Problem

Board footer