indessed roscivs

I’ve always been fascinated with combinatorics. For those of you not familiar with the field, it’s part of the study of discrete mathematics, which is in essence the part of math that’s particularly interesting to computer scientists. (My apologies to any mathematicians who just cringed.) Combinatorics in particular concerns itself with trying to figure out how various combinations and permutations of items work.

For example, let’s say we have three musical notes: G, C, and F^#. Given only those three notes, how many unique series of notes can you have? It depends on how long the series of notes can be, first of all. Let’s start out looking at two-note series: GG, GC, GF^#, CG, CC, CF^#, F^#G, F^#C, and F^#F^#. That’s a total of 9 possible combinations.

How many possible three-note series are there? Or ten-note series? Or thousand-note series? It would take a while to list all of them, but combinatorics gives us a really simple formula for figuring out the answer:

where n is the number of notes to choose from, and r is the length of the series. So there can be 3² two-note series of three notes—a total of 9 possible combinations, just as we showed before. There are 27 (3³) possible three-note series, 59,049 (3¹⁰) possible ten-note series, and a whole lot of possible thousand-note series (3¹⁰⁰⁰). And the formula is just as easy if you use all seven notes in a scale (7³ possible three-note series) or all twelve semitones (12³ possible three-note series).

But what if you want to exclude repeats? In other words, how many permutations of a given set of notes can you create? To use our previous example of two-note series of three notes, we could have: GC, GF^#, CG, CF^#, F^#G, and F^#C. Six possible permutations. The formula for this situation is a little tricker, because it involves the “factorial” mathematical operator, represented as an exclamation point. 2-factorial, or 2!, is equal to 2×1. 3! is equal to 3×2×1, 4! is equal to 4×3×2×1, and so on. The mathematical formula for permutations excluding repeats is:

or, for our above scenario of two-note series of three notes (without repeats), 3!/(3-2)!, which becomes 6/1, equalling six possible permutations. Again, you can plug in whatever numbers you like into this formula to get the answer without having to enumerate all the possible permutations yourself. If you have a choice of seven notes in a scale, and want to create a four-note series with no repetitions, you have 7!/3!, or 840 different options to choose from.

One more before I end—what if order doesn’t matter? For example, what if you’re choosing Jelly Bellies to mix. There are fifty official flavors, and let’s say we want to mix three different jelly beans together to get some unique combination. It doesn’t matter whether we pick licorice+lemon+cinnamon or cinnamon+licorice+lemon, it ends up being the same thing. The formula for this is:

So the answer to our Jelly Belly question is 50!/3!x47!, or 19,600 possible combinations. The majority of them, most likely, quite disgusting.

This entry was posted on Tuesday, March 20th, 2007 at 8:02 pm and is filed under Uncategorized. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.