During my calculations I ended up at the following combinatorial problem: In how many way can we write the integer $n$ as the sum of $k$ non-negative integers, each different to one, i.e. calculate
$$\sum_{n_1+n_2+\dots+n_k=n,n_i\ne1}1$$
for non-negative integers $n_i\in\{0,2,3,\dotsc,n\}$, i.e. with $n_i\ne 1$. In fact, I am interested in the order of this sum as $k\to\infty$.
Without the additional assumption $n_i\ne1$, this is a well known problem (see e.g. Number of ways to write n as a sum of k nonnegative integers) and the result is $\binom{n+k−1}{n} = O(k^n)$. How does the order change for my sum? I expect it to be much smaller.
Best Answer
Answering the question for if zeroes are not allowed:
We have the following system:
$\begin{cases} n_1+n_2+\dots+n_k=n\\ n_i\in \Bbb Z\\ n_i\geq 2\end{cases}$
By making a change of variable, setting $m_i=n_i-2$ we have the related system:
$\begin{cases}m_1+m_2+\dots+m_k=n-2k\\ m_i\in\Bbb Z\\ m_i\geq 0\end{cases}$
This is in a known form matching your previous question with answer $\binom{n-k-1}{k-1}$
Allowing $j$ zeroes to be used:
For specifically $j$ zeroes being used, without loss of generality, the first $j$ entries, we have the system $\begin{cases} n_{j+1}+n_{j+2}+\dots+n_k=n\\ n_i\in\Bbb Z\\ n_i\geq 2\end{cases}$
Making a change of variable, $\begin{cases} m_{j+1}+m_{j+2}+\dots+m_k=n-2(k-j)\\ m_i\in \Bbb Z\\ m_i\geq 0\end{cases}$
This is in a known form with $\binom{n-2(k-j)+(k-j)-1}{k-j-1}=\binom{n-k+j-1}{k-j-1}$
The total then is:
$$\sum\limits_{j=0}^{k−1} \binom{k}{j}\binom{n-k+j-1}{k-j-1} = \sum\limits_{j\ge k−\frac{n}{2}}^{k−1} \binom{k}{j}\binom{n-k+j-1}{k-j-1}$$