String 'Em Along

Turtles All the Way Down

I'm Over Counting

Elementary, My Dear

Potpourri

A string of adjacent graph vertices that has each vertex exactly once, except the first is the last.

What is a Hamiltonian cycle?

The terms of this type of sequence are a function of earlier terms.

What is a recursive sequence?

The number of subsets of {0,1,...,9} that are not size 4.

What is

2^(10) - ( (10) ,(4) )

?Two sets with the same number of elements have this type of function between them.

What is a bijection? (invertible/one-to-one correspondence)

A partial order has these three properties.

What are reflexivity, transitivity, and antisymmetry?

These binary strings biject to non-negative integer solutions to

a+b+c+d+e = 148

What are strings with 5 ones and 148 zeros ending in a 1?

Inductive proofs are often phrased as having these three parts.

What are the base case, the inductive hypothesis, and the inductive step?

The number of faces and vertices of a planar graph are this many more than the number of edges.

What is 2?

Dilworth says the fewest number of chains needed to partition the elements of a poset is also this number.

What is the width or the size of the largest antichain?

Charles Babbage and Ada Lovelace are best remembered for their work on this unbuilt thinking machine.

What is the analytic engine?

The number of strings on alphabet {2,7,9} whose digits sum to n have this generating function.

What is

1/(1-(x^2+x^7+x^9))?

This recurrence relation has generating function

f(x) = ( a_0 + (a_1 - 3a_0) x ) / ( 1 - 3x + 2x^2 )

What is

a_(n+2) = 3a_(n+1) - 2a_(n)

?

Including and excluding functions gives this formula for the number of surjections

20 ->18.

What is

sum_{k=0}^18 (-1)^k ((18),(k)) (18-k)^(20)?

These are the elements of a maximal matching in this bipartite graph made by connecting the words SI, IS, AT, AS, SIM to the letters they contain.

What are {SI,S} {IS,I} {AT,T} {AS,A} and {SIM,M} ?

The symmetry group property that a set of derangements fails to have.

What is closure under composition?

(There's also no identity.)

Prufer says the trees with vertex set V biject to these strings.

What are strings on V of length |V|-2?

Eig-ad! A linearly recursive sequence is always big O of this characteristic quantity.

What is

O( n^(m-1) lambda^n)

where

lambda

is the largest eigenvalue and has multiplicity m.

The least weight closed covering walk on the following graph is this much more than the total weight of the graph.

What is 5?

Kuratowski says a graph is planar if and only if its set of subgraphs has no element homeomorphic to this.

What is the complete graph K_5 or the complete bipartite graph K_3,3?

The 26 letter English alphabet has this many partitions.

What is

B_{26} = \sum_{k=1}^{26} {(26),(k):}}?

This function of n is the number of decimal strings of length n where an even digit is never followed by an odd digit.

What is

a_n = (1+n)5^n

?It satisfies a_0 = 1 and a_1 = 10 and the recurrence relation

a_n = 10 a_{n-1}-25a_{n-2}

This is a proof that every tree is 2-colorable.

What is

"As a base case a single vertex is 2-colorable. Suppose that every tree with k vertices is 2-colorable. Let T be a tree with k+1 vertices. Then T must have a degree 1 vertex v attached to some vertex u. By the inductive hypothesis deleting edge {u,v} and v from T gives a 2-colorable graph. Then coloring v the color u is not colored gives a 2-coloring of T."

?

The total number of length 10 strings on {a,b,c,d} is more than this number of strings on {a,b,c,d} considered up to cyclic permutation. ( Cyclic permutation: abc ~ bca ~ cba )

What is

( 4^10 + 4 * 4^5 + 4^2 + 4*4 ) / 10?

The color set of any proper coloring of this graph would need at least this many elements. (Proper means no adjacent vertices are colored the same color.)

What is 4?

Summing the slope one diagonals of Pascal's triangle would result in these numbers.

What are the Fibonacci numbers?