12
$\begingroup$

Some time ago Qiaochu Yuan asked about counting subsets of a set whose number of elements is divisible by 3 (or 4).

The story becomes even more interesting if one asks about number of subsets of n-element set with $r\bmod 5$ elements. Denote this number by, say, $P_n (r \bmod 5)$.

An experiment shows that for small $n$, $P_n(r \bmod 5)-P_n(r' \bmod 5)$ is always a Fibonacci number (recall that for "$r \bmod 3$" corresponding difference is always 0 or 1 and for "$r \bmod 2$" they are all 0). It's not hard to prove this statement by induction but as always inductive proof explains nothing. Does anybody have a combinatorial proof? (Or maybe some homological proof — I've heard one for "$r \bmod 3$"-case.)

And is there some theorem about $P_n(r \bmod l)$ for arbitrary $l$ (besides that it satisfies some recurrence relation of degree growing with $l$)?

  • 1
    In general your $P_n$ (r mod l) will be a linear combination of terms $(1+\zeta)^n\pm (1+\zeta^{-1})^n$ where $\zeta$ runs through the $l$-th roots of unity. When $l=5$ then these involve powers of $2$ and also powers of the golden ratio, as that is involved in $\cos \pi/5$ and $\cos 2\pi/5$.2010-08-02
  • 0
    @Robin Yes, I thought about it (although I was too lazy to carry out actual proof from this) but it's more like solving recurrence relation (packed into generating function, but anyway) and it would be nice to have a combinatorial proof.2010-08-02
  • 0
    I didn't want to ask about this case because the eigenvalues are complicated, but here is one way you might start: P_n(r mod l) is the number of walks of length n between certain vertices on the cycle graph of length l.2010-08-02
  • 0
    @Qiaochu Yuan could you please elaborate a little?2010-08-02
  • 1
    Take the graph whose vertices are the vertices of a regular l-gon and whose edges are its edges. Then, for example, P_n(0 mod l) is the number of walks of length n on this graph which begin and start at a particular vertex. The bijection is that going left corresponds to having a particular element in your subset and going right corresponds to not having it. The Fibonacci numbers admit a similar interpretation (on more than one graph!) so one might be able to do something from here.2010-08-02
  • 1
    In particular, Fibonacci numbers count walks on the path graph of length 4, which is the one I think will be relevant to this problem.2010-08-02
  • 0
    @Qiaochu Yuan: I think, your observation combined with reflection method gives a proof. I'll try to post details later, probably.2010-08-06
  • 1
    The proof of the Rogers-Ramanujan conjecture in Andrews and Eriksson's book *Integer Partitions* http://books.google.co.uk/books?id=_5gsjNr0lWAC&lpg=PP1&dq=andrews%20eriksson&pg=PP1#v=onepage&q&f=false relies, in effect, on a $q$-analogue of the relation between Fibonacci numbers and the differences between the "Pn(r mod 5)".2010-08-06
  • 0
    Dear Adriano, that edit a) was quite unnecessary; b) title now looks quite ugly. I'm rolling back.2014-12-22

1 Answers 1

3

(Sketch of a bijective solution.)

Recall that binomial coefficients count number of walks with steps (+1,+1) and (+1,-1) from the origin to different points (e.g. the number of walks to the point (2n,0) is $\binom{2n}{n}$). Consider the following involution on the set of all such walks: if the path intersects with the line y=l-1 or the line y=-1, reflect its part starting from the first intersection point (w.r.t. corresponding line).

This involution almost gives a bijection between Pn(r mod l) and Pn(-r-2 mod l) (and moving the strip we can get other correspondences of this kind). But it has some fixed points — namely, paths that lie inside the strip 0≤y≤l-2 (aka walks on the path graph of length l-1 mentioned by Qiaochu Yuan).

Now to answer original question one only needs to recall that numbers of such paths for l=5 are exactly Fibonacci numbers.

  • 0
    Nice! I was going to try working this out this weekend but I see you have beaten me to it :)2010-08-07