Solving Inclusion Exclusion Homework w/ Formula

  • Thread starter talolard
  • Start date
In summary, there are two ways to approach this problem: using the inclusion-exclusion principle or using the concept of derangements. Both methods result in the formula 2n!-n!(1-1/1!+1/2!-1/3!+...+(-1)^n/n!) to find the number of ways to arrange n pairs of identical books such that no two identical books are next to each other.
  • #1
talolard
125
0

Homework Statement


I'm not sure i got thiss one
John has n pairs of identitical books. Find a formula for the number of ways can he arange them so that no two identical books are next to each other.


Homework Equations


Inclusion exclusion principle


The Attempt at a Solution


for 2n books, where there are n identical pairs, there are [tex] \frac{2n!}{2^n} [/tex] ways to arange them. We divide by 2^n because there are n identical items and 2n! areanges 2n distinct items.

We will find the number of ways that at least one pair is adjanctent and and remove that from all possible arangements, then that is the awnser.
denote [tex] A_i [/tex] the group of all arangemnts such that at least i pairs are next to each other.
[tex] A_i=C(n,i)* \frac{(2n-i)!}{2^{n-i}} [/tex]
In words: We chose i pairs from n, we arange 2n-i distinct items and divide by [tex]2^{n-i} [/tex] because we have already ignored the symetrys of the pairs.
Then by the inclusion exclusion principle the number of ways that no pair adjactent is
[tex]\sum (-1)^i*C(n,i)* \frac{(2n-i)!}{2^{n-i}} [/tex] where the summation is from 0 to n.


 
Physics news on Phys.org
  • #2



Hello there!

Your solution seems to be correct and follows the inclusion-exclusion principle. Another way to approach this problem is by using the concept of derangements. A derangement is a permutation of a set where no element appears in its original position. In this case, we can think of each pair of identical books as a single element, and the total number of derangements of n pairs of books is given by the formula D(n) = n!(1-1/1!+1/2!-1/3!+...+(-1)^n/n!). This formula can also be derived using the inclusion-exclusion principle.

To find the number of ways to arrange the books so that no two identical books are next to each other, we can subtract the number of derangements from the total number of possible arrangements (2n!). This gives us the formula 2n!-n!(1-1/1!+1/2!-1/3!+...+(-1)^n/n!).

Both methods yield the same result, and it's always good to have multiple approaches to a problem. Keep up the good work in your studies!
 

1. What is the inclusion-exclusion principle?

The inclusion-exclusion principle is a counting technique used in combinatorics to solve problems involving overlapping sets. It states that the size of the union of two or more sets can be calculated by adding the sizes of the individual sets, subtracting the size of their intersection, adding the size of the intersection of the sets taken two at a time, subtracting the size of the intersection of the sets taken three at a time, and so on.

2. What is the formula for solving inclusion-exclusion problems?

The formula for solving inclusion-exclusion problems is given by:
|A1 ∪ A2 ∪ ... ∪ An| = ∑i|Ai| - ∑i|Ai ∩ Aj| + ∑i|Ai ∩ Aj ∩ Ak| - ... + (-1)n+1|A1 ∩ A2 ∩ ... ∩ An|
where |A| represents the size of set A and n represents the number of sets being considered.

3. When should the inclusion-exclusion principle be used?

The inclusion-exclusion principle should be used when there are overlapping sets and we want to find the size of their union. It can also be used to find the probability of an event occurring when there are multiple events with some overlap.

4. How do you apply the inclusion-exclusion principle to solve a problem?

To apply the inclusion-exclusion principle, first identify the sets involved and their sizes. Then, use the formula to calculate the size of the union of the sets. Make sure to subtract the sizes of the intersections of the sets to avoid double-counting. Finally, solve for the desired quantity by plugging in the calculated values.

5. Can the inclusion-exclusion principle be extended to more than three sets?

Yes, the inclusion-exclusion principle can be extended to any number of sets. The formula remains the same, with the number of terms increasing as the number of sets increases. However, it can become more complicated to calculate as the number of sets increases, so it is important to carefully organize and simplify the problem before applying the formula.

Similar threads

Replies
23
Views
1K
  • Calculus and Beyond Homework Help
Replies
2
Views
1K
  • Calculus and Beyond Homework Help
Replies
3
Views
503
  • Calculus and Beyond Homework Help
Replies
10
Views
966
  • Calculus and Beyond Homework Help
Replies
9
Views
1K
  • Calculus and Beyond Homework Help
Replies
3
Views
847
  • Calculus and Beyond Homework Help
Replies
1
Views
1K
  • Calculus and Beyond Homework Help
Replies
1
Views
2K
  • Calculus and Beyond Homework Help
Replies
7
Views
2K
  • Math Proof Training and Practice
Replies
5
Views
921
Back
Top