Philosophy of adding extra term in combinatorics question If x 1 </msub> +

Leah Pope 2022-06-30 Answered
Philosophy of adding extra term in combinatorics question
If x 1 + x 2 + x 3 + x 4 20 where x 1 , x 2 , x 3 , x 4 are non negative integers , then how many possible outcome are there ?
It is basic counting problem, we solve it by adding an extra non-negative integer such that x 1 + x 2 + x 3 + x 4 + x 5 = 20, and then use star and bars . Hence the answer is ( 20 + 5 1 20 ) .
However , there is something that stuck in my mind such that why are we adding only one extra variable x 5 , to be clearer , why dont we add more than one extra variable. For example , why did not i find the solution of x 1 + x 2 + x 3 + x 4 + x 5 + x 6 = 20 where the extra terms x 5 and x 6 are non-negative, too. Briefly, why did we restrict ourselved with only one extra variable? Can you enlighten me ?
You can still ask an expert for help

Want to know more about Discrete math?

Expert Community at Your Service

  • Live experts 24/7
  • Questions are typically answered in as fast as 30 minutes
  • Personalized clear answers
Learn more

Solve your problem for the price of one coffee

  • Available 24/7
  • Math expert for every subject
  • Pay only if we can solve it
Ask Question

Answers (2)

America Barrera
Answered 2022-07-01 Author has 23 answers
Step 1
Stars and bars work for i = 1 k x i = n , x i { 0 , 1 , 2 } because we only need k 1 bars to separate k groups of x. Hence, we consider n stars and k 1 bars to obtain ( n + k 1 n ) ways to place the stars, while the bars fill the rest of the positions.
x 1 + x 2 + x 3 + x 4 = m 20 is another way of saying place the 4th bar in the m+4th position. We need the 4th bar because there is at least one group remaining.
Step 2
For example x 1 + x 2 + x 3 + x 4 = 12 20 means in the first 16 positions we placed 12 stars and 4 bars. It happens that if we have simply have 5 groups, the remaining stars are forced into place, so the set of ( x 1 , x 2 , x 3 , x 4 ) forms an one-to-one and onto relation with the set of solutions of x 1 + x 2 + x 3 + x 4 + x 5 = 20. This means we can use stars and bars for the second problem as the answer would be the same as the first. If additional groups and bars (or variables) are introduced, we get instead an one-to-many relationship so we are unable to immediately take advantage of stars and bars.

We have step-by-step solutions for your answer!

Taniyah Estrada
Answered 2022-07-02 Author has 5 answers
Step 1
Because we want to consider unique cases. Using more than one variable overcounts. For example, if you took x 5 and x 6 such that x 1 + x 2 + x 3 + x 4 + x 5 + x 6 = 20.
Say we have x 1 = 1, x 2 = 5, x 3 = 7, x 4 = 2. Then, this is a solution to our original inequality. With our new equation we formed, this would mean that in this one case, we are actually counting the same case six times, as stars and bars would count ( x 5 , x 6 ) to be (0,5), (1,4), (2,3), (3,2), (4,1) and (5,0). That's why we take one variable so we don't count duplicates.

We have step-by-step solutions for your answer!

Expert Community at Your Service

  • Live experts 24/7
  • Questions are typically answered in as fast as 30 minutes
  • Personalized clear answers
Learn more

You might be interested in

asked 2021-08-02
Suppose that A is the set of sophomores at your school and B is the set of students in discrete mathematics at your school. Express each of these sets in terms of A and B.
a) the set of sophomores taking discrete mathematics in your school
b) the set of sophomores at your school who are not taking discrete mathematics
c) the set of students at your school who either are sophomores or are taking discrete mathematics
Use these symbols:
asked 2021-08-18
Discrete Mathematics Basics
1) Determine whether the relation R on the set of all Web pages is reflexive, symmetric, antisymmetric, and/or transitive, where (a,b)R if and only if
I) everyone who has visited Web page a has also visited Web page b.
II) there are no common links found on both Web page a and Web page b.
III) there is at least one common link on Web page a and Web page b.
asked 2021-08-15
How many elements are in the set { 0, { { 0 } }?
asked 2021-07-28

Let A, B, and C be sets. Show that (AB)C=(AC)(BC)
image

asked 2021-08-21

Discrete math Question.
Suppose your friend makes the following English statement "If XY, but X, then we have Y." Convert it into a statement form. Then show that your friend's statement is valid. Is it true that "XY, but X" is equivalent to Y?

asked 2021-05-05

Consider a Poisson process on [0,) with parameter λ and let T be a random variable independent of the process. Assume T has an exponential distribution with parameter v. Let NT denote the number of particles in the interval [0,T]. Compute the discrete density of NT.

asked 2021-08-12
Please assist with this probability question for discrete mathematics.
A class with n kids lines up for recess. The order in which the kids line up is random with each ordering being likely. There are two kids in the class named Betty and Mary. The use of the word "or" in the description of the events, should be interpreted as the inclusive or. That is "A or B" means that A is true, B is true, or both A and B are true.
What is the probability that Betty is first in line or Mary is last in line as a function of n? Simplify your final expression as much as possible and include an explanation of how you calculated this probability.

New questions

Solve your problem for the price of one coffee

  • Available 24/7
  • Math expert for every subject
  • Pay only if we can solve it
Ask Question