# AOCP/Permutations

### From charlesreid1

## Contents

# Volume 1

## Chapter 1: Basic Concepts

### Permutations and Factorials

If we have n distinct objects to arrange in a row, and order of placement matters, we can arrange these things in n! different ways.

For the first object, we have n choices of places to put it. For the second object, we have n-1 choices of places to put it. And so on.

In general, if we have to choose k objects out of n total, and arrange them in a row, we have the number of possibilities as:

The total number of permutations is

The process of constructing a permutation of n objects, given all permutations of n-1 objects, is important. If we consider the case of three objects ,

Here are permutations of order 3:

Now, how to get to permutations of 4 objects?

**Method 1:**

For each permutation of n-1 elements, form n additional permutations by inserting the nth element in every possible open slot

Adding 4 to our set of objects and using method 1 gives:

**Method 2:**

For each permutation of the n-1 elements, form n new permutations by first constructing the array:

Aaaaaand... yeah. No idea.

### Factorial Identities

Factorial definition:

and with this convention,

for all positive integers n.

10! is a useful benchmark - it is around 3.5 million.

10! represents an upper ceiling on computable tasks.

To tell how large a very big factorial is going to be, use Stirling's formula:

Thus, for 8! = 40320:

Relative error of Stirling's formula is approximately

To obtain the exact value of n! factored into primes, we can use some useful identities. First, the prime p is a divisor of n! with multiplicity:

As an example, for n = 1000, p = 3,

which gives

Therefore, is divisible by , but not by .

Furthermore, to speed up the calculation of the above, we can use the identity

### Binomial Coefficients

See AOCP/Binomial Coefficients

### Multinomial Coefficients

See AOCP/Multinomial Coefficients

### Generating Functions

# Flags

The Art of Computer ProgrammingArt of Computer Programming
Part of the 2017 CS Study Plan.
Mathematical Foundations: AOCP/Infinite Series AOCP/Harmonic Numbers Puzzles/Exercises:
AOCP/Combinatorics
AOCP/Combinatorial Algorithms AOCP/Five Letter Words AOCP/Generating Permutations and Tuples
· Template:AOCPFlag · e |