Category Archives: combinatorics

A few words about PWW #33: subset permutations

Posted on August 20, 2021 by Brent

My previous post showed four rows of diagrams, where the th row (counting from zero) has diagrams with dots. The diagrams in the th row depict all possible paths that start at the top left dot, end at the top … Continue reading →

Posted in combinatorics, posts without words | Tagged Haskell, path, permutation, subset | 6 Comments

Post without words #33

Posted on August 18, 2021 by Brent

Posted in combinatorics, posts without words | Tagged path, permutation, subset | 4 Comments

A combinatorial proof: PIE a la mode!

Posted on October 25, 2019 by Brent

Continuing from my last post in this series, we’re trying to show that , where is defined as which is what we get when we start with a sequence of consecutive th powers and repeatedly take successive differences. Recall that … Continue reading →

Posted in arithmetic, combinatorics, proof | Tagged consecutive, difference, function, integers, matching, powers | Comments Off

A combinatorial proof: counting bad functions

Posted on September 29, 2019 by Brent

In a previous post we derived the following expression: . We are trying to show that , in order to show that starting with a sequence of consecutive th powers and repeatedly taking successive differences will always result in . … Continue reading →

Posted in arithmetic, combinatorics, proof | Tagged consecutive, difference, function, integers, matching, powers | 1 Comment

A combinatorial proof: functions and matchings

Posted on September 26, 2019 by Brent

We’re trying to prove the following equality (see my previous post for a recap of the story so far): In particular we’re trying to show that the two sides of this equation correspond to two different ways to count the … Continue reading →

Posted in arithmetic, combinatorics, proof | Tagged consecutive, difference, function, integers, matching, powers | 5 Comments

A combinatorial proof: the story so far

Posted on September 6, 2019 by Brent

In my last post I reintroduced this seemingly odd phenomenon: Start with consecutive integers and raise them all to the th power. Then repeatedly take pairwise differences (i.e. subtract the first from the second, and the second from the third, … Continue reading →

Posted in arithmetic, combinatorics, proof | Tagged consecutive, difference, integers, powers | 1 Comment

A combinatorial proof: reboot!

Posted on August 31, 2019 by Brent

More than seven years ago I wrote about a curious phenomenon, which I found out about from Patrick Vennebush: if you start with a sequence of consecutive th powers, and repeatedly take pairwise differences, you always end up with , … Continue reading →

Posted in arithmetic, combinatorics, proof | Tagged consecutive, difference, integers, powers | 11 Comments

PIE: proof by counting

Posted on August 13, 2019 by Brent

Recall the setup: we have a universal set and a collection of subsets , , , and so on, up to . PIE claims that we can compute the number of elements of that are in none of the (that … Continue reading →

Posted in combinatorics, pattern, proof | Tagged counting, exclusion, inclusion, PIE, proof | 1 Comment

PIE: proof by algebra

Posted on August 7, 2019 by Brent

In my previous post I stated a very formal, general form of the Principle of Inclusion-Exclusion, or PIE.1 In this post I am going to outline one proof of PIE. I’m not going to give a completely formal proof, because … Continue reading →

Posted in combinatorics, induction, pattern, proof | Tagged exclusion, formal, inclusion, induction, PIE, proof, sets | 2 Comments

Formal PIE

Posted on July 27, 2019 by Brent

I’ve been talking informally about the Principle of Inclusion-Exclusion but I realized it would be useful to state it more formally before proceeding to some proofs. The only problem is that a fully formal statement of PIE has a lot … Continue reading →

Posted in combinatorics, pattern | Tagged equation, exclusion, formal, inclusion, PIE, sets | 5 Comments