Combinatorics

Problems from Enumerative Combinatorics

ch.1 ex. 2a

How many subsets of the set |10| = {1, 2, …, 10} contain at least one odd integer?


There are 25 - 1 = 31 non-empty subsets of {1, 3, …, 9} and 25 = 32 subsets of {2, 4, …, 10}. Each solution is a disjoint union of subsets drawn from these two power sets. Hence 31 × 32 = 992.

ch.1 ex. 2b

In how many ways can seven people be seated in a circle if two arrangements are considered the same whenever each person has the same neighbors (not necessarily on the same side)?


There are 7! ways to seat people in seven seats and 7! / 7 = 6! ways to seat people in a circle of seats where rotations of the seat are indistinguishable.

The solution is 6! / 2 = 360. Choose a person and assign him/her a seat. Since the seats are indistinguishable, there is one way to do this. Choose the person's two neighbors. There are 6 choose 2 ways to do this. There are 4! ways to allocate the remaining 4 seats.

ch1. ex. 2c

How many permutations of w: |6| → |6| satisfy w(1) ≠ 2?


There are 6! = 720 permutations of |6| and 5! = 120 permutations of |6| for which w(1) = 2. Hence the solution is 6! - 5! = 600.

ch1. ex. 2d

How many permutations of |6| have exactly two cycles (i.e. find c(6, 2))?


Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License