Monthly Archives: April 2013

Asymptotics and generating functions

(Warning, equation-heavy post!)

A while ago I stumbled upon a following problem (when doing analysis of a certain distributed exploration algorithm):

We have n groups of agents, each of equal size (lets say =1. Positions of groups are indexed: 1, 2,\ldots,n. Groups ,,diffuse”, and they diffuse at different speeds, depending on the position of the group:
\lambda_i = \frac{1}{i}
(where \lambda_i is the amount of agents disappearing from group being at position i in one unit of time)

Whenever a group size is reduced to 0, (it will be always a first group), every other one is shifted:
2 \to 1, 3 \to 2, \ldots, n \to (n-1)
[0,a_2,a_3,\ldots,a_n] \text{ into} [a_2,a_3,\ldots,a_n]

Question: How long does it take to dissipate all the groups? (We are not interested in exact formula, just asymptotic one.)

For example, if n=3:
[1,1,1] \to [0,\frac{1}{2},\frac{2}{3}]
(1 unit of time)
[\frac{1}{2},\frac{2}{3}] \to [0,\frac{5}{12}]
(\frac{1}{2} units of time)
[\frac{5}{12}] \to [0]
(\frac{5}{12} units of time)
and the answer is 1 + \frac{1}{2} + \frac{5}{12} = \frac{23}{12}
Continue reading

Catalan numbers, mirror image and walks enumeration

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 n opening and n closing brackets(n-th Catalan number) is equal to:
C_n = \frac{1}{n+1} {2n\choose n}.

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:
Continue reading

Enumeration of Antimatroids, part IV

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.
Continue reading

Enumeration of Antimatroids, part III

Let us continue the fun we had before here.

How do we speed up the calculation? Well, we need to limit somehow the space on which we perform the search.
Very obvious way is to eliminate the symmetries. Every permutation \pi \in S_n : \{0,1\ldots,n-1\} \to \{0,1\ldots,n-1\} induces a natural transformation on sets (and sets of sets, like antimatroids, …). For example:
\sigma = (120) = \{ 0 \to 1; 1 \to 2; 2 \to 0 \}
working on :
F = \{ \{\}, \{0\}, \{0,1\}, \{0,2\}, \{0,1,2\} \}
\sigma(F) = \{ \{\}, \{1\}, \{1,2\}, \{1,0\}, \{1,2,0\} \} = \{ \{\}, \{1\}, \{1,2\}, \{0,1\}, \{0,1,2\} \}
Continue reading

Enumeration of Antimatroids, part II

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, ...
Continue reading

Enumeration of Antimatroids, part I

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, F is an antimatroid iff:

  • F is closed under unions, that is: \forall_{u,v \in F} u \cup v \in F
  • F is a nonempty accesible: \forall_{u \in F} ((u = \emptyset) \vee (\exists_{a \in u} u \setminus \{a\} \in F))

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 S (so in previous example, S=\{0,1,2\}).

Just as matroids are generalization of antichains, antimatroids are generalization of chains.
Continue reading