Lucas numbers count hi-hat patterns

My friend Molly is a drummer, and posed the following question: in rock music the hihat is usually struck on every eighth-note of a measure, either open or closed, with an open hit typically never followed by another open hit. Given measures containing m eighth notes, how many possible patterns are there?

That is, what is the number d_m of patterns of length m on the alphabet \{x,o\} such that no two o’s appear consecutively? Note that we consider the first and last letters of a give pattern to be consecutive occurrences, since beat patterns usually/often repeat.

Here’s how Molly and I solved this. Let w be a valid pattern of length m. We have the following cases: (1) w = xo\ldots x, (2) w = xx\ldots o, (3) w=xx\ldots x, (4) w = ox\ldots x, or (5) w = xo \ldots o. Note that these cases are mutually exclusive.

In cases (1-3), removing the initial x gives you a valid pattern of length m-1. Moreover, from any valid pattern of length m-1, you can add an x to the beginning to get a valid pattern of length m, so these account for d_{m-1} patterns of length m.

In cases (4-5), removing the initial two letters gives a valid pattern of length m-2.  Moreover, any valid pattern of length m-2 either ends in x, in which cases adding ox gives a pattern of type (4), or in o, in which case adding xo gives a pattern of type (5). Thus, these contribute d_{m-2} many patterns to d_m.

This shows that d_m = d_{m-1} + d_{m-2}, with d_1 = 1 and d_2 = 3 (these initial conditions can be verified by hand.)

That looks familiar…..

…..and it is! This is the defining recurrence of the Lucas numbers!

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s