Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
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

2 Answers 2

up vote 2 down vote accepted

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.

share|improve this answer

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.