Counting Spanning Trees, A Neat Approach

In my last blog I commented on the relationship between a "parking sequence" problem for n cars and the number of spanning trees of degree n+1. Because I knew so little about the "WHY" of the counting method, I decided to read up a little on the proof for counting spanning trees. It turns out that Cayley [A. Cayley. A theorem on trees. Quart. J. Math., 23:376–378, 1889.] first proved the sequence, but the first combinatorial type proof was by Prufer in 1918 [H. Prufer. Never beweis eines satzes ¨uber permutationen. Arch. Math. Phys. Sci., 27:742–744,1918.] Prufer's method was so interesting, I thought I would share it with interested others who might not have come across it.

Prufer proved that the number of spanning trees for n nodes would be n^n-2 by showing that there is a bijection (For my students, you can think of that as sort of like a one-to-one function relationship) between the set of spanning trees and the number of ordered vectors (don't think that is how he said it) of length n-2 of the integers from one to n. For example, if n = 5, then the number of ordered triples (5-2) you could make with the integers 1 through 5 (allowing repetition) would count the number of spanning trees. To do it, he had to show that each spanning tree would produce a unique ordered n-2 tuple (is that a math word?) and that each such vector would produce a unique spanning tree.... and then he did... and since there are quite easily n choices for each of the n-2 spaces, the number of spanning trees must equal n^n-2.... admit it, that's pretty neat..

For a Spanning tree such as the one below the rules for deriving a code is to take the leaf (vertex with only a single edge to it) with the smallest number, and remove it, and record the vertex it is connected to. In the image, we would remove vertex 1, and write a 5. Now the lowest number on a leaf is 3, and it is connected to vertex 2, so we remove the vertex at 3 and our code is now 5,2. The next lowest leaf is 4, and it is also connected to vertex 2, so our code is now 5,2,2. At this point we have the n-2 terms we need for degree five.. and we can stop... I did some serious head scratching at this point about how he knew that we could ignore the remaining two vertices... but somehow, it all works... you can take the code and presto, you get all the vertices and edges...

Let's make up a code and see what happens... if we write (2,3,3) what spanning tree would it produce. Well, we know the degree of each vertex is one more than the number of times it appears on the code, so 1, 4, and 5 have degree 1 (they are leaves) and 2 has degree 2. Vertex 3 has degree 3, since it shows up 2 times in the code. We begin by remembering that the lowest numbered leaf (one) was removed first, so one must be connected to the vertex named first in our code, 2. Our next smallest leaf is vertex 4, so it must be connected to the vertex named second in the code, vertex 3. Finally we have vertex 5 as a leaf, and so we must have it connected to vertex 3 as well. Finally, we need to remember that the numbers in the code were connected to each other (hence the additional degree) and we should connect vertices 2 and 3.




But what if we changed the code to (3,2,3)? Same numbers, different order... We still have the same three leaves at 1, 4, and 5, but now 1 is connected to vertex 3; 4 connected to 2; and 5 would be connected to three.

What I haven't figured out yet (any help out there??) is how to find a bijection between the Prufer codes and the parking problem. More to learn....

Another Interesting Answer

Here are two interesting problems, the second is a little more abstract, but bare with me... there is a purpose...

Suppose there are n parking spaces in a row along a one way street, and n people are driving into town, each with a most preferred spot in the row of spaces. Each of the n people adopts the plan that they will drive along the line until they come to their preferred space. If it is open, they take it, and if not, they continue driving and will take the next available spot. For instance if n=2 parking spaces, then the two drivers would find a parking space if both wanted the first spot, or they both wanted different spots; but one of them is out of luck if they both preferred the last spot, since the one who got there second is out of parking places. Thus for n=2, there are 3 possible solutions out of 2^2 = 4 possible situations. So here are the easy questions, find the number of possible solutions for n=3 and 4, and their associated probabilities of success.
And for the clever people, generalize for n.

If you found that either too hard, too easy, or just want to read on, here is a second problem. For those who have never studied graph theory, or don't remember the terms, a brief introduction. A complete graph with n nodes is called the k_n graph. For n = 4 and 5 the complete graphs look like the ones shown below.




Now a spanning Tree is a graph with N vertices but no complete circuits. You can get from any vertex to any other, but only by one path. Here is an example of a tree with six labeled vertices. Finally, we can give the question... For a complete graph of 3 vertices, 4 vertices, or n vertices, how many different spanning trees are possible?

The amazing result is that the two problems seem to be exactly the same, at least they produce the same sequence. The number of solutions for the parking problem is 1, 3, 16, 125, ... (N+1)^(n-1)... For the spanning trees, if we start with a graph of 2 points, there is only one tree. For three points there can be three different trees, and for four... yeah..16 . The image below shows all 16 of them as depicted by Wolfram Mathworld.. the sequence is the same but the index is off by one, so we get 1, 3, 16, 125, ... (n)^(n-2)... Ok, here is the real question for this blog... why are they the same...

Ok, one more curiously beautiful detail about this problem.... the probability of success for the n parking cars at the top has a limit of e/(n+1) as n approaches infinity. I love how often e pops up in these "sorting" type problems. 

Merry Christmas

Stole this off John's Post at The Endeavour, Well worth repeating

Exploring an Isoperimetric Theme

Recently we have been doing maxima/minima applications in calculus. By the time they get her most of them know that when they maximize the area of a rectangle with perimeter constraints, they get a square. In Pre-calc we do some basic problems with 2 adjacent pens, a single pen against a wall or river, and all the similar cases. I have written about the generalizations of some of these here, and here. The problem of two adjacent congruent pens is (or should be) easy for a calculus or precalc student. It turns out that the maximum occurs when the total width is one-fourth the perimeter and the height is one-sixth the perimeter, for a maximum area of one twenty-fourth of the perimeter value (in square units, of course). If you extend that to even more congruent rectangular pens placed end to end it turns out that the width stays the same?

If you extend this, as many teachers do, to a shape like this one, it starts to get interesting to the more observant student. The height is now one-eighth of the total , and the width is one-sixth of the perimeter. Even slow students can figure out that the area of the total turns out to be one forty-eighth of the value of the perimeter. Some will even generalize the area of an array of mxn congruent pens to be the perimeter squared divided by [4(m+1)(n+1))].... but it seems to take forever for some one to finally realize that in all these problems, whether there was one rectangle, or one with one side adjacent to a river or barn, or rows of rectangles... there is one invariant...

