You can actually make the first proof slightly more direct: To pick two line segments, start by picking four points among n+1 points: the original n, and a special wildcard point. That's directly (n+1) choose 4. It suffices to show there are always three ways to pick two line segments from there. If you picked the wildcard, simply pick which of the other three points is the shared one. If you didn't, start at an arbitrary point and pick which of the three others it connects to. (Obviously, this is the same case split as in your proof, but I enjoyed the fact that I could bake in the n+1 without any algebra. Yours is probably easier to follow, though …)
I think the question of Bin(Bin(n,2),k) is related to the OEIS entry A325010. In particular, they give a formula for an array of numbers they call T(n,k) and give a formula for it. And it looks to me that Bin(Bin(n,2),k) = Sum[T(k,m) Bin(n,m),{m,1,2k}]. Perhaps you can relate the problem of counting sets of edges to the problem describing the array
Indeed, I think I've found the relation between the problems. The values we're after are the T(k,m), the coefficient in front of Bin(n,m) in the expansion of Bin(Bin(n,2),k). The analysis in the video, put another way, says that T(k,m) is the number of labelled graphs with m vertices and k edges, such that every vertex has positive degree. In the sequence A325010, T(k,m) is the number of chiral pairs of facet colourings of the k-dimensional hypercube using exactly m colours, that is to say colourings in which each of the m colours is used at least once. If we can show these are the same, we'll indeed have a formula for expanding the nested binomial coefficient Bin(Bin(n,2),k) in terms of the ordinary binomial coefficients Bin(n,m). We first note that the colourings of the hypercube are counted up to symmetries of the full hypercube group. That is, all rotations and reflections, as we are counting chiral pairs as a single object, and each member of a chiral pair is a reflection of the other. Next we consider the action of the full hypercube group on the k axes joining opposite facets of the hypercube, the axes normal to the facets. The action of the full hypercube group can permute these axes in any order, as well as being able to reflect any axis. As such, any achiral colouring has two opposite faces of the same colour and any chiral colouring has each pair of opposite faces differently coloured. As the full hypercube group can rearrange the axes any way we like, pick some bijection between the k axes and the k edges of a graph. From any chiral pair colouring we can construct a labelled graph by letting the m colours be mapped to the m labelled vertices, and the two colours of opposite faces correspond to an edge of the graph having endpoints corresponding to the vertices with the same labels as the colours. As the colouring uses exactly m colours, the graph has m vertices each with positive degree, and as the chiral pair colourings have opposite faces always differently coloured, no edge has both of its endpoints the same. Similarly, from any labelled graph on m vertices, all of positive degree, we can colour opposite faces of each axis according to the vertex labels of the corresponding edge, producing a member of a chiral pair colouring of the cube, with each colour used at least once, as each vertex appears as an endpoint. So indeed these T(k,m) in the two problems are equivalent and we obtain a recurrence the coefficients, which allows for quicker calculation of the coefficients and maybe with more work with generating functions, an exact formula
Thank you very much for your explaination, I really appreciate it! I'm trying to digest it, gonna take a while! I expected that there should exist a straightforward solution for this, but apparentnly it's more complicated than I imagined.
at 11:34 you divided by 2 as order does not matter but in combination i think order always doesn't matter ? it matters in permutation i am sorry if i am wrong but i am unable to accept the division by 2 fact also why we didn't divided by 2 in n choose 2 choose 3 case because in that case we have line segments instead of triangle and AB=BA ?...btw a great video basic to advance all the best for SOMEpi win 🏆. i already rated you outstanding😉.thankyou...
Very good question! In fact I should have explained it better in the video. You're right, when we use a combination, there's no order. But when we multiply two combinations, it's different. Consider this case: We draw the first triangle called ABC. As a result, DEF will be the second triangle. So our two triangles will be ABC and DEF. If the first triangle was DEF, then ABC would be the second one. Again, our two triangles will be ABC and DEF. That's why we need to divide by 2 (in fact we need to divide by 2 factorial). For "(n choose 2) choose 3", let's consider the first case. We have six points, and we want to draw 3 lines. We can count by picking the first line out of 6 points, then second line given the remaining 4 points, and finally the third line given the remaining 2 points. The number of ways is (6 choose 2) * (4 choose 2) * (2 choose 2) / 3!. We divide by 3 factorial because order does not matter. In the video I used a different way of counting this which does not require dividing, because I'm specifying which nodes are used and which ones are remained. I do not have an academic education on combinatorics, I've only studied random things on the internet, so I can't recommend any resources. It wasn't me who called it double counting, and I don't know who was the first who came up with this name. Thank you very much for your comment!
@@Upsampled you said "The number of ways is (6 choose 2) * (4 choose 2) * (2 choose 2) / 3!. We divide by 3 factorial because order does not matter." but recently i thought should it not be (6 choose 2)* 1/2(for as AB=BA)(4 choose 2) *1/2(same reason)*(2 choose 2). whats the error in my reasoning ? later i understood that the 3 ! is taken in account for the same thing the way in which 2 points taken are taken in which order i just not deleted the post becz i want to tell you that at 9:22 you can also say that take (n choose 4) *(4 choose 1)(to take account from which point to start out of 4 ) *(3 choose 1) for which point to end at !) ty...you helped me a lot btw if you wish i certainly would love to join you ! also i edited it 3rd time because i want to mention what a beautiful line you wrote ! "when we use a combination, there's no order. But when we multiply two combinations, it's different. " just magnificient
I really liked this, but surely, the FINAL final boss is (n choose k) choose m, k
That's the final boss in a different league! :)
From Mathoverflow: "A weight formula for subgraphs of K_n and log-concavity of nested binomial coefficients"
@@pierf.car.2592 Awsome, thank you!
Very good. Thank you.
With luck and more power to you.
hoping for more videos.
Great work, excited to see more videos from you 🔥
@@SantosAdducci Thank you! Glad you liked it!
This channel is highly underrated. I just watched the other video, and it was also amazing.
Thank you very much for your comment! I'm so glad you enjoyed watching the videos.
Nice work!
loved it! Keep posting please ❤
This was beautifully done
You can actually make the first proof slightly more direct: To pick two line segments, start by picking four points among n+1 points: the original n, and a special wildcard point. That's directly (n+1) choose 4. It suffices to show there are always three ways to pick two line segments from there. If you picked the wildcard, simply pick which of the other three points is the shared one. If you didn't, start at an arbitrary point and pick which of the three others it connects to.
(Obviously, this is the same case split as in your proof, but I enjoyed the fact that I could bake in the n+1 without any algebra. Yours is probably easier to follow, though …)
that's genius. Nice one
Thank you
I think the question of Bin(Bin(n,2),k) is related to the OEIS entry A325010. In particular, they give a formula for an array of numbers they call T(n,k) and give a formula for it. And it looks to me that Bin(Bin(n,2),k) = Sum[T(k,m) Bin(n,m),{m,1,2k}]. Perhaps you can relate the problem of counting sets of edges to the problem describing the array
Indeed, I think I've found the relation between the problems. The values we're after are the T(k,m), the coefficient in front of Bin(n,m) in the expansion of Bin(Bin(n,2),k). The analysis in the video, put another way, says that T(k,m) is the number of labelled graphs with m vertices and k edges, such that every vertex has positive degree. In the sequence A325010, T(k,m) is the number of chiral pairs of facet colourings of the k-dimensional hypercube using exactly m colours, that is to say colourings in which each of the m colours is used at least once.
If we can show these are the same, we'll indeed have a formula for expanding the nested binomial coefficient Bin(Bin(n,2),k) in terms of the ordinary binomial coefficients Bin(n,m). We first note that the colourings of the hypercube are counted up to symmetries of the full hypercube group. That is, all rotations and reflections, as we are counting chiral pairs as a single object, and each member of a chiral pair is a reflection of the other. Next we consider the action of the full hypercube group on the k axes joining opposite facets of the hypercube, the axes normal to the facets. The action of the full hypercube group can permute these axes in any order, as well as being able to reflect any axis. As such, any achiral colouring has two opposite faces of the same colour and any chiral colouring has each pair of opposite faces differently coloured.
As the full hypercube group can rearrange the axes any way we like, pick some bijection between the k axes and the k edges of a graph. From any chiral pair colouring we can construct a labelled graph by letting the m colours be mapped to the m labelled vertices, and the two colours of opposite faces correspond to an edge of the graph having endpoints corresponding to the vertices with the same labels as the colours. As the colouring uses exactly m colours, the graph has m vertices each with positive degree, and as the chiral pair colourings have opposite faces always differently coloured, no edge has both of its endpoints the same. Similarly, from any labelled graph on m vertices, all of positive degree, we can colour opposite faces of each axis according to the vertex labels of the corresponding edge, producing a member of a chiral pair colouring of the cube, with each colour used at least once, as each vertex appears as an endpoint.
So indeed these T(k,m) in the two problems are equivalent and we obtain a recurrence the coefficients, which allows for quicker calculation of the coefficients and maybe with more work with generating functions, an exact formula
Thank you very much for your explaination, I really appreciate it! I'm trying to digest it, gonna take a while! I expected that there should exist a straightforward solution for this, but apparentnly it's more complicated than I imagined.
Impressive.
((n choose k) choose 2) = (n choose k)*((n choose k) - 1)/2. Falls right out of the factorial definition of (m choose 2)
Great video!
🔥🔥🔥
at 11:34 you divided by 2 as order does not matter but in combination i think order always doesn't matter ? it matters in permutation i am sorry if i am wrong but i am unable to accept the division by 2 fact also why we didn't divided by 2 in n choose 2 choose 3 case because in that case we have line segments instead of triangle and AB=BA ?...btw a great video basic to advance all the best for SOMEpi win 🏆. i already rated you outstanding😉.thankyou...
why you named it double counting and can you also tell where can i learn some of these combinatorial type of proof...also can i join you 😅?
Very good question! In fact I should have explained it better in the video. You're right, when we use a combination, there's no order. But when we multiply two combinations, it's different. Consider this case: We draw the first triangle called ABC. As a result, DEF will be the second triangle. So our two triangles will be ABC and DEF. If the first triangle was DEF, then ABC would be the second one. Again, our two triangles will be ABC and DEF. That's why we need to divide by 2 (in fact we need to divide by 2 factorial).
For "(n choose 2) choose 3", let's consider the first case. We have six points, and we want to draw 3 lines. We can count by picking the first line out of 6 points, then second line given the remaining 4 points, and finally the third line given the remaining 2 points. The number of ways is (6 choose 2) * (4 choose 2) * (2 choose 2) / 3!. We divide by 3 factorial because order does not matter. In the video I used a different way of counting this which does not require dividing, because I'm specifying which nodes are used and which ones are remained.
I do not have an academic education on combinatorics, I've only studied random things on the internet, so I can't recommend any resources. It wasn't me who called it double counting, and I don't know who was the first who came up with this name.
Thank you very much for your comment!
Thankyou I loved it ❤
@@Upsampled you said "The number of ways is (6 choose 2) * (4 choose 2) * (2 choose 2) / 3!. We divide by 3 factorial because order does not matter." but recently i thought should it not be (6 choose 2)* 1/2(for as AB=BA)(4 choose 2) *1/2(same reason)*(2 choose 2). whats the error in my reasoning ? later i understood that the 3 ! is taken in account for the same thing the way in which 2 points taken are taken in which order i just not deleted the post becz i want to tell you that at 9:22 you can also say that take (n choose 4) *(4 choose 1)(to take account from which point to start out of 4 ) *(3 choose 1) for which point to end at !) ty...you helped me a lot btw if you wish i certainly would love to join you ! also i edited it 3rd time because i want to mention what a beautiful line you wrote ! "when we use a combination, there's no order. But when we multiply two combinations, it's different. " just magnificient
Cheers to Mr. Kord :)
@@AliGholami-g9p Cheers! 😁🍻
nice
2022 aime ii problem 10
Thanks!
Watching at 1.5x speed, too slooow otherwise.