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

Question

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.

Answer 1

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);
}