Number of ways to write $n$ as sum of $k$ non-negative integers without 1 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.
 A: 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:


*

*pick which entries are zero

*apply the same process as above to the remaining entries


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}$$
A: Let $t(n)$ be the number you are interested in and let $c(n,k)$ be the number of way that $n$ can be written as the sum of $k$ distinct nonnegative numbers. Then, 
$$c(n,k) \ge t(n) \ge c(n,k) - k\cdot c(n-1,k-1)$$
because $c(n-1,k-1)$ counts all those decompositions where $n_1=1$, or all those decompositions where $n_2=1$, etcetera. Of course we have subtracted too much, inclusion-exclusion and all, but note that 
$c(n,k) - k\cdot c(n-1,k-1)$ is still on the order of $n^k$. Hence, $t(n)$ is also on the order of $n^k$.
A: If $T(n,k)$ is the answer, we have
$$ \eqalign{T(n,0) &= \cases{1 & if $n=0$\cr
                             0 & otherwise}\cr
             T(n,k+1) &= T(n,k) + \sum_{j=2}^n T(n-j,k)\cr}$$
This has generating function $$G(x,y) = \sum_{n=0}^\infty \sum_{k=0}^\infty T(n,k) x^n y^k = \dfrac{1-x}{1-x-y+xy-x^2y}$$
This can be written as $$G(x,y) = \sum_{k=0}^\infty \left( 1 - \frac{x^2}{1-x}\right)^k y^k$$
or as
$$ G(x,y) = \sum_{n=0}^\infty a_n(y) x^n$$
where
$$ a_n(y) = \left(\left( 1+3y+\sqrt {1+2y-3\,{y}^{2}} \right)  \left( 1-y-\sqrt {
1+2y-3\,{y}^{2}} \right) ^{n}+ \left(1+3y- \sqrt {1+2y-3\,{y}^{2}
} \right)  \left( 1-y+\sqrt {1+2y-3\,{y}^{2}} \right) ^{n}
\right)/\left((2+4y-6\,{y}^{2}) (2-2y)^n\right)
$$
Each $a_n$ is actually a rational function with denominator $(1-y)^{\lfloor 1+n/2\rfloor}$ for $n \ne 1$. In particular, it has radius of convergence $1$ for all $n \ne 1$.  The asymptotics of $T(n,k)$ as $k \to \infty$ for fixed $n$ are governed by the coefficient of $(1-y)^{-\lfloor 1+n/2\rfloor}$ in its partial fraction expansion.  It appears that we have 
$$T(n,k) \sim \cases{k^{n/2}/(n/2)! & if $n$ is even\cr k^{(n-1)/2}/((n-3)/2)! & if $n \ge 3$ is odd\cr}$$
