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

Math Help - Inclusion/Exclusion Question

  1. #1
    Member
    Joined
    Aug 2011
    Posts
    76
    Thanks
    1

    Inclusion/Exclusion Question

    Hi. I'm struggling with this question from the section on the inclusion/exclusion principle:

    "How many arrangements of the numbers 1, 1, 2, 2, 3, 3, 4, 4 are there in which no adjacent numbers are equal?"

    My thought was to try and find the total arrangements possible, then subtract off the number of arrangements with at least 2 numbers equal, the latter being calculated with the help of inclusion/exclusion.

    Calculating the total arrangements seems easy: C(8,2)*C(6,2)*C(4,2)*C(2,2)

    But the other part seems complicated. My first attempt was to divide the eight slots into 7 pairs of adjacent slots. Then A_x is the number of arrangments that make pair x equal. But then, I have to go seven levels deep in applying inclusion/exclusion, and I'm doing about half a page of careful case calculation before even finishing n_2. When a counting problem gets highly complicated and calculation intensive, that usually means I'm taking the wrong approach.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,642
    Thanks
    1594
    Awards
    1

    Re: Inclusion/Exclusion Question

    Quote Originally Posted by infraRed View Post
    "How many arrangements of the numbers 1, 1, 2, 2, 3, 3, 4, 4 are there in which no adjacent numbers are equal?"
    The total possible number of arrangements is $\dfrac{8!}{2^4}$.

    The number in the one's are together is equal to $\dfrac{7!}{2^3}$

    Inclusion/exclusion $\displaystyle\sum\limits_{k = 0}^4 {{{\left( { - 1} \right)}^k}\dbinom{4}{k}\dfrac{{\left( {8 - k} \right)!}}{{{2^{4 - k}}}}} $
    Thanks from macosxnerd101
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    Aug 2011
    Posts
    76
    Thanks
    1

    Re: Inclusion/Exclusion Question

    Quote Originally Posted by Plato View Post
    The total possible number of arrangements is $\dfrac{8!}{2^4}$.

    The number in the one's are together is equal to $\dfrac{7!}{2^3}$

    Inclusion/exclusion $\displaystyle\sum\limits_{k = 0}^4 {{{\left( { - 1} \right)}^k}\dbinom{4}{k}\dfrac{{\left( {8 - k} \right)!}}{{{2^{4 - k}}}}} $
    Thank you much for the help. However, is it possible you could explain some more about how you came up with those numbers? I imagine you are correct, but I have little understanding at this point.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,642
    Thanks
    1594
    Awards
    1

    Re: Inclusion/Exclusion Question

    Quote Originally Posted by infraRed View Post
    Thank you much for the help. However, is it possible you could explain some more about how you came up with those numbers? I imagine you are correct, but I have little understanding at this point.
    Lets change to $AABBCCDD$, no two identical letters together.

    Think of $AA$ as one 'packet'. So instead of eight we have seven letters to rearrange.
    So, there are $\dfrac{7!}{2^3}$ ways to arrange the string in which the $AA$ appears.

    There are $\dfrac{6!}{2^2}$ ways to arrange the string in which the $AA~\&~BB$ appear.

    Using inclusion/exclusion we calculate the number of ways for at least one of $AA,~BB,~CC,~DD$ appears.
    Thanks from infraRed
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Combinatorics / Inclusion/Exclusion Question
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: October 14th 2012, 09:37 AM
  2. Inclusion and exclusion question
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: April 19th 2011, 04:00 AM
  3. inclusion & exclusion question help
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: May 17th 2010, 07:49 AM
  4. inclusion-exclusion question
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: May 16th 2010, 11:44 PM
  5. inclusion/exclusion question
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: November 3rd 2009, 07:31 PM

Search Tags


/mathhelpforum @mathhelpforum