Timeline for Prime dividing the binomial coefficients
Current License: CC BY-SA 3.0
6 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Nov 27, 2017 at 17:12 | history | edited | darij grinberg | CC BY-SA 3.0 |
the expansions may be of different sizes otherwise
|
| Jul 15, 2011 at 21:08 | history | edited | Jonas Kibelbek | CC BY-SA 3.0 |
Added specialized proof
|
| Jul 15, 2011 at 20:56 | comment | added | Jonas Kibelbek | But for a subset of $M$ to be fixed by $G$, it must be an entire $p^i$-cycle, or a union of several $p^i$-cycles. To get a size $n$ subset of $M$ fixed by $G$, we must used the base $p$ digits of $n$. That is, for each $i$, we choose $n_i$ of the $m_i$ $p^i$-cycles. | |
| Jul 15, 2011 at 20:51 | comment | added | Jonas Kibelbek | @Ofir: There is an independent combinatorial proof given in the Wikipedia article: We have a set $M$ of size $m$ and want to count (mod $p$) the subsets of size $n$. We define a group $G$ acting on $M$ corresponding to the base $p$ digits of $m$: for each $i$, we have $m_i$ cycles of size $p^i$, all mutually disjoint. The group is the product over $i$ of $m_i$ copies of the cyclic group on $p^i$ elements. The group $G$ also acts on the set of all size $n$ subsets of $M$, cutting it into orbits. The nontrivial orbits must have size $p^j$; so to count mod $p$, we need only count fixed points. | |
| Jul 15, 2011 at 19:40 | comment | added | Ofir | The shortest proof I know is by comparing the coefficient of $x^n$ in 2 equal polynomials (modulo $p$): $(1+x)^m$ and $\prod_{i}(1+x)^{m_{i}p^{i}} \equiv \prod_{i}(1+x^{p^i})^{m_i}$. This polynomial identity follows by repeated application of $(1+y)^p \equiv 1+y^p$, which in itself is equivalent to $\binom{p}{i} \equiv 0$ | |
| Jul 14, 2011 at 18:30 | history | answered | Jonas Kibelbek | CC BY-SA 3.0 |