Evaluate binomial coefficients: Difference between revisions

Content added Content deleted

Inline

Revision as of 09:31, 29 September 2015

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 {n}{k}}=^{n}\operatorname {C} _{k}={\frac {n(n-1)\ldots (n-k+1)}{k(k-1)\dots 1}}$	$^{n}\operatorname {P} _{k}=n\cdot (n-1)\cdot (n-2)\cdots (n-k+1)$
Without replacement	Task: Combinations	Task: Permutations
With replacement	${\binom {n+k-1}{k}}=^{n+k-1}\operatorname {C} _{k}={(n+k-1)! \over (n-1)!k!}$	$n^{k}$
With replacement	Task: Combinations with repetitions	Task: Permutations with repetitions

ABAP

<lang ABAP>CLASS lcl_binom DEFINITION CREATE PUBLIC.

 PUBLIC SECTION.
   CLASS-METHODS:
     calc
       IMPORTING n               TYPE i
                 k               TYPE i
       RETURNING VALUE(r_result) TYPE f.

ENDCLASS.

CLASS lcl_binom IMPLEMENTATION.

 METHOD calc.

   r_result = 1.
   DATA(i) = 1.
   DATA(m) = n.

   WHILE i <= k.
     r_result = r_result * m / i.
     i = i + 1.
     m = m - 1.
   ENDWHILE.

 ENDMETHOD.

ENDCLASS.</lang>

Output:

lcl_binom=>calc( n = 5 k = 3 )
1,0000000000000000E+01
lcl_binom=>calc( n = 60 k = 30 )
1,1826458156486142E+17

ACL2

<lang Lisp>(defun fac (n)

  (if (zp n)
      1
      (* n (fac (1- n)))))

(defun binom (n k)

  (/ (fac n) (* (fac (- n k)) (fac k)))</lang>

Ada

<lang 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; </lang>

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

<lang algol68>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))

)</lang>

Output:

+10

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 </lang>

AutoHotkey

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

}</lang> Message box shows:

BBC BASIC

<lang bbcbasic> @%=&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%

</lang>

Output:

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

Bracmat

<lang 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 </lang>

Burlesque

C

<lang 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;

}</lang>

Output:

10
131282408400
11923179284862717872

C++

<lang cpp>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;
  }</lang>

Implementation: <lang cpp>int main() {

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

}</lang>

Output:

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

C#

<lang csharp>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;
       }
   }

}</lang>

Clojure

<lang clojure>(defn binomial-coefficient [n k]

 (let [rprod (fn [a b] (reduce * (range a (inc b))))]
   (/ (rprod (- n k -1) n) (rprod 1 k))))</lang>

CoffeeScript

<lang 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)}"

</lang>

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

Common Lisp

<lang 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))))

</lang>

D

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

}</lang>

Output:

(  5   3) = 2
(100   2) = 50
(100  98) = 50
(100  50) = 1976664223067613962806675336

dc

<lang dc>[sx1q]sz[d0=zd1-lfx*]sf[skdlfxrlk-lfxlklfx*/]sb</lang>

Demonstration:

<lang dc>5 3lbxp</lang> 10

Annotated version:

<lang dc>[ 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</lang>

Delphi

<lang 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.</lang>

Elixir

Translation of: Erlang

<lang elixir>defmodule RC do

 def choose(n,k) when is_integer(n) and is_integer(k) and n>=0 and k>=0 and n>=k do
   if k==0, do: 1, else: choose(n,k,1,1)
 end
 
 def choose(n,k,k,acc), do: div(acc * (n-k+1), k)
 def choose(n,k,i,acc), do: choose(n, k, i+1, div(acc * (n-i+1), i))

end

IO.inspect RC.choose(5,3) IO.inspect RC.choose(60,30)</lang>

Output:

10
118264581564861424

Erlang

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

</lang>

ERRE

<lang>PROGRAM BINOMIAL

!$DOUBLE

PROCEDURE BINOMIAL(N,K->BIN)

     LOCAL R,D
     R=1 D=N-K
     IF D>K THEN K=D D=N-K  END IF
     WHILE N>K DO
       R*=N
       N-=1
       WHILE D>1 AND (R-D*INT(R/D))=0 DO
         R/=D
         D-=1
       END WHILE
     END WHILE
     BIN=R

END PROCEDURE

BEGIN

  BINOMIAL(5,3->BIN)
  PRINT("Binomial (5,3) = ";BIN)
  BINOMIAL(100,2->BIN)
  PRINT("Binomial (100,2) = ";BIN)
  BINOMIAL(33,17->BIN)
  PRINT("Binomial (33,17) = ";BIN)

END PROGRAM </lang>

Output:

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

F#

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

Forth

<lang forth>: choose ( n k -- nCk ) 1 swap 0 ?do over i - i 1+ */ loop nip ;

5  3 choose .   \ 10

33 17 choose . \ 1166803110</lang>

Fortran

Works with: Fortran version 90 and later

<lang fortran>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</lang>

Output:

Frink

Frink has a built-in efficient function to find binomial coefficients. It produces arbitrarily-large integers. <lang frink> println[binomial[5,3]] </lang>

FunL

FunL has pre-defined function choose in module integers, which is defined as: <lang funl>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) )</lang>

