Category Archives: Combinatorics

A combinatorial identity

While tutoring today a student asked me about the following identity

(*)\qquad\qquad\qquad\displaystyle\sum_{n\ge i\ge j\ge k\ge 0}\binom ni\binom ij\binom jk=4^n.

One way to prove it is to count the number of possible triples (A,B,C) of sets with C\subseteq B\subseteq A\subseteq S=\{1,\dots,n\}. This can be done in two ways. First, if A, B, C contain i,j,k elements respectively then the number of such triples clearly equals the left-hand side of (*). On the other hand, since each element of S must belong to one of the four disjoint regions in the picture below

screenshot-2016-10-03-21

the number of such triples equals precisely 4^n.

An algebraic proof can be obtained by repeated use of the binomial theorem:

\displaystyle 4^n=\sum_{n\ge i\ge 0}\binom ni3^i=\sum_{n\ge i\ge j\ge 0}\binom ni\binom ij2^j=\sum_{n\ge i\ge j\ge k\ge 0}\binom ni\binom ij\binom jk.

Similarly, one obtains the more general identity

\displaystyle\sum_{n\ge i_m\ge\cdots\ge i_1\ge 0}\binom{n}{i_1}\binom{i_1}{i_2}\cdots\binom{i_{m-1}}{i_m}=(m+1)^n.

This also follows from the multinomial theorem since the left-hand side equals

\displaystyle\sum_{n\ge i_m\ge\cdots\ge i_1\ge 0}\frac{n!}{(n-i_1)!(i_1-i_2)!\cdots (i_{m-1}-i_m)!i_m!}=(m+1)^n.

Advertisements

Leave a comment

Filed under Combinatorics

Number of irreducible polynomials over a finite field

I and some friends just came up with this. (We came up with some ideas for the proof, after coming across the formula on the internet.) This is the coolest application of the Möbius inversion formula that I’ve seen so far.

Let q be a prime power and n any positive integer. We wish to count the number C(n) of monic irreducible polynomials of degree n over the finite field \mathbb F_q.

Note that the zeros of

\displaystyle F_d(X):=\prod_{\deg(f)=d}f(X)

are precisely the elements of degree d over \mathbb F_q, where the product is taken over monic irreducible polynomials f\in\mathbb F_q[X]. Further, we have the following:

Lemma 1. Let g\neq h be relatively prime polynomials over a field k. Then g and h have no common zeros.

Proof. Since k[X] is a PID, there are polynomials u,v\in k[X] such that ug+vh=1. If \alpha is a common zero of g and h in some extension K/k, then X-\alpha divides 1=ug+vh in K[X], a contradiction. \square

Lemma 2. If f is irreducible over a field k, then f has distinct zeros.

Proof. Note that any multiple zero of f must be a common zero of f and its formal derivative f'. Since f is irreducible over k, it follows that f and f' are relatively prime over k. Now apply lemma 1 to f and f'. \square

It follows that the zeros of

\displaystyle \prod_{d\mid n}F_d(X)

are all distinct and are precisely the elements of the union of all the subfields of \mathbb F_{q^n}, which is just \mathbb F_{q^n}. This implies

(*)\qquad\qquad\qquad\qquad\quad\displaystyle\prod_{d\mid n}F_d(X)=X^{q^n}-X,

since \mathbb F_{q^n} is the splitting field of X^{q^n}-X over \mathbb F_q. Now a comparison of the degrees of both sides reveals that

\displaystyle\sum_{d\mid n}dC(d)=q^n.

Finally, Möbius inversion gives

\displaystyle \boxed{C(n)=\frac 1n\sum_{d\mid n}\mu(d)q^{n/d}}.

Leave a comment

Filed under Combinatorics, Number theory

Proof of a well-known identity involving Euler’s phi function

Let \phi(n) be Euler’s function, i.e., the number of positive integers not exceeding n that are coprime to n. A famous identity goes as follows:

\displaystyle\sum_{d\mid n}\phi(d)=n

where the sum is taken over all positive divisors of n. Here is a counting argument for a proof.

Let S=\{1,\dots,n\}. For each divisor d of n, let us count the number of elements m\in S with \gcd(m,n)=d. When d=1, this is just \phi(n). What about when d=2? If n is odd then clearly there is no such m. Otherwise, \gcd(m,n)=2 implies that m and n must both be even. Moreover, this happens iff \gcd(m/2,n/2)=1. Hence, as before, the number of such m is \phi(n/2).

