Maximum Cycle Value of 1
Time limit1sMemory limit128 MB
Given n and k, count permutations of 1..n whose cycle containing element 1 has maximum element exactly k.
- Level
Medium6 of 10
- Topics
- Combinatorics, Math, Dynamic programming
- Solved
- No attempts yet
Problem
P is a permutation of the integers from 1 to n. Starting from 1 and repeatedly applying P produces the sequence
P(1), P(P(1)), P(P(P(1))), ...
The largest value that appears in this repeating cycle is called the maximum cycle value of 1.
For example, if P = (3, 2, 5, 4, 1, 7, 8, 6), then
P(1) = 3
P(P(1)) = P(3) = 5
P(P(P(1))) = P(5) = 1
So 3, 5, and 1 repeat, and the maximum cycle value of 1 is 5.
Given integers n and k, count the permutations whose maximum cycle value of 1 is exactly k.
Input
The first line contains the number of test cases T. (1 <= T <= 1,000)
Each test case contains two integers n and k. (1 <= k <= n <= 20)
Output
For each test case, output the number of permutations of 1, ..., n whose maximum cycle value of 1 is exactly k.