# Arrangements of values in a set that can contain the same number twice

So I have a problem that can simplify to this : "Given a set $A=\{1,2,3,4\}$, calculate the number of arrangements of at most $n$ values that can be formed"

For example, for $n=4$, one correct arrangement is $1142$, or $1111$.

Initially, I thought that I could make arrangements of $4\cdot n$ values, then I found out that there are arrangements that get counted twice (because, for $n=2$, for example, I "imagined" $A$ as $\{1,1,2,2,3,3,4,4\}$, then I tried dividing that value by $n-1$, because I thought that there are $n$ arrangements with the same configuration, and I only need $1$. This also didn't work, as I tested it with a program that counted by backtracking.

Can you please give me any tips?

-
Is $1142$ the same as $1124$? – Henry Feb 20 '12 at 15:17
When you say "the number of arrangements of at most $n$ values" is $114$ a correct arrangement for $n=4$? – Henry Feb 20 '12 at 15:17

Tip: Start small. If $n=1$, there are $4$ arrangements of length $n$, easily listed: $1$, $2$, $3$, $4$.

How many arrangements of length $2$ are there? Make an explicit listing of them, as follows. There is $1$, followed by anything, that is $11$, $12$, $13$, and $14$. That's $4$ arrangements. Then there is $2$, followed by anything. That's $4$ more. Then there is $3$, followed by anything, $4$ more. Finally, there is $4$, followed by anything. The total is $4+4+4+4=16$.

How many arrangements of length $3$? There are the ones of shape $1ab$, where $ab$ is any arrangement of length $2$. By the previous paragraph, there are $16$ of these. Then there are the ones of shape $2ab$, where $ab$ is any of the $16$ arrangements of length $2$, another $16$. And then there are the $3ab$, and the $4ab$, a total of $16+16+16+16=64$.

Continue. How many arrangements of length $4$? There are the ones of shape $1abc$, where $abc$ is any of the $64$ arrangements of length $3$. And the ones of shape $2abc$, $3abc$, $4abc$, a total of $64+64+64+64$.

Note that the number of arrangements of length $n+1$ is, by the same argument, $4$ times the number of arrangements of length $n$. Now you should be able to find a compact general formula.

Remark: The description "at most $n$ values" is unfortunately imprecise. My interpretation was based on the examples in the post, and is not necessarily the one that you intend.

If you mean that arranements of any length $\le n$ are allowed, then one would add together the number of arrangements of length $1$, of length $2$, and so on up to length $n$. By the argument above, this sum is $4+4^2+5^3+\cdots +4^n$, which is a geometric series. There is a "closed form" formula for this sum.

There are other possible interpretations, for example the one in which we allow any string, with the only restriction being that there are at most $n$ occurrences of $1$, at most $n$ occurrences of $2$, and so on. That version is potentially more difficult to get a simple expression for.

-

If $A$ has $m$ distinct elements then there are $m^n$ ways of arranging $n$ elements of $A$ values where reprition is allowed and order matters.

If you want at most $n$ elements then you get $m^0+m^1+\cdots+m^n = \dfrac{m^{n+1}-1}{m-1}$ ways.

-