MathDB
2001 BAMO p5 3^{334} divides a_2001, number of permutations

Source:

August 26, 2019
Sequencenumber theorypermutationdivides

Problem Statement

For each positive integer nn, let ana_n be the number of permutations τ\tau of {1,2,...,n}\{1, 2, ... , n\} such that τ(τ(τ(x)))=x\tau (\tau (\tau (x))) = x for x=1,2,...,nx = 1, 2, ..., n. The first few values are a1=1,a2=1,a3=3,a4=9a_1 = 1, a_2 = 1, a_3 = 3, a_4 = 9. Prove that 33343^{334} divides a2001a_{2001}. (A permutation of {1,2,...,n}\{1, 2, ... , n\} is a rearrangement of the numbers {1,2,...,n}\{1, 2, ... , n\} or equivalently, a one-to-one and onto function from {1,2,...,n}\{1, 2, ... , n\} to {1,2,...,n}\{1, 2, ... , n\}. For example, one permutation of {1,2,3}\{1, 2, 3\} is the rearrangement {2,1,3}\{2, 1, 3\}, which is equivalent to the function σ:{1,2,3}→{1,2,3}\sigma : \{1, 2, 3\} \to \{1, 2, 3\} defined by σ(1)=2,σ(2)=1,σ(3)=3\sigma (1) = 2, \sigma (2) = 1, \sigma (3) = 3.)
Back to ProblemsView on AoPS