I want to select $N$ numbers from the first $N$ natural numbers (repetitions are allowed and the order of picking the numbers matters) such that the maximum among these numbers is $K$.
I thought about fixing the last number as $K$ and varying the other $N - 1$ numbers, and then multiplying by $N!$ to get all permutations of these sequences. The answer this way is $N! \cdot{} K^{N - 1} $
The problem is that this generates a lot of duplicates and the answer is more than I expect.
How can I tackle this problem?
Example:
For $N = 3$:
when $K = 1$, the answer is $1$.
when $K = 2$, the answer is $7$ with the corresponding sequences as $(1, 1, 2), (1, 2, 1), (1, 2, 2), (2, 1, 1), (2, 1, 2), (2, 2, 1), (2, 2, 2)$.
when $K = 3$, the answer is $19$ with the corresponding sequences as $(1, 1, 3), (1, 2, 3), (1, 3, 1), (1, 3, 2), (1, 3, 3), (2, 1, 3), (2, 2, 3), (2, 3, 1), (2, 3, 2), (2, 3, 3), (3, 1, 1), (3, 1, 2), (3, 1, 3), (3, 2, 1), (3, 2, 2), (3, 2, 3), (3, 3, 1), (3, 3, 2), (3, 3, 3)$.
It is easier to solve a small variant. Let $A_K=A_K( N)$ be the number of ways to choose $N$ numbers from $1$ to $K$. Then of course $A_K=K^N$. This counts the number of ways to do what you want such that the maximum is $≤K$. To get exactly what you want we must subtract. The number of ways to do it such that the maximum is exactly $K$ is $$B_K=B_K(N)=A_K-A_{K-1}=K^N-(K-1)^N$$
We remark that $$B_2(3)=2^3-1^3=7\quad \&\quad B_3(3)=3^3-2^3=19$$ as desired.