Archive

Catalan numbers

The Catalan numbers are defined by

C_n = \frac{1}{n + 1} \binom {2n} {n}.

Corollary 2 of the previous post established that

\#\{n < 2^t: C_{n} \equiv 0 \mod {2^k} \} = \sum_{i = k+1}^{i = t} \binom{t} {i}.

This result can be used to show that the asymptotic density of the set  \#\{n < N: C_{n} \equiv 0 \mod {2^k} \} is 1.

To this end let N \in \mathbb{N}: 2^{r} \leq N < 2^{r+1} for some r \in \mathbb{N}. Then  r = \lfloor \log_2(\, N)\,  \rfloor and

 \#\{n < N: d(\, \alpha (\, n )\, )\, = k \} \leq \#\{n < 2^{r+1}: d(\, \alpha (\, n )\, )\, = k \} = \binom {r+1} {k + 1}.

So, as mentioned in the previous post

 \#\{n < N: C_{n} \equiv 0 \mod {2^k} \} = N - \#\{n < N: d(\, \alpha (\, n )\,  )\,  < k \}

= N - \sum_{i = 0}^{i = k - 1} \#\{n < N: d(\, \alpha (\, n )\,  )\,  = i \} \geq N - \sum_{i = 0}^{i = k - 1} \binom {r+1} {i + 1}.

And so

 \frac {1}{N} \#\{n < N: C_{n} \equiv 0 \mod {2^k} \} \geq 1 - \frac {1}{N} P_{k} (\, r )\,

= 1 - \frac {1}{N} P_{k} (\, \lfloor \log_2 (\, N )\,  \rfloor )\,

where P_{k} (\, r )\, is a polynomial in r of degree k with coefficients depending on k. Since k is fixed and lim_{N \to \infty} \frac {1}{N} (\, log_2{N} )\, ^{k} = 0 for fixed k the second term above is zero in the limit and

lim_{N \to \infty} \frac {1}{N} \#\{n < N: C_{n} \equiv 0 \mod {2^k} \} = 1.

This result is not surprising given the highly composite nature of the Catalan numbers. In general we would also expect that the same result holds with 2^{k} replaced by any natural number.

 

Advertisements

Summary

The Catalan numbers are defined by

C_n = \frac{1}{n + 1} \binom {2n} {n}.

This note will use results obtained by Liu and Yeh in [1] to obtain a formula for the number of C_n < 2^{ t } which are divisible by 2^{ k }   where   t,  k   \in   \mathbb{N}.

Firstly, as in [1], let the p-adic order of a positive integer n be defined by

\omega_p(\, n )\, := max\{\alpha \in \mathbb{N} : p^{\alpha} | n\} .

and the cofactor of n with respect to  p^{ \omega_p(\, n )\, }  be defined by

CF_p(\, n )\,  := \frac {n} {p^{\omega_p(\, n )\,}} .

In addition the function \alpha : \mathbb{N} \to \mathbb{N}  is defined by

\alpha (\, n )\, := \frac {CF_2(\, n + 1 )\, - 1} {2}.

For a number p, we write the base p expansion of a number n as

[\, n ]\,_{p} = \langle n_{r} n_{r-1} ... n_{1} n_{0} \rangle

where n_{i} \in [\, 0, p - 1]\,  and n = n_{r} p^{r} + n_{r-1} p^{r-1} + ... + n_{1} p + n_{0}.

Then the function d : \mathbb{N} \to \mathbb{N} := d (\, n )\, = n_{r} + n_{r-1} + ... + n_{1} + n    is the sum of the p-adic digits of a natural number n (i.e. the sum of the digits of n when n is written in base p). Here we will only be interested in the case p = 2 . Then

Theorem   1:   \#\{n < 2^t: d(\, \alpha (\, n )\, )\, = k \} = \binom {t} {k + 1}.

Corollary   2:   \#\{n < 2^t: C_{n} \equiv 0 \mod {2^k} \} =  \sum_{i = k+1}^{i = t} \binom{t} {i}.

Corollary   3:   \#\{n < 2^t: C_{n} \equiv 2^{k-1} \mod {2^k} \} =  \binom{t} {k}.

Proofs.

Proof of Theorem 1:

Let   \alpha = \alpha (\, n )\, = \frac {CF_2(\, n + 1 )\, - 1} {2} .  Then

n + 1 = 2^{s} (\, 2^{\alpha} + 1 )\,

for some arbitrary s \in \mathbb{N} : s  \geq 0 .  Writing n + 1  in base 2 we have

[\, n + 1 ]\,_{2} = \langle [\, \alpha ]\,_{2}, 1, 0 ... 0, 0 \rangle  where there are s  0’s at the end and s \geq 0  is arbitrary. So,

[\, n ]\,_{2} = \langle [\, \alpha ]\,_{2}, 0, 1 ... 1, 1 \rangle  where there are s  1’s  at the end and s \geq 0  is arbitrary. It can be seen that d(\, n )\, = d(\, \alpha )\, + s.

Since n < 2^{t}  and  d(\, \alpha (\, n )\, )\, = k  the possible base 2 representations of n are

[\, n ]\,_{2} = \langle [\, \alpha ]\,_{2}, 0 \rangle  with \alpha < 2^{t - 1}

[\, n ]\,_{2} = \langle [\, \alpha ]\,_{2}, 0, 1 \rangle  with \alpha < 2^{t - 2}

.

.

.

[\, n ]\,_{2} = \langle [\, \alpha ]\,_{2}, 0, 1, 1, ... 1 \rangle  with \alpha < 2^{k}  and (\, t - k - 1)\,   1’s at the end.

Therefore, counting each of these possibilities and using the fact that d (\, \alpha )\, = k  gives

\#\{n < 2^t: d(\, \alpha (\, n )\, )\, = k \} = \sum_{i = k}^{i = t - 1} \binom{i} {k} = \binom{t} {k + 1}.

\Box

 Proof of Corollary 2.

The following result appears in [1].

Theorem 4 (Corollary 4.3 of [1]): In general, we have \omega_{2} (\,  C_{n} )\, = d (\, \alpha )\, .   In particular,  C_{n} \equiv 0 (\,  mod  2^{k}  )\,  if and only if  d (\, \alpha )\, \geq k   ,  and  C_{n} \equiv 2^{k - 1} (\,  mod   2^{k}  )\,    if and only if  d (\, \alpha )\, = k - 1.

 

Corollary 2 follows from Theorem 1 and Theorem 4 above since

\#\{n < 2^t: C_{n} \equiv 0 \mod {2^k} \} = \#\{n < 2^t: d(\, \alpha (\, n )\,  )\,  \geq k \}  from Theorem 4

= 2^{t} - 1 -  \sum_{i = 0}^{i = k - 1} \#\{n < 2^t: d(\, \alpha (\, n )\,  )\,  = i \}

= 2^{t} - 1 - \sum_{i = 0}^{i = k - 1} \binom{t} {i + 1}  from Theorem 1

= 2^{t} - \sum_{i = 0}^{i = k} \binom{t} {i}

= \sum_{i = k + 1}^{i = t} \binom{t} {i}  since   2^{t} = \sum_{i = 0}^{i = t} \binom{t} {i}

\Box

Proof of Corollary 3.

From Theorem 4,

\#\{n < 2^t: C_{n} \equiv 2^{k-1} \mod {2^k} \} = \#\{n < 2^t: d(\, \alpha (\, n )\,  )\, =  k - 1 \}

= \binom{t} {k}  from Theorem 1.

\Box

Reference

[1]  Liu, S.-C., & Yeh, J. (2010). Catalan numbers modulo 2^k. J Integer Sequences. Vol 13 (2010) Article 10.5.4