I have a sequence of n numbers in a computer game, I want to move m solders randomly based on this sequence. for example
n={1,2,3}
and m=3
we get the following solution:
s1={1}, s2: {2,3}, s3={} or
s1={1,2,3}, s2: {},s3={}, or
s1={3,2,1}, s2: {},s3={}, or
s1={3,2}, s2: {}, s3={1}, or
s1={1}, s2: {2}, s3={3}, or
s1={3}, s2: {2}, s3={1}, or
s1={}, s2: {23}, s3={1}, or ...
for n=3 and m=3 I counted 60 different ways if I was not wrong, what is the formula to find the number of all possible solutions?
You can see it in this way:
You have three distinguishable containers s1,...,s3 and 3 distinguishable numbers to put in them, being the order important inside every container.
So your different options can be identified with the number of ways we can order the 3 numbers on a line, with 2 indistinguishable markers added to tag where one container finishes and the following one starts.
For example, your option s1={1},s2={2,3},s3={} is identified with the string 1|23| (the number one in the first container, the numbers 2,3 in the second one, the third one empty), while your option s1={}, s2={}, s3={3,1,2} is identified with the string ||312.
So, the number of options you have is the same as all the possible orderings of 3 distinguishable numbers and 2 indistinguishable markers, or (3+2)!/2! = 5!/2! = 60.
In the general case you will have n numbers and m-1 markers, and hence you will have (n+m-1)!/(m-1)! options.
You can see it in this way:
You have three distinguishable containers s1,...,s3 and 3 distinguishable numbers to put in them, being the order important inside every container.
So your different options can be identified with the number of ways we can order the 3 numbers on a line, with 2 indistinguishable markers added to tag where one container finishes and the following one starts.
For example, your option s1={1},s2={2,3},s3={} is identified with the string 1|23| (the number one in the first container, the numbers 2,3 in the second one, the third one empty), while your option s1={}, s2={}, s3={3,1,2} is identified with the string ||312.
So, the number of options you have is the same as all the possible orderings of 3 distinguishable numbers and 2 indistinguishable markers, or (3+2)!/2! = 5!/2! = 60.
In the general case you will have n numbers and m-1 markers, and hence you will have (n+m-1)!/(m-1)! options.
Thank you Ioulia and Jose
It works, you are so genius, I spent one night trying to figure it out, but could not, thanks for the help, could you please direct me to some proof for the formula.
Cheers
- Badges
- Science topic
- Similar topics
- Mathematics
- Statistics
- Statistical Software
- R