Olympiad level counting (Generating functions)
Why Mathematics Stack Exchange recommends it
Mathematics Stack Exchange users link it as the standard walkthrough of the roots-of-unity filter for counting subset sums, and cite it when asking or answering questions that build on that technique.
Recommended by 3 people across 3 different months, 2022 to 2026.
What it is
A 3Blue1Brown lesson on generating functions, built around the olympiad puzzle of counting subsets of {1,...,2000} whose sum is divisible by 5. It develops the product generating function, evaluates it at complex values, and uses roots of unity to filter out the wanted terms.
What people said
Recommends Nikola Staykov · 2022-08 · Mathematics Stack Exchange · on “How many subsets $T$ of $X$ are such that the sum of the elements of $T$ is divisible by 5?”
Construct a generating function $g(x) = \prod_{i=1}^{2000} (1+x^i) = \sum a_n x^n$ . We are looking for the sum of all $a_n$ where $5/n$ . Precisely those can be filtered out by plugging in powers of the fifth root of unity $\gamma$ . $$\dfrac{\sum_{i=0}^4 g(\gamma^i)}{5} = \dfrac{4\left(\prod_{k=1}^5(1+\gamma^i)\right)^{400}+2^{2000}}{5} = \dfrac{4.2^{400}+2^{2000}}{5}$$ This was just a quick sketch, but there is also a 3 blue 1 brown video on this problem [this video]
Recommends Samuel · 2023-10 · Mathematics Stack Exchange · on “Number of subsets with given sum and length”
Let me tell you, I'd have no idea what you're talking about had I not watched this 3B1B video [this video] (lucky me!). I'll take the time to try digesting your answer. Thank you
Recommends PrincessEev · 2026-02 · Mathematics Stack Exchange · on “What are some applications of the complex exponential in undergraduate analysis problem solving?”
This video [this video] (by 3Blue1Brown: how many subsets of $\{1,\cdots,2000\}$ have a sum divisible by $5$?) and this video [LINK] (by Explain That Again Please) have some applications that could prove extremely interesting to undergrads.
Cites ARG · 2022-05 · Mathematics Stack Exchange · on “Use of $p$-adic numbers in generating functions”
Generating functions are very useful tool to solve various counting problems. One way in which this is done, is to evaluate the generating function at complex values (see e.g. this video of 3b1b [this video] ). Are there cases where one can evaluate a generating function at $p$ -adic numbers to gain information about a combinatorial problem? PS: there is famously a $p$ -adic analogue of the Riemann zeta function, but I'm looking at simpler instances.
Cites Azorfus · 2022-05 · Mathematics Stack Exchange · on “Representing the generating function using binomial theorem.”
Lets say we have a set {1, 2, 3, 4, 5}, There are 32 subsets. Now if we take these subsets and arrange them according to the sum of their members; For eg: The subset {2, 3} would be in the same group as the subset {1, 4} as the sum of their members is the same. If we use the "Generating function" as used in this video: [this video] , We get the number of such arrangements as the coefficients of a long polynomial. Generating function: f(x) = $(1+x^1)(1+x^2) .... (1+x^n)$ , where n is the number of elements in the set. while expanded it forms: $1+x^1+x^2+2x^3+2x^4+3x^5+4x^6+5x^7 + ....$ Now is it possible to represent this function neatly with a single equation using Binomial theorem (Binomial coef
Cites s7eqx9f74nc4 · 2022-06 · Mathematics Stack Exchange · on “Powers of roots of unity are also roots of unity?”
So I was thinking about roots of unity, loosely inspired by this [this video] video (17:28 ff.), in which the author, as best I understand it, says: Suppose $z$ is a 5th root of unity. So, by definition, $z^5=1$ . But positive integer powers of $z$ are also 5th roots of unity, due to the way that powers of $z$ cycle around the unit circle. I tried to come up with an argument that justifies the above statement. I.e. the statement that $z^2, z^3, z^4$ are also 5th roots of unity if $z$ is: If e.g. $z^2$ is a 5th root of unity, then $\left(z^2\right)^5=1$ . But, due to exponent properties, this is the same as $\left(z^5\right)^2=\left(1\right)^2=1$ . So $z^2$ is indeed a 5th root of unity. And simil
Cites Uri · 2022-10 · Mathematics Stack Exchange · on “Complex analysis and generating functions problem or question”
I've been studying some complex analysis lately and I find very intriguing the relation between this field and generating functions. I've seen this video [this video] by 3Blue1Brown and it's really fascinating. Essentially, I'd like to find some kind of problem or question in which I could use this types of techniques in order to ilustrate the procedures for a project. I'd like to remark that this is a project, not actual research, so I just need to find a problem so I can apply this techniques and show some further applications. Ideally, the problem is cloesly related to something like computer science, or anything that allows me to create something, since the project is meant to be original and
Cites Very Interesting · 2023-01 · Mathematics Stack Exchange · on “A Specific Linear Reccurence”
I have been working on a math question that someone asked me, and the following linear recurrence (base cases unspecified) came up: $$ T_{n}=1/6(T_{n-1}+T_{n-2}+T_{n-3}+T_{n-4}+T_{n-5}+T_{n-6})+[rem(n,5)=r] $$ $r$ is a parameter of the recurrence that is an integer between $0$ and $4$ , inclusive. And the term at the end is an Iverson bracket, which evaluates to $1$ if the condition inside is true and $0$ otherwise. Normally when solving linear recurrences, one looks for the homogeneous and inhomogeneous solutions to the recurrence. If you examine the characteristic polynomial of this equation and set it to $0$ , you can figure out that if $T_{n} = a^{n}$ is a solution to the homogeneous var
Cites Darshan P. · 2023-03 · Mathematics Stack Exchange · on “How does this algorithm that multiplies $(1 + x)(1 + x^2)(1 + x^3)(1 + x^4)...$ work?”
# $\color{blue}{p_k(x) = p_{k-1} + x^kp_{k-1}}$ has helped me solve 3B1B-Olympiad Level Problem [this video] . However, my solution [LINK] , as detailed in my post, has an issue in that it cannot handle large numbers. To mitigate this issue, I used `gmpy2.mpz`. Despite this, I have encountered max_recursion in the code [LINK] ., if there are any suggestions that you can offer, I would greatly appreciate it.
Cites jhall · 2024-08 · Mathematics Stack Exchange · on “Subsets whose sum is divisible by 5 and orbits of galois field restricted to subgroup”
In this 3Blue1Brown video [this video] , they use generating functions to count the number of subsets of $\{1,\dots, 2000\}$ whose sum of elements are divisible by $5$ . They construct the generating function $F(z) = (1+z)(1+z^2)\dots(1+z^{2000})$ , they use a root of unity filter, with $\omega=e^{2i\pi/5}$ , to get that this number is $$\frac{1}{5}(F(1)+F(\omega)+F(\omega^2)+F(\omega^3)+F(\omega^4))=\frac{1}{5}(2^{2000}+4\cdot2^{400})$$ . Consider $K=GF(2^{2000})/GF(2)$ , and let $\varphi(x)=x^2$ , where we note that $\left < \varphi \right > = Gal(K)$ . We can find the number of orbits under the action of $\left < \varphi^{400} \right >$ on $K$ using Burnside's lemma. The identity fixes the who