Output:

10
118264581564861424

Here it is defined using the recommended formula for this task. <lang funl>import integers.factorial

def

 binomial( n, k ) | k < 0 or k > n = 0
 binomial( n, k ) = factorial( n )/factorial( n - k )/factorial( k )</lang>

GAP

<lang gap># Built-in Binomial(5, 3);

10</lang>

Go

<lang 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))

}</lang>

Output:

10
118264581564861424

Golfscript

Actually evaluating n!/(k! (n-k)!): <lang golfscript>;5 3 # Set up demo input {),(;{*}*}:f; # Define a factorial function .f@.f@/\@-f/</lang> But Golfscript is meant for golfing, and it's shorter to calculate $\prod _{i=0}^{k-1}{\frac {n-i}{i+1}}$ :

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

Groovy

Solution: <lang groovy>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))

}</lang>

Test: <lang groovy>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)</lang>

Output:

Haskell

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

<lang haskell> choose :: (Integral a) => a -> a -> a choose n k = product [k+1..n] `div` product [1..n-k] </lang>

<lang haskell>> 5 `choose` 3 10</lang>

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

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

Or using "caching":

<lang haskell>coeffs = iterate next [1]

 where
   next ns = zipWith (+) (0:ns) $ ns ++ [0]

main = print $ coeffs !! 5 !! 3</lang>

HicEst

<lang 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</lang>

Icon and Unicon

<lang Icon>link math, factors

procedure main() write("choose(5,3)=",binocoef(5,3)) end</lang>

Output:

choose(5,3)=10

Library: Icon Programming Library

math provides binocoef and factors provides factorial.

<lang Icon>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</lang>

J

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

Example usage: <lang j> 3 ! 5 10</lang>

Java

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

}</lang>

Output:

Translation of: Python

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

} </lang>

Output:

10.0

Recursive version:

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

}</lang>

Output:

JavaScript

<lang 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));</lang>

jq

<lang 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 </lang>

Output:

5 C 3 = 10
100 C 2 = 4950
33 C 17 = 1166803110

Julia

recursive version <lang Julia>function binom(n,k)

 n >= k || return 0              #short circuit base cases
 n == 1 && return 1
 k == 0 && return 1
 
 binom(n-1,k-1) + binom (n-1,k)  #recursive call

end

julia> binom(5,2) 10</lang>

K

Alternative version: <lang K> {[n;k]i:!(k-1);_*/((n-i)%(i+1))} . 5 3 10</lang>

Using Pascal's triangle: <lang K> 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</lang>

Lasso

<lang 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)</lang>

Output:

10
5
118264581564861424

Logo

<lang logo>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</lang>

Lua

<lang 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</lang>

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

</lang>

Maple

<lang Maple>convert(binomial(n,k),factorial);

binomial(5,3);</lang>

Output:

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

                               10

Mathematica

<lang Mathematica>(Local) In[1]:= Binomial[5,3] (Local) Out[1]= 10</lang>

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: <lang MATLAB>>> nchoosek(5,3) ans =

   10</lang>

Alternative implementations are:

<lang MATLAB>function r = binomcoeff1(n,k)

   r = diag(rot90(pascal(n+1))); % vector of all binomial coefficients for order n
   r = r(k);

end; </lang>

<lang MATLAB>function r = binomcoeff2(n,k)

  prod((n-k+1:n)./(1:k))

end; </lang>

<lang MATLAB>function r = binomcoeff3(n,k)

  m = pascal(max(n-k,k)+1); 
  r = m(n-k+1,k+1);

end; </lang>

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: <lang MATLAB>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</lang> Sample Usage: <lang MATLAB>>> 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 =

>> binomialCoeff(5,3)

