// PR Bab 17, tantangan -- pembahasan.

#include <iostream>
using namespace std;

long long C[20][20];

void siapkan_pascal() {
    for (int n = 0; n < 20; n++) {
        C[n][0] = 1;
        for (int r = 1; r <= n; r++)
            C[n][r] = C[n - 1][r - 1] + C[n - 1][r];
    }
}

long long rumus(int n, int r) {
    return C[n][r];
}

long long cacah(int n, int r) {
    long long banyak = 0;
    for (int mask = 0; mask < (1 << n); mask++) {
        int bit = 0;
        for (int i = 0; i < n; i++) if (mask & (1 << i)) bit++;
        if (bit == r) banyak++;
    }
    return banyak;
}

int main() {
    siapkan_pascal();

    bool semua_cocok = true;
    for (int n = 0; n <= 15; n++)
        for (int r = 0; r <= n; r++)
            if (rumus(n, r) != cacah(n, r)) {
                cout << "berbeda pada n = " << n << ", r = " << r << "\n";
                semua_cocok = false;
            }

    if (semua_cocok) cout << "rumus dan cacahan cocok untuk semua n <= 15\n";

    for (int n = 0; n <= 15; n++) {
        long long jumlah = 0;
        for (int r = 0; r <= n; r++) jumlah += rumus(n, r);
        if (jumlah != (1LL << n)) {
            cout << "jumlah baris " << n << " bukan 2^n\n";
            return 0;
        }
    }
    cout << "jumlah tiap baris sama dengan 2^n\n";
    return 0;
}