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.

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.

share|improve this question

1 Answer 1

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

share|improve this answer
    
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 –  pgolash Nov 8 '11 at 13:36
    
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$. –  Robert Israel Nov 9 '11 at 19:31

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.