Archive

Motzkin numbers

In previous posts we have established the asymptotic densities of the Motzkin numbers modulo 2^{k}, k \in \{1, 2, 3 \} and 5. The main result of this note is that

Theorem 1. 

\lim_{N \to \infty} \frac {1}{N} \#\{n \leq N: M_n \equiv 0 \mod 3 \} = 1.

 

Firstly, let T(\, 01 )\, denote the set of natural numbers which have a base 3 expansion containing only the digits 0 and 1. The following theorem from [1] will be used to prove theorem 1.

Theorem 2. (Corollary 4.10 of [1]). The Motzkin numbers satisfy

M_n \equiv  -1 \mod 3 \quad if  \quad n \in 3T (\, 01 )\, - 1,

M_{n} \equiv 1 \mod 3 \quad  if  \quad n \in 3T(\, 01 )\quad or \quad n \in 3T(\, 01 )\, - 2,

M_n \equiv 0 \mod 3 \quad otherwise.

 

We will first examine the nature of the set T(\, 01 \,). We have

Theorem 3. The asymptotic density of the set T(\, 01 \,) is zero.

Proof: 

Choose k \in N: 3^{k} \leq N < 3^{k+1}. Then k = \lfloor log_3 (\, N )\, \rfloor and

\frac {1}{N} \# \{ n \leq N :  n \in  T(01) \}  \leq \frac {2^{k+1}}{N} \leq \frac {2^{k+1}}{3^{k}} \to 0 as N \to \infty.

\Box \, .

 

Proof of Theorem 1.

Since the asymptotic density of T(\, 01 \,) is zero, so is the asymptotic density of the sets 3T(\, 01 \,) - k for k \in \{0, 1, 2\}. Therefore Theorem 2 implies that

\lim_{N \to \infty} \frac {1}{N} \# \{n \leq N : M_n \equiv +-1 \mod 3 \} = 0

and the result follows.

\Box \, .

References.

[1] Deutsch, E., & Sagan, B. E. (2006). Congruences for Catalan and Motzkin numbers and related sequences. Journal of Number Theory, 117(1), 191–215. http://doi.org/10.1016/j.jnt.2005.06.005

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

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.4 of [1]). The Motzkin number M_n is divisible by 5 if and only if n is one of the following forms

(\, 5i + 1 )\, 5^{2j}  - 2,\, (\, 5i + 2 )\, 5^{2j-1}  - 1,\, (\, 5i + 3 )\, 5^{2j-1}  - 2,\,  (\, 5i + 4 )\, 5^{2j}  - 1

where i, j \in \mathbb{N} and j \geq 1.

 

Theorem 2: The asymptotic density of numbers of the first form in theorem 1 is \frac {1}{120}. Numbers of the fourth form also have asymptotic density \frac {1}{120}. The asymptotic density of numbers of the second and third forms in theorem 1 is \frac {1}{24} each.

 

Corollary 3: The asymptotic density of \#\{n < N: M_{n} \equiv 0 \mod {5} \} is \frac {1}{10} \, .

 

Remark 4: Corollary 3 follows immediately from theorems 1 and 2 and the disjointness of the 4 forms of integers listed in theorem 1.

 

Remark 5: Numerical tests also show that roughly 22.5% of Motzkin numbers are congruent to each of 1, 2, 3, 4 \mod {5}.

 

Proof of Theorem 2.

Firstly consider numbers of the form (\, 5i + 1)\, 5^{2j} - 2\,. As we are interested in asymptotic density it is enough to look at numbers of the form (\, 5i + 1)\, 5^{2j}\,. We have, for fixed j \geq 1,

\#\{ i \geq 0: (\, 5i + 1)\, 5^{2j} \leq N \} = \frac {N}{5^{2j+1}} - \frac {1}{5} - E(\, j, N )\,

where 0 \leq E( \, j, N )  < 1 is an error term introduced by not rounding down to the nearest integer. So,

\#\{n < N: n = (\, 5i + 1)\, 5^{2j} \, for some  \, i, j \in \mathbb{N} \, with \, j \geq 1 \}

= \sum_{j \geq 1} (\,  \frac {N}{5^{2j+1}}  - \frac {1}{5} - E(\, j, N )\, )\, = \sum_{j = 1}^{\lfloor \frac{1}{2} (\, \log_{5} (\, N )\,- 1 )\,  \rfloor} (\, \frac {N}{5^{2j+1}}  - \frac {1}{5} - E(\, j, N )\, )\,

= \frac {N}{125} \sum_{j = 0}^{\lfloor \frac{1}{2} (\, \log_{5} (\, N )\,- 1 )\,  \rfloor - 1} (\, \frac {1}{25} )\,^{j} - E^{'}(\, N )\,

where the new error term E^{'} (\, N )\, satisfies 0 \leq E^{'} (\, N )\, < \frac{3}{5} (\, \log_{5} (\, N )\,. Then

\#\{n < N: n = (\, 5i + 1)\, 5^{2j} \, for some  \, i, j \in \mathbb{N} \, with \, j \geq 1 \}

= (\, \frac {N}{125} )\, \frac {1 - (\, \frac {1}{25} )\,^{\lfloor \frac{1}{2} (\, \log_{5} (\, N )\,- 1 )\,  \rfloor} }{1 - \frac {1}{25} } - E^{'}(\, N )\,.

Since \lim_{N \to \infty} \frac {E^{'}(\, N )\, }{N} = 0

\lim_{N \to \infty} \frac {1}{N} \#\{n < N: n = (\, 5i + 1)\, 5^{2j} \, for some  \, i, j \in \mathbb{N} \, with \, j \geq 1 \} = \frac {1}{120}.

A similar argument can be used to establish the asymptotic densities of the other 3 forms of numbers in the theorem.

\Box.

References

[1] Deutsch, E., & Sagan, B. E. (2006). Congruences for Catalan and Motzkin numbers and related sequences. Journal of Number Theory, 117(1), 191–215. http://doi.org/10.1016/j.jnt.2005.06.005