n n

¯ ¯

A1 © · · · © An = n! ’ (n ’ 1)! + (n ’ 2)! ’ . . .

1 2

n

(’1)k

= n! .

k!

k=0

Dn

Thus Dn is the nearest integer to n! e’1 , since ’ e’1 as n ’ ∞.

n!

3.2 Functions

Let A, B be sets. A function (or mapping, or map) f : A ’ B is a way to associate

a unique image f (a) ∈ B with each a ∈ A. If A and B are ¬nite with |A| = m and

|B| = n then the set of all functions from A to B is ¬nite with nm elements.

De¬nition. The function f : A ’ B is injective (or one-to-one) if f (a1 ) = f (a2 )

implies that a1 = a2 for all a1 , a2 ∈ A.

The number of injective functions from an m-set to an n-set is nm .

De¬nition. The function f : A ’ B is surjective (or onto) if each b ∈ B has at least

one preimage a ∈ A.

The number of surjective functions from an m-set to an n-set is n! S(m, n).

De¬nition. The function f : A ’ B is bijective if it is both injective and surjective.

If A and B are ¬nite then f : A ’ B can only be bijective if |A| = |B|. If

|A| = |B| < ∞ then any injection is a bijection; similarly any surjection is a bijection.

There are n! bijections between two n-sets.

If A and B are in¬nite then there exist injections which are not bijections and vice

versa. For instance if A = B = N, de¬ne

1 n=1

f (n) = g(n) = n + 1.

and

n’1 otherwise

Then f is surjective but not injective and g is injective but not surjective.

Proposition.

n

n

(’1)k (n ’ k)m

n! S(m, n) =

k

k=0

Proof. This is another application of the Inclusion-Exclusion principle. Consider the

set of functions from A to B with |A| = m and |B| = n. For any i ∈ B, de¬ne Xi to

be the set of functions avoiding i.

¯ ¯

So the set of surjections is X1 ©· · ·© Xn . Thus the number of surjections from A to

¯ ¯

B is X1 © · · · © Xn . By the inclusion-exclusion principle this is J⊆B (’1)|J| |XJ |.

If |J| = k then |XJ | = (n ’ k)m . The result follows.

Mappings can be “composed”. Given f : A ’ B and g : B ’ C we can de¬ne

gf : A ’ C by gf (a) = g(f (a)). If f and g are injective then so is gf , similarly for

surjectivity. If we also have h : C ’ D, then associativity of composition is easily

veri¬ed : (hg)f ≡ h(gf ).

3.3. PERMUTATIONS 27

3.3 Permutations

A permutation of A is a bijection f : A ’ A. One notation is

12 3 4 5 6 78

f= .

13 4 2 8 7 65

The set of permutations of A is a group under composition, the symmetric group

sym A. If |A| = n then sym A is also denoted Sn and |sym A| = n!. Sn is not abelian

” you can come up with a counterexample yourself. We can also think of permutations

as directed graphs, in which case the following becomes clear.

Proposition. Any permutation is the product of disjoint cycles.

We have a new notation for permutations, cycle notation.1 For our function f

above, we write

f = (1)(2 3 4)(5 8)(6 7) = (2 3 4)(5 8)(6 7).

3.3.1 Stirling numbers of the ¬rst kind

De¬nition. s(n, k) is the number of permutations of {1, . . . , n} with precisely k cycles

(including ¬xed points).

n

For instance s(n, n) = 1, s(n, n ’ 1) = , s(n, 1) = (n ’ 1)!, s(n, 0) =

2

s(0, k) = 0 for all k, n ∈ N but s(0, 0) = 1.

Lemma 3.1.

s(n, k) = s(n ’ 1, k ’ 1) + (n ’ 1)s(n ’ 1, k)

Proof. Either the point n is in a cycle on its own (s(n’1, k’1) such) or it is not. In this

case, n can be inserted into any of n ’ 1 places in any of the s(n ’ 1, k) permutations

of {1, . . . , n ’ 1}.

We can use this recurrence to prove this proposition. (Proof left as exercise.)

Proposition.

xn = s(n, k)xk

k

3.3.2 Transpositions and shuf¬‚es

A transposition is a permutation which swaps two points and ¬xes the rest.

Theorem 3.2. Every permutation is the product of transpositions.

Proof. Since every permutations is the product of cycles we only need to check for

cycles. This is easy: (i1 i2 . . . ik ) = (i1 i2 )(i2 i3 ) . . . (ik’1 ik ).

Theorem 3.3. For a given permutation π, the number of transpositions used to write

π as their product is either always even or always odd.

1 See the Algebra and Geometry course for more details.

CHAPTER 3. SETS, FUNCTIONS AND RELATIONS

28

+1 if always even even

We write sign π = . We say that π is an permutation.

’1 if always odd odd

Let c(π) be the number of cycles in the disjoint cycle representation of π (including

¬xed points).

Lemma 3.2. If σ = (a b) is a transposition that c(πσ) = c(π) ± 1.

Proof. If a and b are in the same cycle of π then πσ has two cycles, so c(πσ) =

c(π)+1. If a and b are in different cycles then they contract them together and c(πσ) =

c(π) ’ 1.

Proof of theorem 3.3. Assume π = σ1 . . . σk ι = „1 . . . „l ι. Then c(π) = c(ι) + k ≡

c(ι) + l (mod 2). Hence k ≡ l (mod 2) as required.

We note that sign π = (’1)n’c(π) , thus sign(π1 π2 ) = sign π1 sign π2 and thus

sign is a homomorphism from Sn to {±1}.

even

A k-cycle is an even permutation iff k is odd. A permutation is an per-

odd

mutation iff the number of even length cycles in the disjoint cycle representation is

even

.

odd

3.3.3 Order of a permutation

If π is a permutation then the order of π is the least natural number n such that π n = ι.

The order of the permutation π is the lcm of the lengths of the cycles in the disjoint

cycle decomposition of π.

In card shuf¬‚ing we need to maximise the order of the relevant permutation π. One

can show (see) that for π of maximal length we can take all the cycles in the disjoint

cycle representation to have prime power length. For instance with 30 cards we can get

a π ∈ S30 with an order of 4620 (cycle type 3 4 5 7 11).

Conjugacy classes in Sn