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.