# Number of ways to break $n$ into $\lceil n/k\rceil$ positive integers each at most $k$

Basically we want to write $n$ as the sum of positive integers not greater than $k$, and we want to minimize number of terms. So there are $\lceil n/k\rceil$ terms. How many such sequences are there?

Two sequences are distinct if they contain different numbers at some position. That is we're counting ordered sequences.

• Are you counting, for example, $7=3+2+2$ and $7=2+3+2$ as two distinct ways? – Mark Fischler May 6 '17 at 14:26
• Yes. Added to the question. – Artur May 6 '17 at 14:42

## 2 Answers

Let $\bigl\lceil{n\over k}\bigr\rceil=:r$. Then $r-1<{n\over k}\leq r$, or $$0\leq rk-n<k\ .$$ Let $$x_i=k-p_i\>, \quad 0\leq p_i<k\qquad(1\leq i\leq r)$$ be the sizes of the $r$ parts. Then $$n=\sum_{i=1}^r x_i=rk-\sum_{i=1}^r p_i$$ and therefore $$\sum_{i=1}^r p_i=rk-n\in[0,k[\ .\tag{1}$$ This means that we have to count the number of nonnegative solutions $(p_1,\ldots, p_r)$ of $(1)$ satisfying $p_i<k$ for all $i$. This latter condition will be automatically fulfilled since $rk-n<k$. "Stars and bars" then produces the following number $N$ of solutions: $$N={rk-n+r-1\choose r-1}\ .$$

Adopting @ChristianBlatter's terminology, we define

\begin{align} r &= \lceil {n \over k} \rceil \\ h &= rk - n \\ \end{align}

• $r$ is the number of partitions we divide $n$ into; and
• $h$ is the number of holes (shortfalls) we have to distribute amongst the $r$ partitions.

Using a Stars and Bars argument, We have $r - 1$ divisions to put among the $h$ holes. So the number of arrangements is

$${h + r - 1 \choose h}$$

This result is equivalent to @ChristianBlatter's.