Antimatroid, The

thoughts on computer science, electronics, mathematics

Archive for the ‘Combinatorics’ Category

One tree many possibilities: Part 3

with 2 comments

Introduction

When I first began publishing content on this blog, I wrote a couple of posts entitled One tree many possibilities that covered how 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 knowledge from the first two posts and derive closed form solutions to each of the counting techniques through analysis of their respective recurrence relations.

Preliminaries

The basic idea is that that the set S and each of its elements, e, are supplied to a binary operation, \oplus, that maps to a subset S^{\prime} of S. This process is performed iteratively on S^{\prime} until the process has been applied to a depth of k or the resulting subset becomes the empty set.

Since we can have a variety of conceivable sets, we need to map sets of a given cardinality to a common set of the same cardinality. Let b(S) = P_{\lvert S \rvert} be a bijective function that maps a set to the set P_{n} of positive integers from 1 to n.

k-ary Cartesian Product

The k-ary cartesian product is the way of selecting k items from a set where the order of the selection is important and items can be placed back into the set after selection.

The process uses \oplus = id where id(S, e) = S is an identity function. As an example, here is a graph of the process applied to P_{3} with k = 3:

To count the number of elements, we need to count the number of nodes at depth k. We will write this using the following recurrence relation:

\displaystyle f(P_{n}, 0) = 1
\displaystyle f(P_{n}, k) = \sum_{i=1}^{n} {f(P_{n}, k - 1) }

If we think of the tree having a height of k, then we can label each layer from k (at the root) to zero. As a consequence, we can interpret the first statement as a node at depth zero will be considered a leaf node and should be counted once. The second statement says that for each element in P_{n} we will add up whatever number of leaf nodes were counted in the layer beneath the current layer k - 1.

Rearranging the second statement leads to f(P_{n}, k) = n f(P_{n}, k - 1). Reducing further k times leads to f(P_{n}, k) = n (n \cdots (n(1))) = n^{k}.

k-Permutations

The permutation and k-permutation is a way of selecting k items (k \le n) from a list where the order of the selection is important but items cannot be placed back into the set after selection.

The process uses \oplus = \setminus where \setminus(S, e) = \lbrace s \colon s \ne e, s \in S \rbrace is the set difference operator. We use the set difference because the item is removed from the set upon each selection. As before, here is a graph of the process applied to P_{3} with k=3:

To count the number of elements, we need to count the number of nodes at depth k. (The regular permutation can be counted when k = n.) We will write this using the following recurrence relation:

\displaystyle f(P_{n}, 0) = 1
\displaystyle f(P_{n}, k) = \sum_{i = 1}^{n} {f(P_{n-1}, k - 1)}

Using the same labeling scheme as in the k-ary cartesian product, we can interpret the first statement as any node at depth zero will be considered a leaf node and counted once. The second statement says that for each element in P_{n} we will add up whatever number of leaf nodes were counted in the layer beneath the current layer k - 1 for the set P_{n-1}. We use P_{n-1} since we removed an element from P_{n}.

Rearranging the second statement leads to f(P_{n}, k) = n f(P_{n-1}, k - 1). Taking k times leads to f(P_{n}, k) = n (n - 1 \cdots (n - k + 1(1))) = \frac{n!}{(n-k)!}.

Power Set

The power set is the way of selecting zero items to the cardinality of the set items from a set where the order of the selection is not important and items are not placed back into the set after selection.

The process uses \oplus = < where <(S, e) = \lbrace s \colon s < e, s \in S \rbrace. As before, here is a graph of the process applied to P_{3}:

To count the number of elements, we need to count the number of nodes in the tree. We will write this using the following recurrence relation:

\displaystyle f(P_{0}) = 1
\displaystyle f(P_{n}) = \sum_{i=1}^{n} {f(P_{i-1})}

The first statement says for any node a depth zero we will count it once. The second statement states that for each element in P_{n} we will add up the result from P_{0} to P_{n-1}. Starting at i = 1 is a way of encoding that all nodes should be counted. We go up to P_{n-1} because there are n - 1 elements in P_{n} less than n.

Rearranging the second statement leads to f(P_{n}) = \sum_{i=1}^{n-1} {f(P_{i-1})} + f(P_{n-1}) = 2 f(P_{n-1}). Taking the expression to zero leads to f(P_{n}) = 2(2 \cdots(2(1))) = 2^{n}.

k-Combinations

The k-combination is the way of selecting a fixed number of items from a set where the order of the selection is not important and items are not placed back into the set after selection.

