Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

(a) the objects are ordered and repetition is not allowed?

(b) the objects are ordered and repetition is allowed?

(c) the objects are unordered and repetition is not allowed?

(d) the objects are unordered and repetition is allowed?

I'm not really sure what it means for the objects to be "ordered" and repetition to be "allowed." Can someone succinctly explain what happens in each case, and how this can be generalized to other problems of the same type?

share|improve this question

2 Answers 2

up vote 3 down vote accepted

Let’s say that the six types are A, B, C, D, E, and F. You’re going to pick ten of them. I’ll start with the questions that allow repetition, meaning that you can pick more than one object of a given type.

Say you pick $3$ A’s, a B, $4$ D’s, and $2$ F’s. If they’re not ordered, the list $\langle 3,1,0,4,0,2\rangle$, giving the number of items of each type, tells you everything that there is to know about the set. Counting the number of unordered sets of $10$ objects is the same as counting the number of $6$-tuples $$\langle n_A,n_B,n_C,n_D,n_E,n_F\rangle$$ that could describe such a set, where $n_A$ is the number of objects of type A in the set, $n_B$ is the number of objects of type B in the set, and so on. It’s not hard to see that the numbers $n_A,\dots,n_F$ must be non-negative integers, and they must sum to $10$: we want the number of integer solutions to the system

$$\begin{align*} &n_A+n_B+n_C+n_D+n_E+n_F=10\\ &n_A,n_B,n_C,n_D,n_E,n_F\ge 0\;. \end{align*}$$

This is what is sometimes called a stars-and-bars problem; the linked article gives the formula, from which we find that there are

$$\binom{10+6-1}{6-1}=\binom{15}5=3003$$ solutions and therefore $3003$ ways of picking an unordered set of $10$ objects if repetition is allowed. The article also gives a pretty decent explanation of the formula, and you can find other explanation on this site if you search for stars and bars.

Now suppose that we care not only about how many objects of each type we have, but also about the order in which we picked them. If you’re doing a multiple-choice test that has $10$ questions, each with $6$ choices, clearly choosing the answers in the order AAABDDDDFF is going to give you a different score from choosing them in the order ADFDDBAFAD! The appropriate calculation is actually much simpler. There are $6$ ways to choose the type of the first object. No matter which choice you make, there are $6$ ways to choose the type of the second object, so there are $6\cdot6=36$ ways to choose the types of the first two objects, just as there are $6\cdot6=36$ possible outcomes when you roll a red die and a green die. The same reasoning shows that there are $6^3$ possible ways to choose the types of the first three objects, and in general $6^k$ ways to choose the types of the first $k$ objects, so there are $$6^{10}=60,466,176$$ ways to choose the types of all $10$ objects.

Now suppose that repetition is not allowed. That simply means that you can choose at most one object of each type. In particular, in this problem it means that there’s no way to choose $10$ objects without repetition, whether you care about the order of choice or not. That’s easy, but it isn’t going to help much with problems in which the number of objects chosen is no bigger than the number of types, so let’s modify the problem and ask for $4$-element sets without repetition.

If they are unordered sets, all we care about is which of the six types are represented. The binomial coefficient $$\binom64=\frac{6!}{4!(6-4)!}=\frac{6!}{4!2!}=\frac{6\cdot5}{2\cdot1}=15$$ gives the number of $4$-element subsets of a $6$-element set, and that’s exactly what we want. More generally, the number of $k$-element subsets of an $n$-element set is $$\binom{n}k=\frac{n!}{k!(n-k)!}=\frac{\overbrace{n(n-1)(n-2)\ldots(n-k+1)}^{k\text{ factors}}}{k!}\;.\tag{1}$$

Finally, the numerator of $(1)$ gives the answer to the final question: there are

$$n(n-1)(n-2)\ldots(n-k+1)=\binom{n}k\cdot k!$$

ordered ways to choose $k$ distinct elements from a set of $n$ elements, i.e., not just to choose which $k$ elements are to be in our set, but also the order in which we list them. In the example, $n=6$ and $k=4$, so there are

