Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
Is $n$ fixed?... –  user17762 May 17 '12 at 22:18
    
Yes, It is. Assume n=20. –  Hessam May 17 '12 at 22:20
1  
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? –  Gerry Myerson May 18 '12 at 0:00
    
@Gerry, not for a computer! –  Yuval Filmus May 18 '12 at 0:15
    
@Yuval, provided the computer has someone like you around to program it! –  Gerry Myerson May 18 '12 at 0:47

2 Answers 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.

share|improve this answer
    
Dynamic programming always comes in handy! –  Yuval Filmus May 18 '12 at 3:49
    
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. –  Hessam May 22 '12 at 17:27
1  
@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$. –  Robert Israel May 22 '12 at 17:34

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

share|improve this answer
    
Thanks a lot Yuval. –  Hessam May 22 '12 at 17:17

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.