Evaluate binomial coefficients

From Rosetta Code
Jump to: navigation, search
Task
Evaluate binomial coefficients
You are encouraged to solve this task according to the task description, using any language you may know.

This programming task, is to calculate ANY binomial coefficient.

However, it has to be able to output \binom{5}{3}, which is 10.

This formula is recommended:

\binom{n}{k} = \frac{n!}{(n-k)!k!} = \frac{n(n-1)(n-2)\ldots(n-k+1)}{k(k-1)(k-2)\ldots 1}

See Also:

The number of samples of size k from n objects.
With combinations and permutations generation tasks.
Order Unimportant Order Important
Without replacement  \binom nk = ^n\operatorname C_k = \frac{n(n-1)\ldots(n-k+1)}{k(k-1)\dots1} ^n\operatorname P_k = n\cdot(n-1)\cdot(n-2)\cdots(n-k+1)
Task: Combinations Task: Permutations
With replacement  \binom {n+k-1}k = ^{n+k-1}\operatorname C_k = {(n+k-1)! \over (n-1)!k!} nk
Task: Combinations with repetitions Task: Permutations with repetitions

Contents

[edit] ACL2

(defun fac (n)
(if (zp n)
1
(* n (fac (1- n)))))
 
(defun binom (n k)
(/ (fac n) (* (fac (- n k)) (fac k)))

[edit] Ada

 
with Ada.Text_IO; use Ada.Text_IO;
procedure Test_Binomial is
function Binomial (N, K : Natural) return Natural is
Result : Natural := 1;
M  : Natural;
begin
if N < K then
raise Constraint_Error;
end if;
if K > N/2 then -- Use symmetry
M := N - K;
else
M := K;
end if;
for I in 1..M loop
Result := Result * (N - M + I) / I;
end loop;
return Result;
end Binomial;
begin
for N in 0..17 loop
for K in 0..N loop
Put (Integer'Image (Binomial (N, K)));
end loop;
New_Line;
end loop;
end Test_Binomial;
 

Sample output:

 1
 1 1
 1 2 1
 1 3 3 1
 1 4 6 4 1
 1 5 10 10 5 1
 1 6 15 20 15 6 1
 1 7 21 35 35 21 7 1
 1 8 28 56 70 56 28 8 1
 1 9 36 84 126 126 84 36 9 1
 1 10 45 120 210 252 210 120 45 10 1
 1 11 55 165 330 462 462 330 165 55 11 1
 1 12 66 220 495 792 924 792 495 220 66 12 1
 1 13 78 286 715 1287 1716 1716 1287 715 286 78 13 1
 1 14 91 364 1001 2002 3003 3432 3003 2002 1001 364 91 14 1
 1 15 105 455 1365 3003 5005 6435 6435 5005 3003 1365 455 105 15 1
 1 16 120 560 1820 4368 8008 11440 12870 11440 8008 4368 1820 560 120 16 1
 1 17 136 680 2380 6188 12376 19448 24310 24310 19448 12376 6188 2380 680 136 17 1

[edit] ALGOL 68

[edit] Iterative - unoptimised

Translation of: C
- note: This specimen retains the original C coding style.
Works with: ALGOL 68 version Revision 1 - no extensions to language used
Works with: ALGOL 68G version Any - tested with release 1.18.0-9h.tiny
Works with: ELLA ALGOL 68 version Any (with appropriate job cards) - tested with release 1.8-8d
PROC factorial = (INT n)INT:
(
INT result;
 
result := 1;
FOR i TO n DO
result *:= i
OD;
 
result
);
 
PROC choose = (INT n, INT k)INT:
(
INT result;
 
# Note: code can be optimised here as k < n #
result := factorial(n) OVER (factorial(k) * factorial(n - k));
 
result
);
 
test:(
print((choose(5, 3), new line))
)

Output:

        +10

[edit] AppleScript

set n to 5
set k to 3
 
on calculateFactorial(val)
set partial_factorial to 1 as integer
repeat with i from 1 to val
set factorial to i * partial_factorial
set partial_factorial to factorial
end repeat
return factorial
end calculateFactorial
 
set n_factorial to calculateFactorial(n)
set k_factorial to calculateFactorial(k)
set n_minus_k_factorial to calculateFactorial(n - k)
 
return n_factorial / (n_minus_k_factorial) * 1 / (k_factorial) as integer
 

[edit] AutoHotkey

MsgBox, % Round(BinomialCoefficient(5, 3))
 
;---------------------------------------------------------------------------
BinomialCoefficient(n, k) {
;---------------------------------------------------------------------------
r := 1
Loop, % k < n - k ? k : n - k {
r *= n - A_Index + 1
r /= A_Index
}
Return, r
}

Message box shows:

10

[edit] BBC BASIC

      @%=&1010
 
PRINT "Binomial (5,3) = "; FNbinomial(5, 3)
PRINT "Binomial (100,2) = "; FNbinomial(100, 2)
PRINT "Binomial (33,17) = "; FNbinomial(33, 17)
END
 
DEF FNbinomial(N%, K%)
LOCAL R%, D%
R% = 1 : D% = N% - K%
IF D% > K% THEN K% = D% : D% = N% - K%
WHILE N% > K%
R% *= N%
N% -= 1
WHILE D% > 1 AND (R% MOD D%) = 0
R% /= D%
D% -= 1
ENDWHILE
ENDWHILE
= R%
 

Output:

Binomial (5,3) = 10
Binomial (100,2) = 4950
Binomial (33,17) = 1166803110

[edit] Bracmat

(binomial=
n k coef
.  !arg:(?n,?k)
& (!n+-1*!k:<!k:?k|)
& 1:?coef
& whl
' ( !k:>0
& !coef*!n*!k^-1:?coef
& !k+-1:?k
& !n+-1:?n
)
& !coef
);
 
binomial$(5,3)
10
 

[edit] Burlesque

 
blsq ) 5 3nr
10
 

