Pascals identitet

Den här artikeln behöver källhänvisningar för att kunna verifieras. (2022-09) Åtgärda genom att lägga till pålitliga källor (gärna som fotnoter). Uppgifter utan källhänvisning kan ifrågasättas och tas bort utan att det behöver diskuteras på diskussionssidan.

Pascals identitet, matematiskt uttryck för binomialkoefficienter, namngivet efter matematikern Blaise Pascal. Identiten säger att

${\displaystyle {n-1 \choose k}+{n-1 \choose k-1}={n \choose k}}$

där ${\displaystyle 1\leq k\leq n}$, ${\displaystyle k,n\in \mathbb {N} }$.

Pascals identitet är lätt att förstå om man betraktar den ur ett kombinatoriskt perspektiv. Eftersom ${\displaystyle {\tbinom {a}{b}}}$ är antalet sätt vi kan skapa en delmängd med b element ur en mängd med a element, tecknar ${\displaystyle {\tbinom {n}{k}}}$ hur många olika distinkta delmängder med k element man kan få ur en mängd med n element.

Tag nu ett element X ur mängden med n element. För varje delmängd med k element finns då två alternativ – antingen hör X till delmängden eller så gör det inte det.

• Om X tillhör delmängden, behöver man nu endast välja k-1 element bland de n-1 som återstår för att få k stycken. Detta kan göras på ${\displaystyle {\tbinom {n-1}{k-1}}}$ sätt.
• Om X inte tillhör delmängden, behöver man nu välja alla k element ur den n-1 element stora delmängd som innehåller alla element utom X. Det kan göras på ${\displaystyle {\tbinom {n-1}{k}}}$ sätt.

Vi kan alltså dra slutsatsen att antalet sätt att skapa en delmängd med k element ur en mängd med n element är lika många som att skapa en delmängd med k-1 element ur en mängd med n-1 element plus antalet sätt man kan skapa en delmängd med k element ur en mängd med n-1 element.

Vilket skulle visas.

Vi skall visa att

${\displaystyle {n \choose k}+{n \choose k-1}={n+1 \choose k}}$

Vänsterledet kan skrivas om som

${\displaystyle {\frac {n!}{k!(n-k)!}}+{\frac {n!}{(k-1)!(n-(k-1))!}}}$

Genom att hitta minsta gemensamma nämnare och förenkla fås

${\displaystyle {\frac {n!}{k!(n-k)!}}+{\frac {n!}{(k-1)!(n-k+1)!}}={\frac {(n-k+1)n!}{(n-k+1)k!(n-k)!}}+{\frac {kn!}{k(k-1)!(n-k+1)!}}}$

${\displaystyle ={\frac {(n-k+1)n!+kn!}{k!(n-k+1)!}}={\frac {(n+1)n!}{k!((n+1)-k)!}}={\frac {(n+1)!}{k!((n+1)-k)!}}={n+1 \choose k}}$

Vilket skulle visas

• Binomialkoefficienter
• Pascals triangel
• Binomialsatsen