Find the Coefficient of x^105 in this Product

We find the coefficient of x^105 in the product (1 + x)(1 + x^2)(1 + x^3)...(1 + x^15).
00:00 Combinatorial approach
02:04 Simplifying the problem
04:18 Summary of approach
05:05 Counting ways of multiplying terms
06:23 1 or 2 "x terms"
07:12 3 "x terms"
10:10 4 "x terms"
13:20 5 "x terms"
13:49 Conclusion

[@_Heb_]

I was really proud of myself for figuring out how to solve this beforehand, only to watch the video and realize I messed up and miscounted the final total XD

[@ConManAU]

Ooh, integer partitions! You can also build the results up a little bit iteratively, because you can show that the number of ways to add k terms to get n is related to the number of ways to add k-1 terms to get n-1 and the number of ways to add k terms to get n-k, if I remember correctly.

[@birdbeakbeardneck3617]

Dp

[@riccardofroz]

The question can be reformulated as: how many way you can write 105 as the sum of 1 or more distinct integers between 1 and 15? Since there are 121 coefficients, with the maximum exponent being 120 which has coefficient 1 since 120=1+2+3+...+15, then we can simply subtract 15 from 120 to reach 105. 15 Can be written as the following sums: 15 = 1+14 = 2+13 = 3+12 = 4+11 = 5+10 = 6+9 = 7+8 = 1+2+12 = 1+3+11 = 1+4+10 = 1+5+9 = 1+6+8 = 2+3+10 = 2+4+9 = 2+5+8 = 2+6+7 = 3+4+8 = 3+5+7 = 4+5+6 = 1+2+3+9 = 1+2+4+8 = 1+2+5+7 = 1+3+4+7 = 1+3+5+6 = 2+3+4+6 = 1+2+3+4+5 Hence there are 27 ways of writing 105 as the sum of 1 or more distint integers between 1 and 15.

[@DilipKumar-ns2kl]

❤You are absolutely right in your approach .

[@chengkaigoh5101]

Great explanation ,I considered doing it this way but wasn’t able to get past how to get a sum of 105 .I’m wondering how does non 1 coefficients affect the sum and if there’s a way to generalise it 🤔

[@jardozouille1677]

No cleverer solution than brute-force counting?

[@xizar0rg]

integer partitions are notoriously difficult to generalize, even if in specific instances you can find clever workarounds. While there's a clever workaround here (15, instead of 105), note that it doesn't really make finding "coeff. of x^n" easy, for values close to the 'middle' outside of just finding a method to grind out.

[@mrigayu]

Brilliant explanation! I wonder though what a general approach might be. Is there some sort of way to find all the different ways to sum up to a number (a kind of analog to prime factorization but instead for summing) without listing and counting?

[@DrBarker]

There is a function called the "partition function" which counts the number of ways of splitting up a positive integer into a sum of smaller integers, but I don't think it has a particularly simple closed form. For a relatively small number like 15, I think this is about as simple as it can be, but there may be a more efficient way to compute this for larger numbers.

[@mrigayu]

@@DrBarkerPretty cool! Apparently there exist some recurrence relations, which can probably be used computationally to evaluate the partition function at a given value. Another thing I find interesting is how similar the structure of your problem is to the Euler function. Perhaps there is some connection that would allow for an alternate solution.

[@yurenchu]

Answer: 27 Calculation: ∏ (1 + x^k) , from k=1 to k=15 1+2+3+...+15 = 15*16/2 = 120 120 - 105 = 15 Ways to take numbers from {1, 2, 3, ..., 14, 15} to make a sum of 15 : [Take 1 number: 1 solution] 15 [Take 2 numbers: 7 solutions ] 14+1 13+2 12+3 11+4 10+5 9+6 8+7 [Take 3 numbers: 12 solutions ] 12+2+1 11+3+1 10+4+1 10+3+2 9+5+1 9+4+2 8+6+1 8+5+2 8+4+3 7+6+2 7+5+3 6+5+4 [Take 4 numbers: 6 solutions ] 9+3+2+1 8+4+2+1 7+5+2+1 7+4+3+1 6+5+3+1 6+4+3+2 [Take 5 numbers: 1 solution ] 5+4+3+2+1 1+7+12+6+1 = 27 ==> coefficient of x^105 is 27

[@niom9446]

I think it would be faster if we just expand the expression instead of doing all that rough work and thinking 😂

[@michaelcolbourn6719]

I feel like I'm learning Maths from Tim Key

[@psymar]

heck. I missed the two 1+3+a+b terms.

[@holyshit922]

import sympy as sp x = sp.Symbol('x') y = 1 for n in range(1,16): y *= (1+x**n) y = sp.expand(y) y.coeff(x,105)

[@jursamaj]

I did it in seconds with plain Python: v=[1] z=[] for q in range(15): z=z+[0] a=v+z b=z+v v=[a[i]+b[i] for i in range(len(a))] print(v[105]) Knowing that v[15] gives the same result, I could improve efficiency by limiting len(a) to 15. No point adding up any of the coefficients above 15.

[@eiseks3410]

1

[@davidmurphy563]

Why do I watch these videos? I'm way too stupid to follow.