# Counting ballots with crystals

In my graduate Advanced Combinatorics class last semester, I covered the combinatorics of crystal base theory. One of the concepts that came up in this context was ballot sequences, which are motivated by the following elementary problem about voting:

Suppose two candidates, A and B, are running for local office. There are 100 voters in the town, 50 of whom plan to vote for candidate A and 50 of whom plan to vote for candidate B. The 100 voters line up in a random order at the voting booth and cast their ballots one at a time, and the votes are counted real-time as they come in with the tally displayed for all to see. What is the probability that B is never ahead of A in the tally?

We’ll provide a solution to this classical problem on page 2 of this post. For now, this motivates the notion of a ballot sequence in two letters, which is a sequence of A’s and B’s such that, as the word is read from left to right, the number of A’s that have been read so far is always at least as large as the number of B’s.

For instance, the sequence AABABB is ballot, because as we read from left to right we get the words A, AA, AAB, AABA, AABAB, and AABABB, each of which has at least as many A’s as B’s. On the other hand, the sequence ABBAAB is not, because after reading the first three letters ABB, there are more B’s than A’s.

If we replace the A’s by $1$’s and $B$’s by $2$’s and reverse the words, we obtain the notion of a ballot sequence in $1$’s and $2$’s described in our previous post on crystals. In particular, we say a sequence of $1$’s and $2$’s is ballot if, when we read the word from right to left, there are at least as many $1$’s as $2$’s at each step. So $221211$ and $211111$ are both ballot, but $111112$ and $211221$ are not.

## Enumerating all ballot sequences

When I introduced this notion in class, one of my students asked the following.

How many total ballot sequences of $1$’s and $2$’s are there of length $n$?

Now, as in the first question about voting above, the more common version of this type of question is to fix the number of $1$’s and $2$’s in the sequence (the “content” of the word) and ask how many ballot sequences have exactly that many $1$’s and $2$’s. But in this case, the question was asked with no fixed content, resulting in a sum of Littlewood-Richardson coefficients (or, in voting terms, where the voters have not yet decided who they will vote for when they line up, and may vote for either candidate).

To start, let’s try some examples. For $n=0$, there is only one ballot sequence, namely the empty sequence. For $n=1$, there is also just one: $1$. For $n=2$, there are two: $11$ and $21$. For $n=3$, there are three: $111$, $121$, $211$. For $n=4$, there are six: $1111$, $2111$, $1211$, $1121$, $2211$, $2121$. And for $n=5$, there are ten: $$11111, 21111, 12111, 11211, 11121, 22111, 21211, 21121, 12211, 12121$$

The sequence of answers, $1,1,2,3,6,10,\ldots$, so far agrees with the “middle elements” of the rows of Pascal’s triangle:

$$\begin{array}{ccccccccccc} & & & & & \color{red}1 & & & & & \\ &&&&\color{red} 1&&1 &&&& \\ &&&1&&\color{red} 2&&1&&& \\ &&1&&\color{red} 3&&3&&1&& \\ &1&&4&&\color{red} 6&&4&&1& \\ 1&&5&&{\color{red}{10}}&&10&&5&&1 \end{array}$$

More formally, it appears that the number of ballot sequences of $1$’s and $2$’s of length $2n$ is $\binom{2n}{n}$, and the number of length $2n+1$ is $\binom{2n+1}{n}$.

Now, it is possible to prove this formula holds using a somewhat complicated recursive argument, which we will also illustrate on page 2 of this post. But there is also very elegant solution using crystal operators.

## Solution using crystals

Let’s recall the definition of the crystal operator $F_1$ on words of $1$’s and $2$’s. Given such a word, we first replace all $2$’s with left parentheses, “$($”, and all $1$’s with right parentheses, “$)$”. We then “cancel” left and right parentheses in matching pairs as shown in the following example.

