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/
Search the Dr. Math Library:
Ask Dr. MathTM
© 1994- The Math Forum at NCTM. All rights reserved.