# Category Archives: combinatorics

## Dirichlet convolution and the Möbius function

Recall from last time that the Dirichlet convolution of two functions and is written and defined by: where the sum is taken over all possible factorizations of into a product of positive integers. Last time we saw that is commutative … Continue reading

Posted in combinatorics, proof | Tagged , , , | 1 Comment

## Dirichlet convolution

Let and be two functions defined on the positive integers. Then the Dirichlet convolution of and , written , is another function on the positive integers, defined as follows: The sum is taken over all possible factorizations of into a … Continue reading

Posted in combinatorics, proof | Tagged , , , | 8 Comments

## The Möbius function proof, part 2 (the subset parity lemma)

Continuing from my previous post, we are in the middle of proving that satisfies the same equation as , that is, and that therefore for all , that is, is the sum of all the th primitive roots of unity. … Continue reading

Posted in arithmetic, combinatorics, complex numbers, primes, proof | Tagged , , , , , , , , , | 3 Comments

## The birthday candle problem: solution

Recall the birthday candle problem I wrote about in a previous post: A birthday cake has lit candles. At each step you pick a number uniformly at random and blow out candles. If any candles remain lit, the process repeats … Continue reading

Posted in combinatorics, probability, solutions | Tagged , , , | 5 Comments

## The birthday candle problem

After a 1.5-month epic journey1, I am finally settling into my new position at Hendrix College. Here’s a fun problem I just heard from my new colleage Mark Goadrich: A birthday cake has lit candles. At each step you pick … Continue reading

Posted in challenges, combinatorics, probability | Tagged , , , | 5 Comments

## PIE day

[This is part six in an ongoing series; previous posts can be found here: Differences of powers of consecutive integers, Differences of powers of consecutive integers, part II, Combinatorial proofs, Making our equation count, How to explain the principle of … Continue reading

Posted in combinatorics, counting | Tagged , , , , | 2 Comments

## The Steinhaus-Johnson-Trotter algorithm

In a previous post I posed the question: is there a way to list the permutations of in such a way that any two adjacent permutations are related by just a single swap of adjacent numbers? (Just for fun, let’s … Continue reading

Posted in combinatorics, pattern, solutions | Tagged , , , , , | 9 Comments

## Permuting permutations

As you probably know, there are ( factorial) different ways to put the numbers from through (or any set of distinct objects) in a list. For example, here are the different lists containing the numbers through : Each such list … Continue reading

Posted in challenges, combinatorics | Tagged , | 11 Comments

## How to explain the principle of inclusion-exclusion?

I’ve been remiss in finishing my series of posts on a combinatorial proof. I still intend to, but I must confess that part of the reason I haven’t written for a while is that I’m sort of stuck. The next … Continue reading

Posted in combinatorics, meta | Tagged , , , | 7 Comments

## Making our equation count

[This is post #4 in a series; previous posts can be found here: Differences of powers of consecutive integers, Differences of powers of consecutive integers, part II, Combinatorial proofs.] We’re still trying to find a proof of the equation which … Continue reading

Posted in combinatorics, pictures | | 3 Comments