Let A be the set of all possible finite sequences (n₀, n₁, ..., n_k) of integers such that,

for each i = 0, 1, ..., k

i appears in the sequence n_i times.

Here are some sequences in set A:

1,2,1,0
2,0,2,0
2,1,2,0,0
3,2,1,1,0,0,0
4,2,1,0,1,0,0,0
k-3,2,1,0,0,...,1,0,0,0

Are there other sequences in set A? If so, what are they?

Now prove it.

All the sequences in set A were described in the question; there are no others.

Proof:

First, note that in any sequence, n₀+n₁+...+n_k = k+1, because the sum of terms having each value is the total number of terms.

Now, let's look at the non-zero terms among n₁, n₂, ..., n_k. Let m be the number of such terms, which is the number of terms minus the number of zeros. The number of terms among n₁, n₂, ..., n_k is k, and the number of zeros among these terms is n₀ (n₀ can't itself be zero) so the number of non-zero terms among n₁, n₂, ..., n_k is given by

m = k - n₀.

Now, let's look at the sum of such terms. n₁+n₂+...+n_k = k+1 - n₀.

Now, that's interesting. The sum of non-zero terms starting with n₁ is exactly one more than the number of such terms. Since the smallest such term is 1, and all the terms are integers, there is just one "left over", so exactly one non-zero term (starting with n₁) is 2, and all the rest are 1.

Moreover, I can show that there are at most four non-zero terms in the sequence.

Since all the terms starting with n₁ are either zero, one or two, there are at most three different numbers among the elements n₁, n₂, ..., n_k, namely 0, 1, and 2. In the whole sequence, then (including n₀) there are at most four different numbers: n₀, 0, 1, and 2.

So, to summarize, the interesting properties of the sequence are:

(1) The non-zero terms starting with n₁ consist of ones and twos, and at most one of these terms is equal to 2.

(2) There are at most four non-zero terms in the entire sequence.

Now, let's itemize the sequences that have this property:

n₀ can't be 0, because if it were, there would be no zeros, a contradiction.

If n₀ is 1, then n₁ must be at least 1, but it can't be 1 because then there would be two ones, a contradiction.

So if n₀ is 1, n₁ must be 2, so n₂ must be 1, and there are no three's (or higher) in the sequence, so all remaining elements of the sequence are zero. So n₃ is zero, ending the sequence: 1,2,1,0

If n₀ is 2, n₁ can be 0, n₂ must be at least 1, but it can't be one because then there would be two twos, a contradiction.

So if n₀ is 2, and n₁ is 0, then n₂ is 2, and there are no three's (or higher) in the sequence, so n3 is zero, ending the sequence: 2,0,2,0

If n₀ is 2, n₁ can be 1, in which case n₂ must be 2, and the remaining two elements must be zero: 2,1,2,0,0.

If n₀ is 3 or higher, then among the remaining terms there must be one two and two ones to avoid violating one of the "interesting properties" listed above. (There can't be fewer than four non-zero terms, because n_i=1, where i=n₀, so n₁ is non-zero, and one of the terms is two, so n₂ is also non-zero.) Since there are two ones in the sequence, n₁=2, and since there is one two, n₂=1. The other "one" is at n_i, where i=n₀. These are the four non-zero elements of the sequence, so there are k-4=n₀ zeros, finishing out the sequence.

These sequences are:

3,2,1,1,0,0,0
4,2,1,0,1,0,0,0
5,2,1,0,0,1,0,0,0
...