word problem: number of ways to order n things in r groups  TOPIC_SOLVED

Sequences, counting (including probability), logic and truth tables, algorithms, number theory, set theory, etc.

word problem: number of ways to order n things in r groups

Postby vonzel818 on Wed Feb 18, 2009 3:11 am

if the order is not considered, the number of ways a group of n things can be arranged into r groups is
n!
______
r!(n-r)!

If order is considered, the number of ways a group of n things can be aranged into r groups is

n!
______
(n-r)!

The ! symbol is pronounced factorial in this application and represents multiplication by successively decreasing whole numbers greater than zero
For example, 4!= 4*3*2*1 = 24.

A group of 7 elementary students tries out for a 5 person basketball team. How many teams can be formed:

(A) If the order in which the children are picked is considered

(B) If the order in which the children are picked is not considered
vonzel818
 
Posts: 1
Joined: Wed Feb 18, 2009 3:08 am

Sponsor

Sponsor
 

Postby stapel_eliz on Wed Feb 18, 2009 3:19 am

The definitions of "n-choose-r" and "n-permute-r" are odd and more than a little confusing.

The standard definition of n-choose-r is that you have n things (such as n = 7 students), of which you are choosing r (such as r = 5 for the team) without respect to order (that is, all of the r elements are "equal" in some sense).

The standard definition of n-permute-r is that you have n things, of which you are choosing r elements, but order does count (such as the first chosen is assigned to be the team captain, the second chosen is assigned to some other position, etc).

Using these definitions, can you see which formula into which you should plug the numbers for each question? :wink:
User avatar
stapel_eliz
 
Posts: 1717
Joined: Mon Dec 08, 2008 4:22 pm

Re: word problem: number of ways to order n things in r groups  TOPIC_SOLVED

Postby Karl on Wed Feb 18, 2009 5:59 pm

The title seems to suggest that it is not just asking how many ways can you choose r students from a class of n students. Instead it suggests that it is asking, "How many ways can I group n students into r disjoint committees?"

There are two possible problems this could be asking for. The easy one is where, were you to swap two students on two different committees, you would consider that a different arrangement. Here each student can go into any of r committees. So the total arrangements is r^n. This, however, allows for committees of zero students. To find it for committees that must have at least one student each, determine how many ways you can choose r students from the n and place one into each committee. Then use the formula already described on the remaining n-r and multiply the two results.

The other problem it might be asking is how many partitions are there of n students into r committees. Here you don't care who is on which committee, but just how many are on each committee.

This is a harder problem. I will show the solution here with the caveat that it allows for committees that have zero students.

Here's how I'm going to select the students into the committees. First I'm going to take r-1 chairs and line them up against the front wall of the room, with spaces between them and spaces between the chairs on the ends and the side-walls. So this makes for r spaces. I will then sort the students into various spaces between the chairs. All the students that end up in a given space will constitute a committee.

What I have here is 2 kinds of objects -- chairs and students. I have a total of n + r - 1 objects. If you consider the students to be indistinguishable from each other (for this purpose anyway -- I know that in reality they all are individuals) and the chairs to be indistinguishable from each other, then the problem is asking for the number of arrangements of the objects without regard to the ordering of the students or of the ordering of the chairs. If I did pay attention to ordering, then there would be (n + r - 1)! arrangements. But there are n! orderings of students and (r-1)! orderings of chairs. So the total number of ways is



If you require that each committee have at least k members, the problem becomes more complicated, but you solve it using similar methods.
Karl
 
Posts: 7
Joined: Sat Jan 24, 2009 3:56 pm


Return to Discrete Math