Drexel dragonThe Math ForumDonate to the Math Forum

Ask Dr. Math - Questions and Answers from our Archives
_____________________________________________
Associated Topics || Dr. Math Home || Search Dr. Math
_____________________________________________

Blocks of Seats


Date: 11/16/98 at 12:27:57
From: mike
Subject: Discrete math

(1) In a row of 20 seats, in how many ways can 3 blocks of
    consecutive seats with 5 seats in each block be selected?

(2) There are 50 juniors and 50 seniors. Each class has 25 men and 25
    women. In how many ways can an 8 person committee be chosen so 
    that it includes 4 women and 3 juniors?

(3) In how many ways can a group of 8 people be divided into
    committees, subject to the constraint that each person must belong 
    to exactly 1 committee, and each committee must contain at least 2 
    people. (The committees are "anonymous.")

(4) In how many ways can (2*n) people be divided into n pairs?

(5) There is a red box, a blue box, and a green box. There are 10 red
    balls, 10 blue balls, and 10 green balls. There are 2 possible
    constraints:
      1. No box contains a ball having the same color as the box.
      2. No box is empty.
    Determine the number of ways of putting the 30 balls into the 3 
    boxes
      (a) subject to no constraints.
      (b) subject to constraint 1.
      (c) subject to constraint 2.
      (d) subject to both constraints.


Date: 11/17/98 at 14:43:01
From: Doctor Anthony
Subject: Re: Discrete math

You can think of each block as a single unit, so altogether there are 
3 + 5 = 8 objects to be considered

There are 8 objects to be arranged, 3 alike of one kind and 5 alike 
of a second kind.  The number of arrangements is  8!/(3! 5!) = 56

This is just the way the blocks can be chosen, we consider that 
individual seats within a block are indistinguishable.

 
>(2) There are 50 juniors and 50 seniors. Each class has 25 men and 25
>women. In how many ways can an 8 person committee be chosen so that
>it includes 4 women and 3 juniors?

Use the notation C(n,r) to mean the number of combinations of r things 
that can be made from n different things. The formula for C (n,r) is:

              n!                       10!
  C(n,r) = -------    so   C(10,4) = ------  = 210
           r!(n-r)!                   4! 6!

There are 4 groups

  25 junior men  25 senior men   25 junior women   25 senior women

4 women can be chosen from 50 in C(50,4) ways.
3 juniors can be chosen from 50 in C(50,3) ways.

However, this means that junior women could appear in both groups and 
there are C(25,7) groups that would appear twice - and we subtract 
this number so that they will appear only once.

The total number of ways of selecting the 7 is   

   C(50,4) x C(50,3) - C(25,7)

There is still one more to select from any one of the 93 remaining 
and this can be done in C(93,1) ways.

Total committees = [C(50,4) x C(50,3) - C(25,7)] x C(93,1)

>(3) In how many ways can a group of 8 people be divided into
>committees, subject to the constraint that each person must belong 
>to exactly 1 committee, and each committee must contain at least 2
>people. (The committees are "anonymous.")

You could have 4 committees of 2 each   2, 2, 2, 2

                               or       3, 3, 2

                               or       4, 2, 2

                               or       4, 4 

                               or       5, 3

                               or       6, 2

                               or       8

I assume that by 'anonymous' you are not concerned with the 
individual composition of the committees, only with the way the 
committees can be formed.   

  
>(4) In how many ways can (2*n) people be divided into n pairs?

          (2n)!           (2n)!
       -----------    =  ------
        2!2!....2!         2^n     


>(5) There is a red box, a blue box, and a green box. There are 10 red
>balls, 10 blue balls, and 10 green balls. There are 2 possible
>constraints
>1. No box contains a ball having the same color as the box.
>2. No box is empty.
>Determine the number of ways of putting the 30 balls into the 3 
boxes.
>(a) Subject to no constraints.

 The model for this type of question is placing balls in urns.  Here 
