You are here:

# Advanced Math/r-permutations and r-combinations of objects with identical items

Question
1. How is the number of r-permutations of n objects including n1,n2,n3,… identical objects calculated? (r<n)

For example, what is the number of ways in which 3 yellow balls, 2 red balls and 4 green balls can be put in 5 baskets, each in one basket, using five of the balls. (in this example, n=9 , n1=3 , n2=2 , n3=4 and r=5.)

2. How is the number of r-combinations of such objects calculated? (where order does not matter at all, even between different groups)

Thank you very much in advance.

permutations
The first question that you state has a textbook-y answer (see below), however, the solution to the example you give is far from easy.

If there are n objects total but for which m groups of them n1, n2,..., nm of them are identical, where n1+n2+ ... +nm = n, then we can start with the usual result:

number of ways to arrange n objects = n!

and divide out the number of ways each group can be arranged among themselves, given by n1!, n2!, ... , nm!, to get

number of indistinguishable arrangements = n!/(n1!･n2!･...･nm!).

Dividing by the factorials of the number of elements in each group takes into account the fact that, since the elements are identical within each group, rearranging them within the group leaves the overall arrangement unchanged (indistinguishable from any other arrangement). This result can be found in any decent textbook.

The example you give requires much more effort. The key complicating factor is that the original 9 balls are chosen to be placed in 5 bins. This brings up 2 new calculations, 1) how many ways can the 9 balls with the given colors be chosen for the 5 bins and 2) given the number of each color chosen, how many ways can they be arranged in the bins. This latter calculation takes into account the fact that the order of the bins is important, i.e., for instance, for Y=yellow, R=red and G=green, YRYGG and GYGRY are different even though the sequence has the same number of each color.

Let n1 = 3 = number of yellow balls, n2 = 2 = red balls, n3 = 4 = green balls. It is important that the constraint n1+n2+n3 = 5 be met for any combination of the ns. The accompanying table (attached image) lists the possible values of the number of balls in each group, observing the constraint, along with the number of ways this number can be chosen from the original set of balls, Cn, and finally the number of ways that the given number of balls can be arranged in the bins, Pn.

The value Cn is the number of ways, for each color, that m balls can be chosen from n total. Thus Cn1 = n!/[ (n-m)!m! ] where we have calculated the number of ways n balls can be chosen m ways, n!/m! and also taken into account the fact that we don't care what order the balls end up in once we have n of them, i.e., we divide out the ways they can be arranged = (n-m)! (we'll take care of the order in the next step). This is the textbook definition of combinations where order doesn't matter.

After we have calculated how many balls of each color we have put into the 5 bins, we calculate their permutations in the bins. This is done the same way as the textbook definition of permutatons given above

P(n1,n2,n3) = 5!/( n1!･n2!･n3! ).

The total number of ways to arrange the 9 balls with 3 colors into the 5 bins is 4550, as shown in the attached image. You should check the arithmetic, but the method of solution should be apparent. I have not figured out a general formula for the calculation. Perhaps you could come up with something.

As far as the 2nd question, I believe you could leave out the column Pn in the table (make alll values 1) to get rid of the dependence on order in the bins. The more general definition of combination given permutation is given in the above text.

Good luck!

Randy
Questioner's Rating
 Rating(1-10) Knowledgeability = 10 Clarity of Response = 10 Politeness = 10 Comment No Comment

Volunteer

#### randy patton

##### Expertise

college mathematics, applied math, advanced calculus, complex analysis, linear and abstract algebra, probability theory, signal processing, undergraduate physics, physical oceanography

##### Experience

26 years as a professional scientist conducting academic quality research on mostly classified projects involving math/physics modeling and simulation, data analysis and signal processing, instrument development; often ocean related

Publications
J. Physical Oceanography, 1984 "A Numerical Model for Low-Frequency Equatorial Dynamics", with M. Cane

Education/Credentials
M.S. MIT Physical Oceanography, B.S. UC Berkeley Applied Math

Past/Present Clients
Also an Expert in Oceanography