Calcolatrice del triangolo di Pascal

C(n, k) = C(n-1, k-1) + C(n-1, k); C(n, 0) = C(n, n) = 1; somma della riga = 2^n

n

Il numero di righe da stampare, contando il singolo 1 in cima come riga 0. Quindi n righe significa le righe da 0 a n - 1, e l'ultima riga stampata contiene n voci. L'ingresso va da 1 a 53, e il tetto non ha niente a che vedere con le dimensioni dello schermo: guarda la voce sulla somma della riga qui sotto, che è la quantità che finisce lo spazio per prima

k

La posizione dentro una riga, contata da 0 a partire dal bordo sinistro. La riga n ha voci per k = 0 fino a k = n, cioè n + 1 numeri. Le due posizioni di bordo sono speciali: C(n, 0) e C(n, n) valgono entrambe 1, ed è quella coppia di 1 che scende lungo i fianchi del triangolo. Tutto ciò che sta strettamente in mezzo è la somma di due voci della riga sopra

C(n-1, k-1) + C(n-1, k)

La regola che costruisce tutto quanto, ed è quella che la pagina segue. La voce in posizione k della riga n è la somma delle due voci sopra di essa — quella immediatamente in alto a sinistra e quella immediatamente in alto a destra, ed è per questo che i bordi vedono un solo numero e restano a 1. Si procede per addizione invece che con la formula dei fattoriali, così ogni valore intermedio è esatto e il triangolo sullo schermo è letteralmente la sequenza di addizioni che la pagina ha eseguito

C(n, k) = n! / (k! (n-k)!)

L'altra faccia dello stesso numero: il coefficiente binomiale, che conta in quanti modi si possono scegliere k elementi fra n quando l'ordine non conta. Dà lo stesso valore della regola additiva ed è ciò che i numeri della riga significano quando il triangolo serve a contare invece che a fare algebra. La pagina non lo usa per calcolare, perché allora sarebbero due aritmetiche separate che potrebbero allontanarsi

2^n

La somma della riga n, e il motivo per cui l'ingresso si ferma dove si ferma. Somma una riga qualsiasi e ottieni sempre una potenza di due: la riga 0 somma a 1, la riga 1 a 2, la riga 2 a 4 e la riga 6 a 64. Il raddoppio a ogni riga è il motivo per cui la somma esce dall'intervallo rappresentabile esattamente prima di qualunque singolo coefficiente: la riga 52 somma a 4.503.599.627.370.496, la riga 53 a 9.007.199.254.740.992, che è uno oltre l'ultimo intero che un double tiene esatto

1, 6, 15, 20, 15, 6, 1

La riga 6 stampata, che è l'ultima riga delle sette predefinite. Rileggila contro la riga sopra e ogni voce è la somma di due vicini: 6 è 1 + 5, 15 è 5 + 10, 20 è 10 + 10, e poi la riga si specchia. La riga è simmetrica rispetto al suo centro, sempre, perché scegliere k elementi da tenere e scegliere n - k elementi da scartare sono la stessa scelta contata due volte

Il triangolo è il modo più rapido per sviluppare un binomio a mano. Per moltiplicare (x + y) alla sesta potenza basta leggere la riga 6 direttamente dalla pagina e scrivere 1x⁶ + 6x⁵y + 15x⁴y² + 20x³y³ + 15x²y⁴ + 6xy⁵ + 1y⁶, senza moltiplicare nessun polinomio. Un singolo coefficiente è quello che ti serve quando ti interessa un solo termine, e la pagina delle combinazioni lo calcola direttamente da n e k senza costruire le righe in mezzo. Le domande di probabilità con due esiti usano gli stessi numeri: la probabilità di ottenere esattamente 4 teste in 10 lanci è C(10, 4) diviso 2¹⁰, e quel 1024 al denominatore è la somma della riga 10. Il triangolo risponde anche a domande di conteggio che sembrano non c'entrare — il numero di percorsi su una griglia da un angolo a quello opposto, il numero di modi di raggiungere una casella particolare quando puoi muoverti solo a destra e in basso, e il conteggio dei sottoinsiemi di una data dimensione. Quando la domanda è quali sono i numeri e non che cosa significano, questa pagina li stampa; quando è in quante combinazioni diverse può andare a finire qualcosa, la pagina delle combinazioni è la strada più corta; e quando la domanda riguarda i numeri di Fibonacci che si nascondono nelle diagonali, la pagina di Fibonacci copre direttamente quella successione.

