Kombinatsiyalar soni va chaqiruvlar

$C(n, k)$ — $n$ ta narsadan $k$ tasini tanlash usullari soni. U Paskal formulasi bo'yicha rekursiv hisoblanadi:

C(n, k):
    if k == 0 or k == n: return 1
    return C(n - 1, k - 1) + C(n - 1, k)

$C(n, k)$ ni va shu funksiya jami necha marta chaqirilishini toping (birinchi chaqiruv ham sanaladi).

Bitta qatorda $n$ va $k$ ($0 \le k \le n \le 20$).

Bitta qatorda ikkita son: $C(n, k)$ va chaqiruvlar soni.

$C(4, 2)$: C(4,2) → C(3,1), C(3,2); C(3,1) → C(2,0), C(2,1); C(2,1) → C(1,0), C(1,1); C(3,2) ham xuddi shunday $5$ ta chaqiruv. Jami $1 + 5 + 5 = 11$ ta chaqiruv, $C(4, 2) = 6$. Global hisoblagich bilan sanang.