ans =

   10</lang>

Maxima

<lang 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)) */</lang>

МК-61/52

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

MINIL

<lang minil>// Number of combinations nCr 00 0E Go: ENT R0 // n 01 1E ENT R1 // r 02 2C CLR R2 03 2A Loop: ADD1 R2 04 0D DEC R0 05 1D DEC R1 06 C3 JNZ Loop 07 3C CLR R3 // for result 08 3A ADD1 R3 09 0A Next: ADD1 R0 0A 1A ADD1 R1 0B 50 R5 = R0 0C 5D DEC R5 0D 63 R6 = R3 0E 46 Mult: R4 = R6 0F 3A Add: ADD1 R3 10 4D DEC R4 11 CF JNZ Add 12 5D DEC R5 13 CE JNZ Mult 14 61 Divide:R6 = R1 15 5A ADD1 R5 16 3D Sub: DEC R3 17 9B JZ Exact 18 6D DEC R6 19 D6 JNZ Sub 1A 94 JZ Divide 1B 35 Exact: R3 = R5 1C 2D DEC R2 1D C9 JNZ Next 1E 03 R0 = R3 1F 80 JZ Go // Display result</lang>

This uses the recursive definition:

ncr(n, r) = 1 if r = 0

ncr(n, r) = n/r * ncr(n-1, r-1) otherwise

which results from the definition of ncr in terms of factorials.

Nim

<lang nim>proc binomialCoeff(n, k): int =

 result = 1
 for i in 1..k:
   result = result * (n-i+1) div i

echo binomialCoeff(5, 3)</lang>

Output:

OCaml

<lang 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.

</lang>

Alternate version using big integers

<lang ocaml>#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)

</lang>

Simple recursive version

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

Oforth

<lang Oforth>: binomial(n, k) { | i | 1 k loop: i [ n i - 1 + * i / ] }</lang>

Output:

>binomial(5, 3) println
10

Oz

Translation of: Python

<lang oz>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}}</lang>

PARI/GP

<lang parigp>binomial(5,3)</lang>

Pascal

See Delphi

Perl

<lang perl>sub binomial {

   use bigint;
   my ($r, $n, $k) = (1, @_);
   for (1 .. $k) { $r *= $n--; $r /= $_ }
   $r;

}

print binomial(5, 3);</lang>

Output:

Since the bigint module already has a binomial method, this could also be written as: <lang perl>sub binomial {

   use bigint;
   my($n,$k) = @_;
   (0+$n)->bnok($k);

}</lang>

For better performance, especially with large inputs, one can also use something like:

Library: ntheory

<lang perl>use ntheory qw/binomial/; print length(binomial(100000,50000)), "\n";</lang>

Output:

The Math::Pari module also has binomial, but it needs large amounts of added stack space for large arguments (this is due to using a very old version of the underlying Pari library).

Perl 6

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

Output:

One drawback of this method is that it returns a Rat, not an Int. If we really worry about it, we can enforce the conversion: <lang perl6>sub infix:<choose> { ([*] ($^n ... 0) Z/ 1 .. $^p).Int }</lang>

PL/I

<lang 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; </lang>

Output:

PHP

<lang 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; ?></lang>

Alternative version, not based on factorial <lang PHP> 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;

} </lang>

PicoLisp

<lang PicoLisp>(de binomial (N K)

  (let f
     '((N)
        (if (=0 N) 1 (apply * (range 1 N))) )
     (/
        (f N)
        (* (f (- N K)) (f K)) ) ) )</lang>

Output:

: (binomial 5 3)
-> 10

PowerShell

<lang PowerShell> function choose($n,$k) {

   if($k -le $n -and 0 -le $k) {
       $numerator = $denominator = 1
       0..($k-1) | foreach{
           $numerator *= ($n-$_)
           $denominator *= ($_ + 1)
       }
       $numerator/$denominator
   } else {
       "$k is greater than $n or lower than 0"
   }

} choose 5 3 choose 2 1 choose 10 10 choose 10 2 choose 10 8 </lang> Output:

PureBasic

<lang 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</lang> Example

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

Python

Straight-forward implementation: <lang python>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))</lang>

Output:

Alternate implementation <lang python>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) )</lang>

R

R's built-in choose() function evaluates binomial coefficients: <lang r>choose(5,3)</lang>

Output:

[1] 10

Racket

lang racket

(require math) (binomial 10 5) </lang>

REXX

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

idiomatic