1. Sette righe, che finiscono con 1 6 15 20 15 6 1

   1. La riga 0 è 1, e la riga 1 è 1, 1 — i due bordi di ogni riga valgono sempre 1
   2. Riga 2: 1 + 1 = 2 al centro, e viene 1, 2, 1
   3. Riga 3: 1 + 2 = 3 due volte, e viene 1, 3, 3, 1; riga 4: 1 + 3 = 4, 3 + 3 = 6, e viene 1, 4, 6, 4, 1
   4. La riga 5 e la riga 6 continuano allo stesso modo, e finiscono con 1, 6, 15, 20, 15, 6, 1
   5. Somma la riga 6 da sinistra a destra: 1 + 6 + 15 + 20 + 15 + 6 + 1 = 64, che è due elevato alla sesta

   L'ingresso predefinito. Ci sono due cose che vale la pena controllare sullo schermo. Primo, ogni numero è la somma dei due che stanno sopra di lui: 15 è 5 + 10, 20 è 10 + 10, e la riga è simmetrica perché il 20 sta al centro di sette voci e si accoppia da entrambe le parti. Secondo, la somma della riga raddoppia ogni volta — 1, 2, 4, 8, 16, 32, 64 — quindi chi sa che la riga sopra somma a 32 può prevedere questa prima ancora di addizionarla. Quel raddoppio è lo stesso fatto dei due 1 sui bordi: ogni riga sopra contribuisce il proprio totale due volte, una metà a sinistra e una metà a destra.

2. Quattro righe, il triangolo utile più corto

   1. La riga 0 è 1; la riga 1 è 1, 1
   2. La riga 2 è 1, 2, 1, con il 2 che viene da 1 + 1
   3. La riga 3 è 1, 3, 3, 1, con ogni 3 che viene da 1 + 2
   4. Somma l'ultima riga: 1 + 3 + 3 + 1 = 8, che è due elevato alla terza

   La riga 3 è l'ultima qui, ed è il punto in cui il triangolo diventa interessante: 1, 3, 3, 1 sono i coefficienti di (x + y)³, quindi x³ + 3x²y + 3xy² + y³ si può scrivere direttamente da questa riga senza moltiplicare niente. È anche l'ultima riga abbastanza piccola da verificare a mano in pochi secondi, ed è per questo che vale la pena guardarla prima di quelle più lunghe. Nota che 4 righe significa le righe da 0 a 3: il numero che digiti è un numero di righe, non l'indice della riga più grande.

3. Una riga sola, il caso banale

   1. La riga 0 è un solo 1, e non ha niente sopra da sommare
   2. Hai chiesto una riga e una riga viene stampata
   3. La somma della riga è 1, che è due elevato alla zero

   L'ingresso più piccolo che la pagina accetta, ed è accettato invece di essere trattato come vuoto. Un triangolo di una riga non è degenere: è il caso base da cui si costruisce ogni riga successiva. Leggerlo conferma anche l'indicizzazione: chiedere 1 riga dà la riga 0, non la riga 1, e questo conta appena confronti il triangolo con uno sviluppo binomiale. Che la somma sia 1 e non 0 è, in aritmetica, la stessa affermazione del fatto che la cima del triangolo è un unico 1.

Il numero di righe deve essere un numero intero da 1 a 53. Il tetto esiste perché ogni numero stampato deve essere uno che il computer rappresenta ancora esattamente, e oltre quel punto due interi vicini collassano sullo stesso valore: le cifre stampate sembrano ancora del tutto normali, semplicemente non rappresentano più il numero che dichiarano. È la somma della riga a cedere per prima: la riga 52 somma a 4.503.599.627.370.496 e la riga 53 a 9.007.199.254.740.992, uno oltre il più grande intero che un double tiene esatto. I singoli coefficienti resisterebbero fino alla riga 56 — il primo oltre la linea è C(57, 28) — ma un triangolo si stampa una riga alla volta, quindi è la somma a decidere. Zero righe viene rifiutato: un triangolo vuoto non stampa niente, quindi non c'è nessuna risposta da dare. Le frazioni di riga vengono rifiutate invece di essere arrotondate, dato che due righe e mezza non esistono. Le righe tornano come una riga piatta di numeri separati da virgole, con le righe separate da punti e virgola e nessun separatore di migliaia da nessuna parte, quindi un coefficiente grande si stampa come 184756 e non come 184.756. Su un triangolo largo questo significa una riga lunga da scorrere. La tabella di riferimento qui sotto mostra le prime sette righe invece di seguire il tuo ingresso, e nessuna riga è raggiungibile chiedendola direttamente: la pagina stampa sempre dall'alto verso il basso.

A che cosa serve il triangolo di Pascal?

