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

Se p è primo, valgono le seguenti congruenze:

  • Il coefficiente binomiale C(p, k) è multiplo di p e Il coefficiente binomiale C(p, k) diviso p dà resto -1 alla k per 1 ≤ kp – 1;

  • Il coefficiente binomiale C(p + 1, k) è multiplo di p, per 2 ≤ kp – 1;

  • I coefficienti binomiali C(2p - 1, p - 1) e C(2p - 1, p) divisi per il cubo di p danno resto 1, se p > 3 (teorema di Wolstenholme, 1862) e quindi Il coefficiente binomiale C(2p, p) diviso per il cubo di p dà resto 2; più in generale Il coefficiente binomiale C(kp - 1, p) diviso per il cubo di p dà resto k - 1, se p > 3 (Guérin, 1916);

  • Il coefficiente binomiale C(4p - 1, p - 1) è congruente a C(4p, p) – 1 modulo p^5, per p > 5 (Zhi-Wei Sun e D. Wan, 2007);

  • Il coefficiente binomiale C(2n, n) diviso per il cubo di p dà resto meno 1 alla n per 2 alla 4n 2, se p =2n + 1 è maggiore di 3 (F. Morley, 1895);

  • Congruenza soddisfatta dal coefficiente binomiale C(n1 * p + n2, k1 * p + k2), per n2 e k2 minori di p (Lucas 1877);

  • Congruenza soddisfatta dal coefficiente binomiale C(n, k) (Lucas 1877) e in particolare Il coefficiente binomiale C(n + p, p) diviso p dà resto 1, se n < p, e Il coefficiente binomiale C(2p, p) diviso p dà resto 2 (che è anche un corollario del teorema di Wolstenholme, come mostrato sopra);

  • Congruenza soddisfatta dal coefficiente binomiale C(n, k), se Coefficiente binomiale C(n, k) non è divisibile per p e kn mod pm;

  • Congruenza soddisfatta dal coefficiente binomiale C(np^a, kp^b), per p > 2 e ab (N. Robbins, 1988);
  • Congruenza soddisfatta dal coefficiente binomiale C(np^a, kp^b), per p > 3 e abc;

  • Congruenza soddisfatta dal coefficiente binomiale C(p - 1, (p - 1) / 2), per p > 2; questa congruenza fu dimostrata da R.W. Gosper, che congetturò che la relazione valesse solo per i primi; Skiena trovò nel 1990 il controesempio 5907 = 3 • 11 • 179. Vardi nel 1991 dimostrò che i quadrati dei primi di Wieferich sono controesempi e che se pk soddisfa la relazione, con p primo e k > 3, anche pk – 1 la soddisfa. Gli unici controesempi noti minori di 13 milioni sono 5907, 10932 e 35112;

  • Congruenza soddisfatta dal coefficiente binomiale C(p - 1, (p - 1) / 2), per p > 3 (Nielsen, 1913);

  • Congruenza soddisfatta dal coefficiente binomiale C(p - 1, (p - 1) / 2), per p > 3 (Emma Lehmer, 1937);

  • Congruenza soddisfatta dal coefficiente binomiale C(p - 1, (p - 1) / 2), per p > 3 (Emma Lehmer, 1937);

  • Congruenza soddisfatta dal coefficiente binomiale C(p - 1, (p - 1) / 2), per p > 5 (Emma Lehmer, 1937).

 

Formula per il resto della divisione del coefficiente binomiale C(np, kp) per p^t (congruenza di Jacobsthal – Kazandzidis), dove t è l’esponente della massima potenza di p che divide p3nk(nk) per p primo e maggiore di 3 (E. Jacobsthal, 1952) e in particolare Formula per il resto della divisione del coefficiente binomiale C(np, kp) per p^3 (W. Ljunggren, 1952), Formula per il resto della divisione del coefficiente binomiale C(2p^2, p^2) per p^6 e Formula per il resto della divisione del coefficiente binomiale C(2p^3, p^3) per p^9. Nel 2008 C. Helou e G. Terjanian dimostrarono che come esponente t può essere preso quello della massima potenza di p che divide p^3 * n * k * (n – k) *C(n, k). Nel 2008 Z.W. Sun e D.M. Davis dimostrarono che per qualsiasi primo dispari p, come esponente t può essere preso quello della massima potenza di p che divide p2n2.

 

Per altre congruenze analoghe v. numeri di Wolstenholme.

 

Formula per il resto della divisione del coefficiente binomiale C(n, m) per p, per p primo, dove nk e mk sono le cifre della rappresentazione di n e k in base p (Lucas, 1878); di conseguenza per p primo, Coefficiente binomiale C(n * p, m * p) congruente al coefficiente binomiale C(n, m) modulo p e  se sommando nk e k in base p c’è un riporto, Coefficiente binomiale C(n, k) è divisibile per p.

 

Nel 1919 Charles Babbage dimostrò che Il coefficiente binomiale C(2p - 1, p) diviso per il quadrato di p dà resto 1, se p è primo e maggiore di 2 e suppose che la congruenza valesse solo per i primi, ma in seguito venne trovato il controesempio 16843 = 2 ∙ 19 ∙ 443, insieme con tutte le sue potenze.

 

Se p è primo, valgono le seguenti congruenze, coinvolgenti coefficienti binomiali, numeri armonici Hn, numeri armonici generalizzati Hn, k e numeri di Bernoulli Bn:

  • Congruenza soddisfatta dal coefficiente binomiale C(2p - 1, p), se p > 3 (J.W.L. Glaisher, 1900);

  • Congruenza soddisfatta dal coefficiente binomiale C(2p - 1, p), se p > 7 (R.J. McIntosh, 1995);

  • Congruenza soddisfatta dal coefficiente binomiale C(2p - 1, p), se p > 7 (R.J. McIntosh, 1995);

  • Congruenza soddisfatta dal coefficiente binomiale C(2p - 1, p), se p > 5 (J. Zhao, 2007);

  • Congruenza soddisfatta dal coefficiente binomiale C(2p - 1, p), se p > 5 (R.J. McIntosh, 1995);

  • Congruenza soddisfatta dal coefficiente binomiale C(2p - 1, p), se p > 5 (J.W.L. Glaisher, 1900);

  • Congruenza soddisfatta dal coefficiente binomiale C(2p - 1, p), se p > 5 (Ernst Jacobsthal, 1949);

  • Congruenza soddisfatta dal coefficiente binomiale C(2p - 1, p), se p > di 5; la congruenza può essere anche scritta come Congruenza soddisfatta dal coefficiente binomiale C(2p - 1, p) (Roberto Tauraso, 2010);

  • Congruenza soddisfatta dal coefficiente binomiale C(2p - 1, p), per p > 3 (C. Helou e G. Terjanian, 2008);

  • Congruenza soddisfatta dal coefficiente binomiale C(2p - 1, p), per p > 7 (Romeo Meštrović, 2010);

  • Congruenza soddisfatta dal coefficiente binomiale C(2p - 1, p), se p > 3 (Romeo Meštrović, 2010);

  • Congruenza soddisfatta dal coefficiente binomiale C(2p - 1, p), se p > 5; la congruenza può essere anche scritta come Congruenza soddisfatta dal coefficiente binomiale C(2p - 1, p) (Roberto Tauraso, 2011).

 

Se p è primo, valgono le seguenti congruenze per rapporti di coefficienti binomiali:

  • Congruenza soddisfatta da C(2p - 1, p) / C(2p, p)^3 (Andrew Granville, 1995);

  • Congruenza soddisfatta da C(n * p, k * p) / C(n, k), per p > 3 (C. Helou e G. Terjanian, 2008) e in particolare Congruenza soddisfatta dal coefficiente binomiale C(n * p - 1, p - 1), per p > 3 (J.W.L. Glaisher, 1900), Congruenza soddisfatta dal coefficiente binomiale C(2p - 1, p - 1) e Congruenza soddisfatta dal coefficiente binomiale C(n * p - 1, p - 1);

  • Congruenza soddisfatta da C(n * p, k * p) / C(n, k), per p primo maggiore di 5 e Formula per la definizione di w (J. Zhao, 2010);

  • Congruenza soddisfatta da C(n * p, k * p) / C(n, k), per p > 3 (C. Helou e G. Terjanian, 2008).

 

Se p è un primo maggiore di 2, valgono le seguenti congruenze, coinvolgenti somme di coefficienti binomiali:

  • Congruenza soddisfatta da una somma di coefficienti binomiali;

  • Congruenza soddisfatta da una somma di coefficienti binomiali (Zhi-Wei Sun, 2010);

  • Congruenza soddisfatta da una somma di coefficienti binomiali, dove En è un numero di Eulero (Zhi-Wei Sun, 2010),

  • Congruenza soddisfatta da una somma di coefficienti binomiali (Zhi-Wei Sun, 2010).

 

Se p è un primo maggiore di 3, valgono le seguenti congruenze coinvolgenti somme di coefficienti binomiali:

  • Congruenza soddisfatta da una somma di coefficienti binomiali;

  • Congruenza soddisfatta da una somma di coefficienti binomiali, dove En è un numero di Eulero (Zhi-Wei Sun, 2010);

  • Congruenza soddisfatta da una somma di coefficienti binomiali, dove En è un numero di Eulero (Zhi-Wei Sun, 2013);

  • Congruenza soddisfatta da una somma di coefficienti binomiali, dove Simbolo di Legendre (n, p) è il simbolo di Legendre (Zhi-Wei Sun e Roberto Tauraso, 2011);

  • Congruenza soddisfatta da una somma di coefficienti binomiali, tranne nel caso m = 0, a = 0, b = 1 (M. Chamberland e K. Dilcher, 2006);

  • Congruenza soddisfatta da una somma di coefficienti binomiali, (M. Chamberland e K. Dilcher, 2006);

  • Congruenza soddisfatta da una somma di coefficienti binomiali, per n > 0 (H. Pan, 2009) e quindi Congruenza soddisfatta da una somma di coefficienti binomiali; nel 2011 Romeo Meštrović dimostrò che la congruenza vale anche per n = –1, ossia che Congruenza soddisfatta da una somma di coefficienti binomiali  e quindi Congruenza soddisfatta da una somma di coefficienti binomiali;

 

T.X. Cai e Andrew Granville dimostrarono nel 2002 che se p è primo e maggiore di 3, valgono le seguenti congruenze coinvolgenti somme di coefficienti binomiali:

  • Congruenza soddisfatta da una somma di coefficienti binomiali, per n pari.

  • Congruenza soddisfatta da una somma di coefficienti binomiali, per n dispari;

  • Congruenza soddisfatta da una somma di coefficienti binomiali, per n pari;

  • Congruenza soddisfatta da una somma di coefficienti binomiali, per n dispari.

 

Se p è un primo dispari diverso da 5, valgono le seguenti congruenze coinvolgenti somme di coefficienti binomiali:

  • Congruenza soddisfatta da una somma di coefficienti binomiali (Zhi-Wei Sun e Roberto Tauraso, 2010);

  • Congruenza soddisfatta da una somma di coefficienti binomiali (Zhi-Wei Sun, 2010);

  • Congruenza soddisfatta da una somma di coefficienti binomiali (Hao Pan e Zhi-Wei Sun, 2011);

  • Congruenza soddisfatta da una somma di coefficienti binomiali (Zhi-Wei Sun, 2010).

 

Se p è un primo maggiore di 5, valgono le seguenti congruenze coinvolgenti somme di coefficienti binomiali:

  • Congruenza soddisfatta da una somma di coefficienti binomiali, dove Hn, k è un numero armonico generalizzato (Roberto Tauraso, 2010);

  • Congruenza soddisfatta da una somma di coefficienti binomiali, dove Hn, k è un numero armonico generalizzato, (Roberto Tauraso, 2010);

 

Se p è primo e non è un residuo quadratico modulo 7, valgono le seguenti congruenze coinvolgenti somme di coefficienti binomiali:

  • Congruenza soddisfatta da una somma di coefficienti binomiali (Zhi-Hong Sun);

  • Congruenza soddisfatta da una somma di coefficienti binomiali (proposta nel 2011 da Zhi-Wei Sun e dimostrata da Zhi-Hong Sun);

 

Varie altre congruenze per somme di coefficienti binomiali sono state proposte da Zhi-Wei Sun (v. congetture di Zhi-Wei Sun).

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.
  • Surányi, János;  Topics in the Theory of Numbers, Springer, 2003.
  • 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.