<lang rexx>/*REXX program calculates binomial coefficients (aka, combinations). */ numeric digits 100000 /*be able to handle gihugeic numbers. */ parse arg n k . /*obtain N and K from the C.L. */ say 'combinations('n","k')=' comb(n,k) /*display the number of combinations. */ exit /*stick a fork in it, we're all done. */ /*────────────────────────────────────────────────────────────────────────────*/ comb: procedure; parse arg x,y; return !(x) % (!(x-y) * !(y)) /*────────────────────────────────────────────────────────────────────────────*/ !: procedure; !=1; do j=2 to arg(1); !=!*j; end; return !</lang> output when using the input of: 5 3

combinations(5,3)= 10

output when using the input of: 1200 120

combinations(1200,120)= 1004576581793084916475353119318331966507299414258370667602185866686463289093457468590558508056798211449853806741873396451735444387513582540860551330127062642417424083600

optimized

This REXX version takes advantage of reducing the size (product) of the numerator, and also,
only two (factorial) products need be calculated. <lang rexx>/*REXX program calculates binomial coefficients (aka, combinations). */ numeric digits 100000 /*be able to handle gihugeic numbers. */ parse arg n k . /*obtain N and K from the C.L. */ say 'combinations('n","k')=' comb(n,k) /*display the number of combinations. */ exit /*stick a fork in it, we're all done. */ /*────────────────────────────────────────────────────────────────────────────*/ comb: procedure; parse arg x,y; return pfact(x-y+1,x) % pfact(2,y) /*────────────────────────────────────────────────────────────────────────────*/ pfact: procedure; !=1; do j=arg(1) to arg(2); !=!*j; end; return !</lang> output is identical to the 1^st version.

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

Ruby

Translation of: Tcl

Works with: Ruby version 1.8.7+

<lang ruby>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)</lang> result

10
118264581564861424

another implementation:

<lang ruby> def c n, r

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

end </lang>

Run BASIC

<lang runbasic>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</lang>

Output:

binomial (5,1) = 5
binomial (5,2) = 10
binomial (5,3) = 10
binomial (5,4) = 5
binomial (5,5) = 1

Scala

<lang 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)

}</lang>

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:

<lang scala>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)))

}</lang>

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): <lang scala> 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))</lang>

Output:

bico(5,3) = 10

Scheme

Works with: Scheme version R

^{5}

RS

<lang scheme>(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)</lang>

Output:

Seed7

The infix operator ! computes the binomial coefficient. E.g.: 5 ! 3 evaluates to 10. The binomial coefficient operator works also for negative values of n. E.g.: (-6) ! 10 evaluates to 3003.

<lang seed7>$ include "seed7_05.s7i";

const proc: main is func

 local
   var integer: n is 0;
   var integer: k is 0;
 begin
   for n range 0 to 66 do
     for k range 0 to n do
        write(n ! k <& " ");
     end for;
     writeln;
   end for;
 end func;</lang>

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 
1 18 153 816 3060 8568 18564 31824 43758 48620 43758 31824 18564 8568 3060 816 153 18 1 
1 19 171 969 3876 11628 27132 50388 75582 92378 92378 75582 50388 27132 11628 3876 969 171 19 1 
1 20 190 1140 4845 15504 38760 77520 125970 167960 184756 167960 125970 77520 38760 15504 4845 1140 190 20 1 
...

The library bigint.s7i contains a definition of the binomial coefficient operator ! for the type bigInteger:

<lang seed7>const func bigInteger: (in bigInteger: n) ! (in var bigInteger: k) is func

 result
   var bigInteger: binom is 0_;
 local
   var bigInteger: numerator is 0_;
   var bigInteger: denominator is 0_;
 begin
   if n >= 0_ and k > n >> 1 then
     k := n - k;
   end if;
   if k < 0_ then
     binom := 0_;
   elsif k = 0_ then
     binom := 1_;
   else
     binom := n;
     numerator := pred(n);
     denominator := 2_;
     while denominator <= k do
       binom *:= numerator;
       binom := binom div denominator;
       decr(numerator);
       incr(denominator);
     end while;
   end if;
 end func;

</lang>

Original source [1].

Sidef

Straightforward translation of the formula: <lang ruby>__USE_INTNUM__

func binomial(n,k) {

   n! / ((n-k)! * k!);

}

say binomial(400, 200);</lang>

Alternatively, by using the Number.nok() method: <lang ruby>say 400.nok(200);</lang>

Tcl

