Διωνυμικοί συντελεστές (mod p)

#1

Με αφορμή το θέμα που προτάθηκε εδώ.

Έστω $\displaystyle{p}$ πρώτος αριθμός και $\displaystyle{n}$ θετικός ακέραιος. Θεωρούμε τους διωνυμικούς συντελεστές $\displaystyle{\left( \begin{array}{l} a\\ m \end{array} \right)},$ με $\displaystyle{0 \le m \le a \le n},$ το πλήθος των οποίων είναι $\displaystyle{{\frac{1}{2}\left( {n + 1} \right)\left( {n + 2} \right)}.}$

Συμβολίζουμε με $\displaystyle{{F_p}\left( n \right)}$ το πλήθος των παραπάνω διωνυμικών συντελεστών, οι οποίοι δεν είναι πολλαπλάσια του $\displaystyle{p.}$

Να αποδειχθεί ότι

$\displaystyle{\mathop {\lim }\limits_{n \to + \infty } \frac{{{F_p}\left( n \right)}}{{\frac{1}{2}\left( {n + 1} \right)\left( {n + 2} \right)}} = 0.}$

Με άλλα λόγια, αν επιλέξουμε "στην τύχη" ένα διωνυμικό συντελεστή, τότε αυτός "σχεδόν βέβαια" θα είναι πολλαπλάσιο του $\displaystyle{p}.$

Γιάννης Ι. · #2

Το θέμα είναι πολύ ενδιαφέρον. Διατηρώντας τους συμβολισμούς και βάση των όσων έγιναν εδώ http://mathematica.gr/forum/viewtopic.php?f=111&t=16767 έχουμε ότι αν $n=\sum_{i=0}^{K} a_{i} \cdot p^{i}$ (υπενθυμίζω εδώ πως $K \le \log _{ p }{ n }$ ) τότε:
$\displaystyle{F_{ p }(n)=\sum _{ k=0 }^{ n }{ f_{ p }(k) } =\sum _{ { m }_{ 0 }\le { a }_{ 0 }~ ,...,{ m }_{ K }\le{ a }_{ K } }{ \prod _{ k=0 }^{ K }{ (m_{ k }+1) } } =}$
$\displaystyle{(1+...+(a_{ 0 }+1))\cdot \sum _{ { m }_{ 1 }\le { a }_{ 1 }~ ,...,{ m }_{ K }\le { a }_{ K } }{ \prod _{ k=0 }^{ K }{ (m_{ k }+1) } } =\frac { (a_{ 0 }+1)(a_{ 0 }+2) }{ 2 } \cdot \sum _{ { m }_{ 1 }\le{ a }_{ 1 }~ ,...,{ m }_{ K }\le { a }_{ K } }{ \prod _{ k=0 }^{ K }{ (m_{ k }+1) } } =}$
$\displaystyle{\prod _{ k=0 }^{ \qquad K\qquad }{ \frac { (a_{ k }+1)(a_{ k }+2) }{ 2 } } \le {(\frac { p(p+1) }{ 2 })\ }^{K}\le {(\frac { p(p+1) }{ 2 })\ } ^{\log _{ p }{ n }}}$
Xρησιμοποιώντας την ανισότητα $p +1 \le \frac{3}{2}p$ έχουμε ότι $F_{ p }(n)\le { (\frac { 3 }{ 4 } ) }^{ \log _{ p }{ n } }\cdot ~ n^{ 2 }$ .
Έτσι, αν οι πράξεις δε μας αδικούνε, η πυκνότητα των διωνυμικών συντελεστών $\left( \begin{matrix} a \\ m \end{matrix} \right)$ με $0\le a\le m\le n$ που δε διαιρούνται από τον

τείνει εκθετικά στο

όταν το

τείνει στο άπειρο

Διωνυμικοί συντελεστές (mod p)

Διωνυμικοί συντελεστές (mod p)

Re: Διωνυμικοί συντελεστές (mod p)

Μέλη σε σύνδεση