Application of N choose K, unsure of what is happening

[Jonathanlikesmath]

Homework Statement

How many 7-digit numbers are even or have exactly three digits equal to 0?

Relevant Equations

$|A \cup B| = |A| + |B| - |A \cap B|$

A = set of even 7-digit even numbers $= 9 * 10 * 10 * 10 * 10 * 10 * 5 = 4500000$

B = set of 7 -digit numbers with three 0s $= 9 * { 6 \choose 3} * 9 * 9 * 9 = 131220$

$|A \cap B|$

Portion that does not end in $0 = 9 * { 5 \choose 3} * 9 * 9 * 4 = 9^3{ 5 \choose 3}4 = 29160$

Portion that does end in $0 = 9 * { 5 \choose 2} * 9 *9* 9 * 1 = 9^4 { 5 \choose 2} 1 = 65610$

$|A \cup B| = |A| + |B| - |A \cap B|$ = 4500000 + 131220 - (29160 + 65610) = 4536450

My issue is that I "know" I need to use ${ n \choose k}$ in calculating |B| and in both portions of $|A \cap B|$ but I do not know why I need to use it. From the text, ${ \textbf{Definition}}$ If n and k are integers, then ${n \choose k}$ denotes the number of subsets that can be made by choosing k elements from an n-element set." I do not see the connection between the definition and how it is applied in the above problem.

Jonathan

 

[BvU]

Hello,

First time you use ${n \choose k}$ is

$|B| =$ set of 7 -digit numbers with three 0s $= 9 * { 6 \choose 3} * 9 * 9 * 9 = 131220$

7 positions; first position: 9 choices (1...9).
For the remaining 6 positions there are three zeroes and three non-zeros.
The latter give you $9*9*9$ possibilities.
For the three zeroes there are 6 possible postitions, hence the ${ 6 \choose 3}$.

To explain this, you can write it out:
Name the three zeroes A, B and C.

for A, the first zero, there are 6 possible positions, for B, the second, there remain 5 and for C, the third, there are 4 possible positions to choose from, so 6*5*4 = 120.
But in these 120 every distinct number has been counted six times: once each for ABC, BCA, CAB, BAC, ACB, CBA
($3! = 6$ is the number of possible permutations of three items).

So there are $9^4 \ {6*5*4\over 3*2*1} = {6\choose 3}$ times $9^4$ distinct 7-digit numbers with three zeroes.

Clear so far ?

$\$

 

[PeroK]

My issue is that I "know" I need to use ${ n \choose k}$ in calculating |B| and in both portions of $|A \cap B|$ but I do not know why I need to use it. From the text, ${ \textbf{Definition}}$ If n and k are integers, then ${n \choose k}$ denotes the number of subsets that can be made by choosing k elements from an n-element set." I do not see the connection between the definition and how it is applied in the above problem.

Jonathan

Let's look at a specific example. We have five places to fill with the digits 0-9 but we must have precisely three zeroes. We can describe every way of doing that by specifying:

1) The places where the three zeroes go.

2) The digits in the other two places.

This covers all the possibilities. And the first thing we have to do is calculate how many ways we can place three zeroes in five places. If we label the places A-E, say, then the possibilities for where we put the zeroes are:

ABC, ABD, ABE, ACD, ACE, ADE, BCD, BCE, BDE, CDE

This is precisely all the subsets of the set {A, B, C, D, E} with precisely three members.

There are then a number of ways to confirm that the number of ways to do this is $\frac{5!}{3!(5-3)!}$ in this case and in general it's $\binom n k = \frac{n!}{k!(n-k)!}$.

 

[PeroK]

PS in other words, we set up a one-to-one mapping between placing three zeroes in five places and subsets of a five-element set with precisely three elements.

Setting up this sort of one-to-one mapping is a critical idea generally in combinatoric problems.

 

[Delta2]

Because the three zeros are identical you only need to count which positions they ll get inside the 7 digits and not who will get the first position, who the second and who the third. The number of ways with which we can choose 3 positions from 6 positions (first position can't be zero) is simply $6\choose 3$.

 

[Jonathanlikesmath]

Let's look at a specific example. We have five places to fill with the digits 0-9 but we must have precisely three zeroes. We can describe every way of doing that by specifying:

1) The places where the three zeroes go.

2) The digits in the other two places.

This covers all the possibilities. And the first thing we have to do is calculate how many ways we can place three zeroes in five places. If we label the places A-E, say, then the possibilities for where we put the zeroes are:

ABC, ABD, ABE, ACD, ACE, ADE, BCD, BCE, BDE, CDE

This is precisely all the subsets of the set {A, B, C, D, E} with precisely three members.

There are then a number of ways to confirm that the number of ways to do this is $\frac{5!}{3!(5-3)!}$ in this case and in general it's $\binom n k = \frac{n!}{k!(n-k)!}$.

Thank you for the input, I believe I have a better understanding now. Kinda feels like I am working the n choose k backwards by stating I have three 0s then I need to figure how many ways they can be uniquely arranged within six elements.

 

[PeroK]

Thank you for the input, I believe I have a better understanding now. Kinda feels like I am working the n choose k backwards by stating I have three 0s then I need to figure how many ways they can be uniquely arranged within six elements.

Consider that you have five chairs and three friends. How many distinct ways can your three friends sit on those chairs?

The answer is $5 \times 4 \times 3$. Which can also be written as $\frac{5!}{(5-3)!}$. But, if you consider your friends all equivalent and you don't care who is sitting in what chair, then the number of ways is reduced by $3!$. E.g. there are $3!$ ways of your three friends sitting in the first three chairs.

That's where $\binom 5 3 = \frac{5!}{(5-3)!3!}$ comes from in this context.

You should definitely write all these down to see what's happening. E.g.

$F_1,F_2,F_3,X,X$
$F_1,F_3,F_2,X,X$
$F_2,F_1,F_3,X,X$
$F_2,F_3,F_1,X,X$
$F_3,F_1, F_2,X,X$
$F_3, F_2, F_1, X, X$

These are all the ways that your three friends can sit in the first three chairs. And, if you don't care who is sitting where, then these all map to the same solution:

$F, F, F, X, X$

And, of course, for every one of these solutions, you have $3!$ variations if you do care who is sitting where.

That's how the number of solutions in each case relates to the other.