String 'Em Along

Turtles All the Way Down

I'm Over Counting

Elementary, My Dear

Potpourri

100

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

What is a Hamiltonian cycle?

100

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

What is a recursive sequence?

100

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

What is

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

?100

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

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

100

A partial order has these three properties.

What are reflexivity, transitivity, and antisymmetry?

200

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?

200

Inductive proofs are often phrased as having these three parts.

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

200

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

What is 2?

200

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?

200

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

What is the analytic engine?

300

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))?

300

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)

?

300

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)?

300

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} ?

300

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

What is closure under composition?

(There's also no identity.)

400

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

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

400

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.

400

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

What is 5?

400

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?

400

The 26 letter English alphabet has this many partitions.

What is

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

500

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}

500

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."

?

500

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?

500

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?

500

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

What are the Fibonacci numbers?