There is a striking similarity between the songs “Music of Goodbye” from John Barry’s soundtrack to “Out of Africa” and Andrew Lloyd Webber’s “Music of the Night” from “Phantom of the Opera”. Barry’s soundtrack was released in 1985 and “Phantom of the Opera” was first performed in 1986 though the song may have been written earlier. I have not been able to find any evidence of legal action related to the similarity. However, there is a possibility that both composers used a melody from Puccini’s 1910 opera “La fanciulla del West” as the basis for their songs. The following is from Wikipedia’s entry on “Phantom of the Opera”:

Due to similarities between the song and a recurring melody in Giacomo Puccini’s 1910 opera La fanciulla del West (The Girl of the Golden West), the Puccini estate filed lawsuit against Webber, accusing him of plagiarism. An agreement was settled out of court and details were not released to the public.

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

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

This note will establish formulae for the asymptotic densities in the natural numbers of two sets of numbers.  These sets are $S_{1}(\, q, r, s, t )\, = \{ (\, qi + r )\, q^{sj + t} : i, j \in \mathbb{N} \} \quad$

and

$S_{2}(\, q, r, s, t )\, = \{ (\, qi + r )\, q^{sj + t} : i, j \in \mathbb{N}, j > 0 \}$

for integers $\quad q, r, s, t$.

Theorem 1. Let $\quad q, r, s, t \in \mathbb{Z} \quad$ with $\quad q, r, s > 0 \quad$ and $\quad 0 < r < q \quad$. Then the asymptotic density of the set $S_{1} \quad$ is $\quad (\, q^{t + 1 - s} (\, q^{s} - 1 )\, )\, ^{-1} \quad$. In addition the asymptotic density of the set $\, S_{2} \,$ is $\, (\, q^{t + 1} (\, q^{s} - 1 )\, )\, ^{-1}$.

Proof.

We firstly look at $S_{1}$. We have, for fixed $j \geq 0$,

$\#\{ i \geq 0: (\, qi + r)\, q^{sj + t} \leq N \} = \frac {N}{q^{qj+t+1}} - \frac {r}{q} - E(\, j, N, q, r, s, t )\,$

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

$U(N, s, t) =: \quad \lfloor \frac {\log_q (\, N )\, - t - 1}{s} \rfloor \quad \,$,

we have

$\#\{n < N: n = (\, qi + r)\, q^{sj + t} \, for some \, i, j \in \mathbb{N} \}$

$= \sum_{j \geq 0} (\, \frac {N}{q^{sj + t + 1}} - \frac {r}{q} - E(\, j, N, q, r, s, t )\, )\, = \sum_{j = 0}^{U} (\, \frac {N}{q^{sj+t + 1}} - \frac {r}{q} - E(\, j, N, q, r, s, t )\, )\,$

$= \frac {N}{q^{t + 1} } \sum_{j = 0}^{U} (\, \frac {1}{q^{s}} )\,^{j} - E^{'}(\, N, q, r, s, t )\,$

where the new error term $E^{'} (\, N, q, r, s, t )\,$ satisfies $0 < E^{'} (\, N, q, r, s, t )\, < 2(\, U + 1 )\,$.

Then

$\#\{n < N: n = (\, qi + r)\, q^{sj + t} \, for some \, i, j \in \mathbb{N} \}$

$= (\, \frac {N}{q^{t+1}} )\, (\, 1 - (\, \frac {1}{q^{s}} )\, ^{U + 1} )\, (\, 1 - \frac {1}{q^{s} } )\, ^{-1} - E^{'}$

Since $\lim_{N \to \infty} \frac {E^{'}(\, N, q, r, s, t )\, }{N} = 0$ and $\lim_{N \to \infty} \frac {1}{N} (\, \frac {1}{q^{s} } )\, ^{U + 1} = 0$

$\lim_{N \to \infty} \frac {1}{N} \#\{n < N: n = (\, qi + r)\, q^{sj + t} \, for some \, i, j \in \mathbb{N} \}$

$= (\, q^{t + 1 - s} (\, q^{s} - 1 )\,)\, ^{-1}$.

The proof for $S_{2}$ is very similar. With $E, E^{'}$ and $U$ defined as above we have for fixed $j \geq 1$,

$\#\{ i \geq 0: (\, qi + r)\, q^{sj + t} \leq N \} = \frac {N}{q^{qj+t+1}} - \frac {r}{q} - E(\, j, N, q, r, s, t )\,$

and

$\#\{n < N: n = (\, qi + r)\, q^{sj + t} \, for some \, i, j \in \mathbb{N} \, with \, j \geq 1 \}$

$= \sum_{j \geq 1} (\, \frac {N}{q^{sj + t + 1}} - \frac {r}{q} - E(\, j, N, q, r, s, t )\, )\, = \sum_{j = 1}^{U} (\, \frac {N}{q^{sj+t + 1}} - \frac {r}{q} - E(\, j, N, q, r, s, t )\, )\,$

$= \frac {N}{q^{t + 1 + s} } \sum_{j = 0}^{U - 1} (\, \frac {1}{q^{s}} )\,^{j} - E^{'}(\, N, q, r, s, t )\,$

$= (\, \frac {N}{q^{t+1+s}} )\, (\, 1 - (\, \frac {1}{q^{s}} )\, ^{U} )\, (\, 1 - \frac {1}{q^{s} } )\, ^{-1} - E^{'}$

and

$\lim_{N \to \infty} \frac {1}{N} \#\{n < N: n = (\, qi + r)\, q^{sj + t} \, for some \, i, j \in \mathbb{N} \, with \, j \geq 1 \}$

$= (\, q^{t + 1 } (\, q^{s} - 1 )\,)\, ^{-1}$.

$\Box$.

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

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.