summation of product of binomials coefficients over compositions I am having trouble with this problem which arises in the context of computing lowest theoretically possible computation cost for some cryptographic primitive.
Let $n$ and $a$ be positive integers that are given.
Let $C(n)$ denote the set of compositions of $n$.
We wish to compute
$$
\sum_{S\in C(n)} \prod_{x\in S} \binom{a}{x}
$$
Note that $S$ is an ordered sequence (not a set), so that the product ranges over the components (not elements) of this sequence.
Example for $n=4$ is:
$$
\binom{a}{1}^4 + 3 \binom{a}{1}^2\binom{a}{2} + \binom{a}{2} + 2\binom{a}{1}\binom{a}{3} + \binom{a}{4}
$$
Is there any closed form of this? Or any identity I can use to simplify this?
Thank you for your time.
 A: Let $f(a,n)=\sum_{S\in C(n)} \prod_{x\in S} \binom{a}{x}$ denote the sum in question.
I can $f(a,n)$ with the help of a generating function:
$$
f(a,n)=[x^n]\frac{1}{1-[(1+x)^a-1]}=[x^n]\frac1{2-(1+x)^a}\tag1
$$
The notation $[x^n]f(x)$ means the coefficient of $x^n$ when $f(x)$ is expanded to its Maclaurin series. This is not especially useful for computations by hand, but it gives a way for a sufficiently powerful computer algebra system to find the number. For example, this Mathematica code computes $f(a,n)$:
SeriesCoefficient[1/(2-(1+x)^a), {x,0,n}]

Furthermore, the generating function quickly tells us the asymptotic growth rate. Standard generating function theory (see generatingfunctionology, section 5.2) implies that
$$
f(a,n)\sim C_a\left[\frac{1}{2^{1/a}-1}\right]^n\qquad \text{as $n\to\infty$}\tag2
$$
for some constant $C_a$. This is because $2^{1/a}-1$ is the root of the denominator of the generating function $1/(2-(1+x)^a)$ which is smallest in absolute value. Furthermore, we can give the constant of proportionality:
$$
C_a=\lim_{x\to (2^{1/a}-1)} \frac{1-x/(2^{1/a}-1)}{2-(1+x)^a}\tag3
$$
The approximation in $(2)$ is quite good, in the sense that the relative error converges to zero exponentially quickly as $n$ increases. In the case $a=5,n=10$,the exact value of $f(a,n)$ is $146{,}163{,}251$, while the approximate value is
$$
C_5\left[\frac{1}{2^{1/5}-1}\right]^{10}
\approx 0.77520\cdot (6.725023)^{10}
\approx 1.461632510167618\cdot 10^8
$$
