I actually never took a graph theory course while I was in college, but seeing as it’s an extremely pervasive topic in discrete math (and math in general), I wanted to learn more. I worked through chapter 11 of Ralph…
I took a discrete math class in college where I learned about generating functions and recurrence relations. I was amazed at how versatile these kinds of functions were in modeling combinatorial problems, so after I finished the class, I decided…
Given that rooks capture along rows and columns, and given that bishops attack along diagonals, it only seems natural that non-taking queen placements on a board are somehow related to non-taking rook and bishop placements on the same board. We’ve…
In a previous post, I described a set of Python functions within a script that can calculate Rook Polynomials for a board. A lot of that material can be reused, and some of it will serve as a guide to…
One easy way to extend what we’ve talked about thus far is to ask ourselves what happens when we allow both rooks and bishops on the same board. How many ways can we place rooks and bishops on a board…
A “Quick” 3-by-3 Example Just as we can count the number of ways to place some number of non-attacking rooks on a board, we can count the number of ways to place non-attacking bishops on a board. Bishops are perhaps…
Now that we’ve got a handle on Rook Polynomials, we can start asking what else we can do with them. Here are a couple of easy starting points. Faster Decomposition One thing we may want to do is think about…
Now that we know the general approach, we’re ready to start automating the process of calculating these polynomials. I’ve been using Rust for my past few projects, but out of pure laziness, I decided to develop a Python script for…
Ideally, we’d like to avoid having to exhaustively count the number of ways to place rooks on the board in such a way that they don’t attack each other. After all, the whole point is to use Rook Polynomials to…
Some Motivating Examples Before introducing what Rook Polynomials actually are, I want to motivate their existence by discussing some example problems. Example 1: How many ways are there to assign band positions? Let’s say that there are 6 people wanting…
