Want to take part in these discussions? Sign in if you have an account, or apply for one below
Vanilla 1.1.10 is a product of Lussumo. More Information: Documentation, Community Support.
Few words added at Catalan number.
I added “binary” to tree.
What does this have to do with the Cayley-Dickson construction?
Thanks. This link to Cayley-Dickson is left from the version 1 written by Urs, I have no idea.
Thanks for the alert.
I forget why I added that link to the Cayley-Dickson construction. Worse, I have no memory of adding it in the first place. (?)
Googling for “Cayley-Dickson” and “Catalan number” does yield a couple of articles that mention both, but I don’t see any real connection. So I removed the link now.
There should be out there a treatment that goes further than the Baez-Dolan paper on species, who in effect write that after setting up and solving the generating function identity for planar binary trees, and after doing some numerical messing around, one can arrive at the formula $\frac1{n+1}\binom{2n}{n}$. It’s that numerical messing around part that should be enacted straight through at a more categorified level, by setting up a $\mathbb{Z}/(n+1)$-action on a structure with $\binom{2n}{n}$ elements (or something like that).
If I can recall how that goes, I’ll add to the article. It must be related to the monotonic lattice path interpretation.
Indeed there is a bijective proof of the formula described over at the wikipedia article, which works by classifying monotonic lattice paths (= monotone injective functions $[n] \to [n]$, counted by $\binom{2n}{n}$) by their “exceedance” across the diagonal, and then observing that there is a reversible transformation reducing the exceedance of a path by one. If you think you can incorporate something like that into the nlab article, that would be great.
…except that I seem to have been psyching myself out about injectivity. Monotone lattice paths correspond to arbitrary order-preserving functions $[n] \to [n]$ (there is only one injective one), so everything really should be taking place in $\Delta$ rather than $\Delta_{inj}$. I will fix that back.
Let me try to be a bit more careful in order to sort out my confusion, since there was still a small mistake above. A monotonic lattice path on the $n\times n$ grid is just a shuffle of $n$ North steps with $n$ East steps, and is represented most concretely by an injective monotone function $p : [2n] \to [n] \times [n]$ specifying the $(x,y)$-coordinate $p[i]$ of the path at a given time $i$. To obtain a monotone function $f_p : [n] \to [n]$ from the path $p$, we can for example take the function
$f_p = x \mapsto \pi_2 p[\min\{i \mid \pi_1 p[i] = x\}]$which sends any $x$ coordinate to the first (= minimum) $y$ coordinate where $x$ appears along the path. Observe that such an $f = f_p$ will always have the property that $f(0) = 0$, in other words it is an endomorphism $[n] \to [n]$ in the category $\Delta_\bot$ of finite non-empty ordinals and order-and-least-element-preserving maps. (Alternatively, we can use max rather than min, and then we obtain an $f$ such that $f(n) = n$, in other words an endomorphism in $\Delta_\top$.)
Conversely, given any $f : [n] \to [n]$ in $\Delta_\bot$, there is a lattice path $p_f : [2n] \to [n] \times [n]$ which can be described inductively as follows. It takes exactly $x + f(x)$ steps to arrive at coordinate $(x,f(x))$, and to get from $(x,f(x))$ to $(x+1,f(x+1)$, it begins with a sequence of $f(x+1) - f(x)$ North steps, followed by a single East step.
This establishes a bijection between lattice paths $p : [2n] \to [n] \times [n]$ in $Pos_{inj}$ and endomorphisms $f : [n] \to [n]$ in $\Delta_\bot$. Moreover, such paths $p$ stay above the diagonal just in case the corresponding endomorphisms $f$ lie above the identity.
Re #9: thanks! The proof I was struggling to recall actually counts it as the equivalent expression $\frac1{2n+1} \binom{2n+1}{n}$. The picture is similar to the lattice path picture: one is trying to count the number of functions $f: \{1, \ldots, 2n+1\} \to \{1, -1\}$ such that
${|f^{-1}(1)|} = n+1$,
${|f^{-1}(-1)|} = n$,
$\sum_{i \leq j} f(i)$ is positive for every $j \leq 2n+1$.
The idea is that the cyclic permutations $\sigma^k = (1\; 2\; \ldots\; 2n+1)^k$ act on the set of all functions $f$ satisfying the first two conditions, and for each such $f$, the function $\sigma^k f$ satisfies the third condition for exactly one $\sigma^k$. It’s explained pretty nicely in visual terms here.
Dreaming out loud, I would find it nice if this could be related to something happening in the cycle category, but I don’t know how to do this yet.
A TON of work of mine on this entry has apparently been lost because of “an invalid LaTeX block”. Any possibility of retrieval?
This took me DAYS to put together.
Not sure exactly what you mean, but if you still have the opportunity to press “back” in your browser, you should recover the edit panel. But also you should not lose your edits when such an error occurs, though there is a known bug (unrelated to any recent changes) that seems to make this unpredictable.
I did try hitting back. I can’t find it.
The offending phrases when I tried to save my edit seem to have been “mountain ranges” and “stay-ahead races”. If that’s of any help.
Yes, I can see in the logs where the LaTeX error was. The ’new’ code seems to have behaved correctly from that point of view, and it is intended that one receives an error; but one should not lose the content, the error should just appear on the top. Though as I say there may be an old bug such that this happens. I unfortunately (I realise this will be enormously frustrating if you do not have a saved copy of it) cannot recover your edit itself, it is not stored anywhere on the server if it is invalid.
This is if I understand correctly that you had been working on something without saving it yourself. If you were in fact saving it and just cannot get it to the save to the nLab, that is no problem to fix.
In the future we can try to add some kind of draft functionality to the nLab to try to avoid cases like this.
Thanks for the info. Wasn’t saved however. Yes, it is very frustrating.
Out of curiosity: I can’t figure out what triggered the error. I understand that some strings may be blocked (if they are considered salacious of offensive, for example, as one guess), but I don’t really see how any text I had really qualifies.
Yes, it is very frustrating.
I understand. I have double-checked, and see where the (very old) bug is. I will prioritise fixing it, but it is non-trivial, so unfortunately I cannot do so now just now.
I can’t figure out what triggered the error.
Almost certainly it is due to a LaTeX block not being closed properly, i.e. missing a dollar sign at the end, or having an extra one. If you had not lost the edit, you would probably have seen immediately how to fix it.
If you had been working on it for days, maybe you have at least part of the work saved?
It is also a bit strange that you couldn’t find it when you click “Back” in the browser, I always recover it in that way. But it could be browser dependent (and anyhow of course we cannot rely on this, we need this to be handled properly).
If you had been working on it for days, maybe you have at least part of the work saved?
Sadly, not really – only in my head.
Usually I don’t get an error message in a yellow header if it’s simply a matter of a missing dollar sign. And usually I don’t lose work like this – I’ve been editing the nLab for almost 10 years and usually know very well what to do. Sigh. (I’m not griping at you, though. I do appreciate your help.)
I’ll try to gather back the steam in my head to do it all over again.
This particular validation error is new (a few days old) as such, it is needed because undetected syntax errors of this kind lead to hard-to-detect rendering issues. But the bug has been there forever, it will have occurred for the older validation errors as well, one just will have encountered these less often. It only occurs for pages over a certain size.
The old renderer sometimes, it seems, ignored syntax errors of this nature, or made a best guess (often wrong) as to how to fix them. Thus we have a bit of a transition period now where we are fixing them. Urs has been doing most of that so far.
I found a bit of time after all, and the bug should be fixed now. See here.
Thanks for putting in this work of writing (and restoring) all these nice explanations!
I had an idea for another way of obtaining a more structural proof of the formula, based on Rémy’s algorithm for generating random binary trees. The algorithm (see the description at p.16 of this draft of Knuth’s Volume 4A, Section 7.2.1.6) works iteratively by starting from the trivial one-leaf tree, and then repeatedly picking any edge of the tree and growing a leaf off to the left or to the right: after $n$ iterations, the result is a binary tree with $n$ internal nodes, equipped with a random ordering of its $n+1$ leaves. Since at each $k$th iteration of the algorithm there are exactly $(2k-1)\cdot 2$ possible choices of an edge and a direction, after $n$ iterations we obtain the identity:
$(n+1)! C_n = (2n-1)!! \cdot 2^n = \frac{(2n)!}{n!}.$I don’t think this quite counts as a “nice” bijective proof, since it is recursive and relies on having an arbitrary labelling of the edges of the tree. On the other hand, maybe there’s a nicer proof lurking in the identity
$(n+1)! C_n = (2n-1)!! \cdot 2^n$which apparently relates permutations, binary trees, chord diagrams, and subsets!
Let me mull over your Method 3 for a while – thanks!
I’m not sure the long section with the various bijections is a geodesic path linking together the various structures, although most of the steps are close to obvious once you start drawing pictures. A critical step seems to be getting from planar binary trees to planar trees, which is not visually immediate as far as I know, but at least the basic idea is pretty familiar when viewed in terms of exponential laws (cf. Goodstein sequences, etc.).
I was struck by the two “simplicial” examples that you put next to each other. One was in terms of surjective maps $(n) + (n) \to (2n)$, the other in terms of injective maps $[2n] \to [n] \times [n]$. Doesn’t this remind you of the duality between finite linear orders (objects of $\Delta$) and finite linear intervals (objects of $\Delta^{op}$)? Applying $Pos(-, (2))$ to a surjection, we get an injection, and the resulting injection $Pos((2n), (2)) \to Pos((n) + (n), (2)) \cong Pos((n), (2)) \times Pos((n), (2))$ is identified with an injection $[2n] \to [n] \times [n]$, which is kind of nice.
One other thing: in the pointed endomorphism description, I didn’t see how the $x \leq f(x)$ condition follows from pointedness. Maybe I misunderstood what you were saying.
A critical step seems to be getting from planar binary trees to planar trees, which is not visually immediate as far as I know, but at least the basic idea is pretty familiar when viewed in terms of exponential laws (cf. Goodstein sequences, etc.).
The idea of seeing this bijection in terms of exponential laws was actually new and interesting to me. I’ve seen it described (I believe equivalently) in terms of a “left-child right-sibling correspondence” (also called “rotation correspondence”), which is at least mildly visual.
I was struck by the two “simplicial” examples that you put next to each other. One was in terms of surjective maps $(n) + (n) \to (2n)$, the other in terms of injective maps $[2n] \to [n] \times [n]$. Doesn’t this remind you of the duality between finite linear orders (objects of $\Delta$) and finite linear intervals (objects of $\Delta^{op}$)?
Indeed. I think of both of these as shuffles (with an additional constraint): a shuffle of n left parens with n right parens in the case of a Dyck word, and a shuffle of n north steps with n east steps in the case of a lattice path. But a (p,q)-shuffle can be defined in dual ways, either as a surjective map $(p)+(q) \to (p+q)$, or as an injective map $[p+q] \to [p]\times[q]$. (I first learned about this from a talk by Eric Hoffbeck.)
One other thing: in the pointed endomorphism description, I didn’t see how the $x \leq f(x)$ condition follows from pointedness. Maybe I misunderstood what you were saying.
Hmm. What I meant by pointed endomorphism is that $f : [n] \to [n]$ (as a 1-cell in the 2-category $\Delta_\bot$) is equipped with a 2-cell $id_{[n]} \Rightarrow f$ from the identity. I just recently added that definition to the article pointed endofunctor, but I guess it might have other connotations?? If so I can change the terminology, or in any case add clarification.
By the way, I’ve also noticed a similar kind of fact about monads in $\Delta$, and powers of two: a monad on $[n]$ is fully determined by saying which of the elements in $\{0,\dots,n-1\}$ it fixes, and so there are exactly $2^n$ different monads on $[n]$.
tried rephrasing the bit about pointed endomorphisms
…as well as some additional disambiguation.
To get back to this point:
I was struck by the two “simplicial” examples that you put next to each other. One was in terms of surjective maps $(n) + (n) \to (2n)$, the other in terms of injective maps $[2n] \to [n] \times [n]$. Doesn’t this remind you of the duality between finite linear orders (objects of $\Delta$) and finite linear intervals (objects of $\Delta^{op}$)?
I guess that I was thinking of the simplices $[n]$ as non-empty ordinals (objects of $\Delta$) embedded into the category of posets and monotone maps, rather than as linear intervals embedded into the category of general intervals (= posets equipped with $\bot$ and $\top$ elements) and $\bot$-and-$\top$-preserving monotone maps. In the way I saw it, it just so happens that the injectivity + monotonicity condition on the map $p : [2n] \to [n] \times [n]$ forces $p(0) = (0,0)$ and $p(2n) = (n,n)$… But indeed maybe as you suggest it is better to think of $p$ as a morphism of intervals.
I think this is probably related to an issue that came up a while ago when I first started writing the articles on the zeta polynomial and the order polynomial of a poset $P$. Then it seemed to me most natural to (re)define the zeta polynomial as $Z_P(n) = |Hom([n],P)|$ (like the nerve of $P$ hit with cardinality), but this actually has an index shift of 2 relative to the definition found in the literature. Of course I should have taken the accepted definition more seriously! And perhaps it becomes more natural if analyzed in terms of linear intervals rather than in terms of linear orders.
Re #32: thanks for clarifying the bit about “pointed”. Actually when you explained it in #30, it made total sense; I should have remembered that.
1 to 34 of 34