# Inclusion-Exclusion principle problem

Tags:
1. Sep 15, 2015

### Samuel Williams

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. Sep 15, 2015

### andrewkirk

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.

Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook