Προβλήματα Μαθηματικών

24 Οκτωβρίου, 2008

Διωνυμικοί συντελεστές

Filed under: Λυμένα Προβλήματα — Mihalis Kolountzakis @ 10:41 πμ

Για {x \in {\mathbb R}} και για φυσικό αριθμό m ορίζουμε

{\displaystyle {x \choose m} = \frac{1}{m!} x(x-1)\cdots(x-m+1)}.

Αν a ακέραιος και q πρώτος αριθμός δείξτε ότι υπάρχει ακέραιος A και ακέραιος {n\ge 0} ώστε να ισχύει

{\displaystyle {a/q \choose m} = \frac{A}{q^n}}.

14 Σχόλια »

  1. Ο τελευταίος διωνυμικός συντελεστής ισούται με \displaystyle \frac{1}{q^m}\frac{\prod_{i=0}^{m-1}(a-iq)}{m!} .

    Αρκεί επομένως να δειχθεί ότι τα πολλαπλάσια του p^s (όπου p πρώτος διάφορος του q και 0<p^s<m) στο {a, a-q,\ldots,a-q(m-1)} είναι όσα και τα πολλαπλάσια του στο \{0,1,...,m-1\} .

    Όντως {\#\{0 \leq i \leq m-1 : \alpha-i q=0 (\bmod p^s)\}} {=\#\{i : i=\alpha q^{-1}(\bmod p^s)\}=[m / p^s]} .

    Μου αρέσει!

    Σχόλιο από ef8sof — 29 Οκτωβρίου, 2008 @ 5:18 πμ

  2. ef8sof:
    Πολύ καλή προσπάθεια αλλά νομίζω πως δεν είναι ακόμη πλήρης. Λείπει λίγη προσοχή από το μέτρημα στο τέλος.

    Αποδεικνύεις για παράδειγμα ότι το πλήθος των δυνάμεων του p^s είναι ίδιο σε αριθμητή και παρανομαστή, πράγμα που δεν ισχύει. Δες π.χ. το \displaystyle {10/7 \choose 6}. Αυτό έχει παραπάνω 3άρια πάνω απ’ ό,τι κάτω.

    Μου αρέσει!

    Σχόλιο από Mihalis Kolountzakis — 29 Οκτωβρίου, 2008 @ 10:16 πμ

  3. O συντελεστης ειναι :
    [a(a-q)(a-2q)…(a-(m-1)q)]/m!*q^m.Αρκει προφανως να δειξουμε οτι m! διαιρει την ποσοτητα
    [a(a-q)(a-2q)…(a-(m-1)q)].Εστω τωρα i διαφορετικο του j που ανηκουν στο {0,1,…,m-1} ετσι ωστε a-iq=a-jqmodm.Απο εδω ευκολα προκυπτει οτι i=jmodm κατι που ειναι ατοπο.Οποτε a-iq ανισοτιμοι ανα δυο modulo m.Αρα υπαρχει απεικονιση ενα προς ενα και επι σ:{0,1…,m-1}->{1,2,…,m-1,m} ετσι ωστε a-iq=σ(i)modm , i=0,1,…,m-1.Οποτε προφανως [a(a-q)(a-2q)…(a-(m-1)q)]=m!modm και το ζητουμενο αποδειχθηκε.Μαλιστα n=m.

    Μου αρέσει!

    Σχόλιο από nikkaram — 9 Νοεμβρίου, 2008 @ 9:35 μμ

  4. nikkaram:

    Η προτελευταία πρότασή σου («Οπότε προφανώς …») δε συνεπάγεται αυτό που ισχυρίζεσαι.

    Και μάλιστα δε μπορείς να περιμένεις ότι {m=n}. Αν, π.χ., {m=3, a=5, q=2} τότε δεν ισχύει.

    Μου αρέσει!

    Σχόλιο από Mihalis Kolountzakis — 9 Νοεμβρίου, 2008 @ 10:30 μμ

  5. Ναι , βιαστηκα. Με συγχωρειτε για την ταλαιπωρια , θα το δω πιο προσεκτικα.Ευχαριστω.

    Μου αρέσει!

    Σχόλιο από nikkaram — 10 Νοεμβρίου, 2008 @ 6:47 πμ

  6. Κανένα πρόβλημα. Ο μόνος τρόπος για να μην κάνει κανείς ποτέ λάθος είναι να μην λέει ποτέ τίποτα.

    Μου αρέσει!

    Σχόλιο από Mihalis Kolountzakis — 10 Νοεμβρίου, 2008 @ 10:15 πμ

  7. Μπορω να υποθεσω οτι ο q δεν διαιρει τον a?Γιατι αλλιως αναγεται στο γνωστο διωνυμικο συντελεστη των Κ ανα Μ οπου και οι δυο ακεραιοι.

    Μου αρέσει!

    Σχόλιο από nikkaram — 11 Νοεμβρίου, 2008 @ 9:37 μμ

  8. Φυσικά. Αλλιώς δεν υπάρχει τίποτα προς απόδειξη αφού ο διωνυμικός συντελεστής είναι ακέραιος.

    Μου αρέσει!

    Σχόλιο από Mihalis Kolountzakis — 11 Νοεμβρίου, 2008 @ 10:37 μμ

  9. Συμπληρωνω την ιδεα του/της ef8sof. Εστω p^s καποια δυναμη πρωτου διαφορου του q. Εστω u_s\in\{0,1,\dots,p^s-1\} που ικανοποιει τη σχεση u_s\equiv a\bar{q}\pmod{p^s}. Τότε γραφοντας

    \displaystyle \{0\le i\le m-1:\ a-qi\equiv0\pmod{p^s}\} =

    \displaystyle = \{0\le i\le m-1:\ i\equiv a\bar{q}\pmod{p^s}\}

    \displaystyle = \{k:\ 0\le kp^s+u_s\le m-1\}

    \displaystyle = \Bigl\lfloor 1+\frac{m-(u_s+1)}{p^s}\Bigr\rfloor

    \displaystyle = \Bigl\lfloor \frac{m+(p^s-u_s-1)}{p^s}\Bigr\rfloor.

    Επομενως, η ακριβης δυναμη του p που διαρει το γινομενο \prod_{i=0}^{m-1}(a-qi) ειναι ιση με

    \displaystyle (*)\sum_{s=1}^\infty s\Bigl\{\Bigl\lfloor\frac{m+(p^s-u_s-1)}{p^s}\Bigr\rfloor-\Bigl\lfloor\frac{m+(p^s-u_{s+1}-1)}{p^{s+1}}\Bigr\rfloor\Bigr\}=\sum_{s=1}^\infty\Bigl\lfloor\frac{m+(p^s-u_s-1)}{p^s}\Bigr\rfloor

    [αθροιζουμε s\times(οροι γινομενου που διαιρουνται με p^s-οροι γινομενου που ΔΕΝ διαιρουνται με p^{s+1}) ]

    Με παρομοιο τροπο μπορουμε να δειξουμε οτι η ακριβης δυναμη του p που διαρει το m! ειναι

    \displaystyle (**)\sum_{s=1}^\infty \Bigl\lfloor\frac m{p^s}\Bigr\rfloor. Το αθροισμα στην (*) ειναι μεγαλυτερο απο αυτο στην (**), επειδη 0\le u_s\le p^s-1.

    Μου αρέσει!

    Σχόλιο από partalopoulo — 4 Μαΐου, 2009 @ 1:50 πμ

  10. Πολύ ωραία.

    Να διευκρινίσω εδώ ότι στην (*) χρησιμοποίησες «άθροιση κατά μέρη»: \sum_{s=1}^\infty s(a_s-a_{s+1}) = \sum_{s=1}^\infty a_s.

    Πριν από 2-3 χρόνια είχα συναντήσει αυτό το ερώτημα. Μέχρι σήμερα δεν ήξερα αυτή τη «στοιχειώδη» λύση. Η μόνη λύση που είχα καταφέρει να σκεφτώ χρησιμοποιούσε p-αδικούς αριθμούς και μπορείτε να τη βρείτε εδώ (αγγλικά).

    Στη γλώσσα των p-αδικών αριθμών είναι πολύ απλή η λύση, σχεδόν φυσιολογική αν κανείς έχει χωνέψει λίγο τη σχετική ορολογία. Αν κάποιος δεν ξέρει τι είναι αυτοί οι p-αδικοί αριθμοί τότε ελπίζω να του κεντρίσει αυτή η λύση το ενδιαφέρον για να μάθει (εγώ τουλάχιστον μαθαίνω πιο εύκολα όταν έχω κίνητρο).

    Μπορείτε επίσης να δείτε το σχετικό άρθρο:

    R.C. Alperin, p-adic binomial coefficients \bmod p, The American Mathematical Monthly, Vol. 92, No. 8 (Oct., 1985), pp. 576-578.

    Μου αρέσει!

    Σχόλιο από Mihalis Kolountzakis — 4 Μαΐου, 2009 @ 8:41 πμ

  11. Άλλη μια στοιχειώδης λύση (όχι και τόσο ουσιαστικά διαφορετική) βασισμένη πάνω στην ιδέα του nikkaram είναι η εξής: Έστω m!=q^rk, όπου (q,k)=1. Έστω τώρα \bar{q},\bar{k} ακέραιοι ώστε q\bar{q}+k\bar{k}=1. Φυσικά, (\bar{q},k)=1. Θέτουμε A=q^{m+r}{a/q \choose m}, οπότε:

    \displaystyle \bar{q}^{m}A =q^r\frac{\prod_{i=0}^{m-1}(a\bar{q}-iq\bar{q})}{m!}=q^r\frac{ku+\prod_{i=0}^{m-1}(a\bar{q}-i)}{m!}=u+q^r{{a\bar{q}} \choose m}.

    για κάποιο ακέραιο u. Επομένως \bar{q}^{m}A\in\mathbb{Z}. Είναι επίσης φανερό ότι

    \displaystyle kA=\prod_{i=0}^{m-1}(a-iq)\in\mathbb{Z}.

    Εφόσον (\bar{q},k)=1 έχουμε ότι θα πρέπει A\in\mathbb{Z}.

    Μου αρέσει!

    Σχόλιο από Michalis Loulakis — 5 Μαΐου, 2009 @ 12:58 πμ

  12. «Συμπαγές» αλλά τέλειο.

    Μου αρέσει!

    Σχόλιο από Mihalis Kolountzakis — 5 Μαΐου, 2009 @ 9:55 πμ

  13. Μια διαφορετική λύση: Παρατηρώ ότι αρκεί να αποδείξουμε το θεώρημα για a=1. Πράγματι, τo \binom{a/q}{m} ισούται με τον συντελεστή του x^m στο ανάπτυγμα

    \displaystyle (1+x)^{a/q} = ((1+x)^{1/q})^a = \left( \sum\limits_{k=0}^{\infty} \binom{1/q}{k}x^k \right)^a.

    Άρα

    \displaystyle \binom{a/q}{m} = \sum\limits_{\substack{k_0 + \cdots + k_m = a \\ k_1 + 2k_2 + \cdots + mk_m = m}} \binom{a}{k_0 , k_1 , \ldots , k_m}\binom{1/q}{0}^{k_0} \cdots \binom{1/q}{m}^{k_m}.

    Θα αποδείξω τώρα το ζητούμενο με επαγωγή στο m.

    Για m=0,1 είναι προφανές. Βάζοντας όπου a = q στην πιο πάνω ισότητα (για m \geqslant 2) παίρνω

    \displaystyle 0 = \binom{q}{1} \binom{1/q}{0}^{m-1} \binom{1/q}{m} + \sum\limits_{\substack{k_0 + \cdots + k_{m-1} = a \\ k_1 + 2k_2 + \cdots + {m-1}k_{m-1} = m}} \binom{a}{k_0 , k_1 , \ldots , k_m}\binom{1/q}{0}^{k_0} \cdots \binom{1/q}{m-1}^{k_{m-1}}

    όπου ο πρώτος όρος του αθροίσματος είναι ο μοναδικός όρος με k_m = 1. Άρα

    \displaystyle \binom{1/q}{m} = - \frac{1}{q} \sum\limits_{\substack{k_0 + \cdots + k_{m-1} = q \\ k_1 + 2k_2 + \cdots + {m-1}k_{m-1} = m}} \binom{q}{k_0 , k_1 , \ldots , k_m}\binom{1/q}{0}^{k_0} \cdots \binom{1/q}{m-1}^{k_{m-1}}

    το οποίο επαγωγικά έχει την ζητούμενη ιδότητα.

    (Δεν έχω χρησιμοποιήσει πουθενά ότι ο q είναι πρώτος. Ελπίζω να μην έχω κάνει πουθενά λάθος.)

    Μου αρέσει!

    Σχόλιο από Δημήτρης — 5 Μαΐου, 2009 @ 11:27 μμ

  14. Πάρα πολύ ωραία, σωστή κι αυτή η μέθοδος.

    Όντως το q δε χρειάζεται να είναι πρώτος. Και η μέθοδος με τους p-αδικούς αριθμούς που έχω περιγράψει παραπάνω δίνει, ακριβώς όπως είναι γραμμένη, ότι οι μόνοι πρώτοι που εμφανίζονται στον παρανομαστή του {a/q \choose m} είναι αυτοί που συμμετέχουν στον ακέραιο q. Πολλαπλασιάζοντας μετά αριθμητή και παρανομαστή με τον κατάλληλο ακέραιο μπορούμε να εμφανίσουμε δύναμη του q στον παρανομαστή (το κλάσμα βέβαια δεν είναι αναγκαστικά ανάγωγο μετά από αυτή την πράξη).

    Μου αρέσει!

    Σχόλιο από Mihalis Kolountzakis — 6 Μαΐου, 2009 @ 10:24 πμ


RSS feed for comments on this post. TrackBack URI

Σχολιάστε

Blog στο WordPress.com.