Probability of getting 'k' heads with 'n' coins This is an interview question.( http://www.geeksforgeeks.org/directi-interview-set-1/)

Given $n$ biased coins, with each coin giving heads with probability $P_i$, find the probability that on tossing the $n$ coins you will obtain exactly $k$ heads. You have to write the formula for this (i.e. the expression that would give $P (n, k)$).

I can write a recurrence program for this, but how to write the general expression ?
You can use Dynamic Programming as $N$th turn's outcome is mutually independent to $N-1$th and there are two possible cases here :


$K$ heads already came in $N-1$ turns
$K-1$ heads already came in $N-1$ turns


$dp[i][j]$ : probability of getting $j$ heads in $i$ trials.

So, $dp[n][k] = dp[n - 1][k]\cdot (1 - P[n]) + dp[n - 1][k - 1]\cdot p[n]$
Let F(i,j) be the probability of finding exactly j heads when i biased coins are tossed. and P(i) be the probability of landing head when ith coin is tossed.
The recurrence relation for this problem would look like following :
 F(i, j) = F(i-1, j) * (1-P(i)) + F(i-1, j-1) * P(i)
With the base cases being as written here :- F(1,0) = 1-P(1) and F(1,1) = P(1)

So now the problem reduces to finding value F(n, k) which would give us the probability of finding exactly k heads in n tosses.
this can be extended to find at most k heads or atleast k heads also where we have to find the sum of solutions for all j in [0,k] and [k,n] respectively.