cpascals-triangle

c sum of the squares of all the coefficients in pascals triangle in random row


So I´ve been trying to solve this problem, but I just can´t. The thing is, I put a number of row in triangle, (can be any random number/row) and the program should return the sum of the squares of all the coefficients in that row.

#include <stdio.h>

unsigned long sum_triangle(const int row);

int main(){
 printf("%lu\n", sum_triangle(7));

 // sum(7)....7 is number of row

return 0;
}

unsigned long sum_triangle(const int row){
unsigned long sum = 0;
int temp =0;
for (int line = 0; line <= row ; line++) {
    for (int number = 0; number <= line ; number++){
        if (line == row){
            temp = THIS NEEDS TO BE COMBINED SOMEHOW(line , number);
            sum += (temp * temp);
        }
    }
 }
return sum;
}

Problem is in the "temp". I need to somehow combine row and number and thats it. Any help would be much appreciated.


Solution

  • There is a formula for the sum of squares of a row:

    sum of row m squares = binomial(2m, m)
    

    Thus all you need is to implement a proper binomial that doesn't overflow on reasonably sized integers. Coincidentally that Wikipedia article already has an implementation in C. Combining it all together:

    // from https://en.wikipedia.org/wiki/Binomial_coefficient
    unsigned long binomial(unsigned long n, unsigned long k) {
        unsigned long c = 1, i;
        if (k > n-k)
            k = n-k;
        for (i = 1; i <= k; i++, n--)
            c = c / i * n + c % i * n / i;
        return c;
    }
    
    unsigned long sum_triangle(int m) {
        return binomial(2*m, m);
    }