Numberphile - Sophie Maclean on the Catalan Numbers
Timing! Or maybe just ubiquity? I don't know. See bintrees (on page 92 [100 in the PDF]) in the infuriating Proofs and Types by Girard, Lafont and Taylor.
At 5:07 it's not clear to me why she chose those particular edges. I guess it's that whatever four of the five edges she chooses, if she chooses the same ones every time, then the functional relation holds regardless of the element of the group of rotations to which it refers. But that doesn't really explain why: to do that you need some sort of constructive process like recursive subdivision ("step-by-step, either 'do nothing' or 'split') to generate the different triangulations. Similarly, with the interpretation as Dyck words, ... her characerisation of the Dyck words as an invariant, vis "They have the same number of Xs and Ys and , as you scan the string from left to right, at no point do you ever have more Xs than there are Ys before that" is clearly isomorphic to "the set of strings of (s and )s which are balanced strings of parentheses". Then the 'explanation' at 7:13 of the formula in terms of dominating cycles is unintelligible to me. I don't know enough about graph theory and combinatorics, but I am sure you could fill in the gap with another language interpretation. See e.g. Existence of dominating cycles and paths by H.J. Veldman for example:
A cycle C of a graph G is called dominating cycle (D-cycle) if every edge of G is incident with at least one vertex of C.
For an example of how neatly these things can be done, The Mathematics Behind the Banker’s Algorithm.
In retrospect I am grateful to the puzzled looks on my student’s faces. That from a cyclic arrangement of n assertions, each implying the next one, we can conclude that all n assertions are equivalent — or to put it more dramatically: can conclude all n(n − 1) pair-wise implications — is not unknown at all. But the larger the value of n, the more impressive an example of effective reasoning we have, in particular if — as in this case — the assertions have been arranged in such an order, that the n antecedents are not difficult to prove.
But if you don't like that sort of maths, you can do it all with group homomorphisms on vector spaces: see Group representation. See V.I. Arnold on Teaching Mathematics.
She has a blog too, but it doesn't work very well! https://sophiethemathmo.wordpress.com/.
The Catalan numbers very probably turn up in Norman Wildberger's Arithmetic with Negative Msets too. An Mset is a set with multplicity, or you can think of it as a vector of multiplicities. Positive Msets can be represented by balanced parentheses. The number system he develops here is strongly reminiscent of the lazy natural numbers (on page 70 [78 in the PDF]) in Proofs and Types. I guess they're called lazy because you don't have to decide until the end whether you're talking about positive or negative integers. It all depends on how deeply you nest them. I think this is their trick to allow zero to represent omega as well.
Subscribe to Numberphile.
See these tweets I posted a few hours ago:
Here's Norman Wildberger's take on negativity, multiplication and addition: https://t.co/ecV53208g3 I think he's creeping up on Ada Lovelace, ...
— eternal Doorman (@IanANGrant66) January 29, 2024
See also Daniel Tubbenhauer - Noncommutative Algebras in Magma: "MAGMA is an imperative, call by value, lexically scoped, dynamically typed programming language, with an essentially functional subset." Exercise 4B on page 19 of the manual is about the Catalan numbers represented as balanced strings of parentheses:
Here's a way in Magma to describe the process of generating Dyck words as recursive subdivision: "at each step, either 'do nothing' or 'split'":
To understand this code, you need to know that &+ is a command called a reduction operator which evaluates and then reduces the following phrase into an element of some type.
Note that Standard ML is also "an imperative, call by value, lexically scoped, (more or less, as regards the top-level) dynamically typed programming language, with an essentially functional subset." See Another Introduction to Geometric Algebra. And I just started listening to this again: David MacQueen on The History of the Standard ML Programming Language. Max Newman was a topologist by trade:
I guess the big question is "Who took the Y out of ISWIM?". At 26:41 on Robin Milner's let polymorphism: see CLU (programming language) and also https://prooftoys.org/ian-grant/hm/ and me Talking About Computation. At 33:21 Cardelli's VAX ML had serialization so you could send representations over serial channels, I guess. See Luca Cardelli and the Early Evolution of ML by David MacQueen and The History of Standard ML by David MacQueen, Robert Harper and John Reppy, here's an abstype declaration showing how the ins declararation combinator is used:
47:07 Landin's "meta-ISWIM" informal datatype description language with constructors for the identifier case of an expression:
48:47 Comments about the SML Basis inadequacy: What if you could meta-program the basis library using functors to compose machine language primitives? That was the idea I had from doing "Red October". This slide is about WikiML, I reckon, which I only discovered this morning:
New in version 2.10.1 of Moscow ML
- ML Server Pages added to examples
- Build system cleaned up a bit
See https://smlfamily.github.io/. David MacQueen was living in Los Gatos, CA at some point. Hopefully he still does!
Subscribe to ICFP Videos..
William Irwin Thompson used to talk about mind jazz:
This must be a birthday present for my daughter:
Jean Michel Jarre - Oxygene Live In Your Living Room
Subscribe to Jarre 98.
I wonder if I should ask Eben Upton whether he wants to turn his company into the new Ferranti? I know there's one guy with a Brazilian battleship computer plan he wants to realize, ... maybe then we can try get hold of the battleship as well and use it to get Bolivia access to el mar? First stop, Belém:
Comments
Post a Comment