How many sequences can be formed with a given set of characters?

Question

I have a set of characters. The set of characters can ever break their order of characters. They have spaces as well and these can move.

How many sequences can be formed with a given set of characters?

Example

a b d - -

can be

a b d - -
a b - d -
a - b d -
- a b d -
- a b - d
- a - b d
- - a b d

Which has $7$ different possibilities

I need a formula that can calculate the number of sequences for any given characters and spaces

i.e:

a b c d e - - - - -

a b c d - 

Can you help me?

Answer 1

You have to count the total number $n$ of characters and for every characters $c_{k}$ which appears more than once you have to count how many times $n_{k}$ it appears.

Then all the possible combination you are searching for are $$\frac{n!}{n_1!n_2!\cdots n_m!}$$ where $c_m$ is the last character which appears more than once.

P.S. In your example you have $5$ characters and one of them (the space -) appears $2$ times, so the possible combinations are $\frac{5!}{2!} =60$. You have found only $7$ of them because you forgot some (like a b - - d).

EDIT

I misunderstood the question and the solution I provided earlier is not correct. Here I put what sould be the right solution.

We just want to know how many combinations we can obtain by mantaining the order of characters but placing the spaces between them.

If we have $n$ characters (spaces included) a combination is uniquely identified by where the $k$ spaces are put. We have $n$ possible places to put the first space, $n - 1$ to put the second (we are excluding the first place we just filled) and so on, till we have $n - k$ places to put the last space.

Before we can conclude we observe that this works only if the spaces are "different" and we can distinguish them, but since we can't we have to divide the number we found by all the possibile rearrangements of the spaces in their $k$ places. (To understand this think if we have two places and two spaces, at first we consider "first space on first place and second space on second place" different from "first space on second place and second space on first place").

In the end we obtain: $$\frac{n(n-1)\cdots(n-k)}{k!}$$

Answer 2

If you have n objects, m of which are the same (m< n), then the number of distinct permutations is $\frac{n!}{m!}$.

In the case of "abd--" you have 5 objects, two of which, the '-'s, are the same so the number of distinct permutations is $\frac{5!}{2!}= 60$. Your list of 7 misses 53 permutations!

To take a simpler case "ab--" has 4 objects, two of which are the same. There are $\frac{4!}{2}= 12$ permutations. They are:

ab--

a-b-

a--b

-ab-

-a-b

-ba-

-b-a

--ab

--ba

ba--

b-a-

b--a

-a-b-

-ab-

Answer 3

Such a sequence is completely determined by the positions of the spaces. Given a sequence with $n$ characters and $k$ spaces, the number of such sequences is $$\binom{n + k}{k}$$

Let's consider the example you posed. You have three characters and two spaces. Therefore, you should have $$\binom{3 + 2}{2} = \binom{5}{2} = 10$$ sequences. They are $$abd\square\square, ab\square d \square, ab\square\square d, a\square bd \square, a \square b \square d, a \square \square bd, \square abd \square, \square ab \square d, \square a \square bd, \square \square abd$$