$$\binom64\cdot 4!=15\cdot24=360$$

such sets.

share|improve this answer
    
Wow, thank you so much for your thorough response –  user1903336 Dec 18 '12 at 0:56
    
@user1903336: You’re most welcome. –  Brian M. Scott Dec 18 '12 at 7:13

"Order is allowed" means different permutations of the same objects are considered different.

For example, number of ways of picking 2 objects out of $\{a,b,c\}$ with "order allowed" will include $\{ab, ba, bc, cb, ac, ca\}$. A good way of understanding "order allowed but repetition not allowed" in your problem is to think you are picking the six objects one at a time from the ten objects. For instance, in my example $ab$ represents picking $a$ in the first pick and picking $b$ in the second.

The way to count with "order allowed but repetition not allowed" is to see how many choices you have at each pick and multiply them. For my example, I had three choices for the first pick viz. $a,b,c$ and for my second pick, i have two choices left. So the total number of ways is $3 \times 2 = 6$ which is the total number of possibilities in our enumeration viz. $\{ab, ba, bc, cb, ac, ca\}$


"Repetitions are allowed" generally means that an item can picked at another time, even though it has been picked once before.

A good way of understanding "order allowed and repetition allowed" in your problem is to think you are picking the six objects one at a time but you put the object back into the bag after you make note of what you picked. For instance, in my example $aa$ represents picking $a$ in the first pick and putting it back and then picking $a$ again in the second.

For example, number of ways of picking 2 objects out of $\{a,b,c\}$ with "order allowed and repetition allowed" will include $\{aa, bb, cc, ab, ba, bc, cb, ac, ca\}$. Do you see how $aa$ is now included? This represents the possibility of getting $a$ in both picks.

The way to count with "order allowed and repetition allowed" is to see how many choices you have at each pick and multiply them. For my example, I had three choices for the first pick viz. $a,b,c$ and for my second pick, I still have three choices. So the total number of ways is $3 \times 3 = 9$ which is the total number of possibilities in our enumeration viz. $\{aa, bb, cc, ab, ba, bc, cb, ac, ca\}$


If "Order is not allowed", then different permutations of the same objects are considered same.

For example, number of ways of picking 2 objects out of $\{a,b,c\}$ with "order not allowed and repetition not allowed" will include $\{ab, bc, ac\}$. Do you see how $ba$ is not included? This is because $ab$ has been included. The different orderings of $ab$ is irrelevant now.

A good way of understanding "order not allowed and repetition not allowed" in your problem is to think you are picking the six objects all at once. For instance, in my example $ab$ represents picking two objects in one go, where I picked $a$ and $b$, Clearly this experiment does not count permutations of $ab$ as different. All that matters is which object you received.

The way to count with "order not allowed and repetition not allowed" is to use $\binom{n}{r}$ formula. This represents the total number of ways of non-repeated picking of 'r' objects out $n$ objects in an unordered manner. So the total number of ways is $\binom{3}{2} = 3$ which is the total number of possibilities in our enumeration viz. $\{ab, bc, ac\}$


The trickiest case is the last one. This is the case where repetitions are allowed but order is not allowed.

For example, number of ways of picking 2 objects out of $\{a,b,c\}$ with "order not allowed and repetition allowed" will include $\{aa, ab, ac, bb, bc, cc\}$.I think no more explanation is needed for the above enumeration.

A good way of understanding "order not allowed and repetition allowed" in your problem is to think you are distributing $6$ identical objects in $10$ distinct urns. In my example, two identical objects have to be distributed in urns labeled $a,b,c$. For instance, $ab$ on the enumeration represents distributing one of my objects in an urn labeled $a$ and another object in an urn labeled $b$.

The way to count with "order not allowed and repetition allowed" is to use $\binom{n + r - 1}{r}$ formula. This represents the total number of non-negative solutions to the equation $x_1 + x_2 + \cdots + x_r = n$. So the total number of ways is $\binom{3+2-1}{2} = 6$ which is the total number of possibilities in our enumeration viz. $\{aa, bb,cc, ab, bc, ac\}$

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.