0
$\begingroup$

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.

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

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}\ .$$

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.