Let's say I have 3 variables (X, Y and Z)

vortoca

vortoca

Answered question

2022-07-03

Let's say I have 3 variables (X, Y and Z) each one can assume a positive integer value, including zero (0, 1, 2, ..., 100), but the sum of the three must be 100. How many combinations do I have ? Different variables can have the same value.

Answer & Explanation

Kayley Jackson

Kayley Jackson

Beginner2022-07-04Added 16 answers

We use a technique called stars and bars for this question. The general form for stars and bars is that the number of integer solutions to the Diophantine x 1 + x 2 + x 3 + + x k = n such that all numbers ( x 1 , x 2 , x 3 , , x k ) are nonnegative is
( n + k 1 k 1 ) .
Let's walk through a proof of this formula using your question. We are trying to find the number of nonnegatve integer solutions for (X,Y,Z) to the equation X+Y+Z=100. We imagine 100 stars being lined up in a row. When we put in 2 bars splitting the stars into 3 groups, each group represents X,Y, and Z, more specifically the number of stars in each group, which all adds up to the 100 stars. Thus, the number of ways to answer your problem is basically the number of ways to arrange a line of 100 stars and 2 bars to make 102 total objects. By choosing 2 places for the bars, the other places of the other 100 stars are already guaranteed. Thus, we just have to choose 2 places out of 102, which can obviously be done in
( 102 2 ) = 5151 ways.
More generally, to prove that the equation x 1 + x 2 + x 3 + x k = n such that each of ( x 1 , x 2 , x 3 , , x k ) is nonnegative has ( n + k 1 k 1 ) ordered solutions for the k-tuple ( x 1 , x 2 , x 3 , , x k ) we let n stars be lined up in a row. By inserting k-1 bars anywhere between any two stars, we create k groups of stars. Each number x 1 , x 2 , x 3 , , x k would then represent the number of stars in each of the k groups, all adding up to the n stars. Thus, the number of ways desired is the number of ways to arrange n stars and k-1 bars in a line to make n+k-1 total objects, choosing k-1 places, fixing the spots for the another n stars. Expressing the number of ways to do this gives us our desired formula,
( n + k 1 k 1 ) .

Do you have a similar question?

Recalculate according to your conditions!

Ask your question.
Get an expert answer.

Let our experts help you. Answer in as fast as 15 minutes.

Didn't find what you were looking for?