Kevin Gomez

Kevin Gomez

he/him

Research Scientist

Prover Sequence

1 minute read

Published:

Recall that a tree is an undirected network with no cycles or loops such that any node is reachable from any other. A labeled tree is one where we’ve given each node a unique label, by convention a number between $1$ and $n$ for $n$ the number of nodes in the tree. Two labeled trees are the same if they can be drawn identically, with the same labels and connections.

(More technically, we’re considering trees up to isomorphism, but fret not if you don’t know that term.)

Let $T(n)$ be the number of labeled trees with $n$ nodes. Clearly $T(1) = 1$ (there’s just one node labeled $1$) and $T(2) = 1$ (there’s two nodes, labeled $1$ and $2$, connected to each other; two nodes with no connection is not a tree).

  1. Compute $T(3)$.

  2. Compute $T(4)$ (note: tricky).

  3. Define the “prover sequence” for a tree in the following way (the name will make sense shortly):
    • Take the node with only one neighbor (called a leaf) which has the smallest label, remove it from the tree, and write down the label of its neighbor.
    • Repeat until there are only two nodes left.

  4. Given a prover sequence, describe a process for recovering the labeled tree that made it.

  5. Show that there is a one-to-one correspondence between labeled trees and prover sequences.

  6. How many possible prover sequences are there for labeled trees with $n$ nodes?

  7. What do prover sequences then “prove” about $T(n)$?

You May Also Enjoy

Teensy Problems: Alien Astronomer (Part 2)

1 minute read

Published:

Thanks to you, Gryxlb now has a satisfactory picture of what that malfunctioning machine got up to, and is ready to prepare their analysis of the newly-coined Orion Object cOunting interceptiOn (OOOO) for the wider scientific community on Xorgmathrx. They copy the raw interception data from a (functioning) computer onto a USB drive (it’s not called “universal serial bus” for nothing) to take to the Tbibthglx University Library, whose workstations have the analysis software Gryxlb likes to use.

Teensy Problems: Alien Astronomer (Part 1)

1 minute read

Published:

Gryxlb, an alien radio astronomer on planet Xorgmathrx, has started intercepting a peculiarly structured signal. There’s a stream of pulses originating from the Orion Arm counting up from zero in binary; it must be a deliberate message from an intelligent civilization! The telescope’s computers are recording the pulses, but one is malfunctioning: instead of writing the pulses into memory, each memory slot is the bitwise exclusive or (xor) of the incoming pulse and the previous memory slot.

Teensy Problems: Kaprekar Numbers

1 minute read

Published:

Dr. Kaprekar has stumbled upon an interesting class of numbers. A number $N$ is called a “Kaprekar number” if $N^2$, written in base $10$, can be split into two parts, $A$ and $B$, such that $N = A + B$. Here are some examples:

   9² =       81 →   8 +     1 =    9
  45² =     2025 →  20 +    25 =   45
4879² = 23804641 → 238 + 04641 = 4879

Notice that the parts do not have to be equal in size and can include leading zeros; the only restriction is that neither part is totally zero. Let’s help Dr. Kaprekar understand more about his numbers.

Teensy Problems: Sum of Factorials

1 minute read

Published:

Let $\mathrm{sf}(n)$ be the sum-of-factorials function: $0! + 1! + \dots + n!$. Its first few values are $1$, $2$, $4$, $10$, $34$, ….