Theorem one for rectangular arrays of congruent rectangular pens "The amount of fence going right to left is the same as the amount going up and down." If you want to maximize a rectangular array with five rows of three pens in each row, we will need 24 lines of fence, four going vertically, six going horizontally. Use half the fencing to make the four vertical fences, and the other half to make the other six going horizontally. (Prove..... dear reader) ..

I always thought this fifty-fifty use of fencing was a cute mathematical "teacher trick" but I have recently come to believe there is something deeper at work. I played around recently with this problem but loosened the constraints on the pens to be just equal area rectangles rather than congruent. This offered some nice areas to explore. Which would be better, three congruent pens in a row, or two pens with a third beneath... like so. The three adjacent pens turn out to have a max area when the width was p/4 (where p is the perimeter) and the height was p/8, giving a maximum area of p²/32... and as before, that mean that half the perimeter was used for the vertical sections, and half for the horizontal sections..and for the three non-congruent sections with equal area the width was p/6, and the length was 3P/16, giving a max area of....wait, that's also p²/32. (Ok, I hadn't expected that)... but when I checked the dimensions, it turns out that the horizontal sections use up exactly half the perimeter, and the vertical sections the other half in both cases.... hmmm...

Ok, but every kid knows that the area is maximized when the rectangle is closest to a square... so what if we just put three squares arranged as shown below and didn't require that the whole assembly forms a rectangle... I thought that would probably be even more area.. It turns out that it isn't, The equal distribution of left and right still works out, but the total area is only 3p²/100 or about 96% of the other shapes. (ok, I wasn't ready for that)...

So, I decided to move up to five pens... I passed over four absolutely sure that the division into four equal squares in a two by two array would be the most efficient, but five offered several variations, five in a row; two rows of two with a single in the third row, or three in one row and two in another... The five congruent squares in a row gave a max area of p²/48, but the set up with three pens in one row and two in another gave a slightly larger area of 5p²/216 or p²/43.2. The 2,2,1 set up (shown below) gave not quite the same area.. This set up gave a max area of p²/44.8.

From all of this I have a formed a totally unproven conjecture about the maximum area when n equal area rectangular pens are set out in a rectangular boundary with a given amount of fencing.
The Theorem One above for congruent rectangles seems to be a stronger property than I suspected, and is applicable to all equal area pens in a rectangular boundary, And the conjecture is that when the number of pens, n, is between x²-x and x²+x, the maximum area will be found when there are x-rows of pens and all of the pens have either x-1, x, or x+1 pens in the row.

The number of pens in any row will never differ by more than one from any other row. For values of n that are perfect squares or pronic (product of consecutive integers), the number of pens in each row will be the same. When n > x² there will n-x² rows that have x+1 pens, and the remaining rows will all have x pens. Similarly, if n is less than x² there will be x² - n rows that have x-1 pens and the remaining rows will have x pens each. As an example, if n= 23, then x=5 since 5²-5 is less than 23<5²+5. And for 23 pens there will be five rows with x=five pens in three of them, and x-1=four pens in two of them.

I also have discovered that the theorem about equal lengths of fencing horizontally and vertically seems to be more important as a "rule of thumb" for maximizing than is equal sides. For example if five squares are set out as efficiently as possible (four in a square with one attached to a side), the area will be p² / 45 with 8/15 of the perimeter going one way(say horizontally) and 7/15 going the other. If we change the squares to rectangles with each having a height of p/16 and a width of p/14 the area is p²/44.8.. an improvement of about 1/2 %....
Even if you go to six pens (where there is no lost perimeter enclosing the odd pen), putting two rows of three squares gave me an area of P² / (48 1/3) but using the equal division of fencing gives the very slightly improved maximum of p²/48.

I can't explain why, but the equal division of fencing theorem is stronger than I first suspected, and if someone out there can shed more light on it than my feeble exploration, please do.

I haven't had time to expand the formula for the max area of all n when a rectangle is divided into congruent area rectangles, (not too difficult, I think).. but for square or pronic numbers of pens, it seems the max area will always be p²/(4 (x+1)(y+1)) where xy=n. As a limit as n approaches infinity, it seems the max area for rectangles divided into n equal area rectangles approaches