# 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,
Paddy.

2. Originally Posted by paddyjoesoap
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: $3^N-2^N$.

To see why it works there are $3^N$ total strings and $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: $3^N-2^N$.

To see why it works there are $3^N$ total strings and $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 $2^N$ combinations.
But I just couldn't piece the 3 letter alphabet together.

Cheers,
paddy.

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!)

many thanks in advance,
paddy.

5. There are eighteen such strings.
$\begin{array}{*{20}c}
A & A & B \\
A & A & C \\
A & B & A \\
A & B & B \\
A & B & C \\\end{array}$

$\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}$

$\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 $3^n - 2^n - 1$
where $3^n$ is the total strings and $2^n$ do not contain an A and $-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 $2^n$ and I see that if n = 4 calculate $2^3$, if its n is 3 then $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.