# Evaluate binomial coefficients

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}$

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)$
With replacement $\binom {n+k-1}k = ^{n+k-1}\operatorname C_k = {(n+k-1)! \over (n-1)!k!}$ nk

## ACL2

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

 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


## ALGOL 68

### 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


## AppleScript

set n to 5set 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 factorialend 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

## 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

## 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

## 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).

## F#

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

## Forth

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

## 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

## Frink

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

 println[binomial[5,3]]

## GAP

# Built-inBinomial(5, 3);# 10

## Go

package mainimport "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


## 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}$:

## PARI/GP

binomial(5,3)

See Delphi

## Perl

sub binomial {	use bigint;	my ($r,$n, $k) = (1, @_); for (1 ..$k) {	$r *=$n + 1 - $_;$r /= $_ }$r;} print binomial(30, 13);

## Perl 6

sub infix:<choose>($n,$k) { ([*] $n-$k+1 .. $n) / [*] 2 ..$k } say 5 choose 3;
Output:
10

## 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

## 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;}  ## PicoLisp (de binomial (N K) (let f '((N) (apply * (range 1 N))) (/ (f N) (* (f (- N K)) (f K))) ) ) Output: : (binomial 5 3) -> 10 ## PureBasic Procedure Factor(n) Protected Result=1 While n>0 Result*n n-1 Wend ProcedureReturn ResultEndProcedure 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  ## 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 muldef 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) ) ## R R's built-in choose() function evaluates binomial coefficients: choose(5,3) Output: [1] 10 ## Racket  #lang racket(require math)(binomial 10 5)  ## REXX The task is to compute ANY binomial coefficient(s), but this example is limited to 100k digits. /*REXX program calculates binomial coefficients (aka, combinations). */ numeric digits 100000parse arg n k .say 'combinations('n","k') =' comb(n,k)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; parse arg z; !=1; do j=2 to z; !=!*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  ## 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 endend 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) endend  ## 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 ibinomial = coeffend function Output: binomial (5,1) = 5 binomial (5,2) = 10 binomial (5,3) = 10 binomial (5,4) = 5 binomial (5,5) = 1 ## 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 30The 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 ## 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 ## 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


## Tcl

This uses exact arbitrary precision integer arithmetic.

package require Tcl 8.5proc 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

## TI-89 BASIC

Builtin function.

nCr(n,k)

## 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

## 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 doneecho$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"

## 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>

## 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