[edit] C

#include <stdio.h>
#include <limits.h>
 
/* We go to some effort to handle overflow situations */
 
static unsigned long gcd_ui(unsigned long x, unsigned long y) {
unsigned long t;
if (y < x) { t = x; x = y; y = t; }
while (y > 0) {
t = y; y = x % y; x = t; /* y1 <- x0 % y0 ; x1 <- y0 */
}
return x;
}
 
unsigned long binomial(unsigned long n, unsigned long k) {
unsigned long d, g, r = 1;
if (k == 0) return 1;
if (k == 1) return n;
if (k >= n) return (k == n);
if (k > n/2) k = n-k;
for (d = 1; d <= k; d++) {
if (r >= ULONG_MAX/n) { /* Possible overflow */
unsigned long nr, dr; /* reduced numerator / denominator */
g = gcd_ui(n, d); nr = n/g; dr = d/g;
g = gcd_ui(r, dr); r = r/g; dr = dr/g;
if (r >= ULONG_MAX/nr) return 0; /* Unavoidable overflow */
r *= nr;
r /= dr;
n--;
} else {
r *= n--;
r /= d;
}
}
return r;
}
 
int main() {
printf("%lu\n", binomial(5, 3));
printf("%lu\n", binomial(40, 19));
printf("%lu\n", binomial(67, 31));
return 0;
}
Output:
10
131282408400
11923179284862717872

[edit] C++

double Factorial(double nValue)
{
double result = nValue;
double result_next;
double pc = nValue;
do
{
result_next = result*(pc-1);
result = result_next;
pc--;
}while(pc>2);
nValue = result;
return nValue;
}
 
double EvaluateBinomialCoefficient(double nValue, double nValue2)
{
double result;
if(nValue2 == 1)return nValue;
result = (Factorial(nValue))/(Factorial(nValue2)*Factorial((nValue - nValue2)));
nValue2 = result;
return nValue2;
}

Implementation:

int main()
{
cout<<"The Binomial Coefficient of 5, and 3, is equal to: "<< EvaluateBinomialCoefficient(5,3);
cin.get();
}

Output:

The Binomial Coefficient of 5, and 3, is equal to: 10

[edit] C#

using System;
 
namespace BinomialCoefficients
{
class Program
{
static void Main(string[] args)
{
ulong n = 1000000, k = 3;
ulong result = biCoefficient(n, k);
Console.WriteLine("The Binomial Coefficient of {0}, and {1}, is equal to: {2}", n, k, result);
Console.ReadLine();
}
 
static int fact(int n)
{
if (n == 0) return 1;
else return n * fact(n - 1);
}
 
static ulong biCoefficient(ulong n, ulong k)
{
if (k > n - k)
{
k = n - k;
}
 
ulong c = 1;
for (uint i = 0; i < k; i++)
{
c = c * (n - i);
c = c / (i + 1);
}
return c;
}
}
}

[edit] Clojure

(defn binomial-coefficient [n k]
(let [rprod (fn [a b] (reduce * (range a (inc b))))]
(/ (rprod (- n k -1) n) (rprod 1 k))))

[edit] CoffeeScript

 
binomial_coefficient = (n, k) ->
result = 1
for i in [0...k]
result *= (n - i) / (i + 1)
result
 
n = 5
for k in [0..n]
console.log "binomial_coefficient(#{n}, #{k}) = #{binomial_coefficient(n,k)}"
 

output

 
> coffee binomial.coffee
binomial_coefficient(5, 0) = 1
binomial_coefficient(5, 1) = 5
binomial_coefficient(5, 2) = 10
binomial_coefficient(5, 3) = 10
binomial_coefficient(5, 4) = 5
binomial_coefficient(5, 5) = 1
 

[edit] Common Lisp

 
(defun choose (n k)
(labels ((prod-enum (s e)
(do ((i s (1+ i)) (r 1 (* i r))) ((> i e) r)))
(fact (n) (prod-enum 1 n)))
(/ (prod-enum (- (1+ n) k) n) (fact k))))
 

[edit] D

T binomial(T)(in T n, T k) pure nothrow {
if (k > (n / 2))
k = n - k;
T bc = 1;
foreach (T i; T(2) .. k + 1)
bc = (bc * (n - k + i)) / i;
return bc;
}
 
