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.

1 Answers 1

6

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

  • 0
    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, Prashant2011-11-08
  • 0
    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$.2011-11-09