Правило суми і добутку

Найбільше застосовуються при доказах у комбінаториці два правила.

Правило суми. Якщо об'єкт a може бути обраний p способами, а об'єкт b - іншими q способами, то вибір “або a, або b” може бути здійснений p+q способами.

Вибори a і b взаємно виключають одне одного. Необхідно, щоб не один зі способів вибору об'єкта a не збігся з Якім-небудь способом вибору об'єкта b. При наявності таких збігів правило суми незастосовне і результат дорівнює p+q-k, де k – це число збігів.

Правило добутку. Якщо об'єкт a може бути обраний p способами і після кожного з таких виборів об'єкт b у свою чергу може бути обраний q способами, то вибір “a і b” у зазначеному порядку можна здійснити pq способами.

Правило використовується в випадках, коли вибори a і b незалежні.