# Thread: Valid combinations of a 3 letter alphabet

1. ## Valid combinations of a 3 letter alphabet

Hi there,

I was hoping one could tell me how to calculate the following problem in the generic form.

3 possible values A,B,C.
where the following constraint states that, "A" must always exist in a combination.

N is the number of columns in a grid that one of the values will be placed.

For example:

if N = 2, then the following are valid combinations:

A A
A B
B A
A C
C A

Invalid combinations are
BB
CC
BC
CB
as these do not have at least one A.

How would you calculate this for N = 3 or N = 4 etc ?

In another example, I can see how the binary alphabet of A,B for N columns can work without the restriction on A.
That is, it is 2^n where n is the number of columns or input number. For example, a 4-input truth table would be 2^4 and 10-input truth table would be 2^10.

However the above scenario has me stumped.

thanks,

I was hoping one could tell me how to calculate the following problem in the generic form.
3 possible values A,B,C.
where the following constraint states that, "A" must always exist in a combination.
N is the number of columns in a grid that one of the values will be placed.
There is a simple answer to above quoted question.
That is for three values and N columns: $\displaystyle 3^N-2^N$.

To see why it works there are $\displaystyle 3^N$ total strings and $\displaystyle 2^N$ do not contain an A.
Remove those.

3. Originally Posted by Plato
There is a simple answer to above quoted question.
That is for three values and N columns: $\displaystyle 3^N-2^N$.

To see why it works there are $\displaystyle 3^N$ total strings and $\displaystyle 2^N$ do not contain an A.
Remove those.
Thats great.

Thanks for getting back to me. I was drawing tables out on paper all day trying to reverse engineer an equation. I'm rusty as hell at math.

I figured out that for a two letter alphabet of say A,B and if we don't care about the constraint on A then there are $\displaystyle 2^N$ combinations.
But I just couldn't piece the 3 letter alphabet together.

Cheers,

4. Hi Plato,

Is it possible to modify that equation to remove duplicates?

Is it possible to define the following where there is an alphabet of 3 strings A,B,C and N columns, where the following holds:
There exists at least one A,
there must at least exist one B or C
and the remaining columns of N can be either an A or B or C.
and any duplicates are excluded. Note the ordering of of 3-tuple sequence is important. That is ABA is not equal to AAB.

From what I could see all the possible combinations of 3 strings ABC, for 3 columns is as follows:

A,A,A Invalid as there is no B or a C
A,A,B
A,B,A
A,B,B
B,A,A
B,A,B
B,B,A
B,B,B Invalid as there must be an A

A,A,A Invalid as there is no B or a C
A,A,C
A,C,A
A,C,C
C,A,A
C,A,C
C,C,A
C,C,C Invalid as there must be an A

A,B,B Duplicate from above
A,B,C
A,C,B
A,C,C Duplicate from above

With a result of 14 possible combinations (I hope I wrote them all out!)

5. There are eighteen such strings.
$\displaystyle \begin{array}{*{20}c} A & A & B \\ A & A & C \\ A & B & A \\ A & B & B \\ A & B & C \\\end{array}$
$\displaystyle \begin{array}{*{20}c} A & C & A \\ A & C & B \\ A & C & C \\ B & A & A \\ B & A & B \\ B & A & C \\ B & B & A \\ B & C & A \\\end{array}$
$\displaystyle \begin{array}{*{20}c} C & A & A \\ C & A & B \\ C & A & C \\ C & B & A \\ C & C & A \\ \end{array}$
What do you call a duplicate?

6. Hi Plato,

Apologies for having bothered you with this.

I see no duplicates in your list.

Can a generic equation be based on this?

Do you mind if I ask how did you go about constructing the table?

What I did was construct 3 tables, the first table looked at all possible combinations of A and B where there must be 1 A. Table two was a copy but replaced B with C. Table three kept all column1 set to A, and then I done a standard logic truth table for B and C (2^2). My approach of course is incorrect.

7. Construct a table of twenty-seven rows and three columns.
In the first column there is a block of nine A’s, followed by a block of nine B’s, followed by a block of nine C’s.

In the second column there is a block of three A’s, followed by a block of three B’s, followed by a block of three C’s. Repeat the two more times,

In the last column make a block of ‘ABC’ repeated nine times.

8. Great.

I did that out on paper there and worked a threat.

Is there a handy formula that describes how 18 valid combinations can be reached?

Would it be $\displaystyle 3^n - 2^n - 1$
where $\displaystyle 3^n$ is the total strings and $\displaystyle 2^n$ do not contain an A and $\displaystyle -1$ is to remove the combination where all 3 A's exist, that is, there is not also at least one B or C.

How do you decide on how many of the same letter goes into the first column. Is there a common pattern or strategy to adopt? What if I have 4 or 5 columns (with 3 letters)?
I see from listing two columns (N=2) there are 3 A's followed by 3 B's followed by 3 C's.
A,A
A,B
A,C
B,B
B,A
B,C
C,A
C,B
C,C

9. I think I understand how your deciding how many of the same letter you place down the first column. i was looking at the case for truth tables $\displaystyle 2^n$ and I see that if n = 4 calculate $\displaystyle 2^3$, if its n is 3 then $\displaystyle 2^2$ will be how many T's and F's in the first column and then you 1/2 that number as you move across the columns.