Thanks to recently held facebook hacker cup, I learnt some new stuff which is Rencontres Numbers.

Here are the few first numbers : 1 0 1 2 9 44 265

The number represent the possibility of different fixed point on sequences’ permutation.
Let’s assume the above numbers as R and N is the fixed point so
for N = 0 -> R = 1
for N = 1 -> R = 0
for N = 2 -> R = 1
for N = 3 -> R = 2
for N = 4-> R = 9

To explain further for different fixed point 0 -> it means all the fixed point are already alligned so there is only 1 possibility.
For N = 1 or different fixed possibility equal to 1, the possibility is 0, why zero you ask ? here is a little example :

ABC -> original position

1 different position means 2 correct position, assume A and B are already in right position, the only left position is C, since A and B already correct, C will ALWAYS be correct, therefore the possibility for only 1 different position is ZERO

for N = 2

AB -> original position
BA -> 1 different fixed position

for N = 3

ABC -> original position
ACB -> A is in correct position therefore it doesn’t satisfied 3 different fixed position
BAC -> C is in correct position therefore it doesn’t satisfied 3 different fixed position
BCA -> Satisfied N =3
CAB -> Satisfied N =3
CBA -> B is in correct position therefore it doesn’t satisfied 3 different fixed position

So after examining the pattern you can see that


Ri = (i-1) * R(i-1) + R(i-2) for R1 = 1 and R2 = 0

Some chinese (I pressume he’s chinese judging from the username) on facebook wall put comment that he found another more difficult formula but work for this Rencontres Number. it went like this

Ri = i! * ( 1/1! - 1/2! + 1/3! .......... 1/i!)

note that the ‘+’ operator has to be done prior to ‘-‘ operator.

Okay since we’ve covered the rencontres numbers, let’s go to what it has to do with combination.
You could google the facebook hacker cup wine tasting if you want to see the original problem definition, but let’s make it simple here. For example there are 13 glasses and you need to guess which glass belong to whom and if you at least guess 10 glass correctly, you won. So how many way you could win the game.

Answer :

multiply each combination of the glass with number of different fixed possibility that we covered earlier

=13c13 * (0 different fixed possibility) +13c12  * (1 different fixed possibility)+ 13c11 (2 different fixed possibility)+ 13c10 (3 different fixed possibility)

=13c13 * 1 + 13c12 * 0 + 13c11 * 1 + 13c10 * 2

=1 * 1 + 13 * 0 + 78 * 1 + 286 * 2

=1 + 0 + 78 + 572

=651

note that ncr means n! / r! – (n-r) !   —>  the combination of r number of n object.

Peeking some accepted source code from korean (again judging from his username) on facebook, He solved this problem by using memoization for combination generated by pascal triangle and also memoization of rencontres number itself (using above formula for dynamic programming approach).

Advertisements