\begin{array}{ccccccccccc}
2 & 2 & 1 & 1 & 1 & 1 & 2 & 1 & 2 & 2 & 1 \\
( & ( & ) & ) & ) & ) & ( & ) & ( & ( & ) \\
( & & & ) & ) & ) & & & ( & & \\
& & & & ) & ) & & & ( & &
\end{array}

Once all matching pairs have been cancelled, we are left with a subsequence of the form $$)))\cdots))(((\cdots(($$ consisting of some number of right parentheses (possibly zero) followed by some number of left parentheses (possibly zero). If there is a $)$ remaining, then $F_1$ changes the rightmost $)$ that was not cancelled to $($, changing that $1$ to $2$ in the original word. The word therefore becomes:

\begin{array}{ccccccccccc}
2 & 2 & 1 & 1 & 1 & 2 & 2 & 1 & 2 & 2 & 1.
\end{array}

Thus $F_1(22111121221)=22111221221$. If there were no $)$ symbols remaining after cancelling, the operator $F_1$ is undefined.

Now, consider the directed graph on all words of $1$’s and $2$’s of length $n$, where we draw an arrow from word $w$ to word $v$ if $F_1(w)=v$. Here is the graph for $n=4$:

This graph will in general be a union of disjoint one-directional chains, since when $F_1$ is defined it is invertible: the unbracketed $1$ that is changed to a $2$ is still unbracketed, and we can identify it as the leftmost unbracketed $2$ in the new word. We write $E_1$ to denote this inverse operator, which changes the leftmost unpaired $2$ to a $1$ if it exists, and is undefined otherwise.

We also cannot have cycles in the $F_1$ graph, because the number of $1$’s always decreases with every application of $F_1$. Thus we have chains of arrows going forward until we reach an element $w$ for which $F_1(w)$ is undefined. Similarly, going backwards along the $F_1$ arrows, we can continue until $E_1$ is undefined, and we call these top elements of each chain the highest weight words.

There are six highest weight words in the above diagram: $1111$, $2111$, $1211$, $1121$, $2211$, $2121$. Notice that these are precisely the two-letter ballot sequences of length $6$!

Indeed, if a word is ballot, then every $2$ as a left parentheses will be cancelled with some $1$ as a right parentheses to its right, so $E_1$ is undefined on such a word. Conversely, if a word is not ballot, consider the first step in the right-to-left reading of the word that has more $2$’s than $1$’s. The $2$ that is encountered at that step cannot be bracketed with a $1$ to its right, because there are not enough $1$’s to bracket with the $2$’s in that suffix. Thus a word is ballot if and only if $E_1$ is undefined, which means that it is at the top of its chain, or highest weight.

Since there is exactly one highest weight word per chain, we have the following.

The number of ballot sequences of length $n$ is equal to the number of chains in the $F_1$ crystal graph on all $2^n$ words of $1$’s and $2$’s of length $n$.

So, to count the ballot words, it suffices to count the chains of the $F_1$ graph. And here’s the key idea: instead of counting the top elements, count the middle ones!

In the picture above, the middle elements of each chain are: $$1122, 2112, 1212, 1221, 2211, 2121$$ which is just the set of all words having exactly two $1$’s and two $2$’s, and is clearly counted by $\binom{4}{2}$. Why does this work in general?

Here’s where we need one more fact about the $F_1$ chains: they are “content-symmetric”. If the top element of a chain has $k$ ones and $n-k$ twos, then the bottom element has $n-k$ ones and $k$ twos. This is because the top element, after pairing off an equal number of $2$’s and $1$’s by matching parentheses, has a certain number of unpaired $1$’s, which then all get changed to $2$’s one step at a time as we move towards the bottom of the chain. In particular, the middle element of each chain has exactly as many $1$’s as $2$’s (or, if $n$ is odd, the two “middle elements” have one more $1$ than $2$ and one less $1$ than $2$ respectively.)

Finally, since the graph is drawn on all $2^n$ possible words, every word having the same number of $1$’s as $2$’s (or off by $1$ in the odd case) occurs in exactly one chain. It follows that there is a bijection between the chains and these words, which are enumerated by $\binom{2n}{n}$ for words of length $2n$, and $\binom{2n+1}{n}$ for words of length $2n+1$.

For the more elementary approach, and the solution to the classical ballot problem, turn to the next page!

# Doing mathematics in a pandemic – Part IV: Talks with OBS

This is the final post in a four-part series on adapting to the pandemic as a mathematician. See Part I – AlCoVEPart II – Collaboration, and Part III – Teaching.

As conferences moved online, a number of different methods of giving a remote talk became commonplace. One was to simply point a webcam at a chalkboard and lecture as usual. Another is to make slides and use the “Share Screen” option on Zoom to show the slides to the audience. Another popular method, which I have used a number of times, is to make partial handwritten “slides” in Notability or GoodNotes on an iPad, with space left for doing examples and computations, and then share the iPad screen over Zoom and walk the audience through.

Today I’ll be explaining how to use Open Broadcasting Software (OBS) to give a talk from home in which your slides show up behind you as if you were standing next to a projector screen, but are nearly as crisp as if you were reading the PDF on your own computer screen. François Bergeron at UQAM first introduced me to this method, and his COVID-19 page features excellent explanations of how he creates his own virtual talks.

First, here is what the output of my first and only attempt at using OBS in a virtual talk looked like:

The above talk was given at the Enumerative Combinatorics session of the virtual Canadian Math Society winter meeting in 2020. Other videos from this session are available here, including another example using OBS by Marni Mishna.

There are two steps to getting this working: (1) setting up your video sources in OBS, and (2) feeding the video output to Zoom.

## Step 1: Video sources in OBS

The first step is to install OBS from obsproject.com. Once you install and open it, you’ll see a window with a preview of what your video project looks like. At the bottom of the windows are various menus: Scenes, Sources, Audio Mixer, etc.

You’ll only need one Scene, and you’ll add various Sources to put together the Scene, using the + button at the bottom of the Sources box. Here were the Sources I used:

• Color Source. This allows you to essentially set a “Background color” for your scene. It defaults to a dark grey. Once you add the color source, you can right click it and click “Properties” to change its color.
• Window Capture. This is the source that you can use to make your slides appear. Create a Window Capture source, open your slides in your pdf viewer in another window, and then go back to OBS and right click on Window Capture to select Properties. There you can tell it to use the pdf viewer as the window that you’re capturing in this source. Finally, go back to the pdf viewer and go into presentation mode, so that you can flip through the presentation with a clicker or keyboard as you would in a real classroom.

Tip: If you’re on a Mac or another operating system that has multiple desktops, you may need to open your slides on the same desktop window as OBS is opened in for OBS to find the pdf viewer as a source. In particular, you need to feed it to Window Capture before going to full screen or presentation mode; otherwise OBS will not recognize it as a source.
• Video Capture. This uses your laptop webcam or other webcam to capture your face. You can again right click to get to Properties to change the webcam you’re using if you wish. To filter out everything except your head, you want to use:
• Chroma Key filter. Right click on the Video Capture source and go to “Filters”. Then click the + under the “Effect filters” box and click “Chroma Key”. You can then click on the Chroma Key filter to choose which color you want to filter out.

Since I had a green screen (see Part III), I filtered out the color of my green screen behind my head, and voila, the video capture source only showed the outline of my head and nothing else. If you don’t have a green screen, make sure you’re positioned in front of a blank wall and then just choose the color of that wall to filter out.

Finally, make sure you order the above sources in the Sources box so that Video Capture is highest up, then Window Capture is second, then Color Source is third. This way your head appears in front of the slides which appears in front of the background color.

I resized my Window Capture layer by dragging its outline in the OBS preview window so that it sat in the upper left of the screen, leaving room for my head on the right as if I were standing next to the projector screen.

Here is a screen shot of OBS after setting up everything as above (plus an audio input source – see Optional Step 3 below):

## Step 2: Connecting OBS output to Zoom

For this step, you’ll need to install the OBS Virtual Camera plugin. It’s easy to install, and once you do, if you restart OBS there will now be a “Start Virtual Camera” option under the Tools menu.

If you click “Start Virtual Camera”, this creates a virtual camera device recognized by Zoom. Now, log into Zoom, start a meeting, and click on the up arrow next to the “Stop Video” (or “Start Video”) button. There should now be an option to select “OBS Virtual Camera” as your video camera in Zoom. Select it, and you should see your OBS creation being streamed over Zoom!

Now comes a tricky technical issue. Suppose you want to use a clicker to flip through your slides in presentation mode. Then you need your laptop monitor to be focused on the displayed slides so that the click registers as a slide advancement. But then that means that you can’t see OBS or Zoom on your laptop screen, so you can’t see yourself as you’re gesturing to things on the virtual screen, and can’t aim appropriately or make sure your head isn’t blocking the words.

To solve this, what I did was to log into Zoom on both my laptop and iPad, and position the iPad in front of my laptop webcam so that the webcam still captured my head, but so that I could see myself on the iPad while my clicker clicked through the slides on my laptop. There are other solutions as well; it should be possible to port the iPad screen itself into Window Capture in OBS as well, though I haven’t personally figured out how to do this. But as long as you have one screen to click through your slides and another to view yourself, you’re good to go.

At this point, you’re nearly ready. Zoom will capture your audio as normal, and displays your new video setup from OBS, so you can give your talk!

## Optional Step 3: Audio via OBS

There was one minor issue when I practiced this setup: OBS does some processing which makes the video feed into Zoom lag behind the audio that is also being captured by Zoom. It was only about a half-second lag, and people who I practiced with said it was noticeable but not a major issue.

I did find a way to fix the lag issue, however, and that was to pipe the audio through OBS as well, so that OBS took in both audio and video inputs from me and output both in sync to Zoom. Here are the steps I took to do so:

1. Create an Audio Source in OBS. Go to Sources again and add an Audio Input Capture source. You can go to its Properties to set it to capture whichever microphone you prefer (in my case, the lapel mic that I described in Part III).
2. Install a Virtual Audio Cable. This will have to be third party software, as at the moment OBS does not have a virtual audio plugin that resembles its virtual camera feature. I installed VB-Audio Cable, which is a program that can take output audio from one software source (in our case, OBS) and “plug it in” as the input audio to another software (Zoom).
3. Turn on audio monitoring in OBS. To do so, in the Audio Mixer box at the bottom of your OBS screen, click the Settings wheel next to the volume button on Audio Input Capture, and go to Advanced Audio Properties. Then in the Audio Monitoring column, set both settings (for both Audio Input Capture and Mic/Aux) to “Monitor and Output”.
4. Launch VB-Audio Cable. It needs to be running for the next steps to work. Besides this step, you don’t need to interact with the VB-Audio Cable program at all.
5. Set OBS’s audio monitor to VB-Cable. Go to the main OBS menu at the top and click on Preferences. Click on the Audio tab, then scroll down to Advanced. There, set the Monitoring Device to VB-Cable.
6. In your Zoom meeting, set your microphone to VB-Cable, which should appear as an option for your Zoom microphone now.

Now you’re all set! Time to go give that awesome virtual talk.

# Doing mathematics in a pandemic – Part III: Teaching

This is the third post in a four-part series on adapting to the pandemic as a mathematician. See Part I – AlCoVE, Part II – Collaboration, and Part IV – Talks with OBS.

Of all the things I had to figure out how to adapt to the pandemic reality, I found teaching to be the most challenging by far. So much of the value of teaching comes from the in-person connection between students and teachers, and between peers in the classroom. How can you replicate an entire classroom experience on a 14 inch computer screen? How can you pull off hybrid teaching without diminishing the experience for those students who take the course remotely?

I taught two courses in the fall of 2020 – a small graduate-level class on advanced combinatorics topics, and a larger undergraduate class of 30 students on introductory combinatorics.

When, over the summer, the studies came out showing that outdoor transmission of the coronavirus was minimal, I decided to see if I could get outdoor teaching set up for my graduate class for at least the first half of term, with the plan of moving the class online once it got too cold.

There were a lot of considerations to take into account when setting up a good outdoor learning environment. What do you write on? What if it rained? How do you record the lectures outdoors, with good sound quality, to make sure everyone can still participate even if they have to quarantine due to a COVID-19 exposure? How do you make sure the students can hear you over the noise of nearby traffic and birds and other outdoor distractions? How do you ensure student comfort when taking notes, without having traditional desks?

Here were the tools I used to solve – or at least attempt to solve – each of these issues.

• Rolling whiteboards. The CSU math department ordered lightweight rolling whiteboards with weather-resistant aluminum frames specifically for this purpose. There were at least three instructors who started the semester teaching outdoors, and we made a schedule of who would roll it out and who would roll it back in each day. They worked well outdoors, and as long as you could guarantee you’d be in a shady spot, there was no glare.
• A good location. Behind the math building on my campus was a shady spot on the grass next to a large parking lot with very little daytime traffic going in and out. A generator nearby provided some ambient white noise that drowned out the traffic from a nearby road. Two trees provided a feel of being somewhat removed from the bustling campus sidewalk on the other side. It wasn’t too much effort to roll a whiteboard there. We really lucked out on that front – it was pretty much ideal.

Not all campuses may have such a spot, and some universities solved this using outdoor tents.

Here is a picture of the location and the whiteboard (from a meeting with a grad student, not from class):
• USB lapel mic for recording. A lapel mic, also known as a lavalier mic – one that clips to your collar – is the best way to pick up only your voice and filter out other noises when recording outdoors. I got this one mainly for its 20-foot cable that allowed me to walk around freely at the board, and there are plenty of options out there like it.

I plugged the mic into my laptop and did the recording using the macbook webcam and Quicktime. Nothing fancy, but it did the trick for helping students catch up or participate remotely.
• Personal amplifier for sound projection. It’s hard to project your own voice sufficiently in an outdoor setting, especially with masks. So I got a personal amplifier that would help project my speech to the class. I found that tucking the microphone under my mask and turning the volume low was a good way to get the sound to amplify; it didn’t pick up the sound so well when it was on the other side of the mask.

If teaching outdoors post-pandemic, I highly recommend it; without a mask it would be even better at getting accurate sound and projecting it to the class.
• Weatherproof box and laptop stand. What if it started raining, and all my recording equipment and laptop got rained on? And how do you set your laptop or webcam up at the right height to record yourself writing on the whiteboard?

I solved both of these issues with this large Husky storage box. It allowed me to carry out all my gadgets and whiteboard markers from my office at the start of each class all at once, and then it doubled as a stand to put my laptop on to record my lectures. It’s about the right height – you don’t want something too tall so it doesn’t block the students’ views. And then if it rains, you quickly throw everything back into the storage box.

Luckily, my class was at 1 pm and located in the Colorado front range. The late summer/early fall weather patterns are very predictable, with thunderstorms and rain usually rolling in from the mountains in late afternoon, around 3 pm or later. So rain wasn’t generally an issue. There was one day that it started drizzling in class, but not enough that it wasn’t still pleasant to be outside or possible to take notes. Luckily everyone was there that day, so I put the recording devices back in the box and finished up the lecture without issue.
• Lap desks for student comfort. My graduate class was very small, so I got a couple of cheap lap desks for anyone who wanted to use them. They turned out to be perfect; a simple solution worked in this case. Some students brought folding chairs, others opted to sit on the grass. Either way, student comfort was never a complaint.

There were two aspects of outdoor teaching that I hadn’t accounted for in my planning. One was the record-setting wildfires that hit our region of Colorado starting two days before class started. Some days, the air quality was simply too hazardous to spend a long period of time outside. On those days I sent an email in the morning and moved class online.

The other aspect didn’t really have to do with outdoor teaching per se, but was about in-person vs remote. At CSU, some classes were online and others were in person. It meant that some of my students really liked being in person outdoors, since then they could just stay there for their next outdoor math class in the same location. But others had to sprint to campus from their apartment to make it to my class, since they had an online class just before it that they needed to be at home for.

In the end, the students’ scheduling issues lined up in such a way that it made more sense to go fully remote after the first few weeks. But the outdoor teaching, for the short amount of time it happened, went fairly smoothly.