🌟🌟To try everything Brilliant has to offer-free-for a full 30 days, visit brilliant.org/michaelpenn. The first 200 of you will get 20% off Brilliant's annual premium subscription.🌟🌟
@@hrldcpr FYI that Wiki article doesn't actually include the proof of the bijection in it. It simply describes a process to turn an arbitrary sequence into a tree then simply states the tree generated is unique without proof. It likewise doesn't prove that the sequence generated from a tree is unique either. (I don't even see it proven in the hyperlinks in the article either, you'd probably have to find it elsewhere. 🤷♂)
@@Bodyknock honestly, the fact that any sequence can become a tree is enough. Since the process of turning a tree into a sequence is completely deterministic, you can't have one tree become two different sequences, and you can't make a tree that results in a sequence that you can't then build, the two must be the same
@@romajimamulo No, transformations between sequences and trees isn't enough if the results aren't guaranteed to be unique. For example, say I have the really trivial transformations from sequences to trees that map every sequences of length n-2 to the straight line tree 1-2-3-...-n . Every sequence produces a tree, but they're not unique trees (they're all the same in this specific example.) Well now I have a process from the video which can turn any tree into a sequence, and I have a process that can turn any sequence into a tree, but the problem is the composition isn't invertible because the sequence-to-tree function isn't injective. So that's a counter-example where no tree becomes two different sequences and you can go from every sequence back to a tree, but it's not bijective combination. You really do need to prove then that the processes you're using both ways are injective (i.e. different trees give different sequences and vice versa.)
One can actually notice that if A(x) is the generating function of labeled trees, then the following holds: x * (A(x) + A(x) ^ 2 / 2! + A(x) ^ 3 / 3! + ...) = A(x) Essentially, this is the same as saying "Say we have a root, and we attach some number of other trees to the root. Then, whatever we attach will still be a tree" The expression above can be rewritten as follows: x * e ^ A(x) = A(x) Now, solving this using the Lagrange Inversion theorem, we get that the coefficient in front of x ^ n is exactly n ^ (n - 2)
The only thing I wish had been in the video was an example of reversing the process by taking an arbitrary sequence of numbers and using it to construct a tree since it's not immediately obvious how to do it at a glance. (The process is described in the Wiki entry for "Prüfer sequence", it makes sense once you read how to do it but actually seeing it in action would have been nice.)
Here's my approach to the missing portion of the proof: Michael has constructed a function F defining the signature for each labeled tree, but we do not yet know whether F is surjective or even injective. We will construct a function G assigning a labeled tree to each signature, such that F o G is the identity function, showing that F is surjective. First, some observations: Lemma: During the tree destructuring process in F, a node with label L transitions from being a non-leaf to being a leaf at the final occurrence of the label L in the signature. Proof: A node is a leaf if and only if it has exactly one neighbor. A node loses a neighbor exactly when its label appears in the signature. Every node starts with at least one neighbor, its number of neighbors is monotonically decreasing, and at the end of the process, every node was either removed (in which case it had exactly one neighbor) or remains (in which case it has exactly one neighbor), so each node becomes a leaf at some point. Therefore the point at which the number of neighbors drops to exactly one must be the final occurrence of its label. Corollary: A label that does not appear in the signature of a labelled tree corresponds to a leaf of that tree. From these observations, we can see that the first node removed by F must have the lowest label that is absent from the signature. This lets us explicitly construct the inverse function. Define G recursively as follows: Given a signature (L1, L2, ..., Ln-2), let X be the lowest label in the set of labels that does not appear in the signature, that is, X ∉ {L1, ..., Ln-2}. Remove the label X from the set of labels, and apply G recursively to (L2, ..., Ln-2) to produce a labeled tree U with n-1 nodes. Then attach the node with label X to node L1 in that tree to give a labeled tree T, and define G(L1, L2, ..., Ln-2) = T. G applied to the empty signature produces the unique labeled tree of size two. Theorem: F applied to the tree T = G(L1, L2, ..., Ln-2) gives the signature (L1, L2, ..., Ln-2). Proof: We proceed by induction on n. Clearly the result holds for n = 2, where there is only a single signature and a single labeled tree. Step 1) X is the lowest labeled leaf in T. If not, then there is a leaf Y with a lower label. But we know by induction that F(U) is (L2, ..., Ln-2), and because Y < X and X is the lowest label that is absent from (L1, ..., Ln-2), Y ∈ {L1, ..., Ln-2}. Either Y is L1, in which case it is not a leaf in T, or it is Li for i > 1; in the latter case, by the lemma, the node with label Y transitioned from being a non-leaf to being a leaf during the action of F(U), so Y is not a leaf in U, so Y is not a leaf in T. Either way, we contradict the assumption that there is a leaf Y in T with a lower label than X. Step 2) The first element in the signature is L1. This follows because X is the lowest labeled leaf, and is connected to L1. Step 3) The rest of the elements of the signature are (L2, ..., Ln). This follows by induction on the subtree U produced by removing X. This completes the proof: F(T) is (L1, L2, ..., Ln-2). Therefore F o G is the identity function, so F must be surjective. We can see that F is injective similarly: by the lemma, X is the label of the node corresponding to L1 in the original tree, so by induction G rebuilds the same tree that F consumed. So F is a bijection and the cardinality of the set of signatures equals the cardinality of the set of labeled trees.
It might not be as fun, but I'm actually very interested in the proof that its a bijection, because i just thinking thinking to myself "surely this isn't injective... or even surjective" lmao I'm struggling to imagine that there's a unique tree for every possible sequence. Im guessing that its because orientation doesnt matter, so if 2 trees have the same sequence, then they are the same tree but orientated differently.
For the probability, I immediately went with the fact that 1 is smallest so the sequence will never have 1 in it but the sequence length is still (n-2). So total #seq without 1 is (n-1)^(n-2), which should be count of trees having 1 as a leaf.
Cayley's Formula of course also (trivially) works for the number of labeled trees with one vertex: 1^(-1) = 1! Also, it's interesting that the number of derangments divided by the number of permutations of a set with n elements also tends to 1/e in the limit...perhaps they are related, but I'm doubtful. Excellent as always, Michael!
Just to point out that your definition of a "labelled tree" at 7:15 says that only the leaves are labelled, whereas you seem to be labelling all of the vertices. I would surmise this would make quite a bit of difference?
10:11 so a labeled graph is the same, if you can mirror it to be equal? with the n=4, star like ones, consider 1 in the middle, then 2,3,4 leaves. now consider 1 in the middle, 2,4,3 leaves. since we switched 3,4 its not possible to transform the first one into the second one without mirroring. (in 2d)
ow this reminiscent of Isomerism In Organic Chemistry, hah I even tried to find a pattern / formula for the number of isomers for some general n-alkane to make the topic less ambiguous 3 years back(I still have to study it :p) and thought that the partition formula might get me somewhere but it was soon pretty clear that most probably partition formula isnt the way to go. Having no leads I left it - open ended :D
Wow, my friend an I were actually talking about this the other day, but we couldn't prove the bijecture here(only tree -> sequence, no sequence -> tree), do you think you can do an explanation for that?
It is incredible really isn't it? I mean one day trying to get to grips with functional differential equations with families of solutions. Who needs initial conditions, boundary values or even initial boundary values? And is it limited to RxR mapping to some subset of R? Can it be extended to different dimensions? Are two plus one dimensions the same as three dimensions and what does plus one mean anyway? And why do subspaces of n-dimensional spaces all have to agree on a common zero? Does a linear transformation from n-space to n-space bring along a baggage of stuff that gets muddled up because a common zero has to be found? And then ... discrete math ... with an infinite sum. Salute! (It is a French way to say "cheers" ) Excellent channel!
Why do we multiply by the n-1 at the end? Doesn’t counting for all trees labeled with n-1 vertices already take into account the n-1 different possibilities for the vertices connecting the 1 leaf?
It may be easier to think of that step like this: - If [1] is a leaf, it would be the smallest-valued leaf at the start; it would be removed and it's neighbour written in the list, meaning 1 cannot be in the sequence. - Since we can equate these lists with a matching tree, the number of trees with [1] as a leaf would be equal to the number of sequences which do not contain the number 1. - That is to say, there are (n-2) choices from the set {2, 3, ..., n}, which is (n-1)^(n-2).
No. Because n^(n-2) counts different labeled trees, and to do what you described we need the same tree, just with different labels moved to the "docking port". You may think if it like that: all vertices are in a fixed position, the different trees you made only by adding edges. Since vertex "4" is always the same position, you are no longer tempted the idea it moves to the "docking port" :)
If there's a cycle, there's an edge that can be removed without disconnecting the tree (to complete the cycle), hence making it not a tree under this definition
Different disciplines define the term _tree_ in different ways, but AFAIK, all agree that a tree is an _acyclic_ graph. It may or may not have a root node (vertex), and it may be directed or undirected, but it is always acyclic.
@@philstubblefield Back when I studied graph theory (35 years ago!) an acyclic connected graph was one definition of a tree. If it was acyclic but not necessarily connected (so every connected component is a tree) it was named a Forest.
"His" definition is a simple way of saying "a graph without cycles" without defining a cycle. But it means exactly the same. There is a cycle in a graph you can remove an edge and the graph is still connected.
Sir you and your vidio is adorable, we are waiting in India for ur new vidio. It just like a heroine rush in mind to learn something new from you. Please recommend some lecture series on topology or u can make about this topic Please please please ❤❤
🌟🌟To try everything Brilliant has to offer-free-for a full 30 days, visit brilliant.org/michaelpenn. The first 200 of you will get 20% off Brilliant's annual premium subscription.🌟🌟
strange that there is a simple formula for the number of labelled trees, but none for unlabelled trees....
Graph isomorphisms are hard
Eco-friendly maths🌺🪷⚘️🌷🪻💐!
Great video as always!
I'd love to see a proof of the bijection, showing that such a list creates a labeled tree
en.wikipedia.org/wiki/Pr%C3%BCfer_sequence
@@hrldcpr FYI that Wiki article doesn't actually include the proof of the bijection in it. It simply describes a process to turn an arbitrary sequence into a tree then simply states the tree generated is unique without proof. It likewise doesn't prove that the sequence generated from a tree is unique either. (I don't even see it proven in the hyperlinks in the article either, you'd probably have to find it elsewhere. 🤷♂)
@@Bodyknock Good point. Perhaps someone reading this can add a proof to the Wikipedia article!
@@Bodyknock honestly, the fact that any sequence can become a tree is enough. Since the process of turning a tree into a sequence is completely deterministic, you can't have one tree become two different sequences, and you can't make a tree that results in a sequence that you can't then build, the two must be the same
@@romajimamulo No, transformations between sequences and trees isn't enough if the results aren't guaranteed to be unique.
For example, say I have the really trivial transformations from sequences to trees that map every sequences of length n-2 to the straight line tree 1-2-3-...-n . Every sequence produces a tree, but they're not unique trees (they're all the same in this specific example.) Well now I have a process from the video which can turn any tree into a sequence, and I have a process that can turn any sequence into a tree, but the problem is the composition isn't invertible because the sequence-to-tree function isn't injective.
So that's a counter-example where no tree becomes two different sequences and you can go from every sequence back to a tree, but it's not bijective combination. You really do need to prove then that the processes you're using both ways are injective (i.e. different trees give different sequences and vice versa.)
"Prüfer" in German means "tester". What a great name to prove hypotheses... :-)
I'm finding the extended joke-metaphors on actual trees quite amusing, especially the one-node "acorn."
One can actually notice that if A(x) is the generating function of labeled trees, then the following holds:
x * (A(x) + A(x) ^ 2 / 2! + A(x) ^ 3 / 3! + ...) = A(x)
Essentially, this is the same as saying "Say we have a root, and we attach some number of other trees to the root. Then, whatever we attach will still be a tree"
The expression above can be rewritten as follows:
x * e ^ A(x) = A(x)
Now, solving this using the Lagrange Inversion theorem, we get that the coefficient in front of x ^ n is exactly n ^ (n - 2)
Very similar to the lambert W function which is W(x)e^W(x)=x
x=A(x)e^(-A(x))
-x=-A(x)e^(-A(x))
The only thing I wish had been in the video was an example of reversing the process by taking an arbitrary sequence of numbers and using it to construct a tree since it's not immediately obvious how to do it at a glance. (The process is described in the Wiki entry for "Prüfer sequence", it makes sense once you read how to do it but actually seeing it in action would have been nice.)
Here's my approach to the missing portion of the proof:
Michael has constructed a function F defining the signature for each labeled tree, but we do not yet know whether F is surjective or even injective. We will construct a function G assigning a labeled tree to each signature, such that F o G is the identity function, showing that F is surjective. First, some observations:
Lemma: During the tree destructuring process in F, a node with label L transitions from being a non-leaf to being a leaf at the final occurrence of the label L in the signature.
Proof: A node is a leaf if and only if it has exactly one neighbor. A node loses a neighbor exactly when its label appears in the signature. Every node starts with at least one neighbor, its number of neighbors is monotonically decreasing, and at the end of the process, every node was either removed (in which case it had exactly one neighbor) or remains (in which case it has exactly one neighbor), so each node becomes a leaf at some point. Therefore the point at which the number of neighbors drops to exactly one must be the final occurrence of its label.
Corollary: A label that does not appear in the signature of a labelled tree corresponds to a leaf of that tree.
From these observations, we can see that the first node removed by F must have the lowest label that is absent from the signature. This lets us explicitly construct the inverse function. Define G recursively as follows:
Given a signature (L1, L2, ..., Ln-2), let X be the lowest label in the set of labels that does not appear in the signature, that is, X ∉ {L1, ..., Ln-2}. Remove the label X from the set of labels, and apply G recursively to (L2, ..., Ln-2) to produce a labeled tree U with n-1 nodes. Then attach the node with label X to node L1 in that tree to give a labeled tree T, and define G(L1, L2, ..., Ln-2) = T. G applied to the empty signature produces the unique labeled tree of size two.
Theorem: F applied to the tree T = G(L1, L2, ..., Ln-2) gives the signature (L1, L2, ..., Ln-2).
Proof: We proceed by induction on n. Clearly the result holds for n = 2, where there is only a single signature and a single labeled tree.
Step 1) X is the lowest labeled leaf in T. If not, then there is a leaf Y with a lower label. But we know by induction that F(U) is (L2, ..., Ln-2), and because Y < X and X is the lowest label that is absent from (L1, ..., Ln-2), Y ∈ {L1, ..., Ln-2}. Either Y is L1, in which case it is not a leaf in T, or it is Li for i > 1; in the latter case, by the lemma, the node with label Y transitioned from being a non-leaf to being a leaf during the action of F(U), so Y is not a leaf in U, so Y is not a leaf in T. Either way, we contradict the assumption that there is a leaf Y in T with a lower label than X.
Step 2) The first element in the signature is L1. This follows because X is the lowest labeled leaf, and is connected to L1.
Step 3) The rest of the elements of the signature are (L2, ..., Ln). This follows by induction on the subtree U produced by removing X.
This completes the proof: F(T) is (L1, L2, ..., Ln-2).
Therefore F o G is the identity function, so F must be surjective.
We can see that F is injective similarly: by the lemma, X is the label of the node corresponding to L1 in the original tree, so by induction G rebuilds the same tree that F consumed.
So F is a bijection and the cardinality of the set of signatures equals the cardinality of the set of labeled trees.
It might not be as fun, but I'm actually very interested in the proof that its a bijection, because i just thinking thinking to myself "surely this isn't injective... or even surjective" lmao
I'm struggling to imagine that there's a unique tree for every possible sequence. Im guessing that its because orientation doesnt matter, so if 2 trees have the same sequence, then they are the same tree but orientated differently.
I can confirm. Trees are also giant plants.
Potentially.
@@emperornortoni2871 true. Potentially stupidly big.
@@ariel_haymarket What are you, a goddamn botanist? Get out of this math channel!
No Bonsai?
It is good that you made the leaves green. If you chose brown then we would all be dreaming of California.
For the probability, I immediately went with the fact that 1 is smallest so the sequence will never have 1 in it but the sequence length is still (n-2). So total #seq without 1 is (n-1)^(n-2), which should be count of trees having 1 as a leaf.
I'm trying to find the paper by Reshetnikov on the connection between trees and circles on a sphere. Does anyone have a link to it?
So do I but couldn't find it. Only the OEIS page on the integer sequence A000055 mentions this work
Cayley's Formula of course also (trivially) works for the number of labeled trees with one vertex: 1^(-1) = 1!
Also, it's interesting that the number of derangments divided by the number of permutations of a set with n elements also tends to 1/e in the limit...perhaps they are related, but I'm doubtful. Excellent as always, Michael!
The number of derangements is [n!/e], where [x] is the integer closest to x.
I'm surprised that no one has mentioned _Good Will Hunting_ and the math problem on the hallway chalkboard.
22:08
Just to point out that your definition of a "labelled tree" at 7:15 says that only the leaves are labelled, whereas you seem to be labelling all of the vertices. I would surmise this would make quite a bit of difference?
The definition that he _wrote_ uses the world "leaves", but at 7:21 he says "A labeled tree is a tree whose *_vertices_* have been labeled..."
So I went to search for dynkin diagrams and I found myself taking the whole course of Lie group and Lie algebra.
10:11 so a labeled graph is the same, if you can mirror it to be equal? with the n=4, star like ones, consider 1 in the middle, then 2,3,4 leaves. now consider 1 in the middle, 2,4,3 leaves. since we switched 3,4 its not possible to transform the first one into the second one without mirroring. (in 2d)
Mike says... 0:16 "What is a tree ? ... it's POTENTIALLY a very large plant". I'd say it's ACTUALLY a very large plant.✅ 🧑🏫
Good combinatorial problems 🙂
Merry Christmas
ow this reminiscent of Isomerism In Organic Chemistry, hah I even tried to find a pattern / formula for the number of isomers for some general n-alkane to make the topic less ambiguous 3 years back(I still have to study it :p) and thought that the partition formula might get me somewhere but it was soon pretty clear that most probably partition formula isnt the way to go. Having no leads I left it - open ended :D
Been thinking about trees recently as a computer scientist. What a coincidence :)
Perfect
Wow, my friend an I were actually talking about this the other day, but we couldn't prove the bijecture here(only tree -> sequence, no sequence -> tree), do you think you can do an explanation for that?
0:15 does anyone know of resources that could help me go more into depth into this topic?
It is incredible really isn't it?
I mean one day trying to get to grips with functional differential equations with families of solutions. Who needs initial conditions, boundary values or even initial boundary values? And is it limited to RxR mapping to some subset of R? Can it be extended to different dimensions? Are two plus one dimensions the same as three dimensions and what does plus one mean anyway? And why do subspaces of n-dimensional spaces all have to agree on a common zero? Does a linear transformation from n-space to n-space bring along a baggage of stuff that gets muddled up because a common zero has to be found?
And then ... discrete math ... with an infinite sum.
Salute! (It is a French way to say "cheers" )
Excellent channel!
Why do we multiply by the n-1 at the end?
Doesn’t counting for all trees labeled with n-1 vertices already take into account the n-1 different possibilities for the vertices connecting the 1 leaf?
It may be easier to think of that step like this:
- If [1] is a leaf, it would be the smallest-valued leaf at the start; it would be removed and it's neighbour written in the list, meaning 1 cannot be in the sequence.
- Since we can equate these lists with a matching tree, the number of trees with [1] as a leaf would be equal to the number of sequences which do not contain the number 1.
- That is to say, there are (n-2) choices from the set {2, 3, ..., n}, which is (n-1)^(n-2).
No. Because n^(n-2) counts different labeled trees, and to do what you described we need the same tree, just with different labels moved to the "docking port".
You may think if it like that: all vertices are in a fixed position, the different trees you made only by adding edges. Since vertex "4" is always the same position, you are no longer tempted the idea it moves to the "docking port" :)
MichaelPenn e e
Math and biology? What can’t Michael do??
Hahaha I thought this was gonna be a linguistics video 😂
Tree definition shouldn’t allow cycles and yours does, or what am I missing?
If there's a cycle, there's an edge that can be removed without disconnecting the tree (to complete the cycle), hence making it not a tree under this definition
Different disciplines define the term _tree_ in different ways, but AFAIK, all agree that a tree is an _acyclic_ graph. It may or may not have a root node (vertex), and it may be directed or undirected, but it is always acyclic.
@@philstubblefield Back when I studied graph theory (35 years ago!) an acyclic connected graph was one definition of a tree. If it was acyclic but not necessarily connected (so every connected component is a tree) it was named a Forest.
also tree is 1D shape with face-vector (n,n-1).
"His" definition is a simple way of saying "a graph without cycles" without defining a cycle. But it means exactly the same. There is a cycle in a graph you can remove an edge and the graph is still connected.
Sir you and your vidio is adorable, we are waiting in India for ur new vidio. It just like a heroine rush in mind to learn something new from you. Please recommend some lecture series on topology or u can make about this topic
Please please please ❤❤
0 1 1 2 3 hmm🤔