Combinatorics

Let `P(n)` be the statement that there are `2^n` subsets of a set of size `n`

For a set with `0` elements, the only subset is `O/`, which is consistent with `2^0 = 1` so `P(0)` is true

Suppose `P(n)` is true. Want to show `P(n+1)` is true, i.e., there are `2^(n+1)` subsets of a set of size `n+1`

Let `S` be a set of size `n+1`

Fix any `x in S` and consider `S' = S\\{x}`

Since `S'` has `n` elements, there are `2^n` subsets

Every subset of `S` either contains `x` or it doesn't contain `x`

The subsets that don't contain `x` are in `S'`, which has `2^n` subsets

So there are `2^n` subsets that don't contain `x`

The subsets that do contain `x` can be obtained by adding `x` to each of the `2^n` subsets that don't contain `x`

So there are `2^n` subsets that do contain `x`

The total number of subsets of `S` is the number of subsets containing `x` plus the number of the subsets not containing `x`

So the total number of subsets of `S` is `2^n + 2^n = 2*2^(n) = 2^(n+1)`

So `P(n+1)` is true

Let `P(n)` be the statement `sum_(i=0)^n i = (n*(n+1))/2`

For `n=0`, `sum_(i=0)^0 i = 0` and `(0*(0+1))/2 = 0` so `P(0)` is true

Suppose `P(n)` is true. Want to show `P(n+1)` is true, i.e., `sum_(i=0)^(n+1) i = ((n+1)(n+2))/2`

So `P(n+1)` is true

Let `P(n)` be the statement `4n lt 2^n` for `n ge 5`

For `n=0`, `4*0 = 0 lt 2^0 = 1` so `P(0)` is true

Suppose `P(n)` is true. Want to show `P(n+1)` is true, i.e., `4n+4 lt 2^(n+1)`

So `P(n+1)` is true

Let `P(n)` be the statement that every polynomial of degree `n` in `x` is a linear combination of the powers of `x-1`

For `n=0`, the polynomial of degree `0` is a constant `c`, which is a linear combination of `1` (`c = c*1`) so `P(0)` is true

Suppose `P(0), P(1), P(2), ... P(n)` is true. Want to show `P(n+1)` is true, i.e., every polynomial of degree `n+1` in `x` is a linear combination of the powers of `x-1`

Let `f(x)` be a polynomial of degree `n+1`

Let `alpha` be the leading coefficient of `f`

Consider `g(x) = f(x) - alpha*(x-1)^(n+1)`

`g(x)` is a polynomial of degree `le n` so it is a linear combination of the powers of `x-1`

`f(x) = g(x) + alpha*(x-1)^(n+1)`

`alpha*(x-1)^(n+1)` is also a linear combination of the powers of `x-1`

So `f(x)` is a linear combination of the powers of `x-1`

So `P(n+1)` is true

Let `P(n)` be the statement that `n` can be written as `2^rm` where `r ge 0` and `m` is odd

For `n=1`, `1 = 2^0*1 = 1` so `P(1)` is true

Suppose `P(1), ..., P(n)` is true. Want to show `P(n+1)` is true, i.e., `n+1` can be written as `2^rm` where `r ge 0` and `m` is odd

Suppose `n+1` is odd. Then pick `r=0` and pick `m = n+1` so `P(n+1)` is true

Suppose `n+1` is even

Then it can be written as `n+1 = 2k` for some integer `1 le k le n`

Since `k` is a positive integer, it can be written as `2^rm` where `r ge 0` and `m` is odd

`m` is odd and `r ge 0 implies r+1 ge 0` so `n+1` can be written as a power of `2` multiplied by an odd number

So `P(n+1)` is true

Let `P(n)` be the statement that `n` can be written as a product of prime numbers

For `n=2`, `2` is a product of `2`, which is a prime number so `P(2)` is true

Suppose `P(2), ..., P(n)` is true. Want to show `P(n+1)` is true, i.e., `n+1` can be written as a product of prime numbers

Suppose `n+1` is prime. Then it is a product of itself so `P(n+1)` is true

Suppose `n+1` is not prime

Then `n+1` can be written as `n+1 = a*b` for integers `a,b` where `2 le a,b le n`

Since `2 le a,b le n`, `a` and `b` can be written as products of prime numbers

So `n+1` is a product of prime numbers

So `P(n+1)` is true

Let `P(n)` be the statement that `f(n) le 3^n` for `n ge 0`

For `n=0`, `f(0) = 1 le 3^0 = 1`

For `n=1`, `f(1) = 2 le 3^1 = 3`

So `P(0)` and `P(1)` are true

Suppose `P(n)` is true. Want to show that `P(n+1)` is true, i.e., `f(n+1) le 3^(n+1)`

So `P(n+1)` is true

Let `P(n)` be the statement that if `S` has `n gt 0` elements, then there are `n!` permutations of the elements of `S`

For a set of size `1`, there's only `1` way to order all the elements. `1 = 1!` so `P(1)` is true

Suppose `P(n)` is true. Want to show `P(n+1)` is true, i.e., if `S` has `n+1` elements, then there are `(n+1)!` permutations of the elements in `S`

Let `S` be a set of size `n+1`

We could pick any random element of `S` and put that in the first spot

There are `n+1` choices for the random element in the first spot

Now, `S` has `n` elements

So there are `n!` ways to order the remaining elements in `S`

So the total number of ways to order the elements is `(n+1)*n! = (n+1)!`

So `P(n+1)` is true

There are `k` spots, and each spot has `n` choices of entries

So there are `ubrace(n*n*...*n)_k = n^k` words of length `k`

Let `S sube [n]`

Define a word `w_s` of length `n` in the alphabet `{0,1}` as follows:

Let `i in [n]`

If `i in S`, then the `i^(th)` entry of `w_s = 1`

If `i notin S`, then the `i^(th)` entry of `w_s = 0`

Define a function `f:{`subset `S` of `[n]} rarr {`word of length `n` in alphabet `{0,1}}`

We can define another function `g:{`words of length `n` in `{0,1}} rarr {`subset of `[n]}`

The process for converting a subset to a word is reversible, gives a unique result, and always gives a result with valid input

So `g` is the inverse of `f`, which means `f` is bijective

So `|{`subsets of `[n]}| = |{`words of length `n` in `{0,1}}| = 2^n`

Let `sigma = a_1a_2...a_ka_(k+1)...a_n` be a permutation of `A`

The first `k` entries make up a word with no repeating entries

Since there are `n!` permutations, we have `n!` words with no repeating entries

But there are repeated words since the last `(n-k)` entries can be ordered in any way

So there are

words with no repeating entries

We can associate subsets of `[n]` with words of length `n` in `{0,1}`

The number of `k`-element subsets of `[n]` is the number of words of length `n` in `{0,1}` that have exactly `k` `1`'s

For such words, there are `k` ways to arrange the `1`'s and `n-k` ways to arrange the `0`'s

Which gives us `(n!)/(k!(n-k)!) = ((n),(k))`

`sum_(k=0)^n ((n),(k))` is the number of ways to choose subsets of size `0`, `1`, `2`, ..., `n`

Well, that should make up all the possible subsets

Before, we showed that the total number of subsets is `2^n`

`((n+1),(k))` is the number of `k`-element subsets of `[n+1]`

We could split those subsets up into two categories: subsets of size `k` that contain `n+1` and subsets of size `k` that don't contain `n+1`

The subsets of size `k` that don't contain `n+1` are actually the subsets of size `k` of `[n]`, so that gives us `((n),(k))`

If we look at the subsets of size `k` that do contain `n+1` and remove `n+1` from each subset, we end up with the number of subsets of size `k-1` of `[n]`, which gives us `((n),(k-1))`

These two sets don't overlap so there are `((n),(k))+((n),(k-1))` subsets of size `k` of `[n+1]`

There are `13` choices for the value that is the same

There are `48` choices for the fifth card

Total number of ways to get a four of a kind: `13*48`

Alternatively,

There are `13` choices for the value that is the same

There are `12` choices for the value that is different

There are `4` choices for the suit of the different value

Total number of ways to get a four of a kind: `13*12*4`

There are `13` choices for the value of the triple

There are `12` choices for the value of the pair

There are `((4),(3))` choices for the suits of the triple

There are `((4),(2))` choices for the suits of the pair

Total number of ways to get a full house: `13*12*((4),(3))*((4),(2))`

There are `((13),(2))` choices for the value of each pair

There are `((4),(2))` choices for suits of one pair

There are `((4),(2))` choices for suits of other pair

There are `44` choices for the leftover card

Total number of ways to get a two pair: `((13),(2))*((4),(2))*((4),(2))*44`

Alternatively,

There are `((13),(2))` choices for the value of each pair

There are `11` choices for the value of the different card

There are `((4),(2))` choices for suits of one pair

There are `((4),(2))` choices for suits of other pair

There are `4` choices for the suit of the different card

Total number of ways to get a two pair: `((13),(2))*11*((4),(2))*((4),(2))*4`

To pick values, we only need to know what the largest possible values are

The fifth card can be `5`, `6`, `7`, `8`, `9`, `10`, `J`, `Q`, `K`, or `A`

There are `10` choices for the fifth card

There are `4^5` choices for the suits of each card

Total number of ways to get a straight: `10*4^5`

Note: it doesn't matter what the set is, since we can form a bijection between the set and `[n]`

Let `S` be a multiset of size `k` of `[n]`

Sort the elements of `S` so that `s_1 le s_2 le s_3 le ... le s_k`

Add `i-1` to each `s_i`

Then we get `s_1 lt s_2 + 1 lt s_3 + 2 lt ... lt s_k + (k-1)`

Well, `{s_1, s_2+1, s_3+2, ..., s_k+(k-1)}` is a subset of size `k` of `[n+k-1]color(red)(text(*))`

The number of ways to make `k`-element subsets from a set of size `[n+k-1]` is `((n+k-1),(k))`

(Reversing the process -- subtracting `i-1` from each `s_i` -- shows that there is a bijection between `{s_1, s_2, ..., s_k}` and `{s_1, s_2+1, ..., s_k+(k-1)}`)

`color(red)(text(*))` happens when `s_k = n`

`x_1^(a_1)*x_2^(a_2)*...*x_n^(a_n)` is like a multiset of `{x_1,x_2,...,x_n}` where each `x_i` is chosen `a_i` times

Since they add up to `d`, there should be `d` total elements

So the total number of monomials is the number of multisets of size `d` of `{x_1,x_2,...,x_n}`, which is

Claim: There is a bijection between weak compositions of `n` into `k` parts and `n`-element multisets of `[k]`

Given a weak composition `(a_1,...,a_k)`, we get a multiset that has the `i^(th)` element `a_i` times

Since `a_1 + ... + a_k = n`, this is an `n`-element multiset of `[k]`

Given an `n`-element multiset of `[k]`, let `a_i` be the number of times that `i` appears in the multiset

Then we end up with a weak composition `(a_1,...,a_k)` of `n`

The possible number of parts for a composition of `n` ranges from `k = 1` to `k = n`

So the total number of compositions possible is

Well, that is the formula for the number of subsets of `[n-1]`, which is `2^(n-1)`

This is `n` pieces into `1` block. The only way to do this is to put all the pieces into the block

`S(n,1) = 1`

This is `n` pieces into `n` blocks. The only way to do this is to put each piece in each block

`S(n,n)=1`

This is `n` pieces into `2` blocks

We can't put `O/` or the whole set in the blocks, so there are `2^n-2` complementary subsets

The order of the blocks don't matter, so there are `(2^n-2)/(2!) = 2^(n-1)-1` ways to do this

`S(n,2) = 2^(n-1)-1`

This is `n` pieces into `n-1` blocks

One block must have `2` pieces, so we choose `2` elements to be in the same block

`S(n,n-1) = ((n),(2))`

Consider two kinds of partitions of `[n]`

The first kind is partitions where `n` is in its own block

Removing that block, we end up with a partition of `n-1` into `k-1` blocks, which is `S(n-1,k-1)`

The second kind of partition is the partitions where `n` is not in its own block

Removing `n` from each partition, we end up with a partition of `n-1` into `k` blocks

But by doing so, we can't reconstruct the original situation because we don't know which block it came from

There are `k` blocks we could put `n` in `implies k` different ways to reconstruct the original situation

So the number of partitions is `k*S(n-1,k)`

Adding up both types of partitions gives us all the partitions of `[n]`

Separate all the partitions of `[n+1]` based on the number of elements in the block that contains `n+1`

Consider those partitions where the block containing `n+1` is of size `j`

For the block containing `n+1`, there are `n` numbers to choose from and `j-1` spots, so there are `((n),(j-1))` ways to generate such a block

Now, there are `n+1-j` elements remaining

For the other blocks not containing `n+1`, they can be generated by looking at the number of partitions of `[n+j-1]`, i.e., `B(n+j-1)`

So the number of partitions where the block containing `n+1` is of size `j` is `((n),(j-1)) B(n+1-j)`

The possible sizes of blocks containing `n+1` range from `1` to `n+1`

Notice that taking the transpose of `lambda` gives us `mu`

Claim: There is a bijection between `A = {`partitions `lambda` of `n` with `l(lambda) le k}` and `B = {`partitions `mu` of `n` such that `mu_i le k}`

Let `f:A rarr B` be a function defined to be `f(lambda) = lambda^T`

Since `(lambda^T)^T = lambda`, `f circ f` is the identity function, which means it is its own inverse

So `f` is bijective `implies |A| = |B|`

Start with a Young diagram of `lambda`

Take the boxes of the first row and column and put them all in a row

Make that row the first row of `mu`

Repeat this for all the rows/columns of the `lambda`

(Informally, peel off the outer layer of `lambda` and straighten it out to become a row in `mu`)

This process is reversible, so there is a bijection

(Informally, fold the row of `mu` in half and make it the outer layer of `lambda`)

Since `lambda` is self-conjugate, there are an odd number of parts in the `i^(th)` row and column

Now we show why they are distinct

We can come up with a formula for the length of the `i^(th)` row

The `i^(th)` row of `mu` is the `i^(th)` row of `lambda` minus the boxes to the left plus the `i^(th)` row of `lambda^T` minus the boxes from the top minus `1` for the box in the top-left corner

Claim: `mu_1 gt mu_2 gt ...`

Since `lambda` is a partition, `lambda_i ge lambda_(i+1)`

So

Consider the expansion `(x+y)^n = ubrace((x+y)(x+y)...(x+y))_n`

Multiply the terms, considering all the possible choices in each set of parentheses

Some terms will be repeated. For example, `x*x*x*...*x*y` and `x*x*y*x*...*x` both have `n-1` `x's` and `1` `y`