void main() {
import std.stdio, std.bigint;
 
foreach (const d; [[5, 3], [100, 2], [100, 98]])
writefln("(%3d %3d) = %s", d[0], d[1], binomial(d[0], d[1]));
writeln("(100 50) = ", binomial(100.BigInt, 50.BigInt));
}
Output:
(  5   3) = 2
(100   2) = 50
(100  98) = 50
(100  50) = 1976664223067613962806675336

[edit] dc

[sx1q]sz[d0=zd1-lfx*]sf[skdlfxrlk-lfxlklfx*/]sb

Demonstration:

5 3lbxp

10

Annotated version:

[ macro z: factorial base case when n is (z)ero ]sx
[sx [ x is our dump register; get rid of extraneous copy of n we no longer need]sx
1 [ return value is 1 ]sx
q] [ abort processing of calling macro ]sx
sz
 
[ macro f: factorial ]sx [
d [ duplicate the input (n) ]sx
0 =z [ if n is zero, call z, which stops here and returns 1 ]sx
d [ otherwise, duplicate n again ]sx
1 - [ subtract 1 ]sx
lfx [ take the factorial ]sx
* [ we have (n-1)!; multiply it by the copy of n to get n! ]sx
] sf
 
[ macro b(n,k): binomial function (n choose k).
straightforward RPN version of formula.]sx [
sk [ remember k. stack: n ]sx
d [ duplicate: n n ]sx
lfx [ call factorial: n n! ]sx
r [ swap: n! n ]sx
lk [ load k: n! n k ]sx
- [ subtract: n! n-k ]sx
lfx [ call factorial: n! (n-k)! ]sx
lk [ load k: n! (n-k)! k ]sx
lfx [ call factorial; n! (n-k)! k! ]sx
* [ multiply: n! (n-k)!k! ]sx
/ [ divide: n!/(n-k)!k! ]sx
] sb
 
5 3 lb x p [print(5 choose 3)]sx

[edit] Delphi

program Binomial;
 
{$APPTYPE CONSOLE}
 
function BinomialCoff(N, K: Cardinal): Cardinal;
var
L: Cardinal;
 
begin
if N < K then
Result:= 0 // Error
else begin
if K > N - K then
K:= N - K; // Optimization
Result:= 1;
L:= 0;
while L < K do begin
Result:= Result * (N - L);
Inc(L);
Result:= Result div L;
end;
end;
end;
 
begin
Writeln('C(5,3) is ', BinomialCoff(5, 3));
ReadLn;
end.

[edit] Erlang

 
choose(N, K) when is_integer(N), is_integer(K), (N >= 0), (K >= 0), (N >= K) ->
choose(N, K, 1, 1).
 
choose(N, K, K, Acc) ->
(Acc * (N-K+1)) div K;
choose(N, K, I, Acc) ->
choose(N, K, I+1, (Acc * (N-I+1)) div I).
 

[edit] F#

 
let choose n k = List.fold (fun s i -> s * (n-i+1)/i ) 1 [1..k]
 

[edit] Forth

: choose ( n k -- nCk ) 1 swap 0 ?do over i - i 1+ */ loop nip ;
 
5 3 choose . \ 10
33 17 choose . \ 1166803110

[edit] Fortran

Works with: Fortran version 90 and later
program test_choose
 
implicit none
 
write (*, '(i0)') choose (5, 3)
 
contains
 
function factorial (n) result (res)
 
implicit none
integer, intent (in) :: n
integer :: res
integer :: i
 
res = product ((/(i, i = 1, n)/))
 
end function factorial
 
function choose (n, k) result (res)
 
implicit none
integer, intent (in) :: n
integer, intent (in) :: k
integer :: res
 
res = factorial (n) / (factorial (k) * factorial (n - k))
 
end function choose
 
end program test_choose

Output:

10

[edit] Frink

Frink has a built-in efficient function to find binomial coefficients. It produces arbitrarily-large integers.

 
println[binomial[5,3]]
 

[edit] FunL

FunL has pre-defined function choose in module integers, which is defined as:

def
choose( n, k ) | k < 0 or k > n = 0
choose( n, 0 ) = 1
choose( n, n ) = 1
choose( n, k ) = product( [(n - i)/(i + 1) | i <- 0:min( k, n - k )] )
 
println( choose(5, 3) )
println( choose(60, 30) )
Output:
10
118264581564861424

Here it is defined using the recommended formula for this task.

import integers.factorial
 
def
binomial( n, k ) | k < 0 or k > n = 0
binomial( n, k ) = factorial( n )/factorial( n - k )/factorial( k )

[edit] GAP

# Built-in
Binomial(5, 3);
# 10

[edit] Go

package main
import "fmt"
import "math/big"
 
func main() {
fmt.Println(new(big.Int).Binomial(5, 3))
fmt.Println(new(big.Int).Binomial(60, 30))
}
Output:
10
118264581564861424

[edit] Golfscript

Actually evaluating n!/(k! (n-k)!):

;5 3 # Set up demo input
{),(;{*}*}:f; # Define a factorial function
.f@.f@/\@-f/

