Counting parts with r mod 5 components

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

The tale comes to be a lot more intriguing if one inquires about variety of parts of n-element set with $r\bmod 5$ components. Represent this number by, claim, $P_n (r \bmod 5)$.

An experiment reveals that for tiny $n$, $P_n(r \bmod 5)-P_n(r' \bmod 5)$ is constantly a Fibonacci number (recall that for "$r \bmod 3$" matching distinction is constantly 0 or 1 and also for "$r \bmod 2$" they are all 0). It's not tough to confirm this declaration by induction yet as constantly inductive evidence clarifies absolutely nothing. Does any person have a combinatorial evidence? (Or possibly some homological evidence-- I've listened to one for "$r \bmod 3$"- instance.)

And also exists some theory concerning $P_n(r \bmod l)$ for approximate $l$ (besides that it pleases some reappearance relationship of level expanding with $l$)?

2019-05-04 16:27:19
Source Share
Answers: 1

(Sketch of a bijective remedy.)

Remember that binomial coefficients count variety of strolls with actions (+1, +1) and also (+1, -1) from the beginning to various factors (as an example the variety of strolls to the factor (2n,0) is $\binom{2n}{n}$). Take into consideration the adhering to involution on the set of all such strolls : if the course converges with the line y =l-1 or the line y =-1, mirror its component beginning with the first junction factor (w.r.t. equivalent line).

This involution virtually offers a bijection in between P n (r mod l) and also P n (- r-2 mod l) (and also relocating the strip we can get various other documents of this kind). Yet it has some set factors-- particularly, courses that exist inside the strip 0 ≤ y ≤ l-2 (also known as strolls on the course chart of size l-1 stated by Qiaochu Yuan).

Currently to address initial inquiry one just requires to remember that varieties of such courses for l =5 are specifically Fibonacci numbers.

2019-05-08 03:06:36