Application of N choose K, unsure of what is happening

  • Thread starter Jonathanlikesmath
  • Start date
  • Tags
    Application
In summary: Putting a zero in the fifth place.This leaves us with four possibilities for the remaining two places:3A, 3B, 3C, 3DThis is again a subset of the set {A, B, C, D} with three members. There are then a number of ways to confirm that the number of ways to do this is ##\frac{4!}{3!(4-3)!}##.In summary, the number of ways to place three zeros in five places is ##\frac{5!}{3!(5-3)!}##.
  • #1
Jonathanlikesmath
17
15
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
 
  • Like
Likes Delta2 and PeroK
Physics news on Phys.org
  • #2
Hello,

First time you use ##{n \choose k}## is
Jonathanlikesmath said:
##|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 ?

##\ ##
 
  • Like
Likes Jonathanlikesmath and PeroK
  • #3
Jonathanlikesmath said:
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)!}##.
 
  • Like
Likes Jonathanlikesmath and Delta2
  • #4
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.
 
  • Like
Likes Jonathanlikesmath and Delta2
  • #5
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##.
 
  • #6
PeroK said:
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.
 
  • #7
Jonathanlikesmath said:
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.
 

Related to Application of N choose K, unsure of what is happening

1. What is N choose K and how is it used in science?

N choose K is a mathematical concept that represents the number of ways to choose a subset of K elements from a set of N elements. In science, it is often used in statistics to calculate probabilities and combinations.

2. Can you give an example of how N choose K is applied in scientific research?

One example is in genetics, where N represents the total number of possible genotypes and K represents the number of specific genotypes that are being studied. N choose K can be used to calculate the probability of certain genotypes occurring in a population.

3. How does N choose K relate to the concept of combinations and permutations?

N choose K is a specific type of combination, where the order of the elements does not matter. Permutations, on the other hand, consider the order of the elements. N choose K is often used when the order of the elements is not important, such as in selecting a committee from a group of people.

4. What are some real-world applications of N choose K outside of scientific research?

N choose K is used in many fields, including economics, computer science, and engineering. It can be used to calculate the number of possible outcomes in a game of chance, the number of possible combinations for a password, or the number of ways to arrange a set of objects.

5. Is N choose K only applicable to discrete sets of elements, or can it be used with continuous variables?

N choose K can be used with both discrete and continuous variables. In the case of continuous variables, the concept is often referred to as "combinations with repetitions", where the same element can be chosen multiple times. This is commonly used in probability and statistics.

Similar threads

  • Precalculus Mathematics Homework Help
Replies
1
Views
757
  • Precalculus Mathematics Homework Help
Replies
7
Views
1K
  • Precalculus Mathematics Homework Help
Replies
6
Views
1K
  • Precalculus Mathematics Homework Help
Replies
1
Views
718
  • Precalculus Mathematics Homework Help
Replies
1
Views
990
  • Precalculus Mathematics Homework Help
Replies
4
Views
793
  • Precalculus Mathematics Homework Help
Replies
19
Views
1K
  • Precalculus Mathematics Homework Help
Replies
6
Views
810
  • Precalculus Mathematics Homework Help
Replies
3
Views
1K
  • Precalculus Mathematics Homework Help
Replies
6
Views
1K
Back
Top