$p\not\mid \binom{n}{a, b}$

[Ido Bovski]

Dimostrare che il numero di coppie $(a, b)$ tali che $\displaystyle p\not\mid\frac{n!}{(n-a)!(a-b)!b!}$, con $p$ primo, è dato da $\displaystyle \prod_{i=0}^k \binom{n_i+2}{2}$, dove $(\overline{n_k\ldots n_0})_p=n$.

(...generalizzando un problema della semifinale della gara a squadre!)

[Gottinger95]

Che intendi con la notazione \((\bar{n_k \ldots n_0})_p\) che non riesco neanche a emulare ?

[Ido Bovski]

Che intendi con la notazione \((\bar{n_k \ldots n_0})_p\) che non riesco neanche a emulare ?

La scrittura di $n$ in base $p$.

[Gottinger95]

In pratica la tesi è che il numero di coppie sia uguale al numero di modi di scegliere tre numeri \(m_1, m_2, m_3\) tali che \((m_1)_i + (m_2)_i + (m_3)_i = n_i\) (dove \( (m_j)_i\) indica la \(i\)-esima cifra di \(m_j\) in base \(p\) ), per i quali vale ovviamente anche \(m_1 + m_2 + m3 = n\). Effettivamente gli \(m_j\) sarebbero \(n-a, a-b, b\), quindi ad ogni scelta degli \(m_j\) corrisponde una scelta degli \(a,b\).

Vogliamo dimostrare dunque che \(\nu_p \left ( \binom{n}{m_1, m_2, m_3} \right ) = 0)\) se e solo se le cifre degli \(m_i\) sono una partizione delle cifre di \(n\).

Definiamo \(\displaystyle R(i,k,a) = \sum_{j=i+1}^k{a_j p^{j-1} }\), dove \(a_j\) è la \(j\)-esima cifra in base \(p\) di \(a\) e \(k = \left \lfloor \log_p a \right \rfloor\).

Fatto 1: Abbiamo \(\displaystyle \nu_p(n!) =\sum_{i=1}^k{\left \lfloor \frac{n}{p^i} \right \rfloor}\), con \(k = \left \lfloor \log_p n \right \rfloor\).

Fatto 2: Detta \( m_i\) la \(i\)-esima cifra di \(m\) in base \(i\), abbiamo \(\displaystyle m_i = \left \lfloor \frac{m}{p^i} \right \rfloor - R(i,k,m)\).

Prima freccia: \(m_j\) sono una partizione \(\rightarrow\) \(p\) non divide.

Innanzituttto notiamo che vale \(R(i,k,n) = R(i,k,m_1) + R(i,k,m_2)+R(i,k,m_3)\) per la relazione \((m_1)_i + (m_2)_i + (m_3)_i = n_i\) che supponiamo.
Inoltre sommando la suddetta relazione su ogni \(i\) otteniamo:
\(\displaystyle \sum_{i=0}^k{n_i} = \sum_{s=1}^3 \sum_{i=0}^k{(m_1)_i}\)
\(\displaystyle \sum_{i=0}^k{ \left \lfloor \frac{n}{p^i} \right \rfloor - R(i,k,n) } = \sum_{s=1}^3\sum_{i=0}^k{ \left \lfloor \frac{m_s}{p^i} \right \rfloor - R(i,k,m_s) }\)
\(\displaystyle \sum_{i=0}^k{ \left \lfloor \frac{n}{p^i} \right \rfloor} - \sum_{i=0}^k{R(i,k,n) } = \sum_{s=1}^3\sum_{i=0}^k{ \left \lfloor \frac{m_s}{p^i} \right \rfloor} - \sum_{s=1}^3\sum_{i=0}^k{R(i,k,m_s) }\)
\(\displaystyle \sum_{i=0}^k{ \left \lfloor \frac{n}{p^i} \right \rfloor } = \sum_{s=1}^3\sum_{i=0}^k{ \left \lfloor \frac{m_s}{p^i} \right \rfloor}\)
\(\displaystyle \nu_p(n!) + n = \nu_p(m_1!) +m_1 + \nu_p(m_2!)+m_2 + \nu_p(m_3!)+m_3\)
\(\displaystyle \nu_p \left (\binom{n}{m_1,m_2,m_3} \right ) = 0\)
Q.E.D
Per l'altra freccia penso che il procedimento sia più o meno lo stesso ma al contrario, anche se la parte degli \(R(i,k,m)\) viene abbastanza più brutta perchè non le possiamo semplificare termine a termine. Domani ci penso, adesso vò a nanna.

[EvaristeG]

... che non riesco neanche a emulare ?

Scarsone, basta che clicchi col destro e in Show Math As selezioni TeX Commands ed il velo sarà strappato...

[Chuck Schuldiner]

Bagonzo io ho sempre dovuto quotare per cose di questo tipo

[jordan]

Scarsone, basta che clicchi col destro e in Show Math As selezioni TeX Commands ed il velo sarà strappato...

Anch'io quotavo sempre

[Gottinger95]

Ahahah ma non vale rispolverare misfatti del passato! Quel messaggio risale a molto tempo fa, quando ero ancora un ragazzaccio...Adesso mi sono ripulito e addirittura conosco anche Show Math As > Tex Commands.

Ma invece l'idea della dimostrazione è quella?