All entries for Wednesday 16 November 2011

November 16, 2011

Combinatorics – a misread question (graph theory)

While doing combinatorics questions, we come across interesting results by doing the wrong question, whether as a stepping stone (we hope!) to the correct answer, or merely completely misreading the question. Below is one that came up last week:

Find the number of labelled (n-2)-regular graphs with n vertices.
(a k-regular graph is one in which all vertices have degree k)

Clearly for n odd or less than 2 there are no such graphs. The case for even n greater than or equal to 2 runs as follows:

Note that if a vertex has degree (n-2), it is connected to every vertex apart from one other, which is necessarily connected to every vertex bar the first. Thus, we can ‘pair off’ vertices in this manner, obtaining {n \choose 2} {n-2 \choose 2} {n-4 \choose 2}  \cdots = \frac{n!}{(n-2)!2!} \frac{(n-2)!}{(n-4)!2!} \frac{(n-4)!}{(n-6)!2!} \cdots = \frac{n!}{2^{\frac{n}{2}}}.

We then (thanks Nick!) note that order of pairs doesn’t matter, so we need to divide by the number of ways of choosing the \frac{n}{2} pairs—\frac{n}{2}! – giving us \frac{n!}{2^{\frac{n}{2}}\frac{n}{2}!}

This gives the same result as a different way of thinking about it—(n-1)(n-3)(n-5) \cdots = \sum_{k=1}^{\frac{n}{2}} (n-2k+1)

A4: Last entry: time is up.

Follow-up to A4: Memory and Confusion from Midgley, Christopher - Pointless twaddle and meaningless diatribes

Tutor was Ceri Marriott.

The listening part went well – I can now pay attention and get something out of listening to people talk. Focusing I can even remember them standing and saying it, which is rather nice. It was surprising that something so simple took so long.

The colour/sound part of memory was abandoned – I simply couldn’t get it to work. I’ve moved on to thinking about position but it’s likely that I remember best based on something completely different I’m not yet aware of. I can remember whether we talked about something close to something else, or if there’s a vague link between them (say, the IVT and MVT are both frequently used in Analysis, so that’s a ‘link’ of sorts), but not in subjects where we do incredibly similar things for a long time (e.g. Math Stats); this positioning does help me to remember the material itself.

I find it interesting that the task I thought would be harder turned out to be the only one I actually accomplished :)

November 2011

Mo Tu We Th Fr Sa Su
Oct |  Today  | Dec
   1 2 3 4 5 6
7 8 9 10 11 12 13
14 15 16 17 18 19 20
21 22 23 24 25 26 27
28 29 30            

Search this blog


Most recent comments

  • Nice proof! Does this mean you're going to specialize in analysis and differential equations next ye… by Nick on this entry
  • Hi Chris, It was most interesting to read your various reflections – thank you for sharing them. I'm… by Ceri Marriott on this entry
  • Feel free. Chris by Christopher Midgley on this entry
  • Hi Chris This is an honest final entry for the WSPA. Im glad that you have found the WSPA journey wo… by Samena Rashid on this entry
  • Knowing the maximum price you would be comfortable with paying for X is extremely useful for compani… by Nick on this entry

Blog archive

Not signed in
Sign in

Powered by BlogBuilder