This uses exact arbitrary precision integer arithmetic. <lang tcl>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}]

}</lang> Demonstrating: <lang tcl>puts "5_C_3 = [binom 5 3]" puts "60_C_30 = [binom 60 30]"</lang>

Output:

5_C_3 = 10
60_C_30 = 118264581564861424

TI-89 BASIC

Builtin function.

TXR

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

<lang sh>$ txr -p '(n-choose-k 20 15)' 15504</lang>

UNIX Shell

<lang sh>#!/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"</lang>

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. <lang Ursala>#import nat

choose = ~&ar^?\1! quotient^\~&ar product^/~&al ^|R/~& predecessor~~</lang> 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. <lang Ursala>choose = quotient^/factorial@l product+ factorial^~/difference ~&r</lang>

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. <lang Ursala>choose("n","k") = quotient(factorial "n",product factorial~~ (difference("n","k"),"k"))</lang> test program: <lang Ursala>#cast %nL

main = choose* <(5,3),(60,30)></lang>

Output:

<10,118264581564861424>

VBScript

<lang vb>Function binomial(n,k) binomial = factorial(n)/(factorial(n-k)*factorial(k)) End Function

Function factorial(n) If n = 0 Then factorial = 1 Else For i = n To 1 Step -1 If i = n Then factorial = n Else factorial = factorial * i End If Next End If End Function

'calling the function WScript.StdOut.Write "the binomial coefficient of 5 and 3 = " & binomial(5,3) WScript.StdOut.WriteLine</lang>

Output:

the binomial coefficient of 5 and 3 = 10

Windows Batch

<lang dos>@echo off & setlocal

if "%~2"=="" ( echo Usage: %~nx0 n k && goto :EOF )

call :binom binom %~1 %~2 1>&2 set /P "=%~1 choose %~2 = "<NUL echo %binom%

goto :EOF

binom <var_to_set> <N> <K>

setlocal set /a coeff=1, nk=%~2 - %~3 + 1 for /L %%I in (%nk%, 1, %~2) do set /a coeff *= %%I for /L %%I in (1, 1, %~3) do set /a coeff /= %%I endlocal && set "%~1=%coeff%" goto :EOF</lang>

Output:

> binom.bat 5 3
5 choose 3 = 10

> binom.bat 100 2
100 choose 2 = 4950

The string n choose k = is output to stderr, while the result is echoed to stdout. This should allow capturing the result with a for /f loop without needing to define tokens or delims.

But...

> binom.bat 33 17
33 choose 17 = 0

> binom.bat 15 10
15 choose 10 = -547

The Windows cmd console only handles 32-bit integers. If a factoral exceeds 2147483647 at any point, set /a will choke and roll over to a negative value, giving unexpected results. Unfortunately, this is as good as it gets for pure batch. It's probably better to employ a PowerShell or JScript helper or similar instead.

XPL0

<lang 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!</lang>

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

zkl

Using 64 bit ints: <lang zkl>fcn binomial(n,k){ (1).reduce(k,fcn(p,i,n){ p*(n-i+1)/i },1,n) }</lang>

Output:

zkl: binomial(5,3)
10
zkl: binomial(60,30)
118264581564861424

@@ Line 11: / Line 11: @@
 * [[Pascal's triangle]]
 {{Template:Combinations and permutations}}
+=={{header|360 Assembly}}==
+{{trans|ABAP}}
+Very compact version.
+<lang 360asm>
+*        Evaluate binomial coefficients - 29/09/2015
+BINOMIAL CSECT
+         USING  BINOMIAL,R15       set base register
+         SR     R4,R4              clear for mult and div
+         LA     R5,1               r=1
+         LA     R7,1               i=1
+         L      R8,N               m=n
+LOOP     LR     R4,R7              do while i<=k
+         C      R4,K               i<=k
+         BH     LOOPEND            if not then exit while
+         MR     R4,R8              r*m
+         DR     R4,R7              r=r*m/i
+         LA     R7,1(R7)           i=i+1
+         BCTR   R8,0               m=m-1
+         B      LOOP               loop while
+LOOPEND  XDECO  R5,PG              edit r
+         XPRNT  PG,12              print r
+         XR     R15,R15            set return code
+         BR     R14                return to caller
+N        DC     F'10'              <== input value
+K        DC     F'4'               <== input value
+PG       DS     CL12               buffer
+         YREGS
+         END    BINOMIAL
+</lang>
+{{out}}
+<pre>
+</pre>
 =={{header|ABAP}}==