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 ?
 A: 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]$
A: Consider the function
$[ (1-P_1) + P_1x] \times [(1-P_2) + P_2 x ] \ldots [(1-P_n) + P_n x ]$
Then, the coefficient of $x^k$ corresponds to the probability that there are exactly $k$ heads. 
The coefficient of $x^k$ in this polynomial is $\sum_{k-\mbox{subset} S} [\prod_{i\in{S}} \frac{1-p_i}{p_i} \prod_{j \not \in S} p_j] $
A: Let us say p = Pi, and q = 1 - Pi.
Then the probability of a given sequence, e.g., 100010..., in which k heads appear in n flips  e.g pqqqpq... can be given by
$$p^k.q^{n-k}$$
There are a total of $2^n$ possible sequences. Only some of these give k heads and n - k tails. Their number is
$$\frac{n!}{k! (n-k)!} = {n \choose k}$$
Since any one or another of these sequences will do, the probability that exactly k heads occur in n flips would be
$${n \choose k}p^k.q^{n-k}$$
[Source]
A: For exactly k heads in tossing of n biased coins - there are $^nC_k$ possible sets of coins which must be heads while the others are tails, we hence sum over all these sets.

Let S be a set such that $S \subseteq \{1,2,3,\dots,n\}$ and $|S|=k$, then,
 $P(n,k) = \Sigma_{\vee S} \> p_{i_1}p_{i_2}\dots p_{i_k} (1-p_{j_1})(1-p_{j_2})\dots(1-p_{j_{n-k}})$ for $i_{1},i_{2},\dots,i_{k} \in S$ and $j_{1},j_{2},\dots,j_{n-k} \not \in S$
A: 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.  