The process is identical to the power set.

To count the number of elements, we need to count the number of nodes at depth k in the tree. We will write this using the following recurrence relation:

\displaystyle f(P_{n}, 0) = 1
\displaystyle f(P_{n}, k) = \sum_{i=1}^{n} {f(P_{i-1}, k-1) }

The first statement says for depth zero we will count once, the second statement states that we will add up whatever sum was produced by iterating over P_{i-1} from one to n and reducing the depth k by one. To find the closed form solution, we’ll approach the recurrence relation inductively:

\displaystyle f(P_{n}, 0) = 1
\displaystyle f(P_{n}, 1) = \sum_{i=1}^{n} {f(P_{i-1}, 0) } = \sum_{i=1}^{n} {1} = n
\displaystyle f(P_{n}, 2) = \sum_{i=1}^{n} {f(P_{i-1}, 1) } = \sum_{i=1}^{n} {i-1} = \frac{n(n-1)}{2}
\displaystyle f(P_{n}, 3) = \sum_{i=1}^{n} {f(P_{i-1}, 2) } = \sum_{i=1}^{n} {\frac{(i-1)(i-2)}{2}} = \frac{n(n-1)(n-2)}{6}
\displaystyle f(P_{n}, k) = \sum_{i=1}^{n} {f(P_{i-1}, k-1) } = \frac{n(n-1)(n-2)\cdots(n-k+1)}{k(k-1)(k-2)\cdots1} = \frac{n!}{k!(n-k)!}

Important to notice that for k = 0 that we have the unit, for k = 1 we have the natural numbers, for k = 2 we have the triangle numbers, for k = 3 we have the tetrahedral numbers and so on. The generalized sequence is the Figurate number– these numbers constitute Pascal’s Triangle which is one method of calculating combinations.

Written by lewellen

2011-02-01 at 8:00 am

One tree, many possibilities: Part 2

with one comment

Implementation

In my previous post, I wrote about how to construct a rule based tree that allows one to generate the outputs of a number of counting functions. In this installment, I am providing the corresponding implementation in C#. All five functions rely on the basic tree definition of T_{n}(S, \sigma) which is treated as a kernel function in the implementation.

private List<List<T>> kernel<T>(List<T> S, Func<List<T>, int, List<T>> sigma, int N) {
    return kernel<T>(S, sigma, N, new List<T>());
}

private List<List<T>> kernel<T>(List<T> S, Func<List<T>, int, List<T>> sigma, int N, List<T> u) {
    List<List<T>> R = new List<List<T>>(new List<T>[] { u });
    if (N <= 0)
        return R;

    for (int n = 0; n < S.Count; n++) {
        List<T> v = new List<T>(u);
        v.Add(S[n]);
        R.AddRange(kernel<T>(sigma(S, n), sigma, N - 1, v));
    }

    return R;
}

Apart from the kernel, we still need a couple surjective functions to implement the remaining functions. As discussed in the previous post, we need two functions, one that returns all elements of a list except for a specified index, and one that returns all elements of a list greater than a specified index.

private List<T> notEqual<T>(List<T> S, int n) {
    return new List<T>(S.Where((x, m) => m != n));
}

private List<T> greaterThan<T>(List<T> S, int n) {
    return new List<T>(S.Where((x, m) => m > n));
}

The remaining implementations of the n-ary Cartesian Product, Permutation, k-Permutation, Power Set and n-Combination are now rather trivial.

public List<List<T>> nAryCartesianProduct<T>(List<T> S, int n) {
    List<List<T>> R = kernel<T>(S, (x, y) => x, n);
    R.RemoveAll((x) => x.Count < n);
    return R;
}

public List<List<T>> permutation<T>(List<T> S) {
    return kPermutation<T>(S, S.Count);
}

public List<List<T>> kPermutation<T>(List<T> S, int k) {
    List<List<T>> R = kernel<T>(S, notEqual, k);
    R.RemoveAll((x) => x.Count != k);
    return R;
}

public List<List<T>> powerset<T>(List<T> S) {
    return kernel<T>(S, greaterThan, S.Count);
}

public List<List<T>> nCombination<T>(List<T> S, int n) {
    List<List<T>> R = kernel<T>(S, greaterThan, n);
    R.RemoveAll((x) => x.Count != k);
    return R;
}

Written by lewellen

2008-07-06 at 7:50 pm

One tree, many possibilities

with 2 comments

Introduction

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