Count the number of integer solution to $\sum_{i=i}^{n}{f_ig_i} \geq 5 $

Question

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?

Answer 1

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$.

Answer 2

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.