we have r balls to be placed in n urns. For the moment consider the 
balls to be indistinguishable. You can represent the balls by stars 
'*' and the n urns by spaces between n+1 bars. Thus |***|*||||****| is 
used to represent r = 8 balls in n = 6 urns, with occupancy numbers 3, 
1, 0, 0, 0, 4. This arrangement must start and end with a bar, but the 
remaining n-1 bars and r stars can appear in an arbitrary order. It is 
clear that the number of distinguishable distributions equals the 
number of ways of arranging (n+r-1) objects, r being alike of one kind 
and n-1 being alike of a second kind.

                 (n+r-1)!
So this gives = ---------    arrangements.
                 r!(n-1)!  

However the balls are of three colours and we must consider how each 
set of 10 balls can be distributed.

If there are no restrictions consider how the red balls can be 
distributed.   r = 10 and n = 3, so we get

         (3+10-1)!      12!
        ----------- = -------  = 66
          10! 2!       10! 2!

Similarly the blue and green balls can each be distributed in 66 ways, 
so all 30 can be distributed in 66^3 = 287496 ways.

>(b) Subject to constraint 1.

The red balls must go into blue or green boxes, and similarly for the 
blue and green balls; they must not go into the boxes of their own 
colour.

The number of ways of distributing 10 red balls into 2 boxes is

         (2+10-1)!      11!
       ------------ = ------  = 11
         10! 1!         10!

Similarly the blue and green balls can be distributed in 11 ways, each 
giving a total of 11^3 = 1331 arrangements.

>(c) Subject to constraint 2.

The number of arrangements under the condition that no box is empty is 
calculated as follows. In the model of stars and bars we must not have 
two bars together.

You can think of the r stars laid out in a row and you have to start 
and end with a bar. This leaves n-1 bars to place in r-1 gaps between 
the stars, and this can be done in C(r-1,n-1) ways.

With r = 10 and n = 3 this gives  C(9,2) = 36 ways.

However with 3 different colours and the possibilities of 0, 1, 2 
boxes left empty with each colour, I shall use a different approach 
to this question.

We consider the number of ways that say the red box could be left 
empty. This requires that each of the 10 balls of each colour be 
distributed into two boxes only. We have already seen that this could 
be done in 11 ways for each colour, giving 11^3 = 1331 ways altogether 
for the red box to be left empty. Similarly, there are 1331 ways for 
the blue box and a further 1331 for the green box to be empty. So the 
number of ways that one box can be empty is 3 x 1331 = 3993. If we 
subtract this from the total ways of distributing the balls, as found 
in part (a), we shall get the number of ways with no box left empty
  
  = 287496 - 3993  =  283503  ways 

>(d) Subject to both constraints.

Again consider how the red box might be left empty. The red balls will 
in any case not go into the red box, but the blue and green balls 
could. If the green ball is not to go into the red box, then with the 
first restriction in place all the green balls will go into the blue 
box, this gives only one arrangement with the green balls, and 
similarly all the blue balls would go in the green box, giving just 
one arrangement. The red balls could be distributed in 11 ways into 
the blue and green boxes, so altogether there would be 11 ways for the 
red box to be empty under constraint (1). Similarly the blue and green 
boxes could each be empty in 11 ways under constraint (1), giving 33 
ways for one box to be empty under constraint (1). We must therefore 
subtract this number of ways from the total already calculated for 
constraint (1).

The total under both constraints = 1331 - 33  =  1298.

- Doctor Anthony, The Math Forum
  http://mathforum.org/dr.math/   
    
Associated Topics:
High School Permutations and Combinations

Search the Dr. Math Library:


Find items containing (put spaces between keywords):
 
Click only once for faster results:

[ Choose "whole words" when searching for a word like age.]

all keywords, in any order at least one, that exact phrase
parts of words whole words

Submit your own question to Dr. Math

[Privacy Policy] [Terms of Use]

_____________________________________
Math Forum Home || Math Library || Quick Reference || Math Forum Search
_____________________________________

Ask Dr. MathTM
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/