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
add comment

1 Answer

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
add comment

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.