I always enjoyed seeing short and elegant proofs of theorems that I knew before.
I really enjoy this short proof that number of proper placing of opening and closing brackets(-th Catalan number) is equal to:
for example, there are 2 ways to properly place 2 opening and 2 closing brackets, out of 6 total ways:
())(, )((), )()(, ))((
First, we may transform the problem into one about walks on plane.
If we take (0,0) as a starting position, and assign to ‘(‘ a walk into UP-RIGHT direction, and ‘)’ a walk into DOWN-RIGHT direction, we might encode sequences of brackets. So, encoding of ((())))(() is:
I promise to finish this topic with this post! (part 1, part 2, part 3)
We ended with a rather efficient (but still double exponential) code that gave us hope to extend the sequence a little bit further. So, what can we improve? Constant, a little, by efficient parallelisation.
As explained before, we would like to extend the following sequence A119770 (don’t click, it will spoil all the fun!):
1, 1, 3, 22, 485, 59386, ...
Recently I found an interesting problem: enumeration of possible antimatroids over finite set.
From combinatorial point of view, an antimatroid is a family of sets, with special properties.
Following the wikipedia definition, is an antimatroid iff:
- is closed under unions, that is:
- is a nonempty accesible:
For example, following family is an antimatroid:
From now, I will denote the largest set, being also a superset of every other one in the family, as (so in previous example, ).
Just as matroids are generalization of antichains, antimatroids are generalization of chains.