Grade 12 · Math for programmingCitește în română

Pascal's triangle (combinations)

Original: Triunghiul lui Pascal (combinări)

O(n²)C++1757 lines2 examples

The idea

The combinations C(i, j), the number of j-element subsets of an i-element set, satisfy C(i, j) = C(i-1, j-1) + C(i-1, j): either we choose element i, or we do not. With C(i, 0) = C(i, i) = 1 we build the table row by row, using only additions (no factorials that would overflow). The program prints rows 0, 1, ..., n of the triangle, then the value C(n, k). For n ≤ 66 all values fit in long long.

Original description (Romanian)

Combinările C(i, j) — numărul de submulțimi cu j elemente ale unei mulțimi cu i elemente — respectă relația C(i, j) = C(i-1, j-1) + C(i-1, j): fie alegem elementul i, fie nu. Cu C(i, 0) = C(i, i) = 1 construim tabelul linie cu linie, folosind doar adunări (fără factoriale care ar depăși). Programul afișează liniile 0, 1, ..., n ale triunghiului, apoi valoarea C(n, k). Pentru n ≤ 66 toate valorile încap în long long.

Complexity
O(n^2)
Grade
Grade 12 (Clasa a XII-a)

Examples

Example 1

Input

5 2

Expected output

1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
10
Example 2

Input

2 3

Expected output

1
1 1
1 2 1
0

The code

Comments are in Romanian, as in the original collection. Edit freely: you can reset at any time.

triunghiul-lui-pascal.cpp
/*
 * Titlu: Triunghiul lui Pascal (combinări)
 * Clasa: 12
 * Capitol: Matematică pentru programare
 * Descriere: Combinările C(i, j) — numărul de submulțimi cu j elemente ale unei
 *            mulțimi cu i elemente — respectă relația C(i, j) = C(i-1, j-1) +
 *            C(i-1, j): fie alegem elementul i, fie nu. Cu C(i, 0) = C(i, i) = 1
 *            construim tabelul linie cu linie, folosind doar adunări (fără
 *            factoriale care ar depăși). Programul afișează liniile 0, 1, ..., n
 *            ale triunghiului, apoi valoarea C(n, k). Pentru n ≤ 66 toate valorile
 *            încap în long long.
 * Complexitate: O(n^2)
 *
 * Exemplu
 * Intrare: 5 2
 * Ieșire:
 * 1
 * 1 1
 * 1 2 1
 * 1 3 3 1
 * 1 4 6 4 1
 * 1 5 10 10 5 1
 * 10
 *
 * Exemplu
 * Intrare: 2 3
 * Ieșire:
 * 1
 * 1 1
 * 1 2 1
 * 0
 */
#include <iostream>
using namespace std;

long long c[67][67];

int main()
{
    int n, k;
    cin >> n >> k;
    for (int i = 0; i <= n; i++)
    {
        c[i][0] = c[i][i] = 1;
        for (int j = 1; j < i; j++)
            c[i][j] = c[i - 1][j - 1] + c[i - 1][j];
    }
    for (int i = 0; i <= n; i++)
    {
        for (int j = 0; j <= i; j++)
            cout << c[i][j] << (j < i ? ' ' : '\n');
    }
    // Dacă k > n nu există submulțimi cu k elemente.
    cout << (k <= n ? c[n][k] : 0) << '\n';
    return 0;
}

Runs on a real g++ (C++17, -O2) through Compiler Explorer. Keep runs short; there's a time limit.