1
$\begingroup$

What is the number of solutions of $(a_i)_{i=1}^n$ such that $$\sum_{i=1}^nia_i\le b,\quad a_i\in\{-1,1\},\quad \sum_{i=1}^n{a_i}=c$$ given $b,c\in\mathbf Z$?

Is there a generating function solution?

$\endgroup$
4
$\begingroup$

The g.f. equals $$\frac1{1-y}\prod_{i=1}^n \left(xy^i + (xy^i)^{-1}\right).$$ That is, the number of solutions is given by the coefficient of $x^cy^b$.

$\endgroup$
4
  • $\begingroup$ Thank you, Max. I came up with the same formulation. However, I was expecting further development to get a simpler and direct expression like many other generating function solutions produce. Perhaps, this is the most we can obtain. Short of further analytical simplification, if we enumerate it with a computer, does this generating function formulation help with reducing complexity of the enumeration compared to generating solutions of the inequality with brute force? Do we need a symbolic computation software? $\endgroup$ – Hans Aug 11 '16 at 21:05
  • $\begingroup$ Call the above generating function $g(x,y)$. The coefficient of $x^cy^b$ is the complex contour integral $\frac{1}{(2\pi i)^2}\oint_{|x|=\delta_1<1}\oint_{|y|=\delta_2<1}\frac{g(x,y)}{x^{c+1}y^{b+1}}dxdy$. But there does not seem to be a simple expression for this integral. Maybe it is useful in obtaining asymptotics for large $n$, $b$ or $c$. I would appreciate it, Max, if you could share your opinion on the benefit/usefulness of generating functions that does not produce simpler expression. $\endgroup$ – Hans Aug 11 '16 at 21:28
  • $\begingroup$ @Hans: I believe the formula is not so helpful for computation. It can lead to a dynamic programming algorithm for computing the coefficient, but this algorithm can be directly seen from the original problem formulation. $\endgroup$ – Max Alekseyev Aug 12 '16 at 14:15
  • $\begingroup$ That was what I thought. I have a dynamic programming or recursive algorithm. Do you know if my contour integral is any good for finding the asymptotics for large $n$, $b$ or $c$? $\endgroup$ – Hans Aug 12 '16 at 17:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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