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

# 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

# Asymptotic densities of Motzkin numbers modulo 5

The Motzkin numbers are defined by

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

**Theorem 1 (Theorem 5.4 of [1]). **The Motzkin number is divisible by if and only if is one of the following forms

where and .

**Theorem 2: **The asymptotic density of numbers of the first form in theorem 1 is . Numbers of the fourth form also have asymptotic density . The asymptotic density of numbers of the second and third forms in theorem 1 is each.

**Corollary 3: **The asymptotic density of is .

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

**Proof of Theorem 2.**

Firstly consider numbers of the form . As we are interested in asymptotic density it is enough to look at numbers of the form . We have, for fixed ,

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

where the new error term satisfies . Then

.

Since

.

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

**.**

## 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 Catalan numbers modulo 2^k

The Catalan numbers are defined by

Corollary 2 of the previous post established that

This result can be used to show that the asymptotic density of the set is

To this end let for some Then and

So, as mentioned in the previous post

And so

where is a polynomial in of degree with coefficients depending on . Since is fixed and for fixed the second term above is zero in the limit and

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 replaced by any natural number.

# A formula for the number of Catalan numbers divisible by 2^k

## Summary

The Catalan numbers are defined by

This note will use results obtained by Liu and Yeh in [1] to obtain a formula for the number of which are divisible by where

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

and the cofactor of n with respect to be defined by

In addition the function is defined by

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

where and

Then the function 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 . Then

**Theorem 1**:

**Corollary 2**:

**Corollary 3**:

## Proofs.

**Proof of Theorem 1:**

Let . Then

for some arbitrary . Writing in base 2 we have

where there are s 0’s at the end and is arbitrary. So,

where there are s 1’s at the end and is arbitrary. It can be seen that

Since and the possible base 2 representations of n are

with

with

.

.

.

with and 1’s at the end.

Therefore, counting each of these possibilities and using the fact that gives

## Proof of Corollary 2.

The following result appears in [1].

**Theorem 4 (Corollary 4.3 of [1]): **In general, we have In particular, if and only if , and if and only if

Corollary 2 follows from Theorem 1 and Theorem 4 above since

from Theorem 4

from Theorem 1

since

## Proof of Corollary 3.

From Theorem 4,

from Theorem 1.

## Reference

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