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
    $\begingroup$ 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$. $\endgroup$ – Robin Chapman Aug 2 '10 at 11:04
  • $\begingroup$ @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. $\endgroup$ – Grigory M Aug 2 '10 at 11:25
  • 1
    $\begingroup$ 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. $\endgroup$ – Qiaochu Yuan Aug 2 '10 at 17:52
  • 1
    $\begingroup$ 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. $\endgroup$ – Qiaochu Yuan Aug 2 '10 at 20:02
  • 1
    $\begingroup$ The proof of the Rogers-Ramanujan conjecture in Andrews and Eriksson's book Integer Partitions books.google.co.uk/… relies, in effect, on a $q$-analogue of the relation between Fibonacci numbers and the differences between the "Pn(r mod 5)". $\endgroup$ – Robin Chapman Aug 6 '10 at 19:29

(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.

  • $\begingroup$ Nice! I was going to try working this out this weekend but I see you have beaten me to it :) $\endgroup$ – Qiaochu Yuan Aug 7 '10 at 4:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.