Math Is Fun Forum

  Discussion about math, puzzles, games and fun.   Useful symbols: ÷ × ½ √ ∞ ≠ ≤ ≥ ≈ ⇒ ± ∈ Δ θ ∴ ∑ ∫ • π ƒ -¹ ² ³ °

You are not logged in.

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

gizmoguy19
Member
Registered: 2012-07-03
Posts: 6

Discrete Math Advanced Counting Problem

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

Offline

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

William F
Member
Registered: 2012-07-03
Posts: 16

Re: Discrete Math Advanced Counting Problem

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.

Offline

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

Bob
Administrator
Registered: 2010-06-20
Posts: 10,052

Re: Discrete Math Advanced Counting Problem

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


Children are not defined by school ...........The Fonz
You cannot teach a man anything;  you can only help him find it within himself..........Galileo Galilei
Sometimes I deliberately make mistakes, just to test you!  …………….Bob smile

Offline

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

anonimnystefy
Real Member
From: Harlan's World
Registered: 2011-05-23
Posts: 16,049

Re: Discrete Math Advanced Counting Problem

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


“Here lies the reader who will never open this book. He is forever dead.
“Taking a new step, uttering a new word, is what people fear most.” ― Fyodor Dostoyevsky, Crime and Punishment
The knowledge of some things as a function of age is a delta function.

Offline

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

careless25
Real Member
Registered: 2008-07-24
Posts: 560

Re: Discrete Math Advanced Counting Problem

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.

Offline

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

anonimnystefy
Real Member
From: Harlan's World
Registered: 2011-05-23
Posts: 16,049

Re: Discrete Math Advanced Counting Problem

Hi careless

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


“Here lies the reader who will never open this book. He is forever dead.
“Taking a new step, uttering a new word, is what people fear most.” ― Fyodor Dostoyevsky, Crime and Punishment
The knowledge of some things as a function of age is a delta function.

Offline

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

suresh74
Member
Registered: 2012-07-04
Posts: 1

Re: Discrete Math Advanced Counting Problem

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

Offline

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

bobbym
bumpkin
From: Bumpkinland
Registered: 2009-04-12
Posts: 109,606

Re: Discrete Math Advanced Counting Problem

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.


In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

Offline

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

careless25
Real Member
Registered: 2008-07-24
Posts: 560

Re: Discrete Math Advanced Counting Problem

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?

Offline

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

bobbym
bumpkin
From: Bumpkinland
Registered: 2009-04-12
Posts: 109,606

Re: Discrete Math Advanced Counting Problem

Hi;

Yes, 44 is the next derangement number.


In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

Offline

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

careless25
Real Member
Registered: 2008-07-24
Posts: 560

Re: Discrete Math Advanced Counting Problem

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.

Offline

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

bobbym
bumpkin
From: Bumpkinland
Registered: 2009-04-12
Posts: 109,606

Re: Discrete Math Advanced Counting Problem

Hi careless25;

Okay, I am looking at it.

In the meantime check this out:

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


In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

Offline

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

careless25
Real Member
Registered: 2008-07-24
Posts: 560

Re: Discrete Math Advanced Counting Problem

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!

Offline

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

bobbym
bumpkin
From: Bumpkinland
Registered: 2009-04-12
Posts: 109,606

Re: Discrete Math Advanced Counting Problem

Hi careless25;

It is kind of complicated isn't it?


In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

Offline

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

careless25
Real Member
Registered: 2008-07-24
Posts: 560

Re: Discrete Math Advanced Counting Problem

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

Offline

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

careless25
Real Member
Registered: 2008-07-24
Posts: 560

Re: Discrete Math Advanced Counting Problem

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)

Offline

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

bobbym
bumpkin
From: Bumpkinland
Registered: 2009-04-12
Posts: 109,606

Re: Discrete Math Advanced Counting Problem

Why not use a pigeonhole principle?


In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

Offline

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

anonimnystefy
Real Member
From: Harlan's World
Registered: 2011-05-23
Posts: 16,049

Re: Discrete Math Advanced Counting Problem

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?


“Here lies the reader who will never open this book. He is forever dead.
“Taking a new step, uttering a new word, is what people fear most.” ― Fyodor Dostoyevsky, Crime and Punishment
The knowledge of some things as a function of age is a delta function.

Offline

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

bobbym
bumpkin
From: Bumpkinland
Registered: 2009-04-12
Posts: 109,606

Re: Discrete Math Advanced Counting Problem

Hi suresh74;

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


In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

Offline

Board footer

Powered by FluxBB