In general, a permutation is a one-to-one mapping from all of some collection to all of that collection; its outputs are exactly its inputs and it's invertible. If we compose a permutation before a mapping from its space, we get the same outputs as before, although the composite maps different inputs to each given output. However, here, I'll be looking at the special case of a permutation of a natural; and the mappings from a natural are called lists, so the rearranged mapping obtained by composing one after a permutation is just another list, of the same length, but with its entries possibly in a different order. Indeed, since a permutaiton is a mapping from the natural to itself, it is naturally represented as a list of the earlier naturals; their order within the list is what distinguishes one permutation of that natural from any other. The identity permutation is simply the list of earlier naturals in increasing order.
Most of what I have to say below is equally applicable to any finite set, via any choice of a single isomorphism between it and the natural that is its number of members; and the available choices for that isomorphism are, given one of them, just the results of composing the given one before the permutations of that natural. However, precisely because of this equivalence, there is very little of interest to say about a finite set beyond that its corresponds exactly with the natural that is the count of its members.
So suppose we have a natural n; every permutation of it is a list of the n earlier naturals, in some order. We have n candidates to put first in the list; for each choice of the first i entries in the list, we're left with n −i choices for the next entry in the list; when we get to chose the last entry in the list, we've already chosen n −1 entries, so we're left with only 1 choice. Thus the nuber of possible permutations of a natural n is just product(: n −i ←i |n); the factors are, reversing the order, just 1 through n, making this equivalently product(: i +1 ←i |n).
This product is written n! and the function that maps n to it is known
as factorial
. As may readilly be verified from its
specification, (n +1)! = n!.(n +1) and the first few of its values, [0!, 1!, 2!,
…], are
As might not be a huge surprise, once you think about it, factorial grows rather rapidly; faster, indeed, than exponentially.
We can define an ordering on permutations by, when comparing two of them,
looking for the least index at which they have distinct entries; if there's no
such index, they're the same permutaiton (equal at every index); otherwise, they
each have a natural at the position where they differ, so we sort the one with a
lower natural in this position before the one with a higher natural there. If
this sorts permutation r before s and s before t, then there's some i for which
(:r:i) = (:s:i) and r(i) < s(i) and, likewise, some j for which (:s:j) =
(:t:j) and s(j) < t(j). If i = j, this gives (:r:i) = (:s:i) = (:t:i) and
r(i) < s(i) < t(i). If i < j then (:r:i) = (:s:i) = (:t:i) and r(i)
< s(i) = t(i); otherwise, j < i so (:r:j) = (:s:j) = (:t:j) and r(j) =
s(j) < t(j). In each case, we duly sort r before t, so this sorts
before
ordering is transitive; and it's manifestly a full ordering on
permutations of any given natural. We can, furthermore, enumerate all
polynomials of a given n, starting with the identity permutation (which sorts
before any other) by applying the following successor operation to the last that
was iterated, call it p:
(Here I use reverse
in the sense appropriate to lists, [a, b, c,
d] ↔ [d, c, b, a], rather than the sense generally applicable to relations,
where r relates x to y precisely if reverse(r) relates y to x.] I provide an
implementation of this iteration
in study.maths.permute's Permutation.all(n) class
method.
Given a set of size n, its power set
is the set of
subsets of it; for each member of the set, each subset either does or doesn't
include that member, so the possible subsets correspond exactly with the the
mappings from the set to a set with exactly two members, e.g. {0, 1}, with the
subset corresponding to a mapping ({0, 1}: f |S) being {s in S: f(s) = 1}, for
example. Consequently, as each member of the set gives us two choices for the
function's output, we have power(n, 2)
subsets of a set of size n.
Next let us consider partitioning those subsets by size; how many subsets does it have, of each size ? Let chose(n, i) be the number of subsets of size i that we can chose from within a set of size n. Clearly chose(n, 0) = 1 as there's only one empty set; it is a sub-set of every set; so every set does have it as the set's sole empty sub-set. Equally, by considering which elements are left out of each sub-set, chose(n, i) = chose(n, n −i) for each i; and, by specification, chose(n, i) is 0 unless 0 ≤ i ≤ n. We can quickly infer chose(n, n) = chose(n, 0) = 1, which should be no surprise; the only subset that has n elements is the one that has all n elements in it, with none left out.
For n in {0, 1}, that's told us all about chose(n); now let's consider how we can infer chose(n +1) from chose(n). Given a set with n +1 members, we can pick any one member of it, label that q and then ask, for any given sub-set, whether it has q in it; a sub-set of size i +1 that does has q in it has, as its set of other members, one of the chose(n, i) subsets of size i drawn from the remaining n elements; all other sub-sets of size i +1 are subsets of this set of remaining elements, so there are chose(n, i +1) of them. Since every subset of size i +1 in the size n +1 set is of one of these forms, and no subset is of both forms, we can infer
If we represent a set by a list of its i members, we get i! lists that all equally represent the same set; having quantified this redundancy, we can think in terms of lists to determine chose(n, i) as follows: there are n! lists of the n members of the set; if we take the first i entries of the list as a subset, every subset of size i must show up in i! forms, with the rest of the permutation comprising the rest of the elements of the set in their (n −i)! forms; so each initial portion of length i shows up (n −i)! times and i! such lists all represent the same sub-set; and there are n! lists in all, so there must be chose(n, i) = n!/i!/(n −i)! subsets of size i, whenever 0 ≤ i ≤ n.
Certainly we can confirm this for chose(n, 0) = n!/0!/(n −0)! = 1 for every natural n; and the chose(n, i) = chose(n, n −i) symmetry is immediately apparent from the formula. Let's now just check this matches with the iterative formula above:
So we could obtain this formula inductively from the iterative formula (always nice to know, if only as a sanity check on our reasoning). In particular, since the iterative calculation starts with ({0, 1}: chose(0) :) and each output of chose(n +1) is a sum of outputs of chose(n), we can induce that all outputs of chose(n) are natural, for all natural n. Thus, in particular, n! is a multiple of i!j! whenever i +j = n.
We can also rearrange the formula into a more symmetric form:
for which F(i, j) = F(j, i) and, rearranging the iterative formula, we get:
Here, F(i, j) is the number of ways one may partition a set of size i +j into one subset of size i and another of size j. (It is also the number of distinct lists ({naturals}: f |j+1) with sum(f) = i.)
Notice that, for natural n, since every sub-set of a set of size n is finite, so has some size, sum(chose(n)) = power(n, 2). In particular, as all its outputs are naturals (so there are no negative contributions to that sum), every output of chose(n) is bounded above by power(n, 2).
A fuller treatment in my messier area, or Ben Orlin's counting of the subsets.
Written by Eddy.