On Wednesday night, accompanied by Tameem, a student of mine, I wandered across campus to attend the “Mathematics in Music” event. I blogged about it earlier. I don’t really want to talk about the event itself in this post. It was a nice enough recital of three pieces. I don’t know why, but the promised “mathematics” was disappointingly virtually non-existent. I’m not exaggerating, I’m afraid.
Keep in mind that it may simply just be my misunderstanding of the intent of the event, but there’s simply next to nothing to report in the way of what was said about mathematical aspects of music. There were plenty of opportunities, but (almost) none were taken. I got out my notebook and pen, all excited at what the presenters might say at various points… and the mathematics never showed up. There were a few extremely elementary remarks about tonal ratios in chords, about scales, keys, and time, and that was it, more or less. This was a bit of a shame, since I suspect that Elaine Chew could have talked at length and with some authority on the matter (given the projects she’s involved in – see e.g. here), but mathematics was almost completely missing in the event – despite the title. I imagine there were what seemed like good reasons for this. I was not party to decisions made behind the scenes, so cannot comment further.
More interestingly on that front was what took place in the minutes leading up to the delayed start of the event. First, although it was a free event, they pointed us to the box office where an attendant printed us two tickets from the computer so that we can show them to someone at the door who wasn’t really looking anyway. Fine. We got into the recital hall, but rather than sitting at the obvious available seats, I suggested that we move to the other side of the room where one can get a better view of the piano keyboard. I’m less than happy when I can’t see what a musician is doing, you see, so I always try to sit with the pianist’s view of the piano. So we did that, and found two seats. While we chatted and looked around us at the growing assembly, I spotted a friend and colleague of mine, the composer Veronika Krausas. She was in the company of someone who she introduced as Brian Head, who is a composer, performer (guitar) and music theorist (a “triple threat”, Veronika joked), also in USC’s Thornton school of music. They were looking for seats and there was one on either side of the two we were sitting in, and so they joined us and we chatted some more.
When the event start was about ten or fifteen minutes late -they were trying to get the reassuringly large crown all seated, they announced- Veronika idly looked at her ticket, pointed out that they were numbered, and wondered if we should have been sitting in the assigned seats. We decided that this was unlikely, but Veronika checked her seat number, then checked the number of the seat she was in. She then wanted to know what number was on my ticket. It matched the one she was sitting in! She was amused by the fact that she was sitting in “my seat”, and I was amused by the fact that of all the seats I could have chosen in the theatre, I chose the one right next to the one written on the ticket that I’d not looked at. We wondered idly what the chances were of someone sitting in the correct seat by accident…
It wouldn’t go away. We began to talk about it – If you gave N people each a random seat assignment written on a piece of paper, but did not allow them to read it, and then let them file into a concert hall with N seats and let them fill it up, what is the probability that at least one person ends up sitting in the seat that matches their ticket?
One of the first thoughts we had was that it was a bit like the “birthday” problem – given N people in a room, what is the probability that at least two of those people share a birthday? In that problem, it turns out that the answer is surprisingly high for even low numbers? Obviously the probability is one (it is certain) if there are more people than there are possible birthdays (365), but you don’t have to be anywhere near that number to be close to high likelihood. In fact, it becomes more likely than not when you pass as few as N=23 people! It rapidly grows in probability with N after that, and by 60 or more people, it is already 99% certain. In case you’re interested, the exact answer is:
[tex]
p(N)=1-\frac{365!}{365^N(365-N)!}\ ,
[/tex]
and there is a nice discussion of the problem on Wikipedia, and on the Skeptical Inquirer’s website, where both articles are talking about it mostly as an antidote to people’s surprise (and willingness to believe some “weirdness” is going on) at finding birthday coincidences.
So was this like the birthday problem? No, I decided, and then proceeded to explain it to Veronika (who’d not heard of it) and then go on to talk about why I thought they were similar, but different, why I expected that the probability would turn out to be surprisingly high, whether it would map to any other well known problem we knew the solution to. One complication that seems to make it notably different from the birthday problem is the fact that once someone sits in a wrong seat, that means that the person who has the ticket for that seat will have to sit in a wrong seat as well – but it need not be the seat of the person who sat in their seat…
What was most amusing to me was the following three markedly different behaviours:
- Veronika proceeded to tap people on the shoulder and ask them what their seat numbers were (on their tickets and on their actual seats)
- Brian got out a pen and started working out a few cases beyond the obvious N=1, N=2, that we worked out together. He did N=3 and decided that the result was surprisingly high already and maybe it was always the case. I declared it was maybe an anomaly of low N and maybe it would settle to a different (but still likely high) number as N grew large… but not as fast as the birthday problem, I guessed. Brian continued computing cases….
- I, on the other hand, useless über-theorist that I am, continued to think and babble about what other problem the problem might map to, whether it scales with N or saturates, what effects determine the one or the other… and so forth. Notably, I did not start to try to solve the problem. My only redemption lies in the fact that I did actually notice these three markedly different behaviours -especially my own- within a few minutes, and joked about it.
Tameem had gone noticeably silent some time ago, I suspect in the face of the twin horrors of three professors so thoroughly and unashamedly enjoying such a conversation in a public place1, and my classic theorist-type behaviour of finding way too much pleasure in discussing the anatomy of a problem before actually working out the solution2.
Well, that’s the story I wanted to tell. There’s no moral. It’s just an amusing (in my opinion) observation. If pushed for a moral, I’d say something about these three different styles of approach all having their usefulness in the right situations in, for example, scientific research. In my field, the best and most successful physicists are the ones who have aspects of all three styles in themselves, and they call on one style or the other at different times, and in different mixtures. Sometimes an entire subfield is dominated by one kind of thinking or another -sometimes out of necessity- and this can have both positive and negative aspects to it. On the positive side, you often learn a huge amount about what’s really going on in a problem if you can connect it to lots of other situations which give rise to the same essential structures (style three above), perhaps after making some initial empirical observations (style one above), rather than just solving it by brute force, perhaps resulting in no wider insight other than finding the solution. (Sometimes, it is the other way around, though.) In my own main research areas, one can argue that style three is what has led to the remarkable breadth and richness of string theory as a collection of powerful tools we’re trying to apply to solving a variety of problems in understanding Nature. On the down side, too much of style three’s thinking (and not enough of style two, and not enough guidance from observations using style one) can lead to not enough development where it is needed. Looking back at string theory, we see that we’ve been blessed with lots of remarkable results in various areas, often in the form of major breakthroughs producing revolutions in thought, but it is not always clear that progress has always taken place in the most urgent directions (of course, we’ll never fully know until we have the benefit of 20/20 hindsight, and we’re still in the middle of things so cannot clearly look back yet), but instead in the directions where we can make progress on these often very hard problems. As a result, we are still trying to come to grips with lots of the most basic and profound questions about the theory – What are the basic degrees of freedom? How is it best formulated? Why on earth does it manage to achieve some of the wonderful things that it does? What is string theory really (certainly not a theory of strings)? Well, I’ve chatted a lot about these things before (and no doubt will again), so I’ll stop here for now.
-cvj
___________________________________________________________________________________
1Yes, it’s ok to enjoy thinking for the sake of it in public. Nobody will call the police!!
2Oh… I have not since thought about the solution to the problem, so feel free to pitch in with your own ideas, combinatorics experts.
Brian. Thanks!!
-cvj
As the offending musician, let me first say how inspired I am by everyone’s interest and nimble mathematical minds. I think this attitude is what I enjoyed most about math.
My approximation was based simply on how quickly the results converged even after only 5 seats – at which point I was running out of extra room on my program to run through the possibilities. The results oscillated and were zeroing in fast on 63%. I couldn’t imagine a reason that the pattern would change. Frankly I was more interested in the various patterns of frustration in the seating arrangements themselves. Chains of duos each seating in each other’s chair; trios doing the same; or everyone sitting exactly one to the right of their proper place, etc.
I do carry the sentence of a B.S. in Mathematics (Univ. Md, many years ago), though what skills I may have had have long faded into the musical ether. Nevertheless, I kept my books, and I consulted Sheldon Ross’ A First Course in Probability after the concert, (certainly outside the rules of this forum I’m sure). In there I found the so-called Matching Problem explained and elegantly proven. Since I’m not sure how to input mathematical notation here, I’ll spare you the details, but the problem was this:
A group of people throw their apparently identical hats into the center of a room. The hats are mixed up, and then each person picks up a hat. What are the chances that no one selects his own hat?
The author actually finds it simpler to work out the odds of at least one man selecting his own hat (basically the question that we posed that night about the tickets), and uses a nifty inductive result stating that the probability of the union of n events equals the sum of the probabilities of these events taken one at a time, minus the sum of the probabilities of the events taken two at a time, plus the sum of the probabilities of the events taken three at a time, and so on. (For the simple case of two events, of course, the probability of the union of two events is the sum of their probabilities minus the probability of their intersection.) To me, this is a tremendous extension of that idea.
From that Ross derives the lovely result that (for our ticket version) the odds of at least one person sitting in the proper seat is: 1 – 1/2! + 1/3! – 1/4! + 1/5! and so on. This converges, of course, to 1 – 1/e = .63212… – even I almost remembered the power series for e to the x… Cheers, Brian
Before writing down the “solution” to the problem, I want to claim that most of my evening has been spent reading Massie’s book on the naval side of the Great War, “Castles of Steel”, and dealing with primitive idempotency equations in 6×6 matrices of products of Pauli algebra projection operators.
That said, one can rework [tex]A_n[/tex] to be in the form:
[tex]A_n = (n-1)!\left(1 + \sum_{k=2}^{n-2}\frac{A_k}{k!}\right)[/tex]
This suggests dividing both sides by n! giving:
[tex]\frac{A_n}{n!} = \frac{1}{n}\left(1 + \sum_{k=2}^{n-2}\frac{A_k}{k!}\right)[/tex]
Replacing [tex]A_n/n![/tex] by [tex]B_n[/tex], one obtains a readily soluble formula:
[tex]B_n = \frac{1}{n}\left(1 + \sum_{k=2}^{n-2}B_k\right)[/tex]
To solve this, define
[tex]B(x) = \sum_{n=0}^{n=\infty}x^n B(x)[/tex]
with suitable choices for B(1) and B(0). This can be solved by the usual methods of combinatorial mathematics. I.e. one obtains a differential equation something like:
[tex]B(x) = \int x \frac{dB}{dx} \;dx + x^2B(x)[/tex]
which one solves for the solution that meets the definition of B. I leave the rest as an exercise for the reader. (I.e. I’ve been working on discrete degrees of freedom QM calculations (or qubits) for 3 years, and now am so unused to continuous degrees of freedom that I probably can’t differentiate sin(x) twice and get the same result.)
I’d think that, given the number of physicists here, the number 63% would enable people to guess the correct answer in the large n limit
Well, now I feel stupid. Should have seen that, given the numerical result. 🙂 Anyhow, ‘derangement’ is a fun word.
Permutations that leave nothing invariant are often called ‘derangements’. A lot of computations along these lines are done in Graham, Knuth and Patashnik’s Concrete Mathematics, a great book, BTW. I’d think that, given the number of physicists here, the number 63% would enable people to guess the correct answer in the large n limit :).
I ran across JCD’s problem a while ago and solved it by deriving a recurrence and solving it. The solution’s simple enough that there must be an easy way to see why it’s true. Anyone know such an argument argument?
For real details on the use of group theory in music, I suggest you check out John Baez’s Week 234 and links therein.
Andy
Interestingly, Brian, on his way out between pieces (he had to leave early) hurriedly whispered “about 63%” to myself and Tameem…. It seems he agrees with your numerical experiments Anon and your formula, Carl Brennan.
Perhaps Brian will tell us how his computation worked.
Excellent…
-cvj
Ooops. extra factor of (k-1)! slipped in. Try:
[tex]A_n = (n-1)! + \sum_{k=2}^{n-2}\frac{(n-1)!}{(n-k)!}\;A_{n-k}[/tex]
A better recursion. Let [tex]A_n[/tex] be the number of permutations of n elements with no fixed points. Then
[tex]A_n = (n-1)! + \sum_{k=2}^{n-2} \frac{(n-1)!(k-1)!}{(n-k)!}A_{n-k}[/tex]
The first term is the number of cycles of length n. The second term is a sum over all the ways that the first element can be in a cycle of length k. It consists of the number of ways of picking that cycle (given that the cycle’s first element is given), multiplied by the number of ways of writing the remaining n-k elements as a permutation with no fixed points.
Oooops. Left off a / in that recursion relation, oh well. Should be
[tex]A_{N,M} = A_{N-M,0}\; N!/(M!\;(N-M)!)[/tex]
Some first few results, 1/1, 1/2, 4/6, 12/24, 76/120, 460/720, counted without the above formula.
Oooooh!!! I love challenges like this. And it’s interesting to see how people approach this. I always assume that there is an easy way of making a calculation, so I just jump right in. Then I make a mistake and have to redo it. So here goes…
The number of ways of sitting N people is N!, the numbe of permutations of N objects. Of these, I wish to count the number of ways that have at least one fixed point. So let [tex]A_{N,M}[/tex] be the number of permutations of N objects that happens to have M fixed points. What is desired is [tex]1 – A_{N,0}/N![/tex]. Naturally, one writes down some recursion relations:
[tex]A_{N,1} = A_{N-1,0} \; N [/tex]
[tex]A_{N,2} = A_{N-2,0} \; N(N-1)/2[/tex]
[tex]A_{N,3} = A_{N-3,0} \; N(N-1)(N-2)/6[/tex]
…
[tex]A_{N,M} = A_{N-M,0} \;N!\;M!\;(N-M)![/tex]
the [tex]A_{N-M,0}[/tex] counts the permutations with no fixed points, the Pascal’s triangle counts the number of ways of putting down the fixed points.
Well, that’s a start.
Taking yet another approach:
Numerically, it seems that for large numbers of seats, the probability that at least one patron has their assigned seat is ~ 65% (+/- 3% or so?). (This was true for both 100 and 1000 seats, at least.)
I’m not proficient enough with combinatorics to find an analytic answer, at least not on a Saturday.
Reminds me of a cute problem I heard once…
A flight has 100 seats, each numbered 1 through 100. There are 100 passengers, each assigned to a specific seat. They board in order of seat number. Instead of necessarily sitting in his assigned seat (#1), the first passenger sits in a seat chosen at random. Each of the following passengers sits in his/her assigned seat, if available; if that seat is taken, he/she sits in a seat chosen at random.
What is the probability that the 100th passenger gets his assigned seat?