I've Got Rhythm

Under the given conditions, rhythms can be represented as ordered strings of $\frac{1}{16}$ 's, $\frac{1}{8}$ 's, $\frac{1}{4}$ 's, $\frac{1}{2}$ 's and $1$ 's with a sum of $1$ . The rhythm given in the question would be represented by the string $\left(\frac{1}{4}, \frac{1}{16}, \frac{1}{16}, \frac{1}{8}, \frac{1}{2}\right)$ which has a sum of $1$ .

To simplify the calculations, we note that this is the equivalent of ordered strings of $1$ 's, $2$ 's, $4$ 's, $8$ 's and $16$ 's with a sum of 16. This way, the rhythm given in the question would be represented by the string $(4, 1, 1, 2, 8)$ which has a sum of $16$ .

Two methods came to mind to find the number of such representations, both of which unfortunately required some "grunt" work.

${\color{#FFFFFF} \text{filler}} \\ {\color{#FFFFFF} \text{filler}}$

METHOD 1:

We can use the powers of the polynomial $x^{16} + x^8 + x^4 + x^2 + x$ to determine the number of such representations of fixed length. For example, the number of such strings with seven terms would be the coefficient of $x^{16}$ in $(x^{16} + x^8 + x^4 + x^2 + x)^7$ . Here we'll make use of the Multinomial Theorem .

Unfortunately, we can have strings of any length from $1$ to $16$ , so we'd have to apply the theorem sixteen times. For some of the shortest and longest strings, we can find the number of representations more easily, e.g, it is clear that there is only one string with a single term $(16)$ and one string with two terms $(8, 8)$ ; similarly, there is only one string with sixteen terms, consisting of sixteen $1$ 's, and fifteen strings with fifteen terms, namely all the permutations of one $2$ and fourteen $1$ 's. That still leaves a number of applications of the multinomial theorem; we show one such example.

Length 7:

We seek the coefficient of $x^{16}$ in $(x^{16} + x^8 + x^4 + x^2 + x)^7$ . We can factor out an $x^7$ from the polynomial, so effectively we are looking for the coefficient of $x^{9}$ in $(x^{15} + x^7 + x^3 + x + 1)^7$ . We then note that the $x^{15}$ cannot contribute to this coefficient, so we only need to look at $(x^7 + x^3 + x + 1)^7$ .

The general term of this polynomial will have form

$\dbinom{5}{\alpha_1, \alpha_2, \alpha_3, \alpha_4} \left( x^7 \right)^{\alpha_1} \left( x^3 \right)^{\alpha_2} (x)^{\alpha_3} (1)^{\alpha_4}$

We know that $\alpha_1 + \alpha_2 + \alpha_3 + \alpha_4 = 7$ ; to find the coefficient of $x^{9}$ , we also need $7 \alpha_1 + 3 \alpha_2 + \alpha_3 = 9$ .

We can re-write the second condition as $\alpha_3 = 9 - 7 \alpha_1 - 3 \alpha_2$ ; using this, we re-write the first condition as $\alpha_4 = 6 \alpha_1 + 2 \alpha_2 - 2$ .

This means we have restrictions $7 \alpha_1 + 3 \alpha_2 \le 9$ and $6 \alpha_1 + 2 \alpha_2 \ge 2$ .

Applying those restrictions to the conditions, we find that the four possible sets of values for $(\alpha_1, \alpha_2, \alpha_3, \alpha_4)$ are $(0, 1, 6, 0); (0, 2, 3, 2); (0, 3, 0, 4);$ and $(1, 0, 2, 4)$ .

Then the coefficient of $x^{9}$ in $(x^7 + x^3 + x + 1)^7$ is

$\dbinom{7}{0, 1, 6, 0} + \dbinom{7}{0, 2, 3, 2} + \dbinom{7}{0, 3, 0, 4} + \dbinom{7}{1, 0, 2, 4} = 7 + 210 + 35 + 105 = 357$

and so there are $357$ strings of length $7$ .

Repeating this process for all other possible lengths yields the following table, where $n$ is the length of a string, and $s_n$ the number of strings of length $n$ :

$\begin{array}{|c|c|} \hline \ n \ & s_n \\ \hline 1 & 1 \\ 2 & 1 \\ 3 & 3 \\ 4 & 13 \\ 5 & 75 \\ 6 & 165 \\ 7 & 357 \\ 8 & 645 \\ 9 & 927 \\ 10 & 1095 \\ 11 & 957 \\ 12 & 627 \\ 13 & 299 \\ 14 & 91 \\ 15 & 15 \\ 16 & 1 \\ \hline \end{array}$

Adding these up gives a total of $\boxed{5272}$ rhythms.

${\color{#FFFFFF} \text{filler}} \\ {\color{#FFFFFF} \text{filler}}$

METHOD 2:

Rather than focusing specifically on strings with a sum of $16$ , we consider strings with a sum of $k$ for any $k \in \mathbb{N}$ , and look for a recursive formula for $t_k$ , the number of strings with sum $k$ .

To simplify the reasoning, we first consider $9 \le k \le 15$ . To make a string with sum $k$ , we could take a string with sum $k - 1$ and append a $1$ ; or we could take a string with sum $k - 2$ and append a $2$ ; or we could take a string with sum $k - 4$ and append a $4$ ; or we could take a string with sum $k - 8$ and append an $8$ . This then leads to the recursion $t_k = t_{k-1}+ t_{k-2}+ t_{k-4}+ t_{k-8}$ . We can extend this to lower values of $k$ by using the convention $t_i = 0$ whenever $i \le 0$ . However , we have to be a little more careful when $k$ is a power of $2$ .

Consider strings with a sum of $8$ . We can make such strings by taking strings of length $7$ and appending a $1$ , or taking strings of length $6$ and appending a $2$ , or taking strings of length $4$ and appending a $4$ ; but we can also form one more string by using a single $8$ . Thus whenever $k$ is a power of $2$ , we have to change the recursive formula slightly to $t_k = t_{k-1}+ t_{k-2}+ t_{k-4}+ t_{k-8} + 1$ .

The first few values of $t_k$ are easily found: $t_1 = 1$ ( the only possible string is $(1)$ ); $t_2 = 2$ ( the strings are $(2)$ or $(1, 1)$ ); and $t_3 = 3$ (the strings are $(2, 1), (1, 2)$ and $(1, 1, 1)$ ). After that we apply the recursive formula, being careful to add the extra $1$ whenever $k$ is a power of 2. This yields the following table:

$\begin{array}{|c|c|} \hline \ k \ & t_k \\ \hline 1 & 1 \\ 2 & 2 \\ 3 & 3 \\ 4 & 6 \\ 5 & 10 \\ 6 & 18 \\ 7 & 31 \\ 8 & 56 \\ 9 & 98 \\ 10 & 174 \\ 11 & 306 \\ 12 & 542 \\ 13 & 956 \\ 14 & 1690 \\ 15 & 2983 \\ 16 & 5272 \\ \hline \end{array}$

and again we find that there are a total of $\boxed{5272}$ rhythms.

Let $R_\ell$ be the number of patterns with a total length of $\ell$ sixteenths notes. Each such pattern starts with a note of length $a$ sixteenths, followed by a pattern of length $\ell-a$ , where $a = 1,2,4,8,16$ ; thus we have the recursion $R_\ell = R_{\ell-16} + R_{\ell-8} + R_{\ell-4} + R_{\ell-2} + R_{\ell-1}.$ We set $R_0 = 1$ (there is one trivial valid pattern of zero length), and $R_\ell = 0$ for negative values of $\ell$ .

Once we implement this sequence, the answer to the problem is simply $R_{16}$ .

Dynamic programming implementation

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

#include<stdio.h>

#define length 16
int values[] = { 1,2,4,8,16,0 };

int rhythms[length+1];

int main() {
    rhythms[0] = 1;

    for (int L = 1; L <= length; L++) {
        rhythms[L] = 0;
        for (int i = 0; values[i] != 0; i++) if (L - values[i] >= 0)
            rhythms[L] += rhythms[L - values[i]];

        printf("Length %2d/16 notes: %10d rhythms.\n", L, rhythms[L]);
    }
}

Output:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

Length  1/16 notes:          1 rhythms.
Length  2/16 notes:          2 rhythms.
Length  3/16 notes:          3 rhythms.
Length  4/16 notes:          6 rhythms.
Length  5/16 notes:         10 rhythms.
Length  6/16 notes:         18 rhythms.
Length  7/16 notes:         31 rhythms.
Length  8/16 notes:         56 rhythms.
Length  9/16 notes:         98 rhythms.
Length 10/16 notes:        174 rhythms.
Length 11/16 notes:        306 rhythms.
Length 12/16 notes:        542 rhythms.
Length 13/16 notes:        956 rhythms.
Length 14/16 notes:       1690 rhythms.
Length 15/16 notes:       2983 rhythms.
Length 16/16 notes:       5272 rhythms.

This is sequence A023359 of the OEIS . Hence, the answer is 5272.

The OEIS provides some interesting equivalent problems.

Let $P(n)$ be the number of rhythms occupying $n$ sixteenth notes, and let $P(k,n)$ be the number of rhythms occupying $n$ sixteenth notes that use precisely $k$ notes. Then $P(k,n) \; = \; \sum_{{a+b+c+d+e=k} \atop {a + 2b + 4c + 8d + 16e = n}} \frac{k!}{a! b! c! d! e!}$ is the coefficient of $x^n$ in $(x + x^2 + x^4 + x^8 + x^{16})^k$ . Moreover $P(n) \; = \; \sum_{k \ge 0} P(k,n)$ is the coefficient of $x^n$ in $\sum_{k \ge 0}(x + x^2 + x^4 + x^8 + x^{16})^k$ . Thus we have the generating function $\sum_{n \ge 0}P(n)x^n \; = \; \frac{1}{1 - x - x^2 - x^4 - x^8 - x^{16}}$ and hence $P(n) \; = \; P(n-1) + P(n-2) + P(n-4) + P(n-8) + P(n-16)$ from which it is easy to calculate that $P(16) = \boxed{5272}$ .