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
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.
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.
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 🤔
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.
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?
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.
@@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.
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.
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
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.
Dp
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.
❤You are absolutely right in your approach .
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 🤔
No cleverer solution than brute-force counting?
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.
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?
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.
@@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.
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
I feel like I'm learning Maths from Tim Key
I think it would be faster if we just expand the expression instead of doing all that rough work and thinking 😂
heck. I missed the two 1+3+a+b terms.
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)
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.
1
Why do I watch these videos? I'm way too stupid to follow.