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
    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