Problems with the Multiplication Principle (combinatorics)

In summary, there are 18*35 ways to place 2 red rooks and 17*8*11*31 ways to place 4 blue rooks on a 6 by 6 chessboard. This equals to (2^7)*5*7*11*17*31, which is the total number of ways to place the rooks. For the classroom scenario, there are 8*7*6*5*4 possible ways for the 5 students to sit in the front row and 8*7*6*5 for the 4 students to sit in the back row. There are also 7*6*5*4*3 ways for the remaining 7 seats to be filled
  • #1
chaotixmonjuish
287
0
I'm having problems wrapping my head around this...so I want to post some questions out of this Introductory Combinatorics book and what I believe to be the solutions:

1.) There are 6 rooks placed on a 6 by 6 chessboard. How many ways if there are 2 red and 4 blue?

I got 6!*\binom{6}{4} as there are 6! places to put it and 6 choose 4 ways to pain the rooks blue.

2.) A classroom has 2 rows of 8 seats. There are 14 students, 5 of whom always sit in the front row and 4 whom always sit in the back.

Does this work out in roughly the same way?

\binom{9}{3}*3!+\binom{5}{4}*4!

there are 9 people left who won't sit up front, therefore leaving 3 spots to choose for the nine. In the back there will be 14-5 (that sit up front)-4(the ones who will always be in back). So there will be 5 choose 4*4!
 
Mathematics news on Phys.org
  • #2
1. Is the question asks how many ways are there to paint the 6 rooks and then place them in the board?
Then the answer would be for the colours as you wrote \binom{6}{4} but for placing the rooks you have \binom{36}{6}.

2. What is the question? is it how many ways there are to sit the students?
You have \binom{8}{5}*5! to choose for the upfront seats and \binom{8}{4}*4! for the backseated, and the rest who are 5 students need to be seated either upfront or back, there 7 places for 5 students i.e \binom{7}{5} and either the first is all seated which means two seats are left unmanned in the backseat or the backseat is all seated which means that two seats are left unmanned in the upfront seat.
which roughly means: \binom{8}{5}5!*(\binom{5}{3}3!*\binom{4}{2}+\binom{5}{4}4!*3)*\binom{8}{4}4!
 
  • #3
chaotixmonjuish said:
1.) There are 6 rooks placed on a 6 by 6 chessboard. How many ways if there are 2 red and 4 blue?

I got 6!*\binom{6}{4} as there are 6! places to put it and 6 choose 4 ways to pain the rooks blue.

What about #ways_for_red * #ways_for_blue ?


chaotixmonjuish said:
2.) A classroom has 2 rows of 8 seats. There are 14 students, 5 of whom always sit in the front row and 4 whom always sit in the back.
...

What is the question?
:smile:
 
  • #4
How many ways are there to sit the student?

That's the question.
 
  • #5
I don't understand why its \binom{8}{5} and not \binom{9}{3}. Since 5 are guaranteed to sit in front, wouldn't that leave me 3 to choose from the 9.
 
  • #6
First put the red ones down. For the first red, you have 36 ways. For the second rook, you have 35 ways. Multiplying these gives 36*35.

However, you've double counted, since it doesn't matter which rook you put down first, and you've counted both ways of ordering them. So divide by 2.

Next, put the blue ones down. You have 34, 33, 32, and 31 ways to do this, respectively. Multiplying gives 34*33*32*31.

You've overcounted again. There are 4*3*2*1 ways to number the four blue rooks, so you just need to divide by 4*3*2*1 to get the number of ways to put the blue ones down.

Now just multiply the answer from part 1 to the answer from part 2. In other words, the answer is:

P(36,6) / 2!4!
 
  • #7
To place the two red you have to select a subset of two elements in a set of 36.
So you have a number of choices equal to the combinations of 36 on 2 that is
36*35/2 = 18*35 choices.
Then you have to place the four blue and you have a number of choices equal to the
number of the subsets of four elements in a set of 34 elements that is
34*33*32*31/(4*3*2)= 17*16*11*31/2 = 17*8*11*31 choices.
So the final number is the multiplication of these two
8*11*16*17*31*35
it is a large number indeed so better you don't multiply them
it is
(2^7)*5*7*11*17*31
factorized in primes.
 
  • #8
A classroom has 2 rows of 8 seats. There are 14 students, 5 of whom always sit in the front row and 4 whom always sit in the back.

In the first row there are always 5 students that will seat.
In how many ways they can sit?
It is the number of injective functions from a set of 5 elements in a set of 8 elements.
you have 8 choices for the first student, 7 choices for the second student 6 for the 3rd, 5 for the 4th and 4 for the 5th. In total A = 8*7*6*5*4.

For the back row you have the same logic. You have B = 8*7*6*5 choices.
Now how many seats are still free? 8*2 - (5+4) = 16 - 9 = 7 and how many students are left? 14 - (5+4) = 5.
So you have C = 7*6*5*4*3 choices.

The total choices is

D = A*B*C

I hope I didn't do any mistake... these exercises are often tricky for me...
 

1. What is the Multiplication Principle in combinatorics?

The Multiplication Principle, also known as the Fundamental Counting Principle, is a rule in combinatorics that states that the total number of ways to choose or arrange a set of objects is equal to the product of the number of ways each individual object can be chosen or arranged.

2. What are some common problems that arise with the Multiplication Principle?

Some common problems that arise with the Multiplication Principle include overcounting, undercounting, and the assumption of independence between events.

3. How does overcounting occur with the Multiplication Principle?

Overcounting occurs when the same outcome is counted multiple times in the total number of possibilities. This can happen when there is repetition or when two or more events are not truly independent.

4. How can undercounting happen with the Multiplication Principle?

Undercounting can happen when all possible outcomes are not considered or when order is not taken into account. For example, if arranging 3 books on a shelf is considered the same as arranging 3 books on a table, the total number of possibilities will be undercounted.

5. Can the Multiplication Principle be applied to all combinatorial problems?

No, the Multiplication Principle can only be applied in situations where the events are independent and when there is a fixed number of objects. In cases where the events are dependent or the number of objects is not fixed, other combinatorial methods such as permutations and combinations should be used.

Similar threads

  • General Math
Replies
2
Views
1K
  • General Math
2
Replies
68
Views
9K
  • Precalculus Mathematics Homework Help
Replies
5
Views
1K
  • General Math
Replies
3
Views
2K
  • Precalculus Mathematics Homework Help
Replies
7
Views
1K
  • Calculus and Beyond Homework Help
Replies
7
Views
1K
Replies
6
Views
1K
Replies
1
Views
4K
Replies
2
Views
2K
  • Set Theory, Logic, Probability, Statistics
Replies
12
Views
1K
Back
Top