Archive

Uncategorized

The recent posts regarding Catalan and Motzkin numbers have been consolidated in two papers at arXiv. They are located at https://arxiv.org/pdf/1611.04910v1.pdf (Asymptotic density of Motzkin numbers modulo small primes) and https://arxiv.org/pdf/1611.03705v1.pdf (Asymptotic density of Catalan numbers modulo 3 and powers of 2).

Advertisements

The Motzkin numbers M_n are defined by

M_n := \sum_{k \geq 0} \binom {n}{2k} C_{k}

where  C_{k}\, are the Catalan numbers. The following result is established in [1]

Theorem 1 (Theorem 5.5 of [1]). The nth Motzkin number M_n is even if and only if n = (4i + \epsilon)4^{j+1} - \delta for i, j \in \mathbb{N}, \epsilon \in \{1, 3\} and \delta \in \{1, 2\}. Moreover, we have

M_n \equiv 4 \mod 8 if (\, \epsilon, \delta )\, = (\, 1, 1 )\, or (\, 3, 2 )\,

M_n \equiv 4y + 2 \mod 8 if (\, \epsilon, \delta )\, = (\, 1, 2 )\, or (\, 3, 1 )\,

where \, y \, is the number of digit 1’s in the base 2 representation of \, 4i + \epsilon - 1.

Remark 2. The 4 choices for (\, \epsilon, \delta )\, in the above theorem give 4 disjoint sets of numbers n = (4i + \epsilon)4^{j+1} - \delta.

 

Theorem 3. Each of the 4 disjoint sets defined by the choice of (\, \epsilon, \delta )\, in Theorem 1 has asymptotic density  \frac {1}{12} in the natural numbers.

Proof: Use the result for the set S_{1} of Theorem 1 of the post here with q = 4, r = \epsilon, s = 1, t = 1.

\Box \, .

 

Corollary 4: The asymptotic density of

\{ n < N: M_n \equiv 0 \mod 2 \} is \frac {1}{3}.

The asymptotic density of

\{ n < N: M_n \equiv 4 \mod 8 \} is \frac {1}{6}.

The asymptotic density of each the sets

\{ n < N: M_n \equiv 2 \mod 8 \} and \{ n < N: M_n \equiv 6 \mod 8 \} is \frac {1}{12}.

Remark 5: The first 2 statements of Corollary 4 follows immediately from theorems 1 and 3. The third statement follows from the observation that the numbers of 1’s in the base 2 expansion of  i is equally likely to be odd or even and therefore the same applies the the number of 1’s in the base 2 expansion of 4i + \epsilon - 1. Since the asymptotic density of the 2 sets combined is \frac {1}{6} (from Theorems 1 and 3), each of the two sets has asymptotic density of \frac {1}{12}.

 

Reference

[1] Eu, S.-P., Liu, S.-C., & Yeh, Y.-N. (2008). Catalan and Motzkin numbers modulo 4 and 8. European Journal of Combinatorics, 29(6), 1449–1466. http://doi.org/10.1016/j.ejc.2007.06.019