The classic example of the sum of product binomial coefficients is Vandermonde's Identity: 


$$
\sum\_{a\_{1,1}+a\_{1,2}+a\_{1,3}=x}\binom{n}{a\_{1,1}}\binom{n}{a\_{1,2}}\binom{n}{a\_{1,3}}=\binom{3n}{x}
$$


However, I'm interested in the following twist. To motivate the question, consider the simple case in which I'd like to compute the following sum. Assume that $0\leq c\_1\leq n$, $0\leq c\_2\leq 2c\_1$, $n$ and $x\leq 3c\_1$ are given.


$$
\sum\_{\bigcap\left(\substack{a\_{1,1}\leq c\_1,a\_{1,2}\leq c\_1,a\_{1,3}\leq c\_1\\ a\_{1,1}+a\_{1,2}=a\_{2,1}\leq c\_2,a\_{1,2}+a\_{1,3}=a\_{2,2}\leq c\_2\\a\_{1,1}+a\_{1,2}+a\_{1,3}=x}\right)}\binom{n}{a\_{1,1}}\binom{n}{a\_{1,2}}\binom{n}{a\_{1,3}}
$$
After some algebra, this can be simplified to:


$$
\sum\_{\bigcap\left(\substack{x-c\_2\leq a\_{1,1}\leq c\_1\\x-c\_1\leq a\_{2,1}\leq c\_2\\a\_{2,1}-a\_{1,1}\leq c\_1}\right)}\binom{n}{a\_{1,1}}\binom{n}{a\_{2,1}-a\_{1,1}}\binom{n}{x-a\_{2,1}}
$$


which only involves two terms $a\_{1,1}$ and $a\_{2,1}$ that we can sum over.


This is fairly simple to code and corresponds to the case $L=3$. However, I will eventually run into the complicated case where I have the following constrained sum for general $L$:


$$
\sum\_{\bigcap\left(\substack{\bigcup\_{k=1}^{L-1}\bigcup\_{r=1}^{L-k+1}\{a\_{k,r}\leq c\_k \}\\ a\_{L,1}=x}\right)}\binom{n}{a\_{1,1}}\binom{n}{a\_{1,2}}\binom{n}{a\_{1,3}}\cdots\binom{n}{a\_{1,L}}
$$


or alternatively, like above,


$$
\sum\_{\bigcap\left(\substack{ \bigcup\_{k=1}^{L-1}\{x-c\_{L-k}\leq a\_{k,1}\leq c\_k \} \\ \bigcup\_{k=1}^{L-2}\bigcup\_{r=1}^{L-k-1}\{a\_{k+r,1}-a\_{r,1}\leq c\_k \}}\right)}\binom{n}{a\_{1,1}}\binom{n}{a\_{2,1}-a\_{1,1}}\binom{n}{a\_{3,1}-a\_{2,1}}\cdots\binom{n}{a\_{L-1,1}-a\_{L-2,1}}\binom{n}{x-a\_{L-1,1}}
$$


where $a\_{k,r}=\sum\_{s=r}^{r+k-1} a\_{1,s}$


I'm interested in exact solutions to the problem. Is there an efficient way to calculate this sum for general $L$ using `R` (or similar languages as `MATLAB` and `Python`)? 



Constrained sum of product binomial coefficients
I believe I have a working solution that works for general $L>1$:



```
binom.coeff <- function(x,l,size,cvec){
 sum(apply(valid.counts(l=l,cvec=cvec,x=x),1,function(j) prod(choose(size,j))))
}
valid.counts <- function(l,cvec,x){
  vec = seq(from=0,to=cvec[1])
  lst = lapply(numeric(l), function(i) vec)
  mat = as.matrix(expand.grid(lst))

  if(l==2){
    return(mat[which(rowSums(mat)==x),])
  }
  else{
    #k=1 is redundant since all must be less than or equal to cvec[1]
    for (k in seq(from=2, to=l-1)){
      partial = NULL
      for (r in seq(l-k+1)){
        partial = which(rowSums(mat[,r:(r+k-1),drop=FALSE])<=cvec[k])
        mat = mat[unique(partial),]
      }
    }
    return(mat[which(rowSums(mat)==x),])  
  }
}

```

