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
där , .
Bevis
Kombinatoriskt
Pascals identitet är lätt att förstå om man betraktar den ur ett kombinatoriskt perspektiv. Eftersom är antalet sätt vi kan skapa en delmängd med b element ur en mängd med a element, tecknar 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å 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å 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.
Algebraiskt
Vi skall visa att
Vänsterledet kan skrivas om som
Genom att hitta minsta gemensamma nämnare och förenkla fås
Vilket skulle visas
Se även
- Binomialkoefficienter
- Pascals triangel
- Binomialsatsen