0
$\begingroup$

This is more of a methods question than asking for a specific answer:

In revisiting statistics and attempting various problems, I am curious if anyone has any insights on how to "see" the route to the solution for combination and permutation problems (and not just see the answer and determine the route in retrospect)?

For instance, I am familiar with the general principles of a factorial (n!) being the number of arrangements of any set of n items, and then a permutation nPk being the total possible arrangements of a subset of "n" items. Further refining this, the combination nCk is then the permutations with the various repeats of the same set (those in a different order) removed.

These make logical sense, and I can see them mathematically when doing basic problems that just outline the properties of these tools (e.g., finding the total combinations of 8 cards out of 52....yay, easy!)

The problem I have is then how these tools translate to more complex problems? For instance, and this is only the next step up in complexity, given any random 8 cards from a deck of 52, what are the number of possible such hands that contain a heart?

When I see this, I simply blank and do not know what the heck to do...at all. In essence, it's asking how many combinations of 8 contain a heart. Without making any assumptions or guesses, I know there are 752,538,150 possible combos of 8, so the answer is less than this, but that's where the logic ends. My brain is simply not seeing how to proceed, and I'm curious if there are any suggestions for how to "see" this?

What I do not want to do is see a bunch of similar problems, memorize a method for solving them, and then simply apply that method to other similar ones.

There is a missing link of sorts between knowing the required rules, and how to apply them. I'm looking for some hints, tips, tricks, and whatever approaches folks suggest for learning this.

$\endgroup$
  • $\begingroup$ The number $n!$ is the number of ways $n$ objects can be arranged in order. The number $P(n, k)$ is the number of ways an ordered selection of $k$ of $n$ distinct objects can be made. The number $C(n, k)$ is the number of ways of selecting a subset (unordered arrangement) of $k$ of $n$ distinct objects. $\endgroup$ – N. F. Taussig Apr 14 '15 at 15:53
  • $\begingroup$ My understanding is that if you have n items (say, 12) then n! is the way you can arrange the 12 items (with replacement). This is the same as P(n,k) where n=12 and k=12, that results in 12!/(12-12)! = 12! $\endgroup$ – Topher Apr 14 '15 at 20:10
  • $\begingroup$ The number of ways you can arrange $n$ items without repetition is $n!$. For instance, the number of ways $12$ students can line up for a fire drill is $P(12, 12) = \frac{12!}{(12 - 12)!} = \frac{12!}{0!} = \frac{12!}{1} = 12!$. $\endgroup$ – N. F. Taussig Apr 15 '15 at 9:46
  • $\begingroup$ I should probably explain that an example of a permutation with repetition is forming a license plate with three letters and three digits, which can be performed in $26^3 \cdot 10^3$ ways (ignoring the fact that certain sequences of letters are prohibited since they may be offensive in some language). If you have five black marbles, four blue marbles, and three grey marbles in a bag, the probability of drawing two black marbles depends on whether the first one is replaced. Without replacement, the probability is $\frac{5}{12} \cdot \frac{4}{11}$. With replacement, it is $(\frac{5}{12})^2$. $\endgroup$ – N. F. Taussig Apr 15 '15 at 10:08
4
$\begingroup$

I'm not sure there's a reductionistic trick that you can apply that will work generally. One learns the primitives well enough, and by well enough, I mean that one knows not only what each of them does, but what they can do in combination. With enough facility at that, one can construct any number of combinatorial frameworks to solve general problems.

In the kind of problems that you refer to specifically, one way to approach the problem is to consider how one would construct the selection. How would one go about constructing an eight-card hand that contains at least one heart? Well, you could take one of the $13$ hearts, and seven of the remaining $39$ cards; or two of the $13$ hearts, and six of the remaining $39$ cards; or three of the $13$ hearts, and five of the remaining $39$ cards; and so forth. That would lead to the summation

$$ \binom{13}{1}\binom{39}{7} + \binom{13}{2}\binom{39}{6} + \cdots + \binom{13}{8}\binom{39}{0} $$

Working through those terms would indeed give you the correct answer, $691014402$. However, upon looking at this, one might see a faster way to the answer, by constructing the hand "in the negative": that is to say, by finding which eight-card hands do not qualify, and subtracting them from all eight-card hands. That leads one to the simpler calculation

$$ \binom{52}{8} - \binom{39}{8} $$

which yields the same answer of $691014402$. One could view that as a trick, but it's really just a tool. One sees which "end" of the problem is more "finite", and generally prefers to tackle the problem from that end.

Hope this helps.

$\endgroup$
  • $\begingroup$ Wow! Beautiful! That's exactly what I was looking for. My main frustration is simply not having a familiarity with using these in problems, but somewhat figured that there would be a clever way in each to work out the problem, somewhat like proving a trig identity. Your explanation here is perfect! I think overall I'll just have to work through the logic of some problems given the answer, and do so in retrospect until I can see these approaches clearer. Its frustrating because given the answer, the solution often just becomes obvious. $\endgroup$ – Topher Apr 14 '15 at 20:14
  • $\begingroup$ I think its basically that I simply dont know how to apply these primitives, and therefore can't recognize them in a problem. For instance, in this case its almost silly how obvious it is to subtract the combinations that do not work from those that do, but in the moment I'm only asking myself how to divide 752B possibilities by some combination or permutation to get something that makes sense...and it becomes far larger of a problem than it is...whew! $\endgroup$ – Topher Apr 14 '15 at 20:20
  • $\begingroup$ I'm not sure there's a more efficient path toward proficiency than just doing a bunch of problems, I'm afraid. $\endgroup$ – Brian Tung Apr 14 '15 at 20:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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