Results 1 to 9 of 9

Math Help - Valid combinations of a 3 letter alphabet

  1. #1
    Newbie
    Joined
    Mar 2010
    Posts
    6

    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.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,663
    Thanks
    1616
    Awards
    1
    Quote Originally Posted by paddyjoesoap View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Mar 2010
    Posts
    6
    Quote Originally Posted by Plato View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Newbie
    Joined
    Mar 2010
    Posts
    6
    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.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,663
    Thanks
    1616
    Awards
    1
    There are eighteen such strings.
    \begin{array}{*{20}c}<br />
   A & A & B  \\<br />
   A & A & C  \\<br />
   A & B & A  \\<br />
   A & B & B  \\<br />
   A & B & C  \\\end{array}
    \begin{array}{*{20}c}<br />
   A & C & A  \\<br />
   A & C & B  \\<br />
   A & C & C  \\<br />
   B & A & A  \\<br />
   B & A & B  \\<br />
   B & A & C  \\<br />
   B & B & A  \\<br />
   B & C & A  \\\end{array}
    \begin{array}{*{20}c} <br />
  C & A & A  \\<br />
   C & A & B  \\<br />
   C & A & C  \\<br />
   C & B & A  \\<br />
   C & C & A  \\ \end{array}
    What do you call a duplicate?
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Newbie
    Joined
    Mar 2010
    Posts
    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.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,663
    Thanks
    1616
    Awards
    1
    Construct a table of twenty-seven rows and three columns.
    In the first column there is a block of nine As, followed by a block of nine Bs, followed by a block of nine Cs.

    In the second column there is a block of three As, followed by a block of three Bs, followed by a block of three Cs. Repeat the two more times,

    In the last column make a block of ABC repeated nine times.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Newbie
    Joined
    Mar 2010
    Posts
    6
    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
    Last edited by paddyjoesoap; March 13th 2010 at 03:38 PM.
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Newbie
    Joined
    Mar 2010
    Posts
    6
    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.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. How many? Using the Alphabet - Please help
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: August 9th 2010, 11:42 AM
  2. Replies: 2
    Last Post: October 4th 2009, 06:31 PM
  3. Letter Combinations
    Posted in the Advanced Math Topics Forum
    Replies: 0
    Last Post: April 4th 2008, 06:51 PM
  4. Letter Combinations
    Posted in the Statistics Forum
    Replies: 5
    Last Post: January 30th 2007, 02:10 PM
  5. Our Alphabet
    Posted in the Statistics Forum
    Replies: 7
    Last Post: January 26th 2007, 12:55 PM

Search Tags


/mathhelpforum @mathhelpforum