In how many ways can we create a set of 8 elements out of 7 elements?

Question

Given the set $\{1,2,3,4,5,6,7\}$.

We would like to create a string of size 8 so that each of the elements of the set appears at least once in the result. How many ways are there to create such a set?

I think that the answer should be: order 7 elements $7!$ and chose 1 number out of 7 to reappear and chose a position out of 8 available.

Am I correct? Or am I missing something?

Answer 1

First "decide" on the elements in the string. All seven elements are forced choices, and you have seven choices for the extra element, with only a single repetition. So: $7$ possibilities.

Next think about the order. There are $8!$ ways of ordering eight distinct elements, but there is a single repetition in each string in your problem (mutually swapping their positions won't affect the string). So you need to divide by $2!$ to compensate.

Answer = $7\cdot \frac{8!}{2!}=141120$

Answer 2

You are a factor $2$ too high because you count each list twice. For example, the list $1,1,2,3,4,5,6,7$ is counted once with the order $1,2,3,4,5,6,7$ and the spare $1$ in the first place, then again with the same order and the spare $1$ in the second place. Each list is counted once with each choice of which of the duplicated elements is the spare.

Answer 3

You have $7$ choices of which number to duplicate. Once you've made that choice, you have $\binom 82$ choices of pairs of locations for that number. And once you've made that choice, you have $6!$ choices of arrangements for the remaining numbers.

So the total number of possible strings is $\frac 72 8!$.