The number of repeated terms is the number of ways to create a term that has that form

The form of each term will be `i` `x's` and `n-i` `y's`

Which gives us `((n),(i))` ways to create `x^iy^(n-i)`

To get the final answer, we sum up all the possible products

The sum goes from `0` to `n` because we have situations where `x` appears `0` times and `x` appears `n` times

Set `x_1 = x_2 = ... = x_k = 1`

Set `x_1 = 1-k`, `x_2 = ... = x_k = 1`

Apply `del/(delx_1)` and set `x_1 = ... = x_k = 1`

`(lArr)`Suppose `[x^0]A(x) != 0`. Want to show `A(x)` is invertible

Consider `B(x) = sum_(n ge 0) b_nx^n` and try to pick `b_n` so that `A(x)B(x) = 1`

Expanding out the equation `A(x)B(x) = 1` and matching coefficients, we get:

Using this system of equations, we can try to find `b_n`

At each stage, it is possible to find `b_(n+1)` since it is in terms of `b_0,...,b_n`. More formally, we can do so using induction. Suppose we have solved for `b_0, ..., b_n`. At each stage, we have

So we can solve for `b_(n+1) = -(a_(n+1)b_0 + ...)/a_0`

`(implies)`If the constant term is `0`, then the equation `a_0b_0 = 1` has no solution `implies` cannot find `b_n` `implies` `A(x)` is not invertible

