4
$\begingroup$

I wanted to know if it is possible to use exponential generating functions to evaluate composition of N using K distinct numbers (where the supply of numbers is infinite)?

For e.g if N=10 and a1=2,a2=3,a3=5

then number of solutions would be (2,3,5),(2,5,3),(3,2,5),(3,5,2),(5,2,3),(5,3,2),(2,2,2,2,2),(3,3,2,2),(3,2,2,3),(2,2,3,3),(2,3,2,3),(3,2,3,2),(2,3,3,2)

I tried with writing generating functions for 2,3 and 5 but was not able to deduce anything.

$\endgroup$
6
$\begingroup$

If $f(n,k)$ is the number of compositions of $n$ using exactly $k$ numbers chosen from $\{2,3,5\}$, then the ordinary generating function $F(t,k) = \sum_{n=0}^\infty f(n,k) t^n = (t^2 + t^3 + t^5)^k$. The ordinary generating function for all compositions using numbers chosen from $\{2,3,5\}$ is $\sum_{k=0}^\infty (t^2 + t^3 + t^5)^k = \frac{1}{1 - t^2 - t^3 - t^5}$.

$\endgroup$
  • $\begingroup$ Thanks for your reply. I got what you explained. I could find the coefficient of the power of x concerned. I could find it manually by doing some calculations, but just wanted to know if you are aware of any generic formula to do so. The problem I am trying to solve is given some K integers each of value<=15, I wanted to know the number of ways that N can be summed up using those K (order matters). K and value of each integer will be given as input and changes from one iteration to another. Thanks, Prashant $\endgroup$ – pgolash Nov 8 '11 at 13:36
  • $\begingroup$ If $f(N)$ is the number of compositions of $N$ using a set $S$ of integers, you can compute it fairly efficiently using the recurrence $f(N) = \sum_{s \in S, s \le N} f(N-s)$ with $f(0) = 1$. $\endgroup$ – Robert Israel Nov 9 '11 at 19:31

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.