Graduate Seminar

Brendan Sullivan
Carnegie Mellon University
Title: Avoiding consecutive identical digits in binary strings

Abstract: In this presentation, I will discuss a particularly simple (to state, anyway) counting problem. Namely,

Given $n$, $k\in \mathbb{N}$, how many binary $n$-tuples do *not* have $k$ consecutive identical positions?

This question arose as a natural generalization of a math puzzle, and a complete solution has eluded me for weeks. I have learned several facts about the problem, but all attempts to find a closed formula have fallen short. I hope to present several approaches to the problem I have made, along with the help of friends. In so doing, I will remind/teach you about some interesting areas of mathematics and, particularly, about *generating functions*, where combinatorics and analysis meet.

Date: Tuesday, September 11, 2012
Time: 5:30 pm
Location: Wean Hall 8220
Submitted by:  Brian Kell