Results 1 to 3 of 3

Math Help - Permutations?

  1. #1
    Junior Member
    Joined
    Feb 2010
    Posts
    56

    Permutations?

    How many permutations of the English alphabet do not contain and of the strings "fish", "rat", or "bird"?

    No repetition...obviously.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member

    Joined
    May 2006
    From
    Lexington, MA (USA)
    Posts
    11,735
    Thanks
    642
    Hello, chickeneaterguy!

    I have an imcomplete solution.
    Maybe someone can finish it?


    How many permutations of the English alphabet do not contain
    any of the strings FISH, RAT, or BIRD?

    No repetition . . . obviously.

    There are 26! permutations of the alphabet.

    How many of these do contain FISH, RAT, or BIRD?


    The permutation contains the string FISH.
    FISH can appear in 23 possible positions in the permutation.
    The other 22 letters can be placed in 22! orders. .[1]
    . . Hence, FISH appears in: . 23\cdot 22! permutations.

    The permutation contains the string RAT.
    RAT can appear in 24 positions in the permutation.
    The other 23 letters can be placed in 23! orders.
    . . Hence, RAT appears in: . 24\cdot23! permutations.

    The permutation contains the string BIRD.
    BIRD can appear in 23 possible position in the permutation.
    The other 22 letters can be placed in 22! orders.
    . . Hence, BIRD appears in: . 23\cdot22! permutations.


    I thought the answer is: . 26! - (23\cdot22! + 24\cdot23! + 23\cdot 22!)

    . . but it is wrong.


    In [1] when the other 22 letters are placed,
    . . they could include the strings RAT or BIRD (or both).

    I tried to eliminate this duplication,
    . . but got stuck in a tangled, sticky web.


    Can anyone salvage my work?
    Or simply find a better approach?

    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    Quote Originally Posted by Soroban View Post

    I have an imcomplete solution.
    Maybe someone can finish it?
    You are very close! Due to having a common letter, fish and bird can't appear together, neither can rat and bird, so all we have to consider is fish and rat.

    Backing up just a little, note that to count the permutations that contain "fish", we can treat "fish" as if it were a single letter, then just jump straight to 23! instead of writing 23 * 22!.

    The number of permutations that contain both rat and fish is 21!

    So the answer is 26! - (23! + 24! + 23!) + 21!

    It is an application of the inclusion-exclusion principle.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Permutations
    Posted in the Advanced Algebra Forum
    Replies: 12
    Last Post: October 25th 2010, 02:22 AM
  2. Permutations Help
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: March 9th 2010, 07:30 PM
  3. Permutations
    Posted in the Statistics Forum
    Replies: 3
    Last Post: March 11th 2009, 05:39 PM
  4. permutations
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: February 11th 2009, 05:42 PM
  5. Permutations
    Posted in the Statistics Forum
    Replies: 1
    Last Post: September 20th 2008, 11:11 AM

Search Tags


/mathhelpforum @mathhelpforum