Matpic
mathematics, in pictures
Theme

Counting the same thing twice — page 2

One collection, counted by two different methods, and an identity that falls out because both answers have to agree. The proof is the pair of counts.
8 − 12 + 6 = 27 edges on the corner tree · 5 on the face treea spanning tree of the 8 corners uses 7 edges; what isleft over joins the 6 faces into a tree and uses 57 + 5 = 12, which is V − E + F = 2 with the termsmoved about — and it holds for whichever vertex thetree is grown from Topology

Two trees, and every edge in exactly one of them

Euler's formula is usually proved by deleting things until nothing is left. There is a better argument that deletes nothing — a tree through the corners and a tree through the faces, which between them use every edge once and can therefore be counted.

 90°cornersgap eachtotaltetrahedron180°720°cube90°720°octahedron120°720°dodecahedron36°720°icosahedron60°720°3 squares at a corner of the cube come to 270°, leaving a gap of 90°8 corners × 90° = 720°, and every one of the five gives the same total Topology

Seven hundred and twenty degrees of gap

Unfold the faces around any corner of a solid and they do not close up. The gap left over is different at every corner and on every solid, and the gaps always add to two full turns.

 024681012-4-2024steps takenpositionstart, 2mirror, −2first touchof the 792 paths from 2 to 4 in 12 steps, 220 touch the axisand 220 is exactly the number of paths from −2 to 4, which is what folding turns them into Probability

The path folded at its first touch

Counting the walks that touch a line looks like a question about a walk's whole history. Fold each one where it first touches, and it becomes a question about where walks end up — which is a binomial coefficient, and is already known.

 −ππ-11× sin 1xarea = 4.000coefficient 1.273−ππ-11× sin 2xarea = 0no such harmonic in it−ππ-11× sin 3xarea = 1.333coefficient 0.424−ππ-11× sin 4xarea = 0no such harmonic in iteach panel is the target multiplied by one harmonic, with the area above the axis in one colour and the area below in the otheragainst its own harmonic the two do not cancel; against any other they cancel exactly, which is what makes one coefficient extractable without disturbing the rest Analysis

Where the coefficients come from

The recipe for a square wave has a four over pi in front and a one over three on the second term, and the first rung of this ladder used them without saying where they came from. They come from multiplying by one harmonic and taking the area.

 the graphone edge deletedthe same edge contractedcoloursthe graphdeletedcontracted0000100020223618124488436518026080a four-cycle with one chord: every count is made by trying all k^4 assignments and checking each onethe graph needs 3 colours, and below that the count is not small — it is zero, which is what a countingversion of the question says instead of yes or no Discrete

Counting the colourings

Asking whether a graph can be coloured with four colours gives a yes or a no. Asking how many ways there are gives a polynomial — and the polynomial answers the first question, and several others nobody asked.

All themes