Don't take life too seriously: it's just a temporary situation

Coefficienti binomiali

Algebra  Matematica combinatoria 

Indice

  1. 1. Pagina principale
  2. 2. Proprietà
  3. 3. Formule con coefficienti binomiali
  4. 4. Congruenze con coefficienti binomiali
  5. 5. Divisori dei coefficienti binomiali
  6. 6. Valori

I divisori dei coefficienti binomiali sono stati studiati approfonditamente; riporto alcuni dei risultati più interessanti.

 

Per 0 < 2kn il massimo primo che divide Coefficiente binomiale C(n, k) è maggiore di 1.95k. (T.N. Shorey e R. Tijdeman, 2007).

 

La massima potenza di un primo p che divide Coefficiente binomiale C(n + k, k) è pr, dove r è il numero di riporti che si hanno nel sommare n e k in base p. Questo teorema, dimostrato da Kummer nel 1852, sembrerebbe solo una curiosità matematica, ma ha giocato un ruolo fondamentale nella soluzione del decimo problema di Hilbert, cioè nel dimostrare che non esiste un algoritmo generale per risolvere le equazioni diofantee (v. numeri primi).

Il teorema è equivalente all’affermazione che la massima potenza di un primo p che divide Coefficiente binomiale C(n, k) è uguale al numero di interi non negativi m tali che la parte frazionaria di k diviso p alla m sia maggiore della parte frazionaria di n diviso p alla m.

 

Esiste una costante c tale che se il minimo fattore primo di Coefficiente binomiale C(n, k) è maggiore di k, Limite inferiore per n (Andrew Granville e Olivier Ramaré).

 

I coefficienti binomiali Coefficiente binomiale C(n, k) per k da 1 a n – 1 sono tutti multipli di n se e solo se n è primo, ma la frazione di quelli non multipli tende a zero per n tendente a infinito.

 

Se f(n) è il numero di coefficienti binomiali Coefficiente binomiale C(m, k) divisibili per d, con m < n, tra i possibili Numero di coefficienti binomiali C(m, k) con m e k minori di n, David Singmaster dimostrò nel 1974 che Limite cui tende la frazione di coefficienti binomiali divisibili per un intero qualsiasi, ossia che “quasi tutti” i coefficienti sono divisibili per d, indipendentemente dal valore di d.

 

Se p è primo, nessuno dei coefficienti binomiali Coefficiente binomiale C(n, k) è multiplo di p se è solo se n = tpm – 1, per qualche valore di t minore di p e m intero, anche nullo. In altri termini, nessuno dei numeri della riga n-esima del triangolo di Tartaglia è divisibile per p se e solo se n ha la forma indicata. Nel caso particolare p = 2, t deve essere 1 e otteniamo che le righe contenenti solo numeri dispari sono quelle per n = 2m – 1 (v. Mathematical Diamonds).

 

Se n > 2kCoefficiente binomiale C(n, k) ha almeno un fattore primo maggiore di k; è la formulazione di Erdös di un teorema dimostrato da Sylvester nel 1892, che afferma che il prodotto di k numeri naturali consecutivi magiori di k è divisibile per un primo maggiore di k.

D. Hanson dimostrò nel 1973 che tale prodotto è divisibile per un primo maggiore di Tre mezzi di k, con tre sole eccezioni: 3 • 4, 8 • 9 e 6 • 7 • 8 • 9 • 10.

 

Il numero di coefficienti binomiali Coefficiente binomiale C(n, k) non multipli di un primo p, per 0 ≤ kn, è Formula per il numero di coefficienti binomiali C(n, k) non multipli di p, dove r(m) è il numero di cifre m nella rappresentazione di n in base p; in particolare il numero totale di coefficienti binomiali Coefficiente binomiale C(n, k) dispari, per 0 ≤ kn, è 2m, dove m il numero di 1 nella rappresentazione binaria di n. Per esempio 11 = 10112 ha tre 1 nella rappresentazione binaria e la riga per n = 11 ha 23 = 8 numeri dispari.

V. anche costante di Stolarsky – Harborth.

 

Se esiste un numero primo maggiore di 2k e non superiore a nCoefficiente binomiale C(n, k) è divisibile per esso o per un primo superiore, tranne nei casi Coefficiente binomiale C(9, 2), non divisibile per primi maggiori di 4, e Coefficiente binomiale C(10, 3), non divisibile per primi maggiori di 6 (Marilyn Faulkner, 1966). V. anche coefficienti binomiali eccezionali.

 

Se tutti i fattori primi di k dividono m, allora per ogni intero positivo n, mn + 1 divide Coefficiente binomiale C(k * n + m * n, m * n); Nel 2010 Zhi-Wei Sun avanzò la congettura che se Coefficiente binomiale C(kn + mn, mn) è divisibile per mn + 1 per n abbastanza grande, tutti i fattori primi di k dividono m.

 

Erdös dimostrò che per k da 1 a n, almeno uno dei coefficienti Coefficiente binomiale C(n, k) è multiplo di un quadrato, se n > 23, e che per n abbastanza grande almeno uno è multiplo di una potenza m-esima (Erdös e Eynden, 1992).

I valori di n per i quali Coefficiente binomiale C(n, k) non è mai multiplo di un quadrato sono: 1, 2, 3, 5, 7, 11 e 23 (Andrew Granville e Olivier Ramaré). La dimostrazione si basa sul fatto che se il quadrato di un primo p non divide alcuno di questi coefficienti binomiali, allora pr – 1 divide n + 1, dove pr + 1 > npr.

 

Il coefficiente binomiale Coefficiente binomiale C(2 * n - 1, k) è quasi sempre un multiplo di un quadrato; le eccezioni sono in numero finito (Andrew Granville e Olivier Ramaré, 1996). Le eccezioni note sono: 1, 2, 3, 4, 6, 9, 10, 12, 36; se ve ne sono altre sono maggiori di 2300 (Robert Israel, 1015).

E’ possibile che queste siano le uniche perché è stato dimostrato che Coefficiente binomiale C(2 * n - 1, k)è multiplo di 4, a meno che la rappresentazione di n in base 2 sia costituita da uno o due 1 e vari 0, e che è multiplo di 9, a meno che la rappresentazione di 2n in base 3 sia costituita da soli 0 e 2 con al massimo una coppia di 1 consecutivi.

I numeri che soddisfano contemporaneamente questi requisti sono pochissimi e forse in numero finito. I 32 minori di 264 sono: 1, 2, 3, 4, 6, 9, 10, 12, 18, 33, 34, 36, 40, 64, 66, 192, 256, 264, 272, 513, 514, 516, 576, 768, 1026, 1056, 2304, 16392, 65664, 81920, 532480, 545259520, e i relativi coefficienti sono multipli di altri quadrati, tranne nei casi indicati; in particolare, l’ultimo è multiplo di 54 (M. Fiorentini, 2015).

 

Esistono infiniti coefficienti binomiali non multipli di quadrati; in particolare Andrew Granville e Olivier Ramaré dimostrarono che:

  • esiste una costante c tale che vi sono infiniti coefficienti binomiali Coefficiente binomiale C(n, k) non multipli di quadrati con Limiti inferiore e superiore per k;

  • esistono infiniti interi n tali che Coefficiente binomiale C(n, k) non è multiplo di quadrati per tutti i valori di k non superiori a log(n) / 5;

  • gli interi n per i quali vi sono esattamente 2m + 2 coefficienti binomiali Coefficiente binomiale C(n, k) non multipli di quadrati hanno densità asintotica maggiore di zero, ma minore di Limite superiore per la densità asintotica, per una costante c e qualsiasi intero positivo m;

  • fissato k, gli interi n per i quali Coefficiente binomiale C(n, k) non è multiplo di quadrati hanno densità asintotica maggiore di zero.

 

Per altre informazioni sui coefficienti binomiali non multipli di quadrati v. coefficienti binomiali centrali.

 

Coefficiente binomiale C(n, k) non è mai una potenza per Limiti per il valore di k; per k = 2 esistono infiniti quadrati (tutti i numeri che sono contemporaneamente quadrati e triangolari), ma probabilmente nessuna potenza superiore; per k = 3, l’unica potenza è Coefficiente binomiale C(50, 3) (Erdös).

 

Se scriviamo Coefficiente binomiale C(n, k) come prodotto di due termini, dove u è il prodotto dei fattori primi minori di k e v è il prodotto dei restanti, con k diviso 2 minore o uguale a n, è logico attendersi che v > u; in effetti le eccezioni sono solo 12 (E.F. Ecklund, R.B. Eggleton, P. Erdös, J.L. Selfridge, 1978):

  • Coefficiente binomiale C(8, 3),

  • Coefficiente binomiale C(9, 4),

  • Coefficiente binomiale C(10, 5),

  • Coefficiente binomiale C(12, 5),

  • Coefficiente binomiale C(21, 7),

  • Coefficiente binomiale C(21, 8),

  • Coefficiente binomiale C(30, 7),

  • Coefficiente binomiale C(33, 13),

  • Coefficiente binomiale C(33, 14),

  • Coefficiente binomiale C(36, 13),

  • Coefficiente binomiale C(36, 17),

  • Coefficiente binomiale C(56, 13).

Se invece u è il prodotto dei fattori primi minori o uguali a k, vi sono altri casi, in numero finito, quali:

  • Coefficiente binomiale C(9, 3),

  • Coefficiente binomiale C(10, 3),

  • Coefficiente binomiale C(18, 3),

  • Coefficiente binomiale C(28, 5),

  • Coefficiente binomiale C(54, 7),

  • Coefficiente binomiale C(82, 3),

  • Coefficiente binomiale C(162, 3).

 

Il minimo comune multiplo dei coefficienti Coefficiente binomiale C(n, k) per k da 1 a n è uguale al prodotto dei primi minori o uguali a n solo se n è 2, 11 o 23. Tale minimo comune multiplo è uguale al minimo comune multiplo degli interi da 1 a n + 1 diviso per n + 1.

 

Il massimo comun divisore dei coefficienti binomiali Coefficiente binomiale C(n, k), per k da 1 a n e non multiplo di un primo p, è pr, dove pr è la massima potenza di p che divide n.

 

Formula per il massimo comun divisore di coefficienti binomiali (D. Singmaster).

 

Formula per il massimo comun divisore di coefficienti binomiali (Sato, 1975).

 

Coefficiente binomiale C(n, r) e Coefficiente binomiale C(n, s), con r e s maggiori di 0 e minori di n, non sono mai primi tra loro.

 

Nel 2011 Zhi-Wei Sun propose la congettura che ogni elemento delle sequenze Somma di potenze di coefficienti binomiali abbia un fattore primo primitivo, cioè sia multiplo di un primo che non divide nessuno dei precedenti, per n abbastanza grande.

Bibliografia

  • Adler, Andrew;  Coury, John E.;  The Theory of Numbers: a Text and Source Book of Problems, Londra, Jones and Bartlett Publishers, 1995.
  • Andreescu, Titu;  Andrica, Dorin;  Feng, Zuming;  104 Number Theory Problems, Boston, Birkäuser, 2007 -

    Raccolta di problemi utilizzati per agli allenamenti della squadra statunitense per le Olimpiadi di Matematica.

  • Balzarotti, Giorgio;  Lava, Paolo Pietro;  103 Curiosità matematiche, Milano, Hoepli, 2010.
  • Davis, Martin;  Hersh, Reuben;  "Il decimo problema di Hilbert" in Le Scienze, Milano, n. 66, Febbraio 1974, pag. 84 - 92.
  • De Koninck, Jean-Marie;  Those Fascinating Numbers, American Mathematical Society, 2009 -

    Un'inesauribile miniera di notizie sugli interi, informazioni e spunti per approfondimenti.

  • Ecklund, E.F.;  Eggleton, R.B.;  Erdös, Paul;  Selfridge, J.L.;  "On the Prime Factorization of Binomial Coefficients" in Journal of Australian Mathematical Society, a. 26, n. 3, pag. 256 – 269, 1978.
  • Giblin, Peter;  Primes and Programming, Cambridge University Press, 1993.
  • Honsberger, Ross;  Mathematical Diamonds, The Mathematical Association of America, 2003 -

    Una stupenda raccolta di saggi su argomenti disparati.

  • Roberts, Joe;  The Lure of the Integers, The Mathematical Association of America, 1992 -

    Una miniera di informazioni sugli interi.

  • Stanley, Richard P.;  Enumerative Combinatorics, Cambridge University Press, vol. I, 1997.
  • Wells, David;  Prime Numbers, John Wiley & Sons, 2005 -

    Una miniera di informazioni sui numeri primi.

Contattami

Potete contattarmi al seguente indirizzo bitman[at]bitman.name per suggerimenti o segnalazioni d'errori relativi a questo articolo.