But Golfscript is meant for golfing, and it's shorter to calculate \prod_{i=0}^{k-1} \frac{n-i}{i+1}:

;5 3 # Set up demo input
1\,@{1$-@\*\)/}+/

[edit] Groovy

Solution:

def factorial = { x ->
assert x > -1
x == 0 ? 1 : (1..x).inject(1G) { BigInteger product, BigInteger factor -> product *= factor }
}
 
def combinations = { n, k ->
assert k >= 0
assert n >= k
factorial(n).intdiv(factorial(k)*factorial(n-k))
}

Test:

assert combinations(20, 0) == combinations(20, 20)
assert combinations(20, 10) == (combinations(19, 9) + combinations(19, 10))
assert combinations(5, 3) == 10
println combinations(5, 3)

Output:

10

[edit] Haskell

The only trick here is realizing that everything's going to divide nicely, so we can use div instead of (/).

 
choose :: (Integral a) => a -> a -> a
choose n k = product [k+1..n] `div` product [1..n-k]
 
> 5 `choose` 3
10

Or, generate the binomial coefficients iteratively to avoid computing with big numbers:

 
choose :: (Integral a) => a -> a -> a
choose n k = foldl (\z i -> (z * (n-i+1)) `div` i) 1 [1..k]
 

Or using "caching":

coeffs = iterate next [1] 
where
next ns = zipWith (+) (0:ns) $ ns ++ [0]
 
main = print $ coeffs !! 5 !! 3

[edit] HicEst

WRITE(Messagebox) BinomCoeff( 5, 3) ! displays 10
 
FUNCTION factorial( n )
factorial = 1
DO i = 1, n
factorial = factorial * i
ENDDO
END
 
FUNCTION BinomCoeff( n, k )
BinomCoeff = factorial(n)/factorial(n-k)/factorial(k)
END

[edit] Icon and Unicon

link math, factors 
 
procedure main()
write("choose(5,3)=",binocoef(5,3))
end

Output:

choose(5,3)=10

math provides binocoef and factors provides factorial.

procedure binocoef(n, k)	#: binomial coefficient
 
k := integer(k) | fail
n := integer(n) | fail
 
if (k = 0) | (n = k) then return 1
 
if 0 <= k <= n then
return factorial(n) / (factorial(k) * factorial(n - k))
else fail
 
end
 
procedure factorial(n) #: return n! (n factorial)
local i
 
n := integer(n) | runerr(101, n)
 
if n < 0 then fail
 
i := 1
 
every i *:= 1 to n
 
return i
 
end

[edit] J

Solution:
The dyadic form of the primitive ! ([Out of]) evaluates binomial coefficients directly.

Example usage:

   3 ! 5
10

[edit] Java

public class Binomial
{
private static long binomial(int n, int k)
{
if (k>n-k)
k=n-k;
 
long b=1;
for (int i=1, m=n; i<=k; i++, m--)
b=b*m/i;
return b;
}
 
public static void main(String[] args)
{
System.out.println(binomial(5, 3));
}
}

Output:

10
Translation of: Python
public class Binom {
public static double binomCoeff(double n, double k) {
double result = 1;
for (int i = 1; i < k + 1; i++) {
result *= (n - i + 1) / i;
}
return result;
}
 
public static void main(String[] args) {
System.out.println(binomCoeff(5, 3));
}
}
 

Output:

10.0

Recursive version:

public class Binomial
{
private static long binom(int n, int k)
{
if (k==0)
return 1;
else if (k>n-k)
return binom(n, n-k);
else
return binom(n-1, k-1)*n/k;
}
 
public static void main(String[] args)
{
System.out.println(binom(5, 3));
}
}

Output:

10

[edit] JavaScript

function binom(n, k) {
var coeff = 1;
for (var i = n-k+1; i <= n; i++) coeff *= i;
for (var i = 1; i <= k; i++) coeff /= i;
return coeff;
}
print(binom(5,3));
10

[edit] jq

# nCk assuming n >= k
def binomial(n; k):
if k > n / 2 then binomial(n; n-k)
else reduce range(1; k+1) as $i (1; . * (n - $i + 1) / $i)
end;
 
def task:
.[0] as $n | .[1] as $k
| "\($n) C \($k) = \(binomial( $n; $k) )";
;
 
([5,3], [100,2], [ 33,17]) | task
 
Output:
5 C 3 = 10
100 C 2 = 4950
33 C 17 = 1166803110

[edit] K

   {[n;k]_(*/(k-1)_1+!n)%(*/1+!k)} . 5 3
10

Alternative version:

   {[n;k]i:!(k-1);_*/((n-i)%(i+1))} . 5 3
10

