How many ordered triplets ( a , b , c ) of integers are there, subject to 1 ≤ a ≤ 5 0 , 1 ≤ b ≤ 5 0 , 1 ≤ c ≤ 5 0 , such that a + b + c = 1 0 1 ?
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
Oh this is nice! You managed to remove all the constraints to a standard stars and bars question.
What a lovely change of variable! +1
Put a = 5 0 − k 1 ; b = 5 0 − k 2 ; c = 5 0 − k 3 as k 1 , k 2 , k 3 are non-negative integers.
1 5 0 − ( k 1 + k 2 + k 3 ) = 1 0 1 ⟹ k 1 + k 2 + k 3 = 4 9
The non-negative integers solutions are ( 3 − 1 4 9 + 3 − 1 ) = ( 2 5 1 ) = 1 2 7 5
Now the important point is that every solutions from above is allowable because every k i vary from 0 → 4 9 that do not hamper the given limit in the question given.
Therefore,total solutions are 1 2 7 5
Yup, this is identical to Ivan's solution. Nicely presented~
what would had been your approach if instead of 101 the sum was say 80
Let f ( n ) denote the number of ordered triplets ( a , b , c ) of integers such that 1 ≤ a , b , c ≤ 5 0 and a + b + c = n . Then n = 0 ∑ ∞ f ( n ) x n = ( x + x 2 + ⋯ + x 5 0 ) 3 = ( 1 − x x − x 5 1 ) 3 = ( 1 − x ) 3 x 3 − 3 x 5 3 + ⋯ = ( x 3 − 3 x 5 3 + ⋯ ) n = 0 ∑ ∞ ( 2 n + 2 ) x n
Selecting only the coefficient of x 1 0 1 , we have f ( 1 0 1 ) = ( 2 1 0 0 ) − 3 ( 2 5 0 ) = 1 2 7 5 .
Hmmmm, I couldn't follow one step. How did you manage to show that .... = (x^3 - 3x^53 + ... ) is true? I don't see any easy way of expanding it.
I believed I'm missing something fundamental here. Am I wrong?
Log in to reply
I'm not sure if I follow your question. You can expand ( x − x 5 1 ) 3 by either the binomial theorem or just distributing by algebra. Then the power series expansion of ( 1 − x ) 3 1 can be found by the usual calculus methods.
If, on the other hand, you're asking about my use of " ⋯ ", then in this case, it's just a shorthand for "there's other stuff here, but I don't care about them". The powers on x will be 103 and 153, both higher than the 101 we're looking for.
We can use generating functions. For each a,b,c the generating function is ( 1 − x x ( 1 − x 5 0 ) ) . Multiply them we'll get ( 1 − x x ( 1 − x 5 0 ) ) 3 . We're trying to find the 101 coefficient. Since it's being multiplied by x 3 , we can simply get rid of the x 3 and subtract the 101 by 3 resulting in 98, [ x 9 8 ] ( 1 − x ) 3 ( 1 − x 5 0 ) 3 . We can can think of this as what will equal x 9 8 by multiplying the numerator and denomanator. One way by ignoring the x 5 0 we will get n C r ( − 3 , 9 8 ) which by using the general binomial coefficient we'll get n C r ( 1 0 0 , 9 8 ) which equals 4950. Then we have to account where we use 1 x 5 0 . This will be − n C r ( 3 , 1 ) ∗ n C r ( 5 0 , 4 8 ) . It's negative since we coef. next to x 5 0 is negative and n C r ( 5 0 , 4 8 ) since we take 1 x 5 0 and what plus 50 equals 98? 40. So then we'll use the negative binomial coef. again and get n C r ( 5 0 , 4 8 ) . Adding n C r ( 1 0 0 , 9 8 ) with − n C r ( 3 , 1 ) ∗ n C r ( 5 0 , 4 8 ) results in 1275 .
Problem Loading...
Note Loading...
Set Loading...
Substituting x = 5 1 − a , y = 5 1 − b , z = 5 1 − c gives x + y + z = 5 2 with the conditions 1 ≤ x , y , z ≤ 5 0 . However, any integral solution to x + y + z = 5 2 with x , y , z ≥ 1 automatically satisfies x , y , z ≤ 5 0 (otherwise, x + y + z ≥ 5 1 + 1 + 1 > 5 2 ), so we can effectively ignore that condition. Now this is a standard problem: the number of 3-tuples of positive integers whose sum is 52, which is given by the formula ( 3 − 1 5 2 − 1 ) = 1 2 7 5 . (The proof is easy: consider 52 1's in a line and place two separators between some pairs of the 1's (must go between different pairs). 51 places to put 2 separators.)