Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Inclusion-Exclusion principle problem

  1. Sep 15, 2015 #1
    Use inclusion-exclusion to find the number of ways to arrange the six numbers 1, 2, 3, 4, 5, 6 such that
    either 1 is immediately followed by 2, or 3 is immediately followed by 4, or 5 is immediately followed
    by 6.

    I believe that this can be solved using unions. By setting the sets to be the numbers, the union should give two numbers next to each other. For example, set A1 as 1 and A2 as 2, then the union would be the number 1,2. However, wouldn't this union also be 2,1?
  2. jcsd
  3. Sep 15, 2015 #2


    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    No, to use the Inclusion-Exclusion principle, the sets you need to use are based on the three events described to you:
    A1 = set of all arrangements in which 2 follows 1
    A2 = set of all arrangements in which 4 follows 3
    and A3 likewise.

    You need to work out the cardinality (number of elements) of those three sets, and of the various intersections thereof used in Bernoulli's formula.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook