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.
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
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)!).
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 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!
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
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.
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.
I think I just found a perfectly good combinatorics channel, hope you keep it up as most seem to overlook these topics
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)
0:40 love be like
Incredible video !
Thanks for sharing it!
🙏📚🏆🥇🙏📚🏆🥇🇧🇷
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)
🎉🎉🎉
Isn't it 2 bijection in a row?
nice
The D.I.E. guy upload another video!!!
Not sure how I feel about that nickname. 😂
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.
I... don't understand.
Ifff
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! 🫠