Skip to Content »

Michi’s blog » archive for 'Combinatorics'

 Recursively counting numbers with fixed bit counts

  • May 13th, 2012
  • 1:04 am

I ran across this problem in a reddit side-bar job-ad, and was intrigued by the task (description paraphrased to decrease googleability):

Write a function

uint64_t bitsquares(uint64_t a, uint64_t b);

such that it return the number of integers in [a,b] that have a square number of bits set to 1. Your function should run in less than O(b-a).

I think I see how to do it in something like logarithmic time. Here’s how:

First off, we notice that we can list all the squares between 0 and 64: these are 0, 1, 9, 16, 25, 36, 49, and 64. The function I will propose will run through a binary tree of depth 64, shortcutting through branches whenever it can. In fact; changing implementation language completely, I wonder if I cannot even write it comprehensively in Haskell.

 Species, derivatives of types and Gröbner bases for operads

  • December 18th, 2010
  • 2:05 am

This is a typed up copy of my lecture notes from the combinatorics seminar at KTH, 2010-09-01. This is not a perfect copy of what was said at the seminar, rather a starting point from which the talk grew.

In some points, I’ve tried to fill in the most sketchy and un-articulated points with some simile of what I ended up actually saying.

Combinatorial species started out as a theory to deal with enumerative combinatorics, by providing a toolset & calculus for formal power series. (see Bergeron-Labelle-Leroux and Joyal)

As it turns out, not only is species useful for manipulating generating functions, btu it provides this with a categorical approach that may be transplanted into other areas.

For the benefit of the entire audience, I shall introduce some definitions.

Definition: A category C is a collection of objects and arrows with each arrow assigned a source and target object, such that

 Homological Inclusion-Exclusion and the Mayer-Vietoris sequence

  • January 9th, 2009
  • 10:44 pm

This blogpost is inspired to a large part by comments made by Rob Ghrist, in connection to his talks on using the Euler characteristic integration theory to count targets detected by sensor networks.

He pointed out that the underlying principle inducing the rule
\chi(A\cup B) = \chi(A)+\chi(B)-\chi(A\cap B)
goes under many names, among those \emph{Inclusion-Exclusion}, favoured among computer scientists (and combinatoricists). He also pointed out that the origin of this principle is the Mayer-Vietoris long exact sequence
\cdots\to H_{n}(A\cap B)\to H_{n}(A)\oplus H_{n}(B)\to H_{n}(A\cup b)\to\cdots

In this blog post, I’d like to give more meat to this assertion as well as point out how the general principle of Inclusion-Exclusion for finite sets follows immediately from Mayer-Vietoris.

Inclusion-Exclusion, and the passage from two sets to many

The basic principle of Inclusion-Exclusion says that if we have two sets, A and B, then the following relationship of cardinalities holds:
|A\cup B| = |A| + |B| – |A\cap B

 More on Lichtenstein

  • October 28th, 2008
  • 11:03 pm

It turns out that there is even more to say on the communes of Lichtenstein.

First of all, there is a 5-clique in the communal graph, as Brian Hayes pointed out. But there are two different excluded subgraphs for planarity – so if we aren’t looking specifically for the chromatic number, but rather how this graph fails to be a “normal” land map, we might want to see whether it realizes BOTH.

It turns out that it does.

The following are two highlighted versions of the Liechtenstein communal graph.


The embedded K5 with edges in blue.


The embedded K33 with blue and red vertices.

 On the chromatic number of Lichtenstein

  • October 28th, 2008
  • 7:41 pm

Following the featuring of the internal political structure of Lichtenstein on the Strange Maps blog, Brian Hayes asks for the chromatic number of Lichtenstein.

Rahul pointed out that I made errors in transferring the map to a graph. Specifically, I missed the borders Schellenberg-Eschen and Vaduz-Triesen. The post below changes accordingly.

Warning: This post DOES contain spoilers to Brian’s question. If you do want to investigate it yourself, you’ll need to stop reading now. Apologies to those on my planet feeds.

As a first step, we need to build a graph out of it. I labeled each region in turn with the exclaves numbered higher than the “main” region of each organizational unit. And then I build a .dot file to capture them all:

 High school topology restarting

  • November 16th, 2007
  • 4:34 pm

Today, I told my two bright students about abstract and geometric simplicial complexes, about the boundary map and the chain complex over a ring R associated with a simplicial complex Δ, and assigned them reading out of Hatcher’s Algebraic Topology.

The next couple of weeks will be spent doing homology of simplicial complexes, singular homology, equivalence of the two, neat things you can do with them; and then we’ll start moving towards a Borsuk-Ulam-y topological combinatorics direction.

I might end up pulling combinatorics papers from my old “gang” in Stockholm on graph complexes, and graph property complexes, and poke around those with them.

 Enumerating the Saneblidze-Umble diagonal in Haskell

  • June 11th, 2007
  • 3:47 pm

IMPORTANT: Note that the implementation herein is severely flawed. Do not use this.

One subject I spent a lot of time thinking about this spring was taking tensor products of A-algebras. This turns out to actually already being solved – having a very combinatorial and pretty neat solution.

Recall that we can describe ways to associate operations and homotopy of associators by a sequence of polyhedra Kn, n=2,3,.., called the associahedra. An A-algebra can be defined as being a map from the cellular chains on the Associahedra to n-ary endomorphisms of a graded vector space.

If this was incomprehensible to you, no matter for this post. The essence is that by figuring out how to deal with these polyhedra, we can figure out how to deal with A-algebras.

 looksay – today’s Haskell snippet

  • April 18th, 2007
  • 9:34 am
nextLookSay = foldr (\xs -> ([length xs, head xs]++)) [] . group
lookSay = iterate nextLookSay [1]
 

Conway’s Look-and-say sequence

 Borsuk-Ulam and West Wing

  • February 7th, 2006
  • 11:56 pm

In West Wing 4×20, CJ states that there are two antipodal points with identical temperature on the earth, as an argument why it should be possible to imagine that an egg could stand on its end at the spring equinox. This particular plotline also has her most emphatically claiming that this should not be possible at the autumn equinox. Why this particular physics is complete idiocy will be left as an exercise to the interested reader, and instead I will focus on the other claim.

This is, in fact, true. It’s a corollary to one of the prettiest theorem conglomerates I have ever seen: the Borsuk-Ulam theorem(s). Alas, I haven’t got my sources on it here at the moment, so I won’t give you the deep indepth survey I want to give; but I do want to give a bit of overview as to why the claim CJ supports her insane theory with is actually true.