Antimatroid, The

thoughts on computer science, electronics, mathematics

One tree, many possibilities

with 2 comments


Given the finite set S and the surjective function \sigma, Let T_{n}\left(S, \sigma\right) be a complete |S|-ary tree of depth n such that T_{0}\left(S, \sigma\right) = \emptyset, T_n(S, \sigma) = T_{n - 1}(S, \sigma) \{ \left( T_{n - 1}(S, \sigma) \oplus s \right) | s \in \sigma(S) \}. For example, Let A = \{0, 1\} and \\f = S \to S, T_{2}\left(A, \\f\right) = \emptyset \{ \left(\emptyset, 0\right) \{ \left(\emptyset, 0, 0\right), \left(\emptyset, 0, 1\right) \}, \left(\emptyset, 1\right) \{ \left(\emptyset, 1, 0\right), \left(\emptyset, 1, 1\right) \} \}. Pictured bellow is T_{3}\left(A, \\f \right) with omitting \emptyset for brevity.

It should be evident from the example that the set of nodes at depth n is the n-ary Cartesian product of S, S^{n} = S \times \ldots \times S.

Now, if we change \\f to now be \\f : S \to \{ s | s \in S \wedge \nu(s) \neq \nu\left(parent\left(s\right)\right)\}, where \nu : S \leftrightarrow \mathbb{N}_{0}, the set of all leaf nodes at depth |S| is the set of permutations of S, S!. Extending the example above, T_{2} \left( A, \\f \right) = \{ \{ \left( \emptyset, 0, 1 \right) \}, \{ \left( \emptyset, 1, 0 \right) \} \}.

Without changing the definition of \\f, it is possible to produce all possible k-permutations from T, P(S, k) by selecting all nodes at depth k.

At this point, if we make a small change to \\f : S \to \{ s | s \in S \wedge \nu\left(s\right) > \nu\left( parent\left(s\right)\right)\}, every node in T now represents the power set of S, 2^{S}. Again, using the example from above, T_{2} \left( A, \\f \right) = \emptyset \{ \left( \emptyset, 0 \right), \left( \emptyset, 1 \right) \{ \left( \emptyset, 1, 1 \right) \} \}.

Finally, without any further changes to the definition of \\f, it is possible to produce all possible n-combinations from T, C(S, n), by selecting all nodes at depth n.

T is a very elegant way of representing and enumerating some of the most rudimentary combinatorial operations of introductory mathematics. In this series of post we’ll explore each operation and look at implementations, time complexities and possible applications.


Written by lewellen

2008-06-29 at 8:25 pm

2 Responses

Subscribe to comments with RSS.

  1. […] my previous post, I wrote about how to construct a rule based tree that allows one to generate the outputs of a […]

  2. […] to enumerate the sets produced by different counting techniques. You can catch up on the idea in part one and the C# implementation in part two. In this post I’m going to cover how to take the […]

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: