3
$\begingroup$

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?

$\endgroup$
5
  • $\begingroup$ Is $n$ fixed?... $\endgroup$
    – user17762
    Commented May 17, 2012 at 22:18
  • $\begingroup$ Yes, It is. Assume n=20. $\endgroup$
    – HHH
    Commented May 17, 2012 at 22:20
  • 1
    $\begingroup$ Looks like a hard question. Why don't you start with something smaller (that is, replace all the numbers with numbers small enough that you can easily write out all the solutions) and see whether there are any patterns you can exploit? $\endgroup$ Commented May 18, 2012 at 0:00
  • $\begingroup$ @Gerry, not for a computer! $\endgroup$ Commented May 18, 2012 at 0:15
  • $\begingroup$ @Yuval, provided the computer has someone like you around to program it! $\endgroup$ Commented May 18, 2012 at 0:47

2 Answers 2

5
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ Dynamic programming always comes in handy! $\endgroup$ Commented May 18, 2012 at 3:49
  • $\begingroup$ Thanks a lot. But what would be the difference in formulating this problem if we add the condition $f_1 \times g_1 \geq 1$? I also wonder to know where I can find some materials on how to solve these kinds of problems? Thanks a lot. $\endgroup$
    – HHH
    Commented May 22, 2012 at 17:27
  • 1
    $\begingroup$ @Hessam: if you add a condition on $f_1$ and $g_1$, it will change $S_1(a,b,c)$, the rest of the dynamic programming algorithm goes similarly. I imagine you'd still get a polynomial for $n \ge 1$. $\endgroup$ Commented May 22, 2012 at 17:34
4
$\begingroup$

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

$\endgroup$
0

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .