Suppose the probability for getting head is $p_i$ for $i$th coin.
You can easily (and economically) compute the probabilities of exactly $k$ heads using the recursive relation -
$H_{n,k}=p_nH_{n-1,k-1}+(1-p_n)H_{n-1,k}$
Explanation follows.
Let $H_{n,k}$ be the probability of getting exactly $k$ heads using the first $n$ coins. For answering the type of questions you want to solve, all you need is a list of $H_{n,k}$'s.
Note that $H_{n,k}=\sum_{\left[e_i\in\{0,1\},\sum e_i=k\right]}p_i^{e_i}(1-p_i)^{1-e_i}$H_{n,k}=\sum_{\left[over\ e_i's\in\{0,1\},\sum_i^n e_i=k\right]}\prod_{i=1}^n p_i^{e_i}(1-p_i)^{1-e_i}$
The sum (as you mentioned) contains $n\choose k$ entries.
However note that $H_{n,k}=p_nH_{n-1,k-1}+(1-p_n)H_{n-1,k}$
So you can recursively build up the $H_{n,k}$'s which should be simple since there are only a few of them. (To be precise, for $N$ coins, there are $N(N+3)/2$ many of $H_{n,k}$'s since $n\in \{1,...,N\}$ and $k\in \{0,...,n\}$).
As a base for the recursive relation, you can use the following (obvious) identities.
- $H_{n,k}=0$ for $k\gt n$
- $H_{n,0}=\prod_{i=1}^n(1-p_i)$
- $H_{n,n}=\prod_{i=1}^np_i$