Using generating functions, the goal is to show that `sum_(n ge 0)p_(text(odd))(n)x^n = sum_(n ge 0)p_(text(dist))(n)x^n`

From the previous example, we have

For `p_(text(dist))(n)x^n`, we can only use unique exponents, so we have

`1+x^k` can be rewritten as

So `p_(text(dist))(n)x^n` can be rewritten as

All the terms in the numerator will cancel out the terms in the denominator with even exponents. What's left is the odd terms

`A(x)^k` is the ordinary generating function for the number of ways to break up `[n]` into `k` consecutive intervals and place structure `alpha` on each piece

This is counted by `h_n` when we sum over all `k`

So `H(x) = sum_(k ge 0) A(x)^k = 1/(1-A(x))`

`b_kA(x)^k` is the ordinary generating function for the number of ways to break up `[n]` into `k` consecutive intervals, place structure `alpha` on each piece, and then place structure `beta` on the `k` pieces

This is counted by `h_n` when we sum over all `k`

So `H(x) = sum_(k ge 0) b_kA(x)^k = B(A(x))`

Every expression starts with a `(` and is matched by some `)`

In between those `()`, we can put another set of balanced parentheses

• Let `i` be the number of pairs inside
• We can put up to `n-1` pairs of parentheses inside
• Then there are `C_i` choices for `0 le i le n-1`

After the `)`, we can put another set of balanced parentheses

• After putting `i` pairs inside the initial balanced parentheses, we have `n-(i+1) = n-1-i` pairs leftover
• Then there are `C_(n-1-i)` choices

These choices are independent of each other, so there are `C_iC_(n-1-i)` total choices

Since `i` can go from `0` to `n-1`, we have `sum_(i = 0)^(n-1)C_iC_(n-1-i)`

The coefficient of `x^n` in `A(x)B(x)` is `sum_(i=0)^na_i/(i!)b_(n-i)/((n-i)!)` by the definition of multiplying two power series

But it is also equal to `c_n/(n!)`

`A(x)^k` is the egf for the number of ways to write `[n] = S_1 uu S_2 uu ... uu S_k` such that the `S_i`'s don't overlap and put structure `alpha` on each `S_i`

Since now the order doesn't matter, we divide by `k!` to get `(A(x)^k)/(k!)`

Considering all `k`, we get `H(x) = sum_(k ge 0) (A(x)^k)/(k!) = e^(A(x))`

We want every `x in A_1 uu ... uu A_n` to be counted exactly once

Let `S = {s_1, s_2, ..., s_k}` be all the indices such that `x in A_(s_1), ..., A_(s_k)`