This works in general: for any d\mid n, the number of elements m\in S such that \gcd(m,n)=d is \phi(n/d). So summing \phi(n/d) over all d\mid n, which is the same as summing \phi(d) over all d\mid n, gives the total number of elements of S, which is n. This proves the desired result.

This begs for a generalisation. I will add it here when I come up with one. (I really need to sleep now!)

4 Comments

Filed under Combinatorics, Number theory

Number of permutations of prime order

In the last post we counted the number of elements of order 2 in the symmetric group S_n. In exactly the same way we can count the number of elements of order p, where p is a prime number. Let this number be denoted by N_p(n). Then

\displaystyle\begin{aligned}N_p(n)&=\sum_{k=1}^{\lfloor n/p\rfloor}\frac{(p-1)!^k}{k!}\binom np\binom{n-p}{p}\cdots\binom{n-pk+p}{p}\\  &=\sum_{k=1}^{\lfloor n/p\rfloor}\frac{n!}{k!(n-pk)!p^k}\\  &=\sum_{k=1}^{\lfloor n/p\rfloor}\binom{n}{pk}\frac{(pk)!}{k!p^k}.\end{aligned}

Here we adopt the convention \binom nm=0 if m>n. Note that

\displaystyle\frac{(pk)!}{k!p^k}=\frac{(pk)!}{p\cdot 2p\cdots kp}\equiv (p-1)!^k\equiv (-1)^k\pmod p

by Wilson’s theorem. So

\displaystyle N_p(n)\equiv\sum_{k=1}^{\lfloor n/p\rfloor}(-1)^k\binom{n}{pk}\pmod p.

If n=n_rp^r+\cdots+n_1p+n_0 and k=k_{r}p^{r-1}+\cdots+k_2p+k_1 are base p expansions, then using Lucas’ theorem one has

\displaystyle\binom{n}{pk}\equiv\binom{n_r}{k_r}\cdots\binom{n_1}{k_1}\pmod p.

Therefore

\displaystyle\begin{aligned}N_p(n)&\equiv -1+\sum_{k=0}^{\lfloor n/p\rfloor}(-1)^k\binom{n}{pk}\pmod p\\  &\equiv -1+\sum_{k=0}^{\lfloor n/p\rfloor}(-1)^{k_1+\cdots+k_r}\binom{n_r}{k_r}\cdots\binom{n_1}{k_1}\pmod p\\  &\equiv -1+\prod_{j=1}^r\sum_{k_j=0}^{n_j}(-1)^{k_j}\binom{n_j}{k_j}\pmod p\\  &\equiv -1\pmod p\end{aligned}

This generalizes the result from the previous post.

Corollary. The number of subgroups of order p in S_n is congruent to 1\pmod p.

Proof. If there are k subgroups of order p in S_n, then N_p(n)=k(p-1)\equiv -1\pmod p and so k\equiv 1\pmod p. \square

1 Comment

Filed under Combinatorics, Number theory

Number of permutations of order 2

Let \sigma\in S_n be an element of order 2. Then \sigma must be a product of k\ge 1 disjoint transpositions. Hence \sigma can be chosen in

\displaystyle\frac{1}{k!}\binom n2\binom{n-2}{2}\cdots\binom{n-2k+2}{2}=\frac{n!}{k!(n-2k)!2^k}

ways. So there are exactly

\displaystyle\boxed{\sum_{k=1}^{\lfloor n/2\rfloor}\frac{n!}{k!(n-2k)!2^k}}

elements of order 2 in S_n.

This can also be expressed in terms of the double factorial

\displaystyle\sum_{k=1}^{\lfloor n/2\rfloor}\binom{n}{2k}(2k-1)!!

The following table lists several values of n (left column) along with the number of elements of order 2 in S_n:

Screenshot 2015-03-15 20.54.56

An interesting feature of the table is that the entries on the second column, except for the first row, are all odd. This is true in general and is not difficult to prove. Using the double factorial notation, the number of elements of order 2 is

\displaystyle\sum_{k=1}^{\lfloor n/2\rfloor}\binom{n}{2k}(2k-1)!!\equiv \sum_{k=1}^{\lfloor n/2\rfloor}\binom{n}{2k}\pmod 2

Using the binomial theorem for (1+1)^n and (1-1)^n one deduces

\displaystyle\sum_{k=1}^{\lfloor n/2\rfloor}\binom{n}{2k}=2^{n-1}-1\equiv 1\pmod 2

as expected. Thus

Fact. The number of elements of order 2 in S_n is odd for every n>1.

1 Comment

Filed under Combinatorics