Introduction to Probability · Problem 3.1.21

Combinatorics — Grinstead & Snell

Mathematics — Probability · permutations

Problem

Modify the program AllPermutations to count the number of permutations of nn objects that have exactly jj fixed points for j=0,1,2,…,nj = 0, 1, 2, \ldots, n. Run your program for n=2n = 2 to 6. Make a conjecture for the relation between the number that have 0 fixed points and the number that have exactly 1 fixed point. A proof of the correct conjecture can be found in Wilf.

Related theory

Browse the problem library