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 coefficienti binomiali, di solito indicati come Coefficiente binomiale C(n, k), secondo la notazione introdotta da von Ettinghausen nel 1826, o C(n, k), sono così chiamati perché compaiono nello sviluppo di potenze di un binomio. Infatti Coefficiente binomiale C(n, k) è il coefficiente di anbnk nello sviluppo di (a + b)n: Formula per (a + b)^n.

 

Sono noti da tempi antichi, forse riscoperti indipendentemente in diverse parti del mondo: compaiono in un testo cinese di Chia Hsien, scritto intorno al 1050, in un manoscritto arabo del 1080 di Omar al-Kayyam, in un testo indiano di Bhaskara Acharya del 1150, in Siyuan yujian (Lo specchio di giada dei quattro elementi), un testo cinese del 1303 di Tshu Shih Chieh. Furono poi studiati da Cardano, Pascal, che costruì con essi il famoso triangolo, dando una semplice regola ricorsiva per calcolarli, Newton, Leibniz, Eulero, Gauss, Erdös: la loro presenza è talmente invasiva nei rami più diversi della matematica che tutti i maggiori matematici sono stati costretti a utilizzarli.

 

Cito solo alcune delle numerosissime applicazioni in matematica combinatoria.

 

Il numero di modi nei quali possono essere scelti k oggetti senza ripetizione da un insieme di n è Coefficiente binomiale C(n, k); se sono ammesse le ripetizioni, cioè se lo stesso oggetto può essere scelto più volte, il numero diventa Coefficiente binomiale C(n, k).

 

Partendo dall’angolo inferiore destro di un reticolo n × m a maglia quadrata si può raggiungere quello opposto, muovendosi solo verso destra e verso l’alto in Numero di percorsi da un vertice a quello opposto in un reticolo n × m modi diversi.

La figura seguente illustra i 15 cammini in un reticolo 4×2.

 

I 15 percorsi da un vertice a quello opposto in un reticolo 3 × 4

 

 

Avendo n coppie di coniugi, il numero di modi di disporli in fila, lasciando una coppia libera di scambiarsi di posto se i due coniugi si trovano uno di seguito all’altro è Numero di modi per disporre n coppie di coniugi in fila (supponendo di definire (–1)! = 1).

 

Il numero di sequenze di n cifre 0 o 1 che abbiano per somma k (ossia contenenti k volte 1) è Numero di sequenze di n cifre 0 o 1 che hanno per somma k.

Il numero di sequenze di n cifre 0 e k cifre 1 è Numero di sequenze di n cifre 0 e k cifre 1.

Il numero di sequenze di n cifre 0 e k cifre 1 che non contengano due 1 adiacenti è Numero di sequenze di n cifre 0 e k cifre 1 che non contengono due 1 adiacenti.

In questi tre esempi le cifre possono essere rimpiazzate da due categorie distinte di oggetti, come palline bianche e nere.

 

Il numero di modi per scomporre n come somma di k interi non negativi, contando separatamente le diverse permutazioni degli addendi, ovvero il numero di modi in cui si possono suddividere n oggetti identici in k insiemi distinguibili (anche vuoti), è Numero di modi per scomporre n come somma di k interi non negativi. Per esempio, 4 può essere scomposto come somma di 3 interi non negativi in Numero di modi per scomporre 4 come somma di 3 interi non negativi modi:

  • 4 = 4 + 0 + 0 (3 permutazioni degli addendi);

  • 4 = 3 + 1 + 0 (6 permutazioni degli addendi);

  • 4 = 2 + 2 + 0 (3 permutazioni degli addendi);

  • 4 = 2 + 1 + 1 (3 permutazioni degli addendi).

Se gli addendi devono essere maggiori di zero, il numero di modi è Numero di modi per scomporre n come somma di k interi maggiori di zero, uguale al numero di modi per suddividere n oggetti indistinguibili in k insiemi non vuoti. Per esempio, 6 può essere scomposto come somma di 3 interi maggiori di zero in Numero di modi per scomporre 6 come somma di 3 interi maggiori di zero modi:

  • 6 = 4 + 1 + 1 (3 permutazioni degli addendi);

  • 6 = 3 + 2 + 1 (6 permutazioni degli addendi);

  • 6 = 2 + 2 + 2 (1 permutazione degli addendi).

Varie altre applicazioni simili si trovano alla voce numero di composizioni.

 

Tra le applicazioni non strettamente combinatorie, ce n’è una particolarmente interessante, che si ricollega ai numeri figurati: il numero di palline che formano una iper-piramide a k dimensioni a facce triangolari (tecnicamente, un simplesso) con n palline lungo ogni spigolo è Numero di modi per scomporre 4 come somma di 3 interi non negativi (v. numeri ipertetraedrici); se k = 2 abbiamo i numeri triangolari, se k = 3 quelli tetraedrici.

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.