# Combinatorics

## How Many Squares in a Checkerboard?

Last week we looked at ways to count paths along the edges of a rectangular grid. Now we’ll look at a companion problem: counting the number of squares (or rectangles) of all sizes in a square (or rectangular) grid. This, too, is a very common question, and I’ll be picking just a few of many …

## How Many Paths from A to B?

A popular kind of question in combinatorics is to count the number of paths between two points in a grid (following simple constraints). This can be done by very different methods at different levels. We’ll look at several problems of this type, starting with the simplest.

## Fibonacci, Pascal, and Induction

A couple weeks ago, while looking at word problems involving the Fibonacci sequence, we saw two answers to the same problem, one involving Fibonacci and the other using combinations that formed an interesting pattern in Pascal’s Triangle. I promised a proof of the relationship, and it’s time to do that. And while we’re there, since …

## Interpreting Probability Questions

(A new question of the week) A couple recent questions centered around how to interpret probability problems, whose wording can often be subtle, and whose solutions require care.

## Writing a Proof: Substance, then Style

(A new question of the week) A question from last month provides an opportunity to show how to develop an algebraic proof of a combinatorial identity involving factorials. We’ll be looking over Doctor Rick’s shoulder as he guides a student through the maze. I’ll also add in a previously published version of the same proof …

## Combinatorics and Coefficients

(A new question of the week) A question from last August gave us some nice problems reminiscent of the Binomial Theorem, which were very deserving of discussion. Three problems The question came from Arsh: I have some coefficient problems which I am unable to solve. I don’t know if a single concept will work for …

## Rank of a Binary Number

(A new question of the week) A few months ago, I wrote about Ranking a Word Among Its Permutations, that is, finding where a word would be found in an ordered list of all possible “words” made by permuting its letters. The problem in general requires a (sometimes lengthy) algorithm. A month or so later, …

## Ranking a Word Among Its Permutations

(A new question of the week) There are some topics that appear to be standard in certain parts of the world, but far less familiar in our own. Sometimes it takes two of us to recognize what a student is asking, due to language issues and different past experience with such questions. This is an …

## Interpreting and Solving a Counting Problem

(An archive question of the week) Combinatorics can be inherently tricky; making up your own problem is doubly so. Here we have a problem created by a teacher, who then is not entirely sure what it means. How can we figure out what meaning to give it? Combine that with working out how to solve …

## Arranging Letters with Duplicates

(A new question of the week) Here is a recent discussion with a frequent user of our service, Kurisada, about combinatorics. He is new to the subject, so this involved several introductions to new ideas. Arranging 8 letters, 2 identical There are 8 letters : A, B, H, N, O, S, U, U I was …