Aha, I knew I forgot a scene! In the conclusion, I wanted to add a clip showing how negative binomial coefficients were connected to the negative binomial distribution in statistics. I may as well leave it as an exercise to the reader! Here is a comparison between the binomial distribution and negative binomial distribution. Each trial is a binary outcome (success or fail) with a p chance of success and a 1-p chance of failure. *Binomial distribution:* number of successes k, given n trials Probability mass function: (nCk) p^k (1-p)^(n-k) *Negative binomial distribution:* number of failures k, given n successes Probability mass function: (-1)^k (-nCk) p^n (1-p)^k = [(k+n-1)Ck] p^n (1-p)^k See if you can derive the probability mass function for each of them (Remember, in the negative binomial distribution, the very last trial must be a success, as that tells us when to stop!), and then use the combinatorial reciprocity theorem to rewrite it using negative binomial coefficients!
Great video! To answer your final question, these reciprocity theorems absolutely do have real world applications. In quantum mechanics, the statistical properties of bosons (like photons, particles of light) and fermions (like electrons and protons, particles of matter) are related by a n -n combinatorial reciprocity like the ones in your video. Here fermions correspond to the "excluding the boundary" counting problem and bosons to the one "including the boundary". This is at the heart of the famous Pauli exclusion principle that two identical fermions aren't allowed to be in the same state, while bosons are allowed to and do group together in the same state (i.e., it helps explain why matter is solid while light can pass through itself!). This also has more mathematical applications in the representation theory of Lie groups where e.g. the representations of SO(2n) and Sp(n) are related; a good book to learn about this is "Group Theory" by P. Cvitanovic.
Came here from the peer review! This is an extraordinary video! I did know the one about chromatic polynomials counting the acyclic orientations, but the examples given in the video convinces me that it is actually part of something more! Honestly shocked at how few views this gets - UA-cam algorithm, do your thing.
I've been watching a lot of the SoME2 submissions, and this one is one of my favorites I've seen. Incredible visuals, narration, and a super interesting topic. I will say it's also one of the more difficult ones to follow: that might just be the topic, but I had to rewind a few times and rewatch things to understand them, especially in the generating functions and multi-set section. You've earned a new subscriber and I'll be watching whatever you make next either way, but I wouldn't mind a few more examples or spending a little longer on the logic/derivation of things in the future. Anyway, amazing video and thank you so much for spending all the time to make it!
18:21 "Thankfully, both chromatic polynomials and flow polynomials are pretty easy to compute algorithmically" I don't think that's right, at least for chromatic polynomials. From watching the video, my understanding is that a chromatic polynomial f with input n for a graph G is the number of ways G can be colored with n colors yeah? Then for any arbitrary graph, we could find its chromatic polynomial and plug in 3, and check if the output is 0 or not to see if the graph is 3 colorable. But... 3 colorability is NP-complete.
Nice observation! I wasn't being very technical when I said "pretty easy". Using the deletion-contraction algorithm I hinted at in the video, the algorithm running time is super-exponential in the worst cases (only exponential in the 3-colorable case specifically using other algorithms) which lines up with what you said! I said "pretty easy" here because I imagine that in most cases that most people would use, the polynomials are still reasonably computable. If anyone needs to find the chromatic polynomial more generally for giant graphs, I apologize for being misleading!
This is an inspiring piece of work! If there is any criticism I think that some of the explanations don't allow much 'take up time' but I guess that can be remedied by pausing. Anyway, thanks so much for all the hard work that went into this video, it has really renewed my interest in combinatorics!
If S has k points on its edges and area A, then nS has nk points on its edges and area n^2A. According to Pick’s theorem, n^2A=x+nk/2-1 f(n)=n^2A-nk/2+1 f(-n) denotes that because it’s like adding nk to f(n), which is as we found is the number of points on the edges of S
Your style is sooo good. This video and the other one with the algorithm to find closed form formulas for some hypergeometric series are impeccable. I hope you make more like them in the future.
Awesome video! I knew the book and really enjoyed seeing a video about it that explains essential examples so well. Makes me wonder: what does f(n*i) count, where i is the complex unit.
I stopped at 21:00 when you suggested finding the polynomial for the partially ordered graph myself, half an hour later came back with a solution, pressed play, and boom! my solution, right there in the video. Time well wasted. uhh I mean spent.
I don't understand why |Y| = (-1)^k \cdot ... Why is the -1 there? If I choose n=3 and k=1, I got three multisets of [3] with 1 element. If I choose n = 3 and k=2, I got 6 of them. None of those are negative. Also, why should that be equal to f(-n)? We didn't explain that much enough for me
If you plug in a negative n instead of a positive n, it's possible (but not always) that your result will be negative. For instance, in the expression (n choose k), plugging in n=-3 and k=1 gives -3, which is why we need the absolute value. It is equal to f(-n) almost by definition. We first declare that there is some combinatorial class Y that equals this, and then we try to find that class.
@@zhulimath So, when you write f(-n)=|y|, did you mean to write f(-n)=(-1)^k * |y|? Because on the preceding slide, you wrote |y| = (n+k-1 choose k), but on this slide you write |y| = (-1)^k * (n+k-1 choose k). What are we missing?
If you take the absolute value first, which is guaranteed to be positive, and then multiply by a power of -1, which is sometimes negative, now the value is sometimes negative, which is not what we want. We want it to always be positive, in which case both expressions give us equivalent results. Take f(n) = (n choose 3) as an example. (n choose 3) = n*(n-1)(n-2)/6. f(-5) = (-5)(-6)(-7)/6 = -35 This is negative, and we get this before we apply absolute value or multiply a power of -1. Obviously, taking the absolute value would make it positive, but we can also multiply a -1 factor for each of the negative factors in the numerator. By multiplying (-1)^3, this will also make the function value positive. Of course, we only needed one -1 factor, we didn't need 3 of them, but thinking about it this way gives us a simple formula, as we know exactly how many -1 factors we need to make the function value positive, and also allows our formula to extend and play nicely with other ideas!
@@zhulimathThanks, we get that for f(-n). But how is (n+k-1 choose k) = |y| = (-1)^k * (n+k-1 choose k) for all multisets? This doesn't seem to work when k is odd.
It does work! Let's take a closer look at a specific example, where k=3: f(n) = n choose 3 = n(n-1)(n-2)/6 f(-n) = (-n)(-n+1)(-n+2)/6 |f(-5)| = |(-5)(-6)(-7)/6| = |-35| = 35 g(n) = (n+3-1) choose 3 g(5) = (5+3-1) choose 3 = 7 choose 3 = 7(6)(5)/6 = 35 Your mistake was saying that (n+k-1) choose k = (-1)^k (n+k-1) choose k It should be -n choose k = (-1)^k (n+k-1) choose k
The link to the paper doesn't work. Man, it's impossible for me to choose favorite (pun intended) out of the some2 entries, but this one certainly is up there; I got really excited of 3-4!
Haha, nice catch! Was thinking the same thing, "hold on, this intro sounds oddly familiar ... damn, it's actually Kapustin's Toccatina Etude! How cultured 🧐"
Uff, I am already lost in the first two minutes. At 0:08 you can see the well known "n choose k" scenario with the usual formula. So, we have a numerator solely dependent on n (it's n!) and a denominator dependent on n and k (it's n! * (n-k)!). So far so good. But in 1:26 where k has been set to 3 suddenly the numerator changes to from n! to n(n-1)(n-2) for all possible n, and the denominator is suddenly a fixed 6 for all possible n. Then n has been set to -2 and suddenly the result is -4 even though a n=-2 would mean negative integer faculties in both the numerator and the denominator that do not exist (even the gamme function does not change this). And in 1:44 the numerator is suddenly dependent on n and k but the demoninator only dependant on k. I am really lost here.
This is actually quite straightforward. If you only look at the n!/(n-k)! part, you will notice that everything in the denominator cancels with something in the numerator. Let's try an example with n=7, k=3. Plugging in, we get 7!/4!. Notice that 7! = 7*6*5*4!. Our expression can be written as 7*6*5*4!/4!. The 4! cancels out, and you're left with 7*6*5. The full expression 7 choose 3 is therefore just the 7*6*5 expression we found divided by 3!=6. If you try a different n value, you will get the numerator to behave similarly. For instance, 12 choose 3 is 12*11*10/6 because the 9! cancels out. The generalized form of n choose 3 therefore is n(n-1)(n-2)/6. Let me know if that helps!
If you replace binomial coefficient with factorial definition, then replace the factorials with their definition in terms of the Gamma function, then simplify, do you come up with the same results?
@@zhulimath aren't the negative integer values to the gamma function essential singularities? I assume you'd have to do a lot of work to show that it still works when the singularities combine in the ratio.
why do you assert that it's necessary for the output to be positive? absolute value causes problems, especially for complex numbers which are useful to plug into generating functions, is it really needed?
In geometric algebra, for n basis vectors (or dimensions), there are "n choose k" k-blades. Which group of related objects are counted by "-n choose k"?
I don't know, but I would assume if we "include the boundary" it works, so we're allowed to choose the blades such that their vectors are linearly dependent (so, not necessarily a basis but at least a spanning set), namely, we're allowed to multi-count the same vector from the basis. That means this represents any ordered linear combination? "add a in the direction of 1, then add b also in the direction of 1" would be a 2-unblade (or perhaps a 2-coblade)?
How does the formula at 21:40 have 1/12? If you plug in n=3 that gives 1, which seems wrong, as there are several ways to order the numbers if nodes can be equal to the previous (1,1,1,1 for example)
When you plug in a positive integer n, it gives you the number of mappings preserving strict order, so 1,1,1,1 is not allowed. The only way to assign integers is 1,2,2,3, so f(3) is in fact 1. If you want the nodes to be equal, this is preserving weak order, not strong order, so you would be plugging in a negative integer, for instance -3, which is the combinatorial reciprocity.
There are several major problems to this approach: 1. A Taylor series expansion requires a continuous and infinitely differentiable function, which isn't the case for the discrete expressions we examined in the video. 2. A Taylor series doesn't always have a nice radius of convergence, which doesn't make it particularly useful to find arbitrary values of the function as a formula. 3. Even if we did find a Taylor series (for instance by analytic continuation), it's still an infinite expression, which we typically do not accept as a "closed form". Usually, we refer to closed forms as finite expressions.
Apologies, there have been some very dramatic changes to my personal life that need to get sorted out. I appreciate people anticipate my content, and will get back to producing content as soon as I can!
Aha, I knew I forgot a scene! In the conclusion, I wanted to add a clip showing how negative binomial coefficients were connected to the negative binomial distribution in statistics. I may as well leave it as an exercise to the reader!
Here is a comparison between the binomial distribution and negative binomial distribution. Each trial is a binary outcome (success or fail) with a p chance of success and a 1-p chance of failure.
*Binomial distribution:* number of successes k, given n trials
Probability mass function: (nCk) p^k (1-p)^(n-k)
*Negative binomial distribution:* number of failures k, given n successes
Probability mass function: (-1)^k (-nCk) p^n (1-p)^k = [(k+n-1)Ck] p^n (1-p)^k
See if you can derive the probability mass function for each of them (Remember, in the negative binomial distribution, the very last trial must be a success, as that tells us when to stop!), and then use the combinatorial reciprocity theorem to rewrite it using negative binomial coefficients!
Great video! To answer your final question, these reciprocity theorems absolutely do have real world applications. In quantum mechanics, the statistical properties of bosons (like photons, particles of light) and fermions (like electrons and protons, particles of matter) are related by a n -n combinatorial reciprocity like the ones in your video. Here fermions correspond to the "excluding the boundary" counting problem and bosons to the one "including the boundary". This is at the heart of the famous Pauli exclusion principle that two identical fermions aren't allowed to be in the same state, while bosons are allowed to and do group together in the same state (i.e., it helps explain why matter is solid while light can pass through itself!). This also has more mathematical applications in the representation theory of Lie groups where e.g. the representations of SO(2n) and Sp(n) are related; a good book to learn about this is "Group Theory" by P. Cvitanovic.
Came here from the peer review!
This is an extraordinary video! I did know the one about chromatic polynomials counting the acyclic orientations, but the examples given in the video convinces me that it is actually part of something more!
Honestly shocked at how few views this gets - UA-cam algorithm, do your thing.
Hey, huge fan! Thanks for watching, I hope you took a peek at the source, because it dives into a lot more detail.
I've been watching a lot of the SoME2 submissions, and this one is one of my favorites I've seen. Incredible visuals, narration, and a super interesting topic. I will say it's also one of the more difficult ones to follow: that might just be the topic, but I had to rewind a few times and rewatch things to understand them, especially in the generating functions and multi-set section. You've earned a new subscriber and I'll be watching whatever you make next either way, but I wouldn't mind a few more examples or spending a little longer on the logic/derivation of things in the future. Anyway, amazing video and thank you so much for spending all the time to make it!
This channel deserves WAY more attention.
This is by far the best quality submission I've seen! This better win!
18:21 "Thankfully, both chromatic polynomials and flow polynomials are pretty easy to compute algorithmically"
I don't think that's right, at least for chromatic polynomials.
From watching the video, my understanding is that a chromatic polynomial f with input n for a graph G is the number of ways G can be colored with n colors yeah?
Then for any arbitrary graph, we could find its chromatic polynomial and plug in 3, and check if the output is 0 or not to see if the graph is 3 colorable.
But... 3 colorability is NP-complete.
Nice observation! I wasn't being very technical when I said "pretty easy". Using the deletion-contraction algorithm I hinted at in the video, the algorithm running time is super-exponential in the worst cases (only exponential in the 3-colorable case specifically using other algorithms) which lines up with what you said!
I said "pretty easy" here because I imagine that in most cases that most people would use, the polynomials are still reasonably computable. If anyone needs to find the chromatic polynomial more generally for giant graphs, I apologize for being misleading!
This is really fascinating, and beautifully explained. Thanks for making it.
Although most comments contain praise to your work, one more is less than you deserve. Keep it up!
This is an inspiring piece of work! If there is any criticism I think that some of the explanations don't allow much 'take up time' but I guess that can be remedied by pausing.
Anyway, thanks so much for all the hard work that went into this video, it has really renewed my interest in combinatorics!
If S has k points on its edges and area A, then nS has nk points on its edges and area n^2A. According to Pick’s theorem, n^2A=x+nk/2-1
f(n)=n^2A-nk/2+1
f(-n) denotes that because it’s like adding nk to f(n), which is as we found is the number of points on the edges of S
Your style is sooo good. This video and the other one with the algorithm to find closed form formulas for some hypergeometric series are impeccable. I hope you make more like them in the future.
YES! what a finding! bless the algorithm
WAIT YOU'RE THAT GUY
nice one my fren
@@jaopredoramires Hm? What guy?
@@zhulimath you, from the other video
Oh xD
The infromation was amazing. The music was astoundingly terrific.
nice username
Awesome video! I knew the book and really enjoyed seeing a video about it that explains essential examples so well. Makes me wonder: what does f(n*i) count, where i is the complex unit.
You're beautiful, man.
🤨📸
I stopped at 21:00 when you suggested finding the polynomial for the partially ordered graph myself, half an hour later came back with a solution, pressed play, and boom! my solution, right there in the video.
Time well wasted. uhh I mean spent.
Very nice! It's a nontrivial exercise, and I think it's pretty good practice.
I'm new here. I hope to see more of your new videos. More derivation of formulas, more amazing facts about numbers.
High quality work! Great job!
This was way way way more interesting than I had anticipated
I don't understand why |Y| = (-1)^k \cdot ...
Why is the -1 there?
If I choose n=3 and k=1, I got three multisets of [3] with 1 element.
If I choose n = 3 and k=2, I got 6 of them.
None of those are negative.
Also, why should that be equal to f(-n)? We didn't explain that much enough for me
If you plug in a negative n instead of a positive n, it's possible (but not always) that your result will be negative. For instance, in the expression (n choose k), plugging in n=-3 and k=1 gives -3, which is why we need the absolute value.
It is equal to f(-n) almost by definition. We first declare that there is some combinatorial class Y that equals this, and then we try to find that class.
@@zhulimath So, when you write f(-n)=|y|, did you mean to write f(-n)=(-1)^k * |y|? Because on the preceding slide, you wrote |y| = (n+k-1 choose k), but on this slide you write |y| = (-1)^k * (n+k-1 choose k). What are we missing?
If you take the absolute value first, which is guaranteed to be positive, and then multiply by a power of -1, which is sometimes negative, now the value is sometimes negative, which is not what we want. We want it to always be positive, in which case both expressions give us equivalent results.
Take f(n) = (n choose 3) as an example. (n choose 3) = n*(n-1)(n-2)/6.
f(-5) = (-5)(-6)(-7)/6 = -35
This is negative, and we get this before we apply absolute value or multiply a power of -1. Obviously, taking the absolute value would make it positive, but we can also multiply a -1 factor for each of the negative factors in the numerator. By multiplying (-1)^3, this will also make the function value positive.
Of course, we only needed one -1 factor, we didn't need 3 of them, but thinking about it this way gives us a simple formula, as we know exactly how many -1 factors we need to make the function value positive, and also allows our formula to extend and play nicely with other ideas!
@@zhulimathThanks, we get that for f(-n). But how is (n+k-1 choose k) = |y| = (-1)^k * (n+k-1 choose k) for all multisets? This doesn't seem to work when k is odd.
It does work! Let's take a closer look at a specific example, where k=3:
f(n) = n choose 3 = n(n-1)(n-2)/6
f(-n) = (-n)(-n+1)(-n+2)/6
|f(-5)| = |(-5)(-6)(-7)/6| = |-35| = 35
g(n) = (n+3-1) choose 3
g(5) = (5+3-1) choose 3 = 7 choose 3 = 7(6)(5)/6 = 35
Your mistake was saying that
(n+k-1) choose k = (-1)^k (n+k-1) choose k
It should be
-n choose k = (-1)^k (n+k-1) choose k
this is quality! hope to see more from u !!
Very nice!
The link to the paper doesn't work. Man, it's impossible for me to choose favorite (pun intended) out of the some2 entries, but this one certainly is up there; I got really excited of 3-4!
I have swapped out the link in the description. It is a slightly different version but the content is largely the same. Hopefully it works now!
This beautiful. Love math. Such wow.
clicked the video, hold on, kapustin!
Haha, nice catch! Was thinking the same thing, "hold on, this intro sounds oddly familiar ... damn, it's actually Kapustin's Toccatina Etude! How cultured 🧐"
This was great, thanks!
Great video :D
Thank you!
Uff, I am already lost in the first two minutes. At 0:08 you can see the well known "n choose k" scenario with the usual formula. So, we have a numerator solely dependent on n (it's n!) and a denominator dependent on n and k (it's n! * (n-k)!). So far so good. But in 1:26 where k has been set to 3 suddenly the numerator changes to from n! to n(n-1)(n-2) for all possible n, and the denominator is suddenly a fixed 6 for all possible n. Then n has been set to -2 and suddenly the result is -4 even though a n=-2 would mean negative integer faculties in both the numerator and the denominator that do not exist (even the gamme function does not change this). And in 1:44 the numerator is suddenly dependent on n and k but the demoninator only dependant on k. I am really lost here.
This is actually quite straightforward. If you only look at the n!/(n-k)! part, you will notice that everything in the denominator cancels with something in the numerator.
Let's try an example with n=7, k=3. Plugging in, we get 7!/4!. Notice that 7! = 7*6*5*4!. Our expression can be written as 7*6*5*4!/4!. The 4! cancels out, and you're left with 7*6*5.
The full expression 7 choose 3 is therefore just the 7*6*5 expression we found divided by 3!=6. If you try a different n value, you will get the numerator to behave similarly. For instance, 12 choose 3 is 12*11*10/6 because the 9! cancels out.
The generalized form of n choose 3 therefore is n(n-1)(n-2)/6.
Let me know if that helps!
Goated video
Cool video
If you replace binomial coefficient with factorial definition, then replace the factorials with their definition in terms of the Gamma function, then simplify, do you come up with the same results?
You do! The Gamma function is the key to extending binomial coefficients to complex inputs!
@@zhulimath nice, was hoping to hear something about the interpretation of complex binomial coefficients when I clicked play. next video?
@@thenumbernine Unlikely I will get to it anytime soon, but I'll see what I can do!
@@zhulimath aren't the negative integer values to the gamma function essential singularities? I assume you'd have to do a lot of work to show that it still works when the singularities combine in the ratio.
All the others are for free! Thank you!
wow.... WOW, this is fantastic
1:19 the bast part of the video
Amazing
why do you assert that it's necessary for the output to be positive? absolute value causes problems, especially for complex numbers which are useful to plug into generating functions, is it really needed?
Because we don't have any examples of negative numbers of things in counting problems. For example, you can't choose a negative number of colors.
You are great
In geometric algebra, for n basis vectors (or dimensions), there are "n choose k" k-blades.
Which group of related objects are counted by "-n choose k"?
I don't know, but I would assume if we "include the boundary" it works, so we're allowed to choose the blades such that their vectors are linearly dependent (so, not necessarily a basis but at least a spanning set), namely, we're allowed to multi-count the same vector from the basis.
That means this represents any ordered linear combination? "add a in the direction of 1, then add b also in the direction of 1" would be a 2-unblade (or perhaps a 2-coblade)?
I followed you because I like math and you had 666 subscribers
How does the formula at 21:40 have 1/12? If you plug in n=3 that gives 1, which seems wrong, as there are several ways to order the numbers if nodes can be equal to the previous (1,1,1,1 for example)
When you plug in a positive integer n, it gives you the number of mappings preserving strict order, so 1,1,1,1 is not allowed. The only way to assign integers is 1,2,2,3, so f(3) is in fact 1. If you want the nodes to be equal, this is preserving weak order, not strong order, so you would be plugging in a negative integer, for instance -3, which is the combinatorial reciprocity.
@@zhulimath understood now, thanks
1:11i don't think negatives work since fractions work but oh negative integers don't result in errors of the gamma?
I guess the error was n choose negative number
2:01
You need to connect to the negative factorial.
Don't know if it was me but the explanation of multisets wasn't clear at all
Is there anything you would like clarification on?
1/2 choose 3 when 0:14
HOW DARE YOU CALL 4:51 AN ABUSE OF NOTATION?! it seems perfectly acceptable to me
Just like my friends their numbers are also imaginary 🙂
who’s in the thumbnail
probably him
just expand it into a Taylor series and you have the result :)
There are several major problems to this approach:
1. A Taylor series expansion requires a continuous and infinitely differentiable function, which isn't the case for the discrete expressions we examined in the video.
2. A Taylor series doesn't always have a nice radius of convergence, which doesn't make it particularly useful to find arbitrary values of the function as a formula.
3. Even if we did find a Taylor series (for instance by analytic continuation), it's still an infinite expression, which we typically do not accept as a "closed form". Usually, we refer to closed forms as finite expressions.
Upload something.
Chill, Zhuli will get to it when they can!
Apologies, there have been some very dramatic changes to my personal life that need to get sorted out. I appreciate people anticipate my content, and will get back to producing content as soon as I can!
Why do you think that music fits on this? Channel blocked. Bye.