Math tips


Tricks with factorials and binomials

Factorials and binomials show up a lot, but they are often pretty nasty to deal with. Here are a few tricks

Know some basic identities

Know that nlognlogn!n\log n \sim \log n!, i.e. they are of the same complexity.

However, if you are taking the difference of facorials, this doesn’t get you as far

Take the log of both sides

This is often a good move because it turns products into summations

Use binomial identities

  1. k(nk)=2n\sum_k \binom{n}{k} = 2^n
  1. (nn/2)(nk)\binom{n}{n/2} \geq \binom{n}{k} for all knk \leq n

Split into factorials

remember that

(nk)=n!(nk)!k!\binom{n}{k} = \frac{n!}{(n-k)!k!}

From here you can combine factorials if needed. For example, (m+nn)\binom{m+n}{n} can be simplified down to (m+n)!m!n!\frac{(m+n)!}{m!n!}

Turn it into product notation

Always remember that factorials have product notation associated with it.

n!=inin! = \prod_i^ni

The binomial coefficient has a nice rendering

(nk)=ikniki\binom{n}{k} = \prod_i^{k}\frac{n-i}{k-i}

Tricks with logs

The general rule is that klogm(n)k^{\log_m(n)} can be expressed as nlogm(k)n^{\log_m(k)}. This is because

x=klogm(n)logmx=logm(n)logm(k)logmx=logm(k)logm(n)x=nlogm(k)x = k^{\log_m(n)}\\ \log_m x = \log_m(n)\log_m(k)\\ \log_m x = \log_m(k)\log_m(n)\\ x = n^{\log_m(k)}

In a pinch, just know that you can swap the base and the thing inside the log.

Here are some useful identities (some of these we derived before)

We also have some expansions and expansions to keep in mind

Floors and ceilings

These are provable facts