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).

# Monthly Archives: November 2016

# Asymptotic density of Motzkin numbers modulo 3

In previous posts we have established the asymptotic densities of the Motzkin numbers modulo and . The main result of this note is that

**Theorem 1. **

.

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

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

if ,

if or ,

otherwise.

We will first examine the nature of the set . We have

**Theorem 3.** The asymptotic density of the set is zero.

**Proof: **

Choose . Then and

as .

** .**

**Proof of Theorem 1.**

Since the asymptotic density of is zero, so is the asymptotic density of the sets for . Therefore Theorem 2 implies that

and the result follows.

** .**

## 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

# Asymptotic densities of certain sets of numbers.

This note will establish formulae for the asymptotic densities in the natural numbers of two sets of numbers. These sets are

and

for integers .

**Theorem 1.** Let with and . Then the asymptotic density of the set is . In addition the asymptotic density of the set is .

**Proof.**

We firstly look at . We have, for fixed ,

where is an error term introduced by not rounding down to the nearest integer. So, letting

,

we have

where the new error term satisfies .

Then

Since and

.

The proof for is very similar. With and defined as above we have for fixed ,

and

and

.

**.**

# Asymptotic density of Motzkin numbers modulo 8

The Motzkin numbers are defined by

where are the Catalan numbers. The following result is established in [1]

**Theorem 1** (Theorem 5.5 of [1]). The nth Motzkin number is even if and only if for and . Moreover, we have

if or

if

where is the number of digit 1’s in the base 2 representation of .

**Remark 2.** The 4 choices for in the above theorem give 4 disjoint sets of numbers .

**Theorem 3**. Each of the 4 disjoint sets defined by the choice of in Theorem 1 has asymptotic density in the natural numbers.

**Proof:** Use the result for the set of Theorem 1 of the post here with .

.

**Corollary 4: **The asymptotic density of

is .

The asymptotic density of

is .

The asymptotic density of each the sets

and is .

**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 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 . Since the asymptotic density of the 2 sets combined is (from Theorems 1 and 3), each of the two sets has asymptotic density of .

## 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