Count the number of integer solution to $\sum_{i=i}^{n}{f_ig_i} \geq 5 $ How to count the number of integer solutions to $$\sum_{i=i}^{n}{f_ig_i} \geq 5$$  such that $\displaystyle \sum_{i=1}^{n}{f_i}=6$ ,  $\displaystyle \sum_{i=1}^{n}{g_i}=5$ , $\displaystyle 0 \leq f_i \leq 4$ , and  $\displaystyle 0 \leq g_i \leq 4$?
Is there a general formula to calculate things like this?
 A: If $S_n(a,b,c)$ is the number of solutions with $\sum_{i=1}^n f_i = a$, $\sum_{i=1}^n g_i = b$ and $\sum_{i=1}^n f_i g_i = c$, then we have
$$ S_n(a,b,c) = \sum_{j=0}^{\min(4,a)} \sum_{k=0}^{\min(4,b,\lfloor c/j \rfloor )} S_{n-1}(a-j,b-k,c-jk)$$ 
(where we ignore the $\lfloor c/j \rfloor$ if $j=0$).  The initial condition is $S_0(a,b,c) = 1$ for $a=b=c=0$, $0$ otherwise.  On the other hand, the number of solutions with $\sum_{i=1}^n f_i = a$, $\sum_{i=1}^n g_i = b$ and no condition on $\sum_{i=1}^n f_i g_i$ is $A_n(a) A_n(b)$ where
$A_n(a) = \sum_{j=0}^{\min(4,a)} A_{n-1}(a-j)$, and $A_0(a)=1$ for $a=0$, $0$ otherwise.
Your number is then $F_n = A_n(6) A_n(5) - \sum_{c=0}^4 S_n(6,5,c)$.  I used the following
Maple program:
 A := proc (n, a)
   local j;
   option remember; 
    if n = 0 then if a = 0 then 1 else 0 end if 
    else add(A(n-1,a-j),j = 0 .. min(4,a)) 
    end if 
end proc;
S := proc (n, a, b, c) 
  local j, k; 
  option remember; 
   if n = 0 then if a+b+c = 0 then 1 else 0 end if 
   else add(S(n-1,a,b-k,c),k = 0 .. min(4,b))
     +add(add(S(n-1,a-j,b-k,c-j*k),k = 0 .. min(4,b,floor(c/j))),j = 1 .. min(4,a)) 
  end if 
end proc;
F:= n -> A(n,6)*A(n,5) - add(S(n,6,5,c),c=0..4);
L:= [seq(F(n),n=0..11)];  

In practically no time, Maple produces 
$$ L := [0, 0, 12, 318, 2780, 14515, 55056, 167664, 435456, 1003014, 2104140, 4096422]$$
It can then find a polynomial to interpolate these:
 CurveFitting:-PolynomialInterpolation([$0..11],L,n);

$$ 
{\frac {19}{144}}\,{n}^{7}+{\frac {497}{240}}\,{n}^{6}-{\frac {2723}{
144}}\,{n}^{5}+{\frac {3559}{48}}\,{n}^{4}-{\frac {1361}{9}}\,{n}^{3}+
{\frac {9107}{60}}\,{n}^{2}-58\,n
$$
which agrees, of course, with Yuval's result.
A: In principle the way to solve this is as follows. Make a list of all partitions of $6$ having largest part $4$, and a list of all partitions of $5$ having largest part $4$. Now consider all possible ways to "align" these together: Suppose that the $6$-partition is in non-decreasing order, and now each part of the $5$-partition can either be attached to a part in the $6$-partition or not. Out of all these pairs, some will satisfy the condition $\sum_i f_i g_i \geq 5$. For each of these, you can count the possible number of realizations as $n$-vectors, where all unspecified entries are zero. Summing everything, you get what you want.
This method is a bit messy, but there's a trick. Suppose you knew that every feasible pattern has length at most $d$ (for example, trivially $d \leq 11$). Then in the formula you will have terms of the form $\binom{n}{c}$ for $1 \leq c \leq d$, and therefore it's a degree $d$ polynomial, with zero constant coefficient. All you have to do is calculate $d$ values of it, say $n=1$ to $n=d$.
Unfortunately, the bound $d \leq 11$ isn't quite good enough (though eventually even my slow python implementation could enumerate the results up to $n = 11$). One can obtain a better bound and use the method, but alternatively, we can just calculate the results for increasing values of $n$, and stop when we see $k+1$ values that fit a degree $k$ polynomial. We can then "guess" that this polynomial is correct (that's not a formal proof, since the polynomial might fit the extra point by sheer luck, but it's probably true).
Using the latter method, we discover that the result is a degree $7$ polynomial:
$$ \frac{1}{6!} (95n^7 + 1491n^6 - 13615n^5 + 53385n^4 - 108880n^3 + 109284n^2 - 41760n). $$
Substituting $n = 20$, we get $251624220$.
