I love the Pascal triangle trick to figure out what you're looking at. Also, I know this sounds silly but so often I look at an identity and I go straight to counting lhs rhs, without actually stopping to think, what am I looking at and what is this identity saying! The way you broke down the first identity as 3 times every third item in the 3nth row of pascals triangle summing to the total of the row but it's over or undercounting has changed the way I will look at identities forever. Before diving into the problem, look at what the problem is asking. Thank you.
Great video for a niche topic! Here's another problem which can be solved by a trijection. For any natural number n, prove that the sum of C(n + k, 2k) ⋅ 2^(n - k) from k = 0 to n is equal to (2^(2n + 1) + 1)/3, where C(a, b) = a! / (b! ⋅ (a - b)!).
Good video, but I don't like the terminology. A bijection uses bi- because it's both a injection and a surjection. That would suggest a trijection somehow adds another kind of -jection. I think "triple bijection" would be a better term for this relationship.
Well, it is kind of a jokey term, made up for this video. But-if you'll allow me to defend myself-I don't know that the Bourbaki group coined the word with the bi- prefix for that specific reason. An alternative, which generalizes better to tri-, is that there is a bijection between A and B if there's an injection from A to B and from B to A (Schröder-Bernstein), so a trijection would have a cycle of injections A to B, B to C, and C to A. Though this is motivated etymology on my part! :P
@@enumerable345 maybe we should worry about if that generalises to category theory properly too the equivalent of a bijection is an isomorphism, an injection a monomorphism, and a surjection an epimorphism, but it's not the case that a morphism that is both a monomoprhism and an epimorphism is automatically an isomorphism that makes me think that having a monomorphism from A to B and a monomorphism from B to A would not necessarily be the same thing as having a monomorphism from A to B that is also an epimorphism from A to B, but I don't know how to properly reason about this
Regarding the bonus problem: consider the set of all functions from Zp to Za, excluding constant functions. Now define an equivalence relation between two functions f and g if there is some x such that f(a) = g(a+x) for all a in Zp. One therefore sees that the equivalence classes are of size p, as they are all p cyclic shifts of the result. To show that all p are different, consider ftsoc some f where f(a+x) = f(a) [x ≠ 0] Then f(0)=f(x)=f(2x)=...=f((p-1)x). This is all the elements in Zp, hence f is constant. Contradiction. One could also imagine this as all sets of length p with elements from Za, which is the same.
In case you only want to do algebra alone, the first formula can be derived by extracting terms of the function f(x)=(1+x)^(3n), simply calculate the average of function input roots of unity (z^3=1). This technique was demonstrated by 3b1b (Olympiad level counting)
@@masonskiekonto590 No, if you do it that way you just have composition of bijections and the overall bijection is, while a bijection, is "fixed" in the sense that it has to follow gf. E..g, if h = gf then h(a) = gf(a). In the trijection we allow for an additional permutation/shuffling. It's like adding a 4th set D and then what you do will work. That is, with a trijection we are allowing for any h(a) != gf(a) but h(A) = gf(A) (and h be a bijection). That is, all around the triangle we want free bijections. If one is determined by the other we don't have the complete degree's of freedom that one expects from a trijection. (e.g., where there is no preferred starting point) Basically if you set h = gf in your example then imagine that, h is fixed but we find all possible bijections f and g then there is an h for each one. Call it H = {h | h = gf and f,g are bijections}. This set H is what we can choose for the 3rd side. if you let r ~ s mean r and s are bijections(on the same set). Then we want h ~ gf rather than h = gf. (we loosen the requirements that the map of the individual elements must be equal and only require the global nature of a bijection)
For even n, the second identity seems to sum to (-1)^(n/2)*C(n,n/2)/4^(n/2) or if we replace n with 2n (to clear most of the denominators), it would equal (-1)^n * C(2n,n)/4^n where C(n,k) is n choose k. I did not even attempt a counting proof of this, but I wonder how that would go...
I haven't fully worked it out, but I also figured it would be too much for this video. The counting argument would go something like... the trijection still cancels out most stuff. Then there are other mini-configurations we can put into trijection that also sum to 0 to cover more. Eliminate as many as you can this way, and the remaining configurations that don't balance all (this is a guess) have sign (-1)^(n/2). Count up the weights of anything that remains to get the RHS.
@@MichaelDarrow-tr1mn Now can you find an equivalence which will always add a card to the 5 if all of them are lower than 15, while "splitting" the 15 into two cards that add up to 15 if 15 is part of the 5 cards.
I think I just found a perfectly good combinatorics channel, hope you keep it up as most seem to overlook these topics
I love the Pascal triangle trick to figure out what you're looking at. Also, I know this sounds silly but so often I look at an identity and I go straight to counting lhs rhs, without actually stopping to think, what am I looking at and what is this identity saying! The way you broke down the first identity as 3 times every third item in the 3nth row of pascals triangle summing to the total of the row but it's over or undercounting has changed the way I will look at identities forever. Before diving into the problem, look at what the problem is asking. Thank you.
What a nice comment. Thank *you*, and keep counting!
Great video for a niche topic!
Here's another problem which can be solved by a trijection. For any natural number n, prove that the sum of C(n + k, 2k) ⋅ 2^(n - k) from k = 0 to n is equal to (2^(2n + 1) + 1)/3, where C(a, b) = a! / (b! ⋅ (a - b)!).
Ooh, I don't think I've seen that identity before! I'll save coming up with the trijective proof for an upcoming plane flight. (Also--fellow Mudder?)
@@enumerable345 Yes I am a mudder, class of '13 :^) I shouldn't be too surprised you went to HMC, since you've clearly studied under Prof Benjamin.
Good video, but I don't like the terminology. A bijection uses bi- because it's both a injection and a surjection. That would suggest a trijection somehow adds another kind of -jection.
I think "triple bijection" would be a better term for this relationship.
Well, it is kind of a jokey term, made up for this video. But-if you'll allow me to defend myself-I don't know that the Bourbaki group coined the word with the bi- prefix for that specific reason. An alternative, which generalizes better to tri-, is that there is a bijection between A and B if there's an injection from A to B and from B to A (Schröder-Bernstein), so a trijection would have a cycle of injections A to B, B to C, and C to A. Though this is motivated etymology on my part! :P
@@enumerable345 maybe we should worry about if that generalises to category theory properly too
the equivalent of a bijection is an isomorphism, an injection a monomorphism, and a surjection an epimorphism, but it's not the case that a morphism that is both a monomoprhism and an epimorphism is automatically an isomorphism
that makes me think that having a monomorphism from A to B and a monomorphism from B to A would not necessarily be the same thing as having a monomorphism from A to B that is also an epimorphism from A to B, but I don't know how to properly reason about this
man we all wanna reach samw height
Thanks for sharing it!
🙏📚🏆🥇🙏📚🏆🥇🇧🇷
Regarding the bonus problem: consider the set of all functions from Zp to Za, excluding constant functions. Now define an equivalence relation between two functions f and g if there is some x such that f(a) = g(a+x) for all a in Zp. One therefore sees that the equivalence classes are of size p, as they are all p cyclic shifts of the result. To show that all p are different, consider ftsoc some f where f(a+x) = f(a) [x ≠ 0] Then f(0)=f(x)=f(2x)=...=f((p-1)x). This is all the elements in Zp, hence f is constant. Contradiction.
One could also imagine this as all sets of length p with elements from Za, which is the same.
In case you only want to do algebra alone, the first formula can be derived by extracting terms of the function f(x)=(1+x)^(3n), simply calculate the average of function input roots of unity (z^3=1). This technique was demonstrated by 3b1b (Olympiad level counting)
Incredible video !
Isn't it 2 bijection in a row?
🎉🎉🎉
A trijection is simply 3 bijections.
Isn't two enough?
For sets A, B, C
and bijections f: A -> B, and g: B -> C
you have:
- f^-1: B -> A
- g^-1: C -> B
- g•f: A -> C
- f^-1•g^-1: C -> A
@@masonskiekonto590
No, if you do it that way you just have composition of bijections and the overall bijection is, while a bijection, is "fixed" in the sense that it has to follow gf.
E..g, if h = gf then h(a) = gf(a).
In the trijection we allow for an additional permutation/shuffling. It's like adding a 4th set D and then what you do will work.
That is, with a trijection we are allowing for any h(a) != gf(a) but h(A) = gf(A) (and h be a bijection).
That is, all around the triangle we want free bijections. If one is determined by the other we don't have the complete degree's of freedom that one expects from a trijection. (e.g., where there is no preferred starting point)
Basically if you set h = gf in your example then imagine that, h is fixed but we find all possible bijections f and g then there is an h for each one. Call it H = {h | h = gf and f,g are bijections}. This set H is what we can choose for the 3rd side.
if you let r ~ s mean r and s are bijections(on the same set). Then we want h ~ gf rather than h = gf. (we loosen the requirements that the map of the individual elements must be equal and only require the global nature of a bijection)
The D.I.E. guy upload another video!!!
Not sure how I feel about that nickname. 😂
nice
For even n, the second identity seems to sum to
(-1)^(n/2)*C(n,n/2)/4^(n/2)
or if we replace n with 2n (to clear most of the denominators), it would equal
(-1)^n * C(2n,n)/4^n
where C(n,k) is n choose k.
I did not even attempt a counting proof of this, but I wonder how that would go...
I haven't fully worked it out, but I also figured it would be too much for this video. The counting argument would go something like... the trijection still cancels out most stuff. Then there are other mini-configurations we can put into trijection that also sum to 0 to cover more. Eliminate as many as you can this way, and the remaining configurations that don't balance all (this is a guess) have sign (-1)^(n/2). Count up the weights of anything that remains to get the RHS.
Fourth!
why is 14 choose 6 equal to 15 choose 5
Was this in the video? At any rate, pretty easy to just plug in these values into the formula and see it is true.
14 choose 6 = 14!/(8!*6!)=15!/(10!*5!) * (10*9)/(15*6)=(15 choose 5) * 1
(n k) =
n!/(n-k)!k!
(14 6) =
14!/(14-6)!6! =
14!/8!6! =
14!•15/8!5!•6•15 =
15!/8!5!9•10 =
15!/10!5! =
15!/(15-5)!5! =
(15 5)
@@KrasBadan amazing. can you use this to construct an equivalence between the two sets
@@MichaelDarrow-tr1mn Now can you find an equivalence which will always add a card to the 5 if all of them are lower than 15, while "splitting" the 15 into two cards that add up to 15 if 15 is part of the 5 cards.
Ifff
I... don't understand.
No, babe! It's not what it seems. It's just a trijection, you see?
I dunno buddy, is 3 greater than 2🤔
By ternary logic, the answer is "file not found."
@@nisonaticdamn
Negative weights! 🫠