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.

I am studying combinatorics, and at the moment I am having trouble with the logic behind more complicated counting problems. Given the following list of counting techniques, in which cases should they be used (ideally with a simple, related example):

  • Repeated multiplication (such as $10 \times 9\times 8\times 7$, but not down to $1$)
  • Addition
  • Exponents
  • Combination of the above ($2^6 + 2^5 + 2^4 + 2^3 + 2^2 + 2^1 + 2^0$)
  • Factorials
  • Permutations
  • Combinations
  • A case like this: $2^{10} \times \left({6 \choose 2} + {6 \choose 1} + {6 \choose 0}\right)$
  • A case like this: $13 \times {4 \choose 3} \times {4 \choose 2} \times 12$
  • A case like this: $13 \times {4 \choose 3} \times {4 \choose 2} \times {4 \choose 1}$

Sorry for the crash list of questions, but I am not clear on these issues, especially not good when I have a test in a few days!

Thank you for your time!

share|improve this question
    
I suggest you understand the basics not just memorize end-result formulas. Problems are not usually like give me the permutations of 3 distinct objects. –  Emmad Kareem Nov 5 '12 at 0:54
2  
@Emmad I think that's what the OP is trying to do/ask: to better understand "the logic behind more complicated counting problems", but I agree that one needs to fully understand the basics, and branch out from there! –  amWhy Nov 5 '12 at 1:00
    
@amWhy Yes, that is correct. Basic problems are just that, basic, and not to hard to grasp. –  spryno724 Nov 5 '12 at 1:01

2 Answers 2

up vote 3 down vote accepted

Let me address some of the more general techniques on your list, since the specific ones just appear to be combinations of the general ones.

Repeated Multiplication: Also called "falling factorial", use this technique when you are choosing items from a list where order matters. For example, if you have ten flowers and you want to plant three of them in a row (where you count different orderings of the flowers), you can do this in $10 \cdot 9 \cdot 8$ ways.

Addition: Use this to combine the results of disjoint cases. For example, if you can have three different cakes or four different kinds of ice cream (but not both), then there you have $3 + 4$ choices of dessert.

Exponents: As with multiplication, but the number of choices does not decrease. For example, if you had ample supply of each of your ten kinds of flowers, you could plant $10 \cdot 10 \cdot 10$ different ways (because you can reuse the same kind of flower).

Factorials/Permutations: As with the first example, except you use all ten flowers rather than just three.

Combinations: Use this when you want to select a group of items from a larger group, but order does not matter. For example, if you have five different marbles and want to grab three of them to put in your pocket (so the order in which you choose them does not matter), this can be done in $\binom{5}{3}$ ways.

share|improve this answer
3  
Nice, Austin. This would be a great start for an FAQ/big list re: combinatorics, as it seems there are a lot of people struggling with how to differentiate between different techniques, and/or better understand particular approaches! –  amWhy Nov 5 '12 at 1:07
    
This is FABulous! Could you please also answer the second to last one, where a constant is used? –  spryno724 Nov 5 '12 at 1:07
    
@amWhy I agree. –  spryno724 Nov 5 '12 at 1:08
1  
@spryno724 Don't focus on the constant as such. That formula represents a sequence of four decisions. The first decision can happen in $13$ ways, the second in $\binom{4}{3}$ ways, the third in $\binom{4}{2}$ ways, and the fourth in $12$ ways. I fear any example I make to fit this will feel contrived and not shed any more light than just thinking about it as a sequence of decisions. –  Austin Mohr Nov 5 '12 at 1:11
    
Ok, that is really simple. Thank you, Austin! –  spryno724 Nov 5 '12 at 1:27

The best bet is to try to reduce your counting problem to count sequences of decisions/different types of things. This because it is easy to count such sequences (just multiply through), and stating the problem this way helps avoid leaving out alternatives (or counting them twice). Combine with some basic cases (mostly how number of $k$-subsets of an $n$-set is $\binom{n}{k}$) and you are all set. If this doesn't work, try splitting the situation up into non-overlapping cases that are easy to compute.

Some examples:

  • Number of poker hands with all suites and no pairs: This being five cards, it means that a suit is represented twice. Your hand can be described by the sequence of repeat suit, values for the cards of the repeat suit, values for the other cards in order of spades, hearts, clubs, diamonds (whichever aren't used in the repeat). Can select the repeat suit in 4 ways, its values in $\binom{13}{2}$ ways, and the other cards in 11 to 9 ways, so this gives $4 \cdot \binom{13}{2} \cdot 11 \cdot 10 \cdot 9$.
  • Number of poker hands with at least one figure (J, Q, K): It often happens that it is easier to compute those that don't comply, and subtract from the total. In this case the total is $\binom{52}{5}$, hands with no figures are $\binom{48}{5}$, so you want $\binom{52}{5} - \binom{48}{5}$.
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.