`x` is only going to be counted by `(-1)^(j-1)|A_(i_1) nn ... nn A_(i_j)|` when all the `i_1, i_2, ..., i_j` are in `S` (otherwise `x` doesn't belong in the intersection)

So we have to look at all the possible ways of choosing indices in `S`

The number of times `x` is counted is

We could simplify that by using the binomial theorem

When `x=-1,y=1` we get

So we have `0 = 1+sum_(i=1)^n((n),(i))(-1)^i`

which looks like the summation above

So the number of times `x` is counted is

It's easier to count the number of non-derangements and subtract from the total number of permutations

`f` is not a derangement if `f(1)=1` or `f(2)=2` or `...\ f(n) = n`

Let `A_i = {f:[n] rarr [n]|f(i)=i}`. So all the non-derangements are included in `A_1 uu A_2 uu ... uu A_n`

`A_1` is the set of all bijections such that `f(1)=1`. For `2,...,n` there are `(n-1)!` ways to assign values, so `|A_1|=(n-1)!`

By similar reasoning, `|A_2| = ... = |A_n| = (n-1)!`

`A_1 nn A_2` is the set of all bijections such that `f(1)=1` and `f(2)=2`. For `3,...,n` there are `(n-2)!` ways to assign values, so `|A_1 nn A_2| = (n-2)!`

In general, `|A_(i_1) nn ... nn A_(i_j)| = (n-j)!`

Since the union of all the `A_i`'s gives us the number of non-derangements, we can use inclusion-exclusion

The number of derangements is the number of permutations minus the number of non-derangements, which is

Big idea: To be a non-derangement, it needs to satisfy (at least) one of `n` conditions. The set of non-derangements is the union of `n` simpler sets.

Count the number of non-surjective functions from `[n]` to `[k]` and subtract from the total number of functions from `[n]` to `[k]`

Being non-surjective means `1` is not in the image or `2` is not in the image or `...\ k` is not in the image

Define `A_i = {f:[n] rarr [k]|i` is not in the image of `f}` for `1 le i le k`

Then the set of non-surjective functions is the union of the `A_i`'s

`A_1` is all the functions where `1` is not in the image, which is the same as `{`functions `[n] rarr {2,3,...,k}}`

There are `(k-1)^n` such functions, so `|A_1| = (k-1)^n`

By similar reasoning, `|A_i| = (k-1)^n` for all `i`

`A_1 nn A_2 = {`functions `[n] rarr {3,4,...,k}}` so `|A_1 nn A_2| = (k-2)^n`

In general, `|A_(i_1) nn ... nn A_(i_j)| = (k-j)^n`

The number of non-surjective functions is

The number of surjective functions is the total number of functions minus the number of non-surjective functions, so we have

To get the Stirling numbers, divide by `k!`:

Consider the prime factorization of `n = p_1^(a_1)p_2^(a_2)...p_r^(a_r)` where each `p_i` is distinct and all `a_i gt 0`

To get divisors of `n`, we just make the exponents smaller

So all divisors `d` of `n` are of the form `d = p_1^(b_1)p_2^(b_2)...p_r^(b_r)` where `0 le b_i le a_i`

We can rewrite the sum as

By the Möbius function, if `n` is divisible by a prime more than once, then the result is `0`. So we only need to consider `b_i`'s `lt 2`:

Since each `b_i` is either `0` or `1`, we either include each `p_i` or we don't:

We have a product of distinct primes so the result will be `(-1)` to some power by the Möbius function:

From the identity before, we can rewrite `k^e` as a sum of `omega`'s

We can rearrange the sum to get

By the lemma, `sum_(g|d/f)mu(g) = 0` if `d/f gt 1 implies d gt f`

So we don't need to consider all the terms where `d gt f`. The only term left is when `f=d`:

Count the number of functions that are one-to-one and subtract from the total number of functions

Total number of functions: there are `n` choices in the codomain for each element in the domain `implies n^n`

One-to-one: assign each element in the domain one element in the codomain and permute `implies n!`

`color(red)(n^n - n!)`

For each of the first `n-1` elements, there are `2` choices: in the subset or not in the subset `implies 2^(n-1)`

For the `n^(th)` element, there is only `1` choice:

• if there are an even number of elements in the subset so far, then add the `n^(th)` element in the subset
• if there are an odd number of elements in the subset so far, then don't add the `n^(th)` element in the subset

Count the number of committees that have all males and all females and subtract both from the total number of ways to form a committee

Total number of ways to form a committee: `((20),(5))`

All male: `((12),(5))`

All female: `((8),(5))`

`color(red)(((20),(5)) - ((12),(5)) - ((8),(5)))`

This problem is the same as counting the number of four-digit positive integers divisible by three since `6` is divisible by three

There are `9999-1000+1 = 9000` four-digit positive integers

Every third number is divisible by three `implies 1/3` of the `9000` four-digit positive integers are divisible by three

`color(red)(3000)`

There are `99999-10000+1 = 90000` five-digit positive integers

Every third number is divisible by three `implies 1/3*90000 = 30000` five-digit positive integers are divisible by three

Now count how many of those don't contain a `9` and subtract from the total number of five-digit positive integers divisible by three

There are `8` choices for the first digit

There are `9` choices for the second digit

There are `9` choices for the third digit

There are `9` choices for the fourth digit

The fifth digit depends on what the first `4` digits sum up to

• if the sum mod `3` equals `0`, then the fifth digit can be `0`, `3`, or `6`

• if the sum mod `3` equals `1`, then the fifth digit can be `2`, `5`, or `8`

• if the sum mod `3` equals `2`, then the fifth digit can be `1`, `4`, or `7`

There are `3` choices for the fifth digit

`color(red)(30000-(8*9*9*9*3))`

Count the number of ways to list the digits where they are in consecutive positions and subtract from the total number of ways to list the digits

Total number of ways to list digits: `(7!)/(2!)`

Consecutive positions: combine the `2`'s into one `2`, then there are `6!` ways to list the digits

`color(red)((7!)/(2!) - 6!)`

Alternatively, there are `6` positions where the `2`'s could go, then there are `5!` ways to rearrange the remaining digits `implies 6*5! = 6!`

Combine the two `1`'s together into one `1`, then there are `(6!)/(2!)` ways to list the digits

`color(red)((6!)/(2!))`

Alternatively, there are `6` positions where the `1`'s could go, then there are `(5!)/(2!)` ways to rearrange the remaining digits `implies 6*(5!)/(2!) = (6!)/(2!)`

Count the number of ways where he works on Saturday and Sunday and subtract from the total number of ways to choose the five days

Total number of ways to choose five days: `((7),(5))`

Works on Saturday and Sunday: `((5),(3))`

`color(red)(((7),(5))-((5),(3)))`

This is a `7`-element multiset of `[5]`

Alternatively, it is also a weak composition of `7` into `5` parts

`color(red)(((11),(7)))`

Count the number of ways to do this where he starts and finishes in the same city and subtract from the total number of ways to visit four cities five times each

Consider a random permutation of cities

Total number of ways:

• There are `20!` ways to rearrange them
• But there are `4` sets of `5` duplicate cities
• `implies (20!)/(5!5!5!5!)`

Start and finish in the same city:

• Choose `1` city that will be the start and finish
• There are `18!` ways to rearrange the cities
• But there are `3` sets of `5` duplicate cities and `1` set of `3` duplicate cities
• There are `4` choices for the cities that are fixed at the start and end
• `implies 4*(18!)/(5!5!5!3!)`

`color(red)((20!)/(5!5!5!5!) - 4*(18!)/(5!5!5!3!))`

For each meal, not getting it is an option

There are `6` choices for soup

There are `11` choices for soup

There are `7` choices for soup

`color(red)(6*11*7)`

Count the number of `6`-digit positive integers in which the sum of the digits is more than `51` and subtract from the total number of `6`-digit positive integers

Total number of `6`-digit positive integers: `999999-100000+1 = 900000`

There are `4` situations where the sum of the digits is more than `51`:

• six `9`'s: `1` way to do this

• five `9`'s and one `8`: `6` ways to do this

• five `9`'s and one `7`: `6` ways to do this

• four `9`'s and two `8`'s: `((6),(2))` ways to do this

`color(red)(900000-(1+6+6+((6),(2))))`

(a) First, pick `11` students for the soccer team: `((30),(11))`

From the remaining `19` students, pick `5` of them to be on the basketball team: `((19),(5))`

`color(red)(((30),(11))*((19),(5)))`

(b) First, pick `11` students for the soccer team: `((30),(11))`

Since we can have students on both teams, we can pick `5` students for the basketball team from the same set of `30` students: `((30),(5))`

`color(red)(((30),(11))*((30),(5)))`

(c) It is valid to have a situation where no student is on both teams. This is part (a): `((30),(11))*((19),(5))`

The (only) other valid situation is to have `1` student on both teams

First, pick `10` students for the soccer team: `((30),(10))`

(the `11^(th)` spot is reserved for the student who is on both teams)

From the remaining `20` students, pick `4` of them to be on the basketball team: `((20),(4))`

(the `4^(th)` spot is reserved for the student who is on both teams)

From the remaining `16` students, pick `1` of them to be on both teams: `16`

`color(red)(((30),(11))*((19),(5)) + ((30),(10))*((20),(4))*16)`

Alternatively, first pick the student who will be on both teams: `30`

From the remaining `29` students, pick `10` of them to be on the soccer team: `((29),(10))`

From the remaining `19` students, pick `4` of them to be on the basketball team: `((19),(4))`

`color(red)(((30),(11))*((19),(5)) + 30*((29),(10))*((19),(4)))`

Pick the digit that will occur three times: `10` choices

From the six positions, pick three of them to be the places where the repeated digit will be: `((6),(3))`

The rest of the digits have to be distinct since there is only one digit that occurs more than once

The fourth digit, regardless of position, has `9` choices

The fifth digit, regardless of position, has `8` choices

The sixth digit, regardless of position, has `7` choices

`color(red)(10*((6),(3))*9*8*7)`

Alternatively,

There are `10` choices for the digit that appears three times

There are `9` choices for the fourth digit

There are `8` choices for the fifth digit

There are `7` choices for the sixth digit

There are `(6!)/(3!)` ways to arrange the six digits

`color(red)(10*9*8*7*(6!)/(3!))`

Place a rook on any row/column: `8` choices

There are `7` remaining rows/columns for the next rook

There are `6` remaining rows/columns for the next rook

`vdots`

There is `1` remaining row/column for the last rook

`color(red)(8!)`

Alternatively, place the `8` rooks in such a way so that none of them are attacking each other (e.g. place them all along a diagonal)

There are `8!` ways to rearrange them and still have them not attacking each other

(swapping two rows/columns will ensure that they are still not attacking each other)

Count the number of three-digit positive integers that contain only one different digit and the number of three-digit positive integers that contain three different digits and subtract both from the total number of three-digit positive integers

Total number of three-digit positive integers: `999-100+1 = 900`

three-digit positive integers with only one different digit:

• one different digit means all three digits are the same and there are `9` of these

three-digit positive integers with three different digits:

• There are `9` choices for the first digit (can't be `0`)
• There are `9` choices for the second digit (can't be the first digit but can be `0`)
• There are `8` choices for the third digit

`color(red)(900-9-9*9*8)`

Consider the subsets of `{3,4,...,n}`

There are `n-2` elements `implies 2^(n-2)` subsets

For each subset, there are `2` choices: put a `1` or put a `2`

`2*2^(n-2) = color(red)(2^(n-1))`

Consider the subsets of `{3,4,...,n}`

There are `n-2` elements `implies 2^(n-2)` subsets

For each subset, there are `3` choices: put a `1`, put a `2`, or put both

`color(red)(3*2^(n-2))`

There are `4` choices for the first digit (can't be `0`)

There are `10` choices for the second digit

There are `5` choices for the third digit

`color(red)(4*10*5)`

There are `9` choices for the first digit (can't be `0`)

There are `9` choices for the second digit

There are `8` choices for the third digit

There are `7` choices for the fourth digit

`color(red)(9*9*8*7)`

Count the number of four-digit positive integers that don't contain the digit `1` and subtract from the total number of four-digit positive integers

Total number of four-digit positive integers: `9999-1000+1 = 9000`

Don't contain `1`:

• There are `8` choices for the first digit (can't be `0` or `1`)
• There are `9` choices for the second digit (can't be `1`)
• There are `9` choices for the third digit (can't be `1`)
• There are `9` choices for the fourth digit (can't be `1`)

`color(red)(9000-8*9*9*9)`

There are four situations where the sum of the digits is even:

• All digits are even
• even odd odd
• odd even odd
• odd odd even

For the case where all digits are even:

• There are `4` choices for the first digit (can't be `0`)
• There are `5` choices for the second digit
• There are `5` choices for the third digit
• `implies 4*5*5 = 100`

For even odd odd:

• There are `4` choices for the first digit (can't be `0`)
• There are `5` choices for the second digit
• There are `5` choices for the third digit
• `implies 4*5*5 = 100`

For odd even odd:

• There are `5` choices for the first digit (can't be `0`)
• There are `5` choices for the second digit
• There are `5` choices for the third digit
• `implies 5*5*5 = 125`

For odd odd even:

• There are `5` choices for the first digit (can't be `0`)
• There are `5` choices for the second digit
• There are `5` choices for the third digit
• `implies 5*5*5 = 125`

`color(red)(100+100+125+125 = 450)`

(a) Consider the set `[4]`

There are six situations where this happens:

• `1234`
• `1324`
• `1342`
• `3214`
• `3124`
• `3142`

Now consider adding `5`

There are `5` choices where it could be placed for each of the six situations

Now consider adding `6`

There are `6` choices where it could be placed for each of the six situations

`vdots`

Now consider adding `n`

There are `n` choices where it could be placed for each of the six situations

`color(red)(6*(n)_(n-4) = 6*n*(n-1)*...*6*5)`

(b) Consider the set `[3]`

There are two situations where this happens:

• `123`
• `132`

Now consider adding `4`

There are `4` choices where it could be placed for each of the two situations

`vdots`

Now consider adding `n`

There are `n` choices where it could be placed for each of the two situations

`color(red)(2*(n)_(n-2) = 2*n*(n-1)*...*5*4)`

There are two situations:

• none of the days is Sunday
• one of the days is Sunday

For the case where none of the days is Sunday, there are `26` days to choose from: `((26),(5))`

For the case where one of the days is Sunday:

• Pick `4` days that aren't Sunday: `((26),(4))`
• There are `5` positions for the Sunday (e.g. Sunday can be the first day, second day, ..., fifth day)
• `implies 5*((26),(4))`

`color(red)(((26),(5))+5*((26),(4)))`

For each of the `n` couples there are `3` options:

• no person speaks
• partner `1` speaks
• partner `2` speaks

`color(red)(3^n)`

Count the number of ways to pick ordered pairs `(A,B)` such that `A nn B = O/` and subtract from the total number of ways to select ordered pairs `(A,B)`

Total number of ways to pick ordered pairs `(A,B)`:

Any element in `[n]` can be:

• `in A` and `in B`
• `in A` and `notin B`
• `notin A` and `in B`
• `notin A` and `notin B`

`4^n` ways

For the case where `A nn B = O/`:

Any element can be:

• `in A and notin B`
• `notin A and in B`
• `notin A and notin B`

`3^n` ways

`color(red)(4^n-3^n)`

Count the number of way to pick subsets so that `A nn B = O/` and subtract from the total number of ways to pick subsets

Total number of ways to pick subsets:

Any element in `[n]` can be:

• `in A and in B`
• `in A and notin B`
• `notin A and in B`
• `notin A and notin B and in C`
• `notin A and notin B and notin C`

`5^n` ways

For the case where `A nn B = O/`:

Any element in `[n]` can be:

• `in A and notin B`
• `notin A and in B`
• `notin A and notin B and in C`
• `notin A and notin B and notin C`

`4^n` ways

`color(red)(5^n-4^n)`

Count the number of ways for people to give talks without any of them being included in the book and subtract from the total number of ways for people to give talks

Total number of ways for people to give talks:

There are five situations for each person:

• don't give a talk at all
• give a talk on Saturday
• give a talk on Sunday
• be included in the book as a Saturday speaker
• be included in the book as a Sunday speaker

`5^n` ways

For the case where no talk is selected to be in the book, there are three situations for each person:

• don't give a talk at all
• give a talk on Saturday
• give a talk on Sunday

`3^n` ways

`color(red)(5^n-3^n)`

The first faculty volunteer has `13` students from which to choose

The second faculty volunteer has `12` students from which to choose

The third faculty volunteer has `11` students from which to choose

The fourth faculty volunteer has `10` students from which to choose

`color(red)(13*12*11*10)`

Let `a` be the number of days she studies for four hours

Let `b` be the number of days she studies for five hours

Let `c` be the number of days she studies for six hours

Considering the conditions, we get the system of equations

`implies b + 2c = 2`

So `b = 2, c = 0, a = 4` (five hours for `2` days and four hours for `4` days)

or

`b = 0, c = 1, a = 5` (six hours for `1` day and four hours for `5` days)

For the case where she studies for four hours for `4` days and five hours for `2` days:

• There are `6` days to choose from and `4` of them could be for the four hours
• `((6),(4)) = 15`
• Alternatively, there are `6` days to choose from and `2` of them could be for the five hours
• `((6),(2)) = 15`

For the case where she studies for four hours for `5` days and six hours for `1` day:

• There are `6` days to choose from and `5` of them could be for the four hours
• `((6),(5)) = 6`
• Alternatively, there are `6` days to choose from and `1` of them could be for the six hours
• `((6),(1)) = 6`

`color(red)(15+6 = 21)`

Calculate Brenda's chance of winning by counting the number of possibilities where none of the dice show a six

Total number of possibilities:

• Each die has `6` possible outcomes `implies 6^4`

None of them show a six:

• Each die has `5` possible outcomes `implies 5^4`

Brenda has a `(5^4)/(6^4) = 625/1296` chance of winning

Andy has a `671/1296` chance of winning

`color(red)(text(Andy))`

For the first sophomore, there are `n` choices of juniors and `n` choices of seniors

For the second sophomore, there are `n-1` choices of juniors and `n-1` choices of seniors

For the third sophomore, there are `n-2` choices of juniors and `n-2` choices of seniors

`vdots`

For the last sophomore, there is `1` choice for the junior and `1` choice for the senior

`color(red)(n!*n!)`

There are a total of `8` divisions

There are `((32),(4))` choices for the first division

There are `((28),(4))` choices for the second division

There are `((24),(4))` choices for the third division

`vdots`

There are `((8),(4))` choices for the seventh division

There are `((4),(4))` choices for the eighth division

`color(red)(((32),(4))*((28),(4))*((24),(4))*...*((8),(4))*((4),(4)))`

There are `3` situations where the two blocks do not have the same size:

• size `1` and size `7`: `((8),(1)) = ((8),(7))` ways to do this
• size `2` and size `6`: `((8),(2)) = ((8),(6))` ways to do this
• size `3` and size `5`: `((8),(3)) = ((8),(5))` ways to to this

`color(red)(((8),(1))+((8),(2))+((8),(3)))`

There are five types of compositions of `5` with a unique largest part:

• `(1,1,1,2)`: `4` permutations
• `(1,1,3)`: `3` permutations
• `(1,4)`: `2` permutations
• `(2,3)`: `2` permutations
• `(5)`: `1` permutation

`color(red)(1+2+2+3+4 = 12)`

Let `a,b,c,d,e` be the number of hours she takes on Monday, Tuesday, Wednesday, Thursday, and Friday respectively

This is a weak composition of `6` into `5` parts

`color(red)(((10),(6)))`

This is the same problem as the number of compositions of `5` into integer parts

`color(red)(2^(5-1) = 2^4 = 16)`

`x_1 + x_2 + x_3 + x_4 + x_5 = 25` where `x_1, ..., x_5` are odd integers

Let `x_i = 2y_i+1`

This is a weak composition of `10` into `5` parts

`color(red)(((14),(10)))`

Let `a,b,c,d,e` be the number of hours he takes on Monday, Tuesday, Wednesday, Thursday, and Friday respectively

`a+b+c+d+e = 8` where `d gt e`

He could take `0, 1, 2, 3` hours on Friday

Since he wants fewer hours on Friday than on Thursday, we add `e+1` hours to `d` to maintain the rule `d gt e` and to turn the problem into a weak composition problem

`color(red)(((10),(7))+((8),(5))+((6),(3))+((4),(1)))`

There are only two ways to have `n-2` blocks:

• one block of size `3` and `n-3` singletons: `((n),(3))`
• two blocks of size `2` and `n-4` singletons: `((n),(4))*((4),(2))*1/2` (choose four numbers to be in the two blocks, then choose two of those four numbers to be in one of the blocks, the order of the blocks don't matter)

`color(red)(((n),(3))+((n),(4))*((4),(2))*1/2)`

Alternatively, for the two blocks of size `2`, we could choose two numbers to be in one block, then choose another two to be in the other block: `((n),(2))*((n-2),(2))*1/2`

There are only `3` ways to have `n-3` blocks:

• one block of size `4` and `n-4` singletons: `((n),(4))`
• one block of size `3`, one block of size `2` and `n-5` singletons: `((n),(5))*((5),(3))` (choose `5` to be in the two blocks, then choose `3` to be in the block of size `3`)
• three blocks of size `2` and `n-6` singletons: `((n),(2))*((n-2),(2))*((n-4),(2))*1/(3!)`

`color(red)(((n),(4))+((n),(5))*((5),(3))+((n),(2))*((n-2),(2))*((n-4),(2))*1/(3!))`

Alternatively, for the one block of size `3`, we could do `((n),(3))*((n-3),(2))`

`B(n)-F(n)` is the number of partitions of `[n]` where each partition has at least one singleton

Goal: Prove `B(n)-F(n) = F(n+1)`

Claim: There is a bijection between `A = {`partitions of `[n]` such that there is at least one singleton`}` and `B = {`partitions of `[n+1]` such that every block has size `gt 1}`

Let `f:A rarr B` be defined as follows:

For a partition in `A`, add the singleton `{n+1}` and merge together all the singleton blocks into one block

This produces an element in `B` because there are no singleton blocks, i.e., every block has size `gt 1`

Let `g:B rarr A` be defined as follows:

For a partition in `B`, break up the block containing `n+1` into singletons and remove the singleton `{n+1}`

This produces an element in `A` because there are now singleton blocks, i.e., there is at least one block with size `1`

So `g` is the inverse of `f`

`implies f` is a bijection

`implies |A| = |B|`

`implies B(n)-F(n) = F(n+1)`

`implies B(n) = F(n) + F(n+1)`

Start with the binomial theorem

Take the derivative (with respect to `x`) of both sides twice

Plug in `x=y=1`

The left-hand side is counting the number of ways to

1. Pick `m` people to form a soccer team from a group of `n` people
2. Then pick `k` people from the remaining people (`n-m`) to form a basketball team

The right-hand side is counting the number of ways to

1. Pick `k` people to form a basketball team from a group of `n` people
2. Then pick `m` people from the remaining people (`n-k`) to form a soccer team

Both are counting the number of ways to form an `m`-member soccer team and a `k`-member basketball team

`((2n),(n))` is the number of `n`-element subsets of `[2n]`

`4^n = 2^(2n)` is the number of all subsets of `[2n]`

Pair each subset with its complement

If `n` is odd:

• The two subsets in each pair will be different sizes, so there will be a larger subset in each pair
• There are `2^(n-1)` unique pairs, so there are `color(red)(2^(n-1))` subsets larger than their complement

If `n` is even, then let `n = 2k`

`sum_(i=0)^(k-1)((n),(i))` counts the number of subsets that are larger than their complements

To get that summation, we could split the subsets of `[n]` into three groups:

• Subsets with size `0 le i le k-1`: `sum_(i=0)^(k-1)((n),(i))=((n),(1))+((n),(2))+...+((n),(k-1))`
• Subsets with size `k=n/2`: `((n),(k))=((n),(n/2))`

• Subsets with size `k+1 le i le n`: this is the "reverse" of `0 le i le k-1`, so it is also counted by `sum_(i=0)^(k-1)((n),(i))`

So we have

Start with the multinomial theorem

Plug in `x_1=x_2=x_3=1`

Start with the multinomial theorem

Plug in `x_1=x_3=1`, `x_2=-1`

Since there's an `n` dropped down from the exponent, it looks like we have to take the derivative of `sum_(n=0)^(oo)x^n = 1/(1-x)`

Take out the constant term from `sum_(n=0)^(oo)x^n` in order to take the derivative

Taking the derivative, we get

Now we have to show that `((2n),(n)) = ((2n)!)/(n!n!) = (1*3*5*...*(2n-1))/(n!)2^n`, which is the same as showing `((2n)!)/(n!) = 1*3*5*...*(2n-1)*2^n`

For `((2n)!)/(n!)`, all the terms on the bottom will divide all the even terms on top in half, resulting in `2^n` and all the odd terms leftover, which is `1*3*5*...*(2n-1)*2^n`

Count the number of pairs `(x,c)` where `x` is a student and `c` is a class

There are `105*3 = 315` pairs

Distribute the pairs among `7` groups so that each group has the same number of pairs

So there are `color(red)(315/7 = 45)` students in each class

Count the paths from `(0,0)` to `(3,3)`:

Count the paths from `(3,3)` to `(10,10)`

Since we can't go through `(5,5)`, count the number of paths going through `(5,5)` and subtract from the total number of paths

Paths from `(3,3)` to `(5,5)`:

Paths from `(5,5)` to `(10,10)`

Paths from `(3,3)` to `(10,10)` that go through `(5,5)`:

Paths from `(3,3)` to `(10,10)` that don't go through `(5,5)`:

Paths from `(0,0)` to `(10,10)` that don't go through `(5,5)`:

Note that `((n),(k))^2 = ((n),(k))*((n),(k)) = ((n),(k))*((n),(n-k))`

The left-hand side is counting the number of ways to pick `n` people from a group of `2n` people

We could pick people another way by splitting the `2n` people into two groups of `n` people

Pick `k` people from the first group: `((n),(k))`

Now we have to pick `n-k` people from the second group: `((n),(n-k))`

Summing over all `k`, we get the result

Note that `((n),(k))^2 = ((n),(k))*((n),(k)) = ((n),(k))*((n),(n-k))`

The left-hand side is counting the number of ways to form a group of `n` people with a leader from a group of `2n` people

First, pick the leader from `n` people, then pick `n-1` people from `2n-1` people to form the group

We could pick people another way by splitting the `2n` people into two groups of `n` people and picking a leader from the first group

Pick `k` people from the first group: `((n),(k))`

Pick a leader from the first group: there are `k` choices

Now we have to pick `n-k` people from the second group: `((n),(n-k))`

Summing over all `k`, we get the result

Start with the binomial theorem:

Plug in `x=2, y=1`:

(Refer to the trick for getting rid of even/odd terms of a formal power series in the egf section)

We can isolate the even terms by adding `sum_(k=0)^n((n),(k))(-2)^k` to `sum_(k=0)^n((n),(k))2^k`

Notice that the terms with odd exponents will cancel out after addition, leaving

Dividing by `2` will give us

Using the binomial theorem, we can simplify `sum_(k=0)^n((n),(k))2^k` and `sum_(k=0)^n((n),(k))(-2)^k`

Adding those and dividing the sum by `2` gives us

which is equal to `sum_(k=0)^n((n),(k))2^k` for even `k` as shown at the beginning

(Refer to the trick for getting rid of even/odd terms of a formal power series in the egf section)

We can isolate the odd terms by subtracting `sum_(k=0)^n((n),(k))(-5)^k` from `sum_(k=0)^n((n),(k))5^k`

Notice that the terms with even exponents will cancel out after subtraction, leaving

Dividing by `2` will give us

Using the binomial theorem, we can simplify `sum_(k=0)^n((n),(k))5^k` and `sum_(k=0)^n((n),(k))(-5)^k`

Adding those and dividing the sum by `2` gives us

which is equal to `sum_(k=0)^n((n),(k))5^k` for odd `k` as shown at the beginning

`root(3)(1-2x) = (1-2x)^(1/3)`

Start with the general binomial theorem:

Plug in `x=-2x` and `m=1/3`

So the coefficient of `x^n` is `color(red)(((1/3),(n))(-2)^n)`

We can think of `sum_(i=0)^(k-1)2^i` as a binary digit with `k` `1`'s

Adding `1` to that binary digit results in a `1` followed by `k` `0`'s, which is `2^k`

So `a_k = sum_(i=0)^(k-1)2^i = color(red)(2^k-1)`

She can reach the `n^(th)` step from either the `(n-1)^(st)` step or the `(n-2)^(nd)` step

So `f(n) = f(n-1) + f(n-2) implies f(n+2) = f(n+1) + f(n)`

Let `f(0)=1`

Multiply the recurrence by `x^(n+2)` and sum over all `n ge 0`

Let `B(x)` be the generating function for the number of ways to pay `n` dollars using only ten-dollar bills

Let `C(x)` be the generating function for the number of ways to pay `n` dollars using only five-dollar bills

Let `D(x)` be the generating function for the number of ways to pay `n` dollars using only one-dollar bills

Then the product `B(x)C(x)D(x)` will be the number of ways to pay `n` dollars using those three types of bills

For `B(x)`, there are no ways to pay `n` dollars using only ten-dollar bills for `1 le n le 9`, `11 le n le 19`, ..., so

Similarly for `C(x)` and `D(x)`

So `A(x)=B(x)C(x)D(x)=color(red)(1/((1-x^10)(1-x^5)(1-x)))`

Multiply the recurrence by `x^n` and sum over all `n`:

Simplifying `((n),(2)) = (n*(n-1)*(n-2)!)/(2*(n-2)!) = (n(n-1))/2`, we get

`sum_(n ge 2)n(n-1)x^n` looks like a double derivative and `sum_(n ge 1)nx^n` looks like a derivative

Taking the derivatives and multiplying by `x` and `x^2` gives us

Consider a subset that satisfies the condition

If `n` is part of the subset, then `n-1` and `n-2` cannot be in the subset

So there would be `f(n-3)` ways to make this subset

If `n` is not part of the subset, then there would be `f(n-1)` ways to make this subset

So we get the recurrence `f(n) = f(n-3)+f(n-1)` for `n ge 3`

`f(0) = 1` (just the empty set)

`f(1) = 2` (the empty set and `{1}`)

`f(2) = 3` (the empty set, `{1}` and `{2}`)

Multiply the recurrence by `x^n` and sum over all `n ge 3`

Since the number of parts is unspecified, this problem involves a composition of generating functions

This is equivalent to splitting up `[n]` into intervals and covering each interval with a single tile of odd length

If the length of the interval is even, then there is no way to do this

If the length of the interval is odd, then there is one way to do this

So `A(x)=x+x^3+x^5+... = x(1+x^2+x^4+...) = x/(1-x^2)`

So `B(x) = 1/(1-A(x))`

Multiply the recurrence by `x^(n+1)` and sum over all `n ge 0`:

Using partial fractions, we get

So `a_n` is the coefficient of `x^n`, which is `color(red)(2*3^n-2^n)`

We can use the characteristic polynomial `t^2-c_1t-c_2` where `c_1=8` and `c_2=-16`

Since the roots are the same there exist `alpha_1,alpha_2` such that `a_n = alpha_1 4^n+alpha_2n4^n`

Plugging in `n=0,1`:

The recurrence is `a_(n+1) = 2a_n + 1000` for `n ge 0` and `a_0=50`

Multiply the recurrence by `x^(n+1)` and sum over `n ge 0`:

Using partial fractions, we get:

So `a_n` is the coefficient of `x^n`, which is `color(red)(1050*2^n-1000)`

Since there's an `(n+1)!`, we should probably use exponential generating functions

Let `A(x) = sum_(n ge 0)a_n/(n!)x^n`

Multiply both sides by `x^(n+1)/((n+1)!)` and sum over `n ge 0`

So `color(red)(a_n = 2n(n!))`

Consider removing the `n^(th)` part of the composition

If it was of size `2`, then there are `h_(n-2)` ways to get a composition of `n`

If it was of size `3`, then there are `h_(n-3)` ways to get a composition of `n`

So we get the recurrence `h_n = h_(n-2)+h_(n-3)` for `n ge 3` and `h_0=1, h_1=0, h_2=1`

Multiply the recurrence by `x^n` and sum over all `n ge 3`:

Alternatively, since the number of parts are unspecified, we could compose generating functions

Let `h_n` be the number of ways to break up `[n]` into consecutive intervals of sizes `2` and `3`

Let `alpha` be the ways to create a set of size `2` or `3`

So `a_2=a_3=1` and `a_n = 0` for `n != 2,3`

So `A(x) = sum_(n ge 0)a_nx^n = x^2+x^3`

`H(x) = 1/(1-A(x)) = color(red)(1/(1-x^2-x^3))`

Consider removing the `n^(th)` tile

If it was a `1xx1` tile, then there are `2` ways to create the rectangle

If it was a `1xx2` tile, then there are `3` ways to create the rectangle

So we get the recurrence `h_n = 2h_(n-1)+3h_(n-2)` for `n ge 2` and `h_0=1, h_1=2`

Multiply the recurrence by `x^n` and sum over all `n ge 2`:

Consider the last letter of the sequence

If it is a `B`, then there are `h_(n-1)` ways to form this sequence

If it is an `A`, then there are `h_(n-2)` ways to form this sequence because the second to last letter must be a `B`

So we get the recurrence `h_n = h_(n-1) + h_(n-2)` where `h_0 = 1` and `h_1 = 2`

Multiply the recurrence by `x_n` and sum over all `n ge 2`:

We want to split up the books into two nonempty subsets and order the books in each subset

Let `a_n` be the number of ways to order the books in the first shelf

Let `b_n` be the number of ways to order the books in the second shelf

`t_n` is the coefficient of `x^n/(n!)` in the product `A(x)B(x)`

So `color(red)(t_n = n!(n-1))` for `n ge 2` and `color(red)(t_0 = t_1 = 0)`

Let `a_n` be the number of ways to order the people in `A` in a line

Let `b_n` be the number of ways to order the people in `B` in a line

Let `c_n` be the number of ways to order the people in `C` in a line

The answer is the coefficient of `x^n/(n!)` in the product `A(x)B(x)C(x)`

And use partial fraction decomposition to continue

This is the same problem as picking subsets `A sube B sube [n]` such that `A` is even, `B\\A` is odd, and `[n]\\B` can be even or odd

(We frame the problem this way to set the problem up with disjoint sets whose union is the whole set)

Let `a_n` be the number of ways for a subset to be even

Let `b_n` be the number of ways for a subset to be odd

Let `c_n` be the number of ways for a subset to be of size `n`

The answer is the coefficient of `x^n/(n!)` in the product `A(x)B(x)C(x)`

The coefficient of `x^n/(n!)` is `color(red)(1/4(3^n-(-1)^n))`

Let `a_n` be the number of ways to form a line of cards

Let `b_n` be the number of ways to form a line of subsets

Let `c_n` be the answer to the problem

So the exponential generating functions are

The answer is the coefficient of `x^n/(n!)` in the composition `B(A(x))`

So `c_n = color(red)(n!(-2)^(n-2))` for `n ge 2`

`c_0` is the constant term, which is `1`

`c_1` is the linear term, which is `0`

Since the number of parts is specified, this problem involves multiplying generating functions

(a) This problem is the same as splitting up `[n]` into `k` consecutive intervals such that the `i^(th)` interval has size `ge 1` and `le a_i`

So `A(x) = A_1(x)A_2(x)...A_k(x)` where `A_i(x)` encodes the conditions on the `i^(th)` interval

`A_i(x) = x + x^2 + ... + x^(a_i) = x(1+x+...+x^(a_i-1))`

So `A(x) = prod_(i=1)^k x(1+x+...+x^(a_i-1)) = color(red)(prod_(i=1)^k x(1-x^(a_i))/(1-x))`

(b) With the same constraints on `1 le i le k`, we have

Since there is no constraint for the `(k+1)^(st)` part, we have

So `B(x) = color(red)((xA(x))/(1-x))`

We can count the number of integers that are not relatively prime to `210` and subtract that from `210`

An integer is not relatively prime to `210` if it is divisible by `2` or `3` or `5` or `7`

Let `A_2` be the set of integers divisible by `2`

Let `A_3` be the set of integers divisible by `3`

Let `A_5` be the set of integers divisible by `5`

Let `A_7` be the set of integers divisible by `7`

Then the set of all integers relatively prime to `210` are in the union `A_2 uu A_3 uu A_5 uu A_7`

By inclusion-exclusion, `|A_2 uu A_3 uu A_5 uu A_7|`

There are `210/2 = 105` integers divisible by `2`, so `|A_2| = 105`

There are `210/(2*3) = 35` integers divisible by `2` and `3`, so `|A_2 nn A_3| = 35`

(A number divisible by `2` and `3` is divisible by `6`)

There are `210/(2*3*5) = 7` integers divisible by `2` and `3` and `5`, so `|A_2 nn A_3 nn A_5| = 7`

So the number of integers not relatively prime to `210` is

The number of integers relatively prime to `210` is

We can count the number of integers that are not relatively prime to `pqr` and subtract that from `pqr`

An integer is not relatively prime to `pqr` if it is divisible by `p` or `q` or `r`

Let `A_p` be the set of integers divisible by `p`

Let `A_q` be the set of integers divisible by `q`

Let `A_r` be the set of integers divisible by `r`

Then the set of all integers relatively prime to `pqr` are in the union `A_p uu A_q uu A_r`

By inclusion-exclusion, `|A_p uu A_q uu A_r|`

which is the number of integers not relatively prime to `pqr`

So the number of integers relatively prime to `pqr` is

Let `A_(n-1)` be the set of `n`-permutations whose excedence set contains only `n-1`

Let `A_(n-2)` be the set of `n`-permutations whose excedence set contains only `n-2`

Then the number of `n`-permutations whose excedence set contains at least one of `n-2` and `n-1` is the union `A_(n-1) uu A_(n-2)`

By inclusion-exclusion, `|A_(n-1) uu A_(n-2)|`

For `n-1` to be an excedence, the number at the `(n-1)^(st)` spot has to be bigger than `n-1`. There is only one number (`n`) bigger than `n-1`, so there is only one choice for `p_(n-1)`. There are `n-1` remaining numbers for the rest of the spots, so `|A_(n-1)| = (n-1)!`

For `n-2` to be an excedence, the number at the `(n-2)^(nd)` spot has to be bigger than `n-2`. There are two numbers (`n` and `n-1`) bigger than `n-2`, so there are two choices for `p_(n-2)`. There are `n-1` remaining numbers for the rest of the spots, so `|A_(n-2)| = 2(n-1)!`

For `n-1` and `n-2` to be an excedence, the number at the `(n-1)^(th)` spot has to be bigger than `n-1` and the number at the `(n-2)^(nd)` spot has to be bigger than `n-2`. `p_(n-1)` is forced to be `n`, which forces `p_(n-2)` to be `n-1`. There are `n-2` remaining numbers for the rest of the spots, so `|A_(n-1) nn A_(n-2)| = (n-2)!`

So the number of `n`-permutations whose excedence set contains at least one of `n-2` and `n-1` is

Let `A_1` be the set of partitions containing the singleton block `{1}`

Let `A_n` be the set of partitions containing the singleton block `{n}`

The set of partitions containing at least one of the singleton blocks is the union `A_1 uu A_n`

By inclusion-exclusion, `|A_1 uu A_n|`

For `A_1`, we put `1` in its own block. Then there are `n-1` numbers to put into blocks, which is counted by `B(n-1)`

For `A_1 nn A_n`, we put `1` and `n` in their own blocks. Then there `n-2` numbers to put into blocks, which is counted by `B(n-2)`

So the number of partitions that contain at least one of the singleton blocks `{1}` and `{n}` is

Count the number of compositions that have a `1` in the first entry or a `1` in the last entry and subtract from the total number of compositions

Let `A_1` be the set of compositions that have a `1` in the first entry

Let `A_2` be the set of compositions that have a `1` in the last entry

Then the set of compositions in which the first or last entry is a `1` is the union `A_1 uu A_2`

By inclusion-exclusion, `|A_1 uu A_2|`

For `A_1`, since there is a `1` in the first entry, the problem turns into compositions of `n-1`, of which there are `2^(n-1-1) = 2^(n-2)`

For `A_1 nn A_2`, since there is are `1`'s in the first and last entry, the problem turns into compositions of `n-2`, of which there are `2^(n-2-1) = 2^(n-3)`

So the number of compositions in which the first or last entry is a `1` is

The number of compositions in which neither the first nor last entry is `1` is

Consider the set `[n+1]`

Consider the number `n+1`. There are `n` choices for it

Suppose `n+1` is mapped to `i`

If `i` is not mapped to `n+1`, then we are now looking at derangements of a set of size `n`, which is `D(n)`

If `i` is mapped to `n+1`, then we are now looking at derangements of a set of size `n-1`, which is `D(n-1)`

So the number of derangements for a set of size `n+1` is `n(D(n)+D(n-1))`

Let `A_6` be the set of integers divisible by six

Let `A_7` be the set of integers divisible by seven

Then the set of integers divisible by six or seven is the union `A_6 uu A_7`

By inclusion-exclusion, `|A_6 uu A_7|`

There are `900/6 = 150` integers divisible by six, so `|A_6| = 150`

There are `lfloor900/7rfloor = 128` integers divisible by seven, so `|A_7| = 128`

There are `lfloor900/42rfloor = 21` integers divisible by six and seven, so `|A_6 nn A_7| = 21`

So the number of integers divisible by at least one of six and seven is

Count the number of integers not relatively prime to two or three and subtract from the total number of two-digit positive integers

Let `A_2` be the set of integers divisible by two

Let `A_3` be the set of integers divisible by three

Then the set of integers divisible by two or three is the union `A_2 uu A_3`

By inclusion-exclusion, `|A_2 uu A_3|`

There are `90/2 = 45` integers divisible by two, so `|A_2| = 45`

There are `90/3 = 30` integers divisible by three, so `|A_3| = 30`

There are `90/6 = 15` integers divisible by two and three, so `|A_2 nn A_3| = 15`

So the number of integers divisible by two or three is

The number of two-digit positive integers that are relatively prime to both two and three is

Count the number of arrangements that have consecutive `1`'s or consecutive `2`'s and subtract from the total number of arrangements

Let `A_1` be the set of arrangements that have consecutive `1`'s

Let `A_2` be the set of arrangements that have consecutive `2`'s

Then the set of arrangements that have consecutive `1`'s or consecutive `2`'s is the union `A_1 uu A_2`

By inclusion-exclusion, `|A_1 uu A_2|`

We can combine the two `1`'s into one `1` since they have to go together

Then there are `(6!)/(2!)` ways to arrange the numbers, so `|A_1| = (6!)/(2!)

We can also combine the two `2`'s into one `2` since they have to go together

Then there are `5!` ways to arrange the numbers, so `|A_1 nn A_2| = 5!`

So the number of arrangements that have consecutive `1`'s or consecutive `2`'s is

The number of arrangements that don't have consecutive `1`'s and `2`'s is

Count the number of integers that are perfect squares or perfect cubes and subtract from the total number of integers

Let `A_2` be the set of perfect squares

Let `A_3` be the set of perfect cubes

Then the set of perfect squares or perfect cubes is the union `|A_2 uu A_3|`

By inclusion-exclusion, `|A_2 uu A_3|`

There are `lfloorsqrt(1000)rfloor = 31` perfect squares, so `|A_2| = 31`

There are `root(3)(1000) = 10` perfect cubes, so `|A_3| = 10`

A perfect square that is also a perfect cube is a number that has the form `(x^2)^3 = x^6`

There are `lfloorroot(6)(1000)rfloor = 3` numbers that are perfect squares and perfect cubes

So the number of integers that are perfect squares or perfect cubes is

The number of integers that are neither perfect squares nor perfect cubes is