Results 1 to 4 of 4
Like Tree2Thanks
  • 2 Post By Plato

Thread: Arrangements of alphabet not containing MATH, RUNS, FROM. (Inclusion-Exclusion)

  1. #1
    Newbie
    Joined
    Nov 2016
    From
    Norway
    Posts
    1

    Arrangements of alphabet not containing MATH, RUNS, FROM. (Inclusion-Exclusion)

    Using the inclusion- Exclusion formula, compute how many arrangements of the 26 alphabet letters there are that contain none of the words MATH, RUNS, FROM?

    Could someone please explain how to do this?


    Solution says; 26! -3*23! +2*20!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Feb 2015
    From
    Ottawa Ontario
    Posts
    1,634
    Thanks
    304

    Re: Arrangements of alphabet not containing MATH, RUNS, FROM. (Inclusion-Exclusion)

    Your question is as unclear as this answer:
    Remove M : no MATH or FROM
    Remove R : no RUNS
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor

    Joined
    Apr 2005
    Posts
    19,104
    Thanks
    2800

    Re: Arrangements of alphabet not containing MATH, RUNS, FROM. (Inclusion-Exclusion)

    It's hard to know what kind of explanation you will understand since you don't tell us what you do understand.
    Do you understand that there are n! ways to arrange n distinct things? There are 26! ways to arrange the 26 letters in the alphabet.
    That's the reason for that first "26!". We then subtract off the number of "forbidden" arrangements.

    If an arrangement contains "MATH" then the other 26- 4= 22 letters can be in any order. There are 22! such arrangements. Further, the "MATH" can appear in any of 23 places-before or after the other letters or in the 21 places between the 22 letters. That gives 23(22!) arrangements that contain "MATH".

    If an arrangement contains "RUNS", the same argument gives 23(22!) arrangements that contain "RUNS".

    If an arrangement contains "FOR", the other 26- 3= 23 letters can appear in 23! arrangements and "FOR" can appear in any of 24 places among those 23 letters. There are 24(23!) arrangements that contain "FOR".

    We need to subtract those from the 26!

    BUT we those 23(22!) arrangements that contain "MATH" may include some that also contain "RUNS" or may include "FOR", or both. Those will get subtracted more than once. We need to calculate how many of those arrangements there are and add them back in.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor

    Joined
    Aug 2006
    Posts
    21,149
    Thanks
    2603
    Awards
    1

    Re: Arrangements of alphabet not containing MATH, RUNS, FROM. (Inclusion-Exclusion)

    Quote Originally Posted by ole94 View Post
    Using the inclusion- Exclusion formula, compute how many arrangements of the 26 alphabet letters there are that contain none of the words MATH, RUNS, FROM? Solution says; 26! -3*23! +2*20!
    The other two replies are solutions. Here is my solution.
    Consider these three blocks: $\boxed{\text{MATH}},~\boxed{\text{RUNS}},~\& ~ \boxed{ \text {FROM}}$
    To use inclusion/exclusion to find the number at least one of the blocks occurs we must find the ways one at a time; subtract ways two at a time; add back way in which all three occur. Each block is four letters long leaving 22 other letters. They with one block make 23 objects. Thus the three taken one at a time gives $3(23!)$

    Now the fun begins. It is impossible the have blocks $\boxed{\text{FROM}}~\&~\boxed{\text{RUNS}}$ occur together. Right?
    But the pair $\boxed{\text{MATH}}~\&~\boxed{\text{RUNS}}$ can occur together, no problem: $(26-8)+2=20)$ So $20! $
    The pair $\boxed{\text{MATH}}~\&~\boxed{\text{FROM}}$ can occur together, only as $\boxed{\text{FROMATH}}$ : $(26-7)+1=20)$ So $20! $
    Thus taken two at a time is $2(20!)$ And we arrive with at least one at a time in $3(23!)-2(20!)$ ways.

    Subtract that from the total: $(26!)-3(23!)+2(20!)$.
    Thanks from topsquark and HallsofIvy
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Inclusion Exclusion
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: Mar 9th 2011, 10:38 AM
  2. Inclusion/Exclusion
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: Jan 19th 2011, 03:49 AM
  3. Inclusion-exclusion math problem
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: Dec 6th 2009, 08:28 PM
  4. Inclusion/Exclusion
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: Nov 3rd 2009, 08:46 AM
  5. math question - inclusion exclusion principle
    Posted in the Discrete Math Forum
    Replies: 9
    Last Post: Jan 28th 2009, 10:44 AM

/mathhelpforum @mathhelpforum