TopCoder problem "UnfixedArrangements" used in TCHS08 Round 2 (Division I Level Three)



Problem Statement

    

There are k slots numbered 1 through k, and you must assign a distinct integer between 1 and n, inclusive, to each slot. The resulting configuration is called an arrangement of k from n. An example of an arrangement of 3 from 5 is (2, 4, 3).

An arrangement is called unfixed if no integer is equal to the number of its slot. For example, the arrangement (2, 4, 3) is not unfixed because the integer 3 is in slot number 3. The arrangement (2, 4, 5), on the other hand, is unfixed.

Given ints n and k, return the number of unfixed arrangements of k from n.

 

Definition

    
Class:UnfixedArrangements
Method:count
Parameters:int, int
Returns:long
Method signature:long count(int n, int k)
(be sure your method is public)
    
 

Constraints

-n will be betwen 1 and 20, inclusive.
-k will be between 1 and n, inclusive.
 

Examples

0)
    
3
2
Returns: 3
The unfixed arrangements of 2 from 3 are (2,1), (2,3) and (3,1).
1)
    
1
1
Returns: 0
The only arrangement of 1 from 1 is not unfixed.
2)
    
2
2
Returns: 1
The arrangement (2,1) is unfixed.
3)
    
5
3
Returns: 32

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=8553

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=11151&pm=8553

Writer:

andrewzta

Testers:

PabloGilberto , Olexiy , marek.cygan , ivan_metelsky

Problem categories:

Dynamic Programming, Math