Clock Problem

The problem is equivalent to the number of ways the number $k$ can be written as the sum of $n$ nonnegative integers with $2x_i \leq k+1$. This condition implies that we are not moving a click twice in a row. If the condition is violated, then $$𝑥_i≥⌈𝑘/2⌉+1. (1)$$ (here $⌈𝑘/2⌉$ is the smallest integer larger than $k/2$). So the total number of combinations without moving a clock twice in a row is the same as the number of nonnegative integer solutions to $$\sum_{i=1}^n 𝑥_𝑖=𝑘, x_i \geq 0 (*)$$ subject to $2𝑥_𝑖≤𝑘+1$. Apply the principle of inclusion-exclusion, where the $𝑛$ properties to be excluded are $2𝑥_𝑖≥𝑘+2$, equivalently, $𝑥_𝑖≥⌈𝑘/2⌉+1$. Without any constraints the total number of solutions of (*) is $C(𝑘+𝑛−1, 𝑛−1)$. Considering the constraints one at a time, the number of solutions violating (1) for some $1\leq i \leq n$ is $C(𝑘−(⌈𝑘/2⌉+1)+𝑛−1, 𝑛−1)$. It is not possible to satisfy (1) more than once. Putting all this together, the total number of solutions of (*) not violating (1) is $$C(𝑘+𝑛−1,𝑛−1)−C(𝑛,1)C(𝑘−⌈𝑘/2⌉+𝑛−2,𝑛−1)$$ $$=C(𝑘+𝑛−1,𝑛−1)−𝑛C(⌊𝑘/2⌋+𝑛−2,𝑛−1).$$
So the total number of different combinations of clocks is
$$\sum_{l=0}^{k}\left( C(l+𝑛−1,𝑛−1)−𝑛C(⌊l/2⌋+𝑛−2,𝑛−1) \right)$$
which is the answer to your questions.


You can check that for $n=2$ and $k=2$ this gives 4.


Next I explain why the number of nonnegative solutions of (*) without any constraint is $C(𝑘+𝑛−1,𝑛−1)$. Write the number $n+k$ as the sum of $n+k$ ones: \[n+k=1+1+1+\dots +1,\] there are $n+k-1$ $"+"$ signs above. In $C(n+k-1,n-1)$ ways we can choose $n-1$ "+" signs to remove and be left with $k-1$ "+" signs. If there are no "+" signs between numbers we just add them. Then we will get a solution to $$\sum_{i=1}^n y_i=k+n, \text{with} \ \ y_i \geq 1.     (**)$$ Subtracting $n$ from both sides and letting $x_i=y_i-1$, we get a solution to (*). So there is a one to one correspondence between solutions of (*) and (**).