Results 1 to 5 of 5
Like Tree1Thanks
  • 1 Post By SlipEternal

Thread: Inclusion–exclusion principle

  1. #1
    Newbie
    Joined
    Sep 2017
    From
    Israel
    Posts
    3

    Inclusion–exclusion principle

    Hi,
    Im trying to solve this problem, but kinda stuck..

    Question:
    In how many ways can you arrange the string AAABBCCDD
    if AAA, BB, CC, DD sequences are not allowed. (AA sequence can appear)

    how can I know how many arrangement for a string when a certain sequence is not allowed?
    Last edited by gk104; Sep 9th 2017 at 01:42 AM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Apr 2005
    Posts
    19,245
    Thanks
    2836

    Re: Inclusion–exclusion principle

    1) Calculate the number of different arrangements of AAABBCCDD.

    2) Calculate the number of arrangements that do include AAA or BB or CC or DD.

    3) Subtract (2) from (1).
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Sep 2017
    From
    Israel
    Posts
    3

    Re: Inclusion–exclusion principle

    Quote Originally Posted by HallsofIvy View Post
    1) Calculate the number of different arrangements of AAABBCCDD.

    2) Calculate the number of arrangements that do include AAA or BB or CC or DD.

    3) Subtract (2) from (1).
    How do i calculate the number of arrangements that include AAA,BB,CC,DD?
    that's the part that I struggle with
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Joined
    Nov 2010
    Posts
    2,706
    Thanks
    1033

    Re: Inclusion–exclusion principle

    Let event $E_{\text{subsequence}} $ be the event that a permutation of $AAABBCCDD $ contains a particular subsequence. (This is not standard notation, just convenient)

    Example:
    $|E|=\dfrac{9!}{3!2!2!2!} $
    $|E_{AAA}|=\dfrac{7!}{1!2!2!2!} $
    $|E_{BB}|=\dfrac{8!}{3!1!2!2!} $
    $|E_{AAA}\cap E_{BB}|=\dfrac{6!}{1!1!2!2!} $

    Basically, treat the subsequence as one character and find the number of ways to permute it.
    Last edited by SlipEternal; Sep 9th 2017 at 04:48 AM.
    Thanks from gk104
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Newbie
    Joined
    Sep 2017
    From
    Israel
    Posts
    3

    Re: Inclusion–exclusion principle

    Quote Originally Posted by SlipEternal View Post
    Let event $E_{\text{subsequence}} $ be the event that a permutation of $AAABBCCDD $ contains a particular subsequence. (This is not standard notation, just convenient)

    Example:
    $|E|=\dfrac{9!}{3!2!2!2!} $
    $|E_{AAA}|=\dfrac{7!}{1!2!2!2!} $
    $|E_{BB}|=\dfrac{8!}{3!1!2!2!} $
    $|E_{AAA}\cap E_{BB}|=\dfrac{6!}{1!1!2!2!} $

    Basically, treat the subsequence as one character and find the number of ways to permute it.
    now I get it
    thanks!
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Principle of inclusion and exclusion
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: Nov 1st 2014, 02:59 AM
  2. Inclusion-Exclusion principle
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: May 16th 2014, 01:11 AM
  3. inclusion and exclusion principle
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: Mar 9th 2013, 01:27 PM
  4. Inclusion Exclusion Principle Help!
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: Sep 28th 2011, 02:43 AM
  5. inclusion exclusion principle help!
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: Aug 9th 2011, 06:17 AM

/mathhelpforum @mathhelpforum