Induction factorial?

Question

Let n be a positive integer, and let S be a set of cardinality n. Show (using induction) that there exist n! permutations on S.

Answer 1

Clearly, there is only one permutation of the empty set, and 0!=1, so this is true when n=0. Now suppose this is true for some n. Suppose we want to construct a permutation of n+1 elements. We have n+1 choices for the first element, times (by our induction hypothesis) n! ways of permuting the remaining elements, so there are (n+1)*n! or (n+1)! permutations. Thus by induction, there are n! permutations of n elements for all n. Q.E.D.

Answer 2

First we need to show that it is true for n = 1.
For a set with exactly one element, there is obviously only 1 permutation so this is obviously true.

Next assume that we know the theorem for n up to some number N. We need to show that it is true for for N+1 as well.
So, lets start by imagining a set with cardinality N. This set will will have N! permutations. Let us then add 1 more element to the set, so it has cardinality N+1. The old permutations are still valid, but we need to add the new element to them. We can do this by placing it before any of the N elements, or by placing it at the very end of the permutation. So there are N+1 choices where to put the new element in changing the old permutation to the new one.
Therefore there are (N+1)*N! possible permutations or (N+1)!

Answer 3

When n = 1 S contains one element so it has only one arrangement ie 1! permutations.

Ie true for n = 1

Assume true for n = k ie S has k elements and so has k! permutations

When n = k + 1 S has k + 1 elements this consists of a set with k elements together with an extra element That extra element can be put in k + 1 different positions in the set with k elements, namely the 1st position the second position the third position ..... the last or k + 1 position and the set with k elements can be arranges k! ways. So The set with k + 1 elements can be arranged in (k + 1) * k! = (k + 1)! ways

So if it true for n = k then it is definitiely true for n =- k + 1

Well it is true for n = 1 and so it is true for n = 2
Since it is true for n = 2 then it is true for n = 3 and so forth for all cardinal numbers