NAME

xt_n_choose_k() - Compute binomial coefficient N choose K

LIBRARY

#include <xtend/math.h>
-lxtend

SYNOPSIS

#include <stdint.h>
#include "math.h"
unsigned long   xt_n_choose_k(unsigned long n, unsigned long k)

ARGUMENTS

n   Number of items to choose from
k   Number of items chosen

DESCRIPTION

Compute the binomial coefficient N choose K = N! / (K! * (N-K)!). This represents the number of ways to choose K items out of a pool of N, such that we don't care about order. E.g., if choosing 2 letters from the set [A B C D E], [C D] is considered the same [D C].

This implementation avoids overflow by alternating multiply and divide operations (rather than try to compute factorials first, which will fail for relatively small values of N or K).

RETURN VALUES

The number of ways to choose K items from N objects.

EXAMPLES

#include <xtend/math.h>
unsigned long   n = 5, k = 2;
printf("Ways to choose %lu items from %lu = %lun",


        k, n, xt_n_choose_k(n, k));