A couple of things that I've noticed (though I haven't worked through all of the code in detail):

public Object[] ApplyTo(Object[] arr)

Again I don't know how this is going to be used, but this looks suspiciously as if you were doing something like Foo[] myFoos = (Foo[]) myPermutation.ApplyTo(oldFoos), which is bad. You should make ApplyTo generic, so you don't need to cast the returned array back to the original type.

result[i] = arr.GetValue(this.data[i]);

I don't see why you use GetValue instead of [] here.

public Permutation Next()

It might be nicer to have a static method which returns an enumerable of all the permutations instead of having to call the Next method all the time. Though of course that depends on how it is used.

public static int Factorial(int n)
{
    int f = 1;
    while (n > 1) { f *= n; --n; }
    return f;
}

The backwards-counting while-loop seems harder to understand than a plain forward-counting for-loop to me. Or you could define it using LINQ's Aggregate method (you did tag this "functional programming" after all).

Also I'd put the main logic into a method int Product(int from, int to) which multiplies the numbers from from to to and then just call that as Product(1, n) to define Factorial.

public static int Combination(int n, int k)
{
    return Factorial(n) / (Factorial(k) * Factorial(n - k));
}

This seems to be a less optimized reimplementation of Permutation.Choose, I don't see why you'd need this method twice.

That said you can optimize this version a bit by using the fact that x! / y! is the product of the numbers from k+1 to n (using my suggested Product method):

return Product(k+1, n) * Factorial(n-k);

This way the method does slightly less work and can work with more numbers without overflowing, while still being as concise as before.

A couple of things that I've noticed (though I haven't worked through all of the code in detail):

public Object[] ApplyTo(Object[] arr)

Again I don't know how this is going to be used, but this looks suspiciously as if you were doing something like Foo[] myFoos = (Foo[]) myPermutation.ApplyTo(oldFoos), which is bad. You should make ApplyTo generic, so you don't need to cast the returned array back to the original type.

result[i] = arr.GetValue(this.data[i]);

I don't see why you use GetValue instead of [] here.

public Permutation Next()

It might be nicer to have a static method which returns an enumerable of all the permutations instead of having to call the Next method all the time. Though of course that depends on how it is used.

public Object[] ApplyTo(Array arr)
{
    Object[] result = new Object[arr.Length];
    for (int i = 0; i < result.Length; ++i)
    {
        result[i] = arr.GetValue(this.data[i]);
    }

    return result;
}

The only reason that comes to mind why it'd make sense to take Array rather than Object[] (or better yet: generics) here, would be to work with arrays of arbitrary dimensions. However the code will only work with one-dimensional arrays, so this overload seems completely superfluous to me.

public static int Factorial(int n)
{
    int f = 1;
    while (n > 1) { f *= n; --n; }
    return f;
}

The backwards-counting while-loop seems harder to understand than a plain forward-counting for-loop to me. Or you could define it using LINQ's Aggregate method (you did tag this "functional programming" after all).

Also I'd put the main logic into a method int Product(int from, int to) which multiplies the numbers from from to to and then just call that as Product(1, n) to define Factorial.

public static int Combination(int n, int k)
{
    return Factorial(n) / (Factorial(k) * Factorial(n - k));
}

This seems to be a less optimized reimplementation of Permutation.Choose, I don't see why you'd need this method twice.

That said you can optimize this version a bit by using the fact that x! / y! is the product of the numbers from k+1 to n (using my suggested Product method):

return Product(k+1, n) * Factorial(n-k);

This way the method does slightly less work and can work with more numbers without overflowing, while still being as concise as before.