Soprattutto a sviluppare i binomi. Le voci della riga n sono i coefficienti che ottieni moltiplicando (x + y) elevato alla n, quindi la riga 6 ti fa scrivere subito i sette termini di (x + y)⁶ senza moltiplicare fra loro nessun polinomio. Gli stessi numeri contano le combinazioni: C(n, k) è la voce in posizione k della riga n, quindi rispondono a domande come in quanti modi si possono scegliere 4 persone fra 10. Compaiono anche nel calcolo delle probabilità, dove la probabilità di ottenere esattamente 4 teste in 10 lanci di moneta è C(10, 4) su 2¹⁰ — e quel 1024 è la somma della riga 10. Anche il conteggio dei percorsi su una griglia li usa: il numero di tragitti da un angolo a quello opposto muovendosi solo a destra e in basso è una voce del triangolo.

Perché l'ingresso si ferma a 53 righe?

Perché la somma della riga smette di essere un intero che il computer può rappresentare esattamente. La riga 52 somma a 4.503.599.627.370.496 e la riga 53 a 9.007.199.254.740.992, e quel secondo numero è uno oltre il valore più grande che un numero in doppia precisione tiene esatto. Oltre quel punto due interi vicini diventano lo stesso valore, quindi le cifre stampate sembrano normali ma non rappresentano più il numero che dichiarano. I singoli coefficienti durerebbero più a lungo — il primo oltre la linea è C(57, 28), nella riga 57 — ma un triangolo si stampa una riga alla volta, quindi è la somma a decidere. Pubblicare una riga il cui totale è sbagliato e le cui singole voci sono giuste sarebbe una cosa confusa da mettere online.

Perché l'ultima riga viene stampata due volte?

Perché su un triangolo grande l'ultima riga è l'unica parte che interessa alla maggior parte dei lettori, e trovarla dentro una lunga riga di cifre è un lavoro. Chiedi 40 righe e il triangolo è un muro di numeri in cui la riga che ti interessa sta all'estrema destra; l'ultima riga è quella stessa riga da sola, in una dimensione leggibile. Vengono dallo stesso calcolo, quindi non possono contraddirsi. La somma della riga viene stampata una terza volta per lo stesso motivo: è un singolo numero che risponde a una domanda a cui la riga di cifre non risponde a colpo d'occhio.

Le righe partono da 0 o da 1?

Da 0, che è la convenzione con cui si indicizzano di solito i coefficienti. C(n, k) indica la voce in posizione k della riga n, quindi l'1 in cima è la riga 0 e chiedere 7 righe dà le righe da 0 a 6, finendo con 1, 6, 15, 20, 15, 6, 1 — sette numeri, perché la riga n ha sempre n + 1 voci. Questo conta quando confronti il triangolo con uno sviluppo binomiale: la riga dei coefficienti di (x + y)⁶ è la riga 6, non la riga 7. Il numero che digiti è un numero di righe, non l'indice della riga più grande.

Che cos'è la somma di una riga, e perché è sempre una potenza di due?

Somma una riga qualsiasi e ottieni 2 elevato all'indice di quella riga: la riga 0 dà 1, la riga 6 dà 64, la riga 10 dà 1024. Il motivo è la regola che costruisce il triangolo. Ogni riga è fatta dalla riga sopra sommata a se stessa spostata di una posizione, quindi ogni numero della riga sopra viene contato due volte in quella sotto: una a sinistra e una a destra. Raddoppiare ogni volta il totale dà le potenze di due. Lo stesso fatto letto in un altro modo: la somma della riga n conta tutti i sottoinsiemi di un insieme di n elementi, e un insieme di n elementi ha 2ⁿ sottoinsiemi. È per questo che il 1024 che sta sotto la probabilità di dieci lanci di moneta esce direttamente dalla riga 10.

Da dove vengono i numeri di Fibonacci in questo triangolo?

Dalle diagonali basse. Somma i numeri lungo una linea che sale verso sinistra — per esempio 1, poi 4, poi 3 — e i totali progressivi vengono 1, 1, 2, 3, 5, 8, 13. Quelli sono i numeri di Fibonacci, in cui ognuno è la somma dei due precedenti. Il motivo è che ogni voce di una diagonale è a sua volta costruita dalle due voci sopra di sé, una delle quali sta sulla stessa diagonale e una sulla diagonale successiva, quindi le diagonali ereditano direttamente la ricorrenza di Fibonacci. La calcolatrice di Fibonacci copre quella successione per conto suo se vuoi seguirla più avanti.

• Pascal's Triangle — the array of binomial coefficients, its additive rule, and the identities that fall out of it — Wolfram MathWorld (United States)
• Binomial Coefficient — what C(n, k) counts, the factorial formula, and why the additive rule gives the same values — Wolfram MathWorld (United States)
• Binomial Theorem — the expansion of (x + y)^n, whose coefficients are the rows of the triangle — Wolfram MathWorld (United States)
• Binomio — lo sviluppo della potenza di un binomio, i cui coefficienti sono le righe del triangolo di Pascal — Treccani, Istituto della Enciclopedia Italiana (Italia)