Using Pascal's triangle:

   pascal:{x{+':0,x,0}\1}
pascal 5
(1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1)
 
{[n;k](pascal n)[n;k]} . 5 3
10


[edit] Lasso

define binomial(n::integer,k::integer) => {
#k == 0 ? return 1
local(result = 1)
loop(#k) => {
#result = #result * (#n - loop_count + 1) / loop_count
}
return #result
}
// Tests
binomial(5, 3)
binomial(5, 4)
binomial(60, 30)
Output:
10
5
118264581564861424

[edit]

to choose :n :k
if :k = 0 [output 1]
output (choose :n :k-1) * (:n - :k + 1) / :k
end
 
show choose 5 3  ; 10
show choose 60 30 ; 1.18264581564861e+17

[edit] Lua

function Binomial( n, k )
if k > n then return nil end
if k > n/2 then k = n - k end -- (n k) = (n n-k)
 
numer, denom = 1, 1
for i = 1, k do
numer = numer * ( n - i + 1 )
denom = denom * i
end
return numer / denom
end

[edit] Liberty BASIC

 
' [RC] Binomial Coefficients
 
print "Binomial Coefficient of "; 5; " and "; 3; " is ",BinomialCoefficient( 5, 3)
n =1 +int( 10 *rnd( 1))
k =1 +int( n *rnd( 1))
print "Binomial Coefficient of "; n; " and "; k; " is ",BinomialCoefficient( n, k)
 
end
 
function BinomialCoefficient( n, k)
BinomialCoefficient =factorial( n) /factorial( n -k) /factorial( k)
end function
 
function factorial( n)
if n <2 then
f =1
else
f =n *factorial( n -1)
end if
factorial =f
end function
 
 


[edit] Maple

convert(binomial(n,k),factorial);
 
binomial(5,3);

Output:

                         factorial(n)         
                 -----------------------------
                 factorial(k) factorial(n - k)

                               10

[edit] Mathematica

(Local) In[1]:= Binomial[5,3]
(Local) Out[1]= 10

[edit] MATLAB / Octave

This is a built-in function in MATLAB called "nchoosek(n,k)". But, this will only work for scalar inputs. If "n" is a vector then "nchoosek(v,k)" finds all combinations of choosing "k" elements out of the "v" vector (see Combinations#MATLAB).

Solution:

>> nchoosek(5,3)
ans =
10

Alternative implementations are:

function r = binomcoeff1(n,k)
r = diag(rot90(pascal(n+1))); % vector of all binomial coefficients for order n
r = r(k);
end;
function r = binomcoeff2(n,k)
prod((n-k+1:n)./(1:k))
end;
function r = binomcoeff3(n,k)
m = pascal(max(n-k,k)+1);
r = m(n-k+1,k+1);
end;

If you want a vectorized function that returns multiple binomial coefficients given vector inputs, you must define that function yourself. A sample implementation is given below. This function takes either scalar or vector inputs for "n" and "v" and returns either a: scalar, vector, or matrix. Where the columns are indexed by the "k" vector and the rows indexed by the "n" vector. binomialCoeff.m:

function coefficients = binomialCoeff(n,k)
 
coefficients = zeros(numel(n),numel(k)); %Preallocate memory
 
columns = (1:numel(k)); %Preallocate row and column counters
rows = (1:numel(n));
 
%Iterate over every row and column. The rows represent the n number,
%and the columns represent the k number. If n is ever greater than k,
%the nchoosek function will throw an error. So, we test to make sure
%it isn't, if it is then we leave that entry in the coefficients matrix
%zero. Which makes sense combinatorically.
for row = rows
for col = columns
if k(col) <= n(row)
coefficients(row,col) = nchoosek(n(row),k(col));
end
end
end
 
end %binomialCoeff

Sample Usage:

>> binomialCoeff((0:5),(0:5))
 
ans =
 
1 0 0 0 0 0
1 1 0 0 0 0
1 2 1 0 0 0
1 3 3 1 0 0
1 4 6 4 1 0
1 5 10 10 5 1
 
>> binomialCoeff([1 0 3 2],(0:3))
 
ans =
 
1 1 0 0
1 0 0 0
1 3 3 1
1 2 1 0
 
>> binomialCoeff(3,(0:3))
 
ans =
 
1 3 3 1
 
>> binomialCoeff((0:3),2)
 
ans =
 
0
0
1
3
 
>> binomialCoeff(5,3)
 
ans =
 
10

[edit] Maxima

binomial( 5,  3);      /* 10 */
binomial(-5, 3); /* -35 */
binomial( 5, -3); /* 0 */
binomial(-5, -3); /* 0 */
binomial( 3, 5); /* 0 */
 
binomial(x, 3); /* ((x - 2)*(x - 1)*x)/6 */
 
binomial(3, 1/2); /* binomial(3, 1/2) */
makegamma(%); /* 32/(5*%pi) */
 
binomial(a, b); /* binomial(a, b) */
makegamma(%); /* gamma(a + 1)/(gamma(-b + a + 1)*gamma(b + 1)) */

[edit] МК-61/52

П1	<->	П0	ПП	22	П2	 ИП1	ПП	22	П3
ИП0 ИП1 - ПП 22 ИП3 * П3 ИП2 ИП3
/ С/П ВП П0 1 ИП0 * L0 25 В/О

Input: n ^ k В/О С/П.

[edit] Nimrod

proc binomialCoeff(n, k): int =
result = 1
for i in 1..k:
result = result * (n-i+1) div i
 
echo binomialCoeff(5, 3)

Output:

10

[edit] OCaml

 
let binomialCoeff n p =
let p = if p < n -. p then p else n -. p in
let rec cm res num denum =
(* this method partially prevents overflow.
* float type is choosen to have increased domain on 32-bits computer,
* however algorithm ensures an integral result as long as it is possible
*)

if denum <= p then cm ((res *. num) /. denum) (num -. 1.) (denum +. 1.)
else res in
cm 1. n 1.
 

[edit] Alternate version using big integers

#load "nums.cma";;
open Num;;
 
let binomial n p =
let m = min p (n - p) in
if m < 0 then Int 0 else
let rec a j v =
if j = m then v
else a (succ j) ((v */ (Int (n - j))) // (Int (succ j)))
in a 0 (Int 1)
;;

[edit] Simple recursive version

open Num;;
let rec binomial n k = if n = k then Int 1 else ((binomial (n-1) k) */ Int n) // Int (n-k)

[edit] Oz

Translation of: Python
declare
fun {BinomialCoeff N K}
{List.foldL {List.number 1 K 1}
fun {$ Z I}
Z * (N-I+1) div I
end
1}
end
in
{Show {BinomialCoeff 5 3}}

[edit] PARI/GP

binomial(5,3)

[edit] Pascal

See Delphi

[edit] Perl

sub binomial {
use bigint;
my ($r, $n, $k) = (1, @_);
for (1 .. $k) { $r *= $n + 1 - $_; $r /= $_ }
$r;
}
 
print binomial(5, 3);
Output:
10

[edit] Perl 6

sub infix:<choose> { [*] ($^n ... 0) Z/ 1 .. $^p }
say 5 choose 3;
Output:
10

[edit] PL/I

 
binomial_coefficients:
procedure options (main);
declare (n, k) fixed;
 
get (n, k);
put (coefficient(n, k));
 
coefficient: procedure (n, k) returns (fixed decimal (15));
declare (n, k) fixed;
return (fact(n)/ (fact(n-k) * fact(k)) );
end coefficient;
 
fact: procedure (n) returns (fixed decimal (15));
declare n fixed;
declare i fixed, f fixed decimal (15);
f = 1;
do i = 1 to n;
f = f * i;
end;
return (f);
end fact;
end binomial_coefficients;
 

Output:

 
10
 

[edit] PHP

<?php
$n=5;
$k=3;
function factorial($val){
for($f=2;$val-1>1;$f*=$val--);
return $f;
}
$binomial_coefficient=factorial($n)/(factorial($k)*factorial($n-$k));
echo $binomial_coefficient;
?>

Alternative version, not based on factorial

 
function binomial_coefficient($n, $k) {
if ($k == 0) return 1;
$result = 1;
foreach (range(0, $k - 1) as $i) {
$result *= ($n - $i) / ($i + 1);
}
return $result;
}
 

[edit] PicoLisp

(de binomial (N K)
(let f
'((N)
(if (=0 N) 1 (apply * (range 1 N))) )
(/
(f N)
(* (f (- N K)) (f K)) ) ) )

Output:

: (binomial 5 3)
-> 10

[edit] PureBasic

Procedure Factor(n)
Protected Result=1
While n>0
Result*n
n-1
Wend
ProcedureReturn Result
EndProcedure
 
Macro C(n,k)
(Factor(n)/(Factor(k)*factor(n-k)))
EndMacro
 
If OpenConsole()
Print("Enter value n: "): n=Val(Input())
Print("Enter value k: "): k=Val(Input())
PrintN("C(n,k)= "+str(C(n,k)))
 
Print("Press ENTER to quit"): Input()
CloseConsole()
EndIf

Example

Enter value n: 5
Enter value k: 3
C(n,k)= 10

[edit] Python

Straight-forward implementation:

def binomialCoeff(n, k):
result = 1
for i in range(1, k+1):
result = result * (n-i+1) / i
return result
 
if __name__ == "__main__":
print(binomialCoeff(5, 3))

Output:

10

Alternate implementation

from operator import mul
def comb(n,r):
''' calculate nCr - the binomial coefficient
>>> comb(3,2)
3
>>> comb(9,4)
126
>>> comb(9,6)
84
>>> comb(20,14)
38760
'''

 
if r > n-r: # for smaller intermediate values
r = n-r
return int( reduce( mul, range((n-r+1), n+1), 1) /
reduce( mul, range(1,r+1), 1) )

[edit] R

R's built-in choose() function evaluates binomial coefficients:

choose(5,3)

Output:

[1] 10


[edit] Racket

 
#lang racket
(require math)
(binomial 10 5)
 

[edit] REXX

The task is to compute ANY binomial coefficient(s), but these REXX examples are limited to 100k digits.

[edit] idiomatic

/*REXX program calculates   binomial coefficients  (aka, combinations). */
numeric digits 100000 /*allow some gihugeic numbers. */
parse arg n k . /*get N and K from the C.L.*/
say 'combinations('n","k')=' comb(n,k) /*display the result to terminal.*/
exit /*stick a fork in it, we're done.*/
/*──────────────────────────────────COMB subroutine─────────────────────*/
comb: procedure; parse arg x,y; return fact(x) % (fact(x-y) * fact(y))
/*──────────────────────────────────FACT subroutine─────────────────────*/
fact: procedure;  !=1; do j=2 to arg(1);  !=!*j; end; return !

output when using the input of:   5 3

combinations(5,3)= 10

output when using the input of:   1200 120

combinations(1200,120)= 1004576581793084916475353119318331966507299414258370667602185866686463289093457468590558508056798211449853806741873396451735444387513582540860551330127062642417424083600

[edit] optimized

This REXX version takes advantage of reducing the size (product) of the numerator,
and also, only two (factorial) products need be calculated.

/*REXX program calculates   binomial coefficients  (aka, combinations). */
numeric digits 100000 /*allow some gihugeic numbers. */
parse arg n k . /*get N and K from the C.L.*/
say 'combinations('n","k')=' comb(n,k) /*display the result to terminal.*/
exit /*stick a fork in it, we're done.*/
/*──────────────────────────────────COMB subroutine─────────────────────*/
comb: procedure; parse arg x,y; return pfact(x-y+1,x) % pfact(2,y)
/*──────────────────────────────────PFACT subroutine────────────────────*/
pfact: procedure; !=1; do j=arg(1) to arg(2); !=!*j; end; return !

output is identical to the 1st version.
It is (around average) about ten times faster than the 1st version for   200,20   and   100,10.
For   100,80   it is about 30% faster.

[edit] Ruby

Translation of: Tcl
Works with: Ruby version 1.8.7+
class Integer
# binomial coefficient: n C k
def choose(k)
# n!/(n-k)!
pTop = (self-k+1 .. self).inject(1, &:*)
# k!
pBottom = (2 .. k).inject(1, &:*)
pTop / pBottom
end
end
 
p 5.choose(3)
p 60.choose(30)

result

10
118264581564861424

another implementation:

 
def c n, r
(0...r).inject(1) do |m,i| (m * (n - i)) / (i + 1) end
end
 

[edit] Run BASIC

print "binomial (5,1) = "; binomial(5, 1)
print "binomial (5,2) = "; binomial(5, 2)
print "binomial (5,3) = "; binomial(5, 3)
print "binomial (5,4) = "; binomial(5,4)
print "binomial (5,5) = "; binomial(5,5)
end
 
function binomial(n,k)
coeff = 1
for i = n - k + 1 to n
coeff = coeff * i
next i
for i = 1 to k
coeff = coeff / i
next i
binomial = coeff
end function
Output:
binomial (5,1) = 5
binomial (5,2) = 10
binomial (5,3) = 10
binomial (5,4) = 5
binomial (5,5) = 1

[edit] Scala

object Binomial {
def main(args: Array[String]): Unit = {
val n=5
val k=3
val result=binomialCoefficient(n,k)
println("The Binomial Coefficient of %d and %d equals %d.".format(n, k, result))
}
 
def binomialCoefficient(n:Int, k:Int)=fact(n) / (fact(k) * fact(n-k))
def fact(n:Int):Int=if (n==0) 1 else n*fact(n-1)
}

Output:

The Binomial Coefficient of 5 and 3 equals 10.

Another (more flexible and efficient) implementation. n and k are taken from command line. The use of BigInts allows to compute coefficients of arbitrary size:

object Binomial extends App {
def binomialCoefficient(n: Int, k: Int) =
(BigInt(n - k + 1) to n).product /
(BigInt(1) to k).product
 
val Array(n, k) = args.map(_.toInt)
println("The Binomial Coefficient of %d and %d equals %,3d.".format(n, k, binomialCoefficient(n, k)))
}

Output:

java Binomial 100 30
The Binomial Coefficient of 100 and 30 equals 29,372,339,821,610,944,823,963,760.

Using recursive formula C(n,k) = C(n-1,k-1) + C(n-1,k):

  def bico(n: Long, k: Long): Long = (n, k) match {
case (n, 0) => 1
case (0, k) => 0
case (n, k) => bico(n - 1, k - 1) + bico(n - 1, k)
}
println("bico(5,3) = " + bico(5, 3))

Output:

bico(5,3) = 10

[edit] Scheme

Works with: Scheme version R5RS
(define (factorial n)
(define (*factorial n acc)
(if (zero? n)
acc
(*factorial (- n 1) (* acc n))))
(*factorial n 1))
 
(define (choose n k)
(/ (factorial n) (* (factorial k) (factorial (- n k)))))
 
(display (choose 5 3))
(newline)

Output:

10

[edit] Seed7

$ include "seed7_05.s7i";
 
const func integer: binomial (in integer: n, in var integer: k) is func
result
var integer: binomial is 0;
local
var integer: l is 0;
begin
if n >= k then
if k > n - k then
k := n - k; # Optimization
end if;
binomial := 1;
l := 0;
while l < k do
binomial *:= n - l;
incr(l);
binomial := binomial div l;
end while;
end if;
end func;
 
const proc: main is func
begin
writeln("binomial coefficient of (5, 3) is " <& binomial(5, 3));
end func;

Output:

binomial coefficient of (5, 3) is 10

[edit] Tcl

This uses exact arbitrary precision integer arithmetic.

package require Tcl 8.5
proc binom {n k} {
# Compute the top half of the division; this is n!/(n-k)!
set pTop 1
for {set i $n} {$i > $n - $k} {incr i -1} {
set pTop [expr {$pTop * $i}]
}
 
# Compute the bottom half of the division; this is k!
set pBottom 1
for {set i $k} {$i > 1} {incr i -1} {
set pBottom [expr {$pBottom * $i}]
}
 
# Integer arithmetic divide is correct here; the factors always cancel out
return [expr {$pTop / $pBottom}]
}

Demonstrating:

puts "5_C_3 = [binom 5 3]"
puts "60_C_30 = [binom 60 30]"

Output:

5_C_3 = 10
60_C_30 = 118264581564861424

[edit] TI-89 BASIC

Builtin function.

nCr(n,k)

[edit] TXR

nCk is a built-in function, along with the one for permutations, nPk:

$ txr -p '(n-choose-k 20 15)'
15504
$ txr -p '(n-perm-k 20 15)'
20274183401472000

[edit] UNIX Shell

#!/bin/sh                                                                                                                                             
n=5;
k=3;
calculate_factorial(){
partial_factorial=1;
for (( i=1; i<="$1"; i++ ))
do
factorial=$(expr $i \* $partial_factorial)
partial_factorial=$factorial
 
done
echo $factorial
}
 
n_factorial=$(calculate_factorial $n)
k_factorial=$(calculate_factorial $k)
n_minus_k_factorial=$(calculate_factorial `expr $n - $k`)
binomial_coefficient=$(expr $n_factorial \/ $k_factorial \* 1 \/ $n_minus_k_factorial )
 
echo "Binomial Coefficient ($n,$k) = $binomial_coefficient"


[edit] Ursala

A function for computing binomial coefficients (choose) is included in a standard library, but if it weren't, it could be defined in one of the following ways, starting from the most idiomatic.

#import nat
 
choose = ~&ar^?\1! quotient^\~&ar product^/~&al ^|R/~& predecessor~~

The standard library functions quotient, product and predecessor pertain to natural numbers in the obvious way.

  • choose is defined using the recursive conditional combinator (^?) as a function taking a pair of numbers, with the predicate ~&ar testing whether the number on the right side of the pair is non-zero.
  • If the predicate does not hold (implying the right side is zero), then a constant value of 1 is returned.
  • If the predicate holds, the function given by the rest of the expression executes as follows.
  • First the predecessor of both sides (~~) of the argument is taken.
  • Then a recursive call (^|R) is made to the whole function (~&) with the pair of predecessors passed to it as an argument.
  • The result returned by the recursive call is multiplied (product) by the left side of the original argument (~&al).
  • The product of these values is then divided (quotient) by the right side (~&ar) of the original argument and returned as the result.

Here is a less efficient implementation more closely following the formula above.

choose = quotient^/factorial@l product+ factorial^~/difference ~&r
  • choose is defined as the quotient of the results of a pair (^) of functions.
  • The left function contributing to the quotient is the factorial of the left side (@l) of the argument, which is assumed to be a pair of natural numbers. The factorial function is provided in a standard library.
  • The right function contributing to the quotient is the function given by the rest of the expression, which applies to the whole pair as follows.
  • It begins by forming a pair of numbers from the argument, the left being their difference obtained by subtraction, and the right being the a copy of the right (~&r) side of the argument.
  • The factorial function is applied separately to both results (^~).
  • A composition (+) of this function with the product function effects the multiplication of the two factorials, to complete the other input to the quotient.

Here is an equivalent implementation using pattern matching, dummy variables, and only the apply-to-both (~~) operator.

choose("n","k") = quotient(factorial "n",product factorial~~ (difference("n","k"),"k"))

test program:

#cast %nL
 
main = choose* <(5,3),(60,30)>

output:

<10,118264581564861424>

[edit] XPL0

code ChOut=8, CrLf=9, IntOut=11;
 
func Binomial(N, K);
int N, K;
int M, B, I;
[M:= K;
if K>N/2 the M:= N-K;
B:=1;
for I:= 1 to M do
B:= B*(N-M+I)/I;
return B;
];
 
int N, K;
[for N:= 0 to 9 do
[for K:= 0 to 9 do
[if N>=K then IntOut(0, Binomial(N,K));
ChOut(0, 9\tab\);
];
CrLf(0);
];
] \Mr. Pascal's triangle!

Output:

1                                                                               
1       1                                                                       
1       2       1                                                               
1       3       3       1                                                       
1       4       6       4       1                                               
1       5       10      10      5       1                                       
1       6       15      20      15      6       1                               
1       7       21      35      35      21      7       1                       
1       8       28      56      70      56      28      8       1               
1       9       36      84      126     126     84      36      9       1       

[edit] zkl

Using 64 bit ints:

fcn binomial(n,k){ (1).reduce(k,fcn(p,i,n){ p*(n-i+1)/i },1,n) }
Output:
zkl: binomial(5,3)
10
zkl: binomial(60,30)
118264581564861424
Personal tools
Namespaces

Variants
Actions
Community
Explore
Misc
Toolbox