0
$\begingroup$

Please provide an efficient algorithm to find the coefficient of $x^n$ in the following expansion,

$(1 + x^1 + x^2 + \cdots + x^k)^m$

where $n$, $m$ and $k$ can be as large as ${10}^{10}$.

I have tried to solve it using $(1 + x^1 + \cdots + x^k) = \frac{x^{k+1} - 1}{x - 1}$ and succeeded for values of $n$ upto $10^5$. I am struck for larger values of $n$.

Any help would be appreciated.

$\endgroup$
6
  • 2
    $\begingroup$ Yes that is a useful factorization. What stops you after $n=10^5$? $\endgroup$ – mathreadler May 5 '17 at 22:18
  • $\begingroup$ Could you please elaborate a bit more? I used summation of 2 terms, i using normal binomial theorem & other using negative binomial theorem. The number of terms in summation is of the order of $n$. Thus it was limiting factor here. $\endgroup$ – Math-Rocks May 5 '17 at 22:20
  • $\begingroup$ The Fourier transform could be a possible choice otherwise. It will turn the convolutions into multiplications. Although the normal distribution will extremely fast become a good approximation due to the law of large numbers. $\endgroup$ – mathreadler May 5 '17 at 22:23
  • $\begingroup$ As far as I know, fast fourier transform is used for multiplication of 2 polynomials, but the size of polynomial is also very large here as $k$ is of the order $10^{10}$. Is there exist no efficient way for finding the answer rather than an approximate one? Also, can the answer be found efficiently if the answer is required modulo some value, which might be small, say $10^5$. $\endgroup$ – Math-Rocks May 5 '17 at 22:28
  • $\begingroup$ Of course you mean $\dfrac{x^{k+1}-1}{x-1}$, not $\dfrac{x^k-1}{x-1}$. $\endgroup$ – Robert Israel May 5 '17 at 22:54
2
$\begingroup$

$$ \left( \frac{x^{k+1}-1}{x-1}\right)^m = (1-x^{k+1})^m (1-x)^{-m}$$ $$ (1-x^{k+1})^m = \sum_{j=0}^m {m \choose j} (-1)^j x^{(k+1)j}$$ $$ (1 - x)^{-m} = \sum_{j=0}^\infty {-m \choose j} (-1)^j x^j $$ $$n = (k+1) j + (n - (k+1) j)\ \text{for}\ 0 \le j \le \min(m, \lfloor n/(k+1)\rfloor)$$ Thus your $x^n$ coefficient is $$ \sum_{j = 0}^{\min(m, \lfloor n/(k+1) \rfloor)} {m \choose j} {-m \choose n-(k+1)j} (-1)^{n - kj}$$ Note that for $m \ge 1$, $${-m \choose i} = (-1)^i {m+i-1 \choose i} $$

$\endgroup$
4
  • $\begingroup$ Could you elaborate on how you eliminated the infinite sum? $\endgroup$ – orlp May 5 '17 at 23:14
  • $\begingroup$ Yes, something similar I had done. But shouldn't the number of terms in summation be order of $10^{10}$, as $m = 10^{10}, n = 10^{10}, k = 1$. Can we reduce the number of terms in the summation? Also, if the required answer is modulo some number which is small, say $10^5$, will it be of some use here? $\endgroup$ – Math-Rocks May 5 '17 at 23:15
  • $\begingroup$ @orlp The only terms in the infinite sum that appear are those that multiply a term in the finite sum to give something in $x^n$. $\endgroup$ – Robert Israel May 5 '17 at 23:19
  • $\begingroup$ @Math-Rocks Kummer's theorem on binomial coefficients might be useful to eliminate some of the terms where the product of binomial coefficients will be divisible by the modulus. $\endgroup$ – Robert Israel May 5 '17 at 23:22

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.