# 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 `2 ^{5} - 1 = 31` non-empty subsets of

`{1, 3, …, 9}`and

`2`subsets of

^{5}= 32`{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)`)?