summation of product of binomials coefficients over compositions

Question

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.

Answer 1

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