0
$\begingroup$

I've just started learning combinatorics, and have the following problem in reasoning.

One of the formulae for ${n \choose k}$ is: $${n \choose k} =\frac{n!}{(n-k)!k!}= \frac{n \ \times \ (n-1) \ \times \ (n-2) \ \times \ ... \ \times \ (n-k+1)}{k \ \times \ (k-1) \ \times \ (k-2) \ \times \ ...\ \times \ 1}$$

My understanding is that we need the denominator to avoid the problem of counting multiple times. For example, this would help avoiding counting the sets {1,2,3,4} and {2,1,4,3} twice, if we want to count the number of 4-elements subsets of n elements.

My problem lies in analyzing other combinatorial situations, where I often don't know if I need to do something similar to the above. Am I correct to assume that every time we actually want all $k!$ permutations to be counted (i.e. we don't mind and actually need both {1,2,3,4} and {2,1,4,3} in the example above to be counted), then we don't have to worry about double counting?

$\endgroup$
3
$\begingroup$

You are right. When you want to arrange $ k $ from total $ n $ elements and order is counted, there are $$ A_n^k=\frac{n!}{(n-k)!}={n\choose k}\cdot k! $$

ways to do this! You can take it as first choosing $ k $ elements without considering the order, then you permute them in all possible ways.

$\endgroup$
0
$\begingroup$

That is the main difference between permutation and combination In permutation we never count the order but in combination, we need to check every order of elements too

$\endgroup$

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.