Permutations & derangements

Overview

Counting arrangements is naturally recursive because fixing one position leaves a smaller counting problem. k-permutations P(n,k) chooses an ordered arrangement of k items from n: pick any of the n for the first slot, then arrange k-1 from the remaining n-1, giving P(n,k) = n * P(n-1, k-1). Derangements — permutations where no element stays in its original position — need a subtler two-term recurrence and, crucially, two base cases, because D(n) depends on both D(n-1) and D(n-2).

Why it matters

Permutation counts size the search spaces you are about to explore: knowing that 12! is roughly half a billion tells you immediately whether brute force is viable. Derangements answer the classic "nobody draws their own name" question in secret-santa assignments, and they are a good example of a recurrence whose derivation genuinely matters — you cannot guess it.

Core concepts

k-permutations. P(n,k) = n * P(n-1, k-1), base case P(n,0) = 1 (exactly one way to arrange nothing). Full permutations are the case k = n, giving n!.

Why two base cases for derangements. The recurrence D(n) = (n-1) * (D(n-1) + D(n-2)) reaches back two steps, so a single base case leaves D(1) undefined. Both D(0) = 1 and D(1) = 0 are required — and D(1) = 0 is correct: a single item has nowhere else to go.

Where the recurrence comes from. Place item 1 in any of the n-1 other positions, say position j. Either item j moves to position 1 (leaving a derangement of the remaining n-2), or it does not (leaving a derangement of n-1 with a relabelled constraint). Hence the two terms.

Growth. Factorials explode: 20! is near the limit of a 64-bit integer, and 21! overflows it. Derangements grow at roughly n!/e.

Overlapping subproblems. The naive two-term derangement recursion recomputes values exponentially, exactly like naive Fibonacci — memoise it or compute bottom-up.

Syntax notes

/* ordered arrangements of k items from n */
long long pnk(int n, int k) {
    return (k == 0) ? 1 : (long long)n * pnk(n - 1, k - 1);
}

/* derangements: TWO base cases are mandatory */
long long derange(int n) {
    if (n == 0) return 1;              /* the empty arrangement counts */
    if (n == 1) return 0;              /* one item must stay put */
    return (long long)(n - 1) * (derange(n - 1) + derange(n - 2));
}

/* bottom-up avoids the exponential recomputation */
long long derange_fast(int n) {
    long long a = 1, b = 0;            /* D(0), D(1) */
    for (int i = 2; i <= n; i++) { long long c = (long long)(i - 1) * (a + b); a = b; b = c; }
    return (n == 0) ? 1 : b;
}

Key points:

• Cast to long long before multiplying, or the product overflows as int first.
• derange as written is exponential — the rolling version is the one to use.
• P(n,0) = 1, not 0; the empty arrangement is a valid arrangement.

Lesson

Counting arrangements is recursive: k-permutations P(n,k) peel one position at a time, and derangements (permutations with no fixed point) follow a two-term recurrence D(n)=(n-1)(D(n-1)+D(n-2)).

Code examples

#include <stdio.h>
static long long pnk(int n,int k){ return k==0 ? 1 : (long long)n*pnk(n-1,k-1); }
static long long derange(int n){ if(n==0) return 1; if(n==1) return 0; return (long long)(n-1)*(derange(n-1)+derange(n-2)); }
int main(void){
    printf("P(10,3) ordered picks = %lld\n", pnk(10,3));
    printf("derangements of 5 items = %lld\n", derange(5));
    return 0;
}

Line by line

Common mistakes

Confusing permutations with combinations; a single base case for derangements.

Debugging tips

Compiler errors and warnings:

• warning: integer overflow in expression — cast to long long before multiplying, not after.
• No warning for a missing second base case; it manifests as infinite recursion.

Runtime symptoms:

• Stack overflow in derange. Only one base case, so derange(1) recurses into derange(-1) and downward forever.
• derange takes visibly long past n = 30. The naive form is exponential — memoise or use the rolling loop.
• pnk(n,0) returns 0. The base case must return 1.
• Wrong results above 20. 20! is about 2.4 x 10^18, near the long long limit; 21! overflows.
• Negative counts. Signed overflow — the values wrapped.

Technique: check both against their known sequences — permutations P(5,2) = 20, derangements 1, 0, 1, 2, 9, 44. A single wrong term identifies which base case is off.

Memory safety

• Signed overflow is undefined behaviour, and factorial-scale values reach it fast. Cast before multiplying, bound the input, and document the largest supported n.
• Missing base cases cause unbounded recursion, which is a stack overflow — a hard crash with no recovery. Any recurrence reaching back two steps needs two seeds.
• Exponential recursion is a runtime hazard, not a memory one: derange(50) naively would never finish. Memoise or iterate.
• Negative inputs. pnk(n, k) with k > n should be 0, and negative arguments are meaningless — validate at the boundary rather than letting the recursion wander.
• No heap use, so nothing to free; the rolling version uses O(1) space.

Real-world uses

Concrete uses: Permutation counts size search spaces in scheduling, routing and puzzle solving — they tell you when brute force is hopeless. Derangements model secret-santa draws where nobody may draw themselves, hat-check problems, and randomised assignment with exclusion constraints. Both appear constantly in probability calculations.

Professional best practices:

Beginner:

• Write out the first few terms of any recurrence and check them before coding.
• Count the base cases: a recurrence reaching back k steps needs k seeds.

Intermediate:

• Convert two-term recurrences to a rolling loop; the recursive form is for exposition, not production.
• Use permutation counts as a feasibility check before committing to an exhaustive search.
• Apply a modulus early when the problem specifies one, rather than overflowing first.

Practice tasks

1. (Beginner) k-permutations. Implement long long pnk(int n, int k). Example: P(5,2) -> 20; P(5,0) -> 1. Concepts: base case, cast-before-multiply.

2. (Beginner) Derangements. Implement derange(n) with both base cases. Example: D(4) -> 9. Concepts: two-term recurrence, two seeds.

3. (Intermediate) Make it fast. Rewrite derange bottom-up with two rolling variables and compare timings for n = 40. Concepts: exponential vs linear.

4. (Intermediate) Probability check. Compute D(n)/n! for n = 5..15 and observe it converging to about 0.3679 (1/e). Concepts: validating a recurrence against a known limit.

Summary

Fixing one position turns an arrangement count into a smaller one: P(n,k) = n * P(n-1,k-1) with P(n,0) = 1. Derangements — permutations leaving nothing in place — follow D(n) = (n-1)(D(n-1) + D(n-2)), and because that reaches back two steps it needs two base cases, D(0) = 1 and D(1) = 0; supplying only one causes unbounded recursion. The naive two-term form recomputes exponentially, so use a rolling loop. Cast to a wide type before multiplying, since factorial-scale values overflow almost immediately.

Practice with these exercises

• k-permutations P(n,k)
• Count derangements