Evaluate binomial coefficients: Difference between revisions
m
→{{header|Oberon}}: Fixed language name
m (→{{header|Oberon}}: Fixed language name) |
|||
(38 intermediate revisions by 22 users not shown) | |||
Line 18:
=={{header|11l}}==
{{trans|Python}}
<
V result = 1
L(i) 1..k
Line 24:
R result
print(binomial_coeff(5, 3))</
{{out}}
Line 34:
{{trans|ABAP}}
Very compact version.
<
BINOMIAL CSECT
USING BINOMIAL,R15 set base register
Line 57:
PG DS CL12 buffer
YREGS
END BINOMIAL</
{{out}}
<pre>
Line 64:
=={{header|ABAP}}==
<
PUBLIC SECTION.
Line 91:
ENDMETHOD.
ENDCLASS.</
{{Out}}
<pre>lcl_binom=>calc( n = 5 k = 3 )
Line 100:
=={{header|ACL2}}==
<
(if (zp n)
1
Line 106:
(defun binom (n k)
(/ (fac n) (* (fac (- n k)) (fac k)))</
=={{header|Ada}}==
<syntaxhighlight lang="ada">
with Ada.Text_IO; use Ada.Text_IO;
procedure Test_Binomial is
Line 137:
end loop;
end Test_Binomial;
</syntaxhighlight>
{{Out}}
<pre>
Line 170:
{{works with|ELLA ALGOL 68|Any (with appropriate job cards) - tested with release [http://sourceforge.net/projects/algol68/files/algol68toc/algol68toc-1.8.8d/algol68toc-1.8-8d.fc9.i386.rpm/download 1.8-8d]}}
<
(
INT result;
Line 194:
test:(
print((choose(5, 3), new line))
)</
{{Out}}
<pre>
Line 201:
=={{header|ALGOL W}}==
<
% calculates n!/k! %
integer procedure factorialOverFactorial( integer value n, k ) ;
Line 232:
write( binomialCoefficient( 5, 3 ) )
end.</
=={{header|APL}}==
When the factorial operator <tt>!</tt> is used as a dyad, it returns the binomial coefficient: <tt>k!n</tt> = <i>n</i> choose <i>k</i>.
<syntaxhighlight lang="apl"> 3!5
10</syntaxhighlight>
=={{header|AppleScript}}==
===Imperative===
<
set k to 3
Line 253 ⟶ 258:
return n_factorial / (n_minus_k_factorial) * 1 / (k_factorial) as integer
</syntaxhighlight>
===Functional===
Line 259 ⟶ 264:
Using a little more abstraction for readability, and currying for ease of both re-use and refactoring:
<
on factorial(n)
product(enumFromTo(1, n))
Line 336 ⟶ 341:
foldl(multiply, 1, xs)
end product</
{{Out}}
<pre>{10, 10}</pre>
=={{header|Arturo}}==
<syntaxhighlight lang="rebol">factorial: function [n]-> product 1..n
binomial: function [x,y]-> (factorial x) / (factorial y) * factorial x-y
print binomial 5 3</syntaxhighlight>
{{out}}
<pre>10</pre>
=={{header|AutoHotkey}}==
<
;---------------------------------------------------------------------------
Line 352 ⟶ 368:
}
Return, r
}</
Message box shows:
<pre>10</pre>
=={{header|AWK}}==
<syntaxhighlight lang="awk">
# syntax: GAWK -f EVALUATE_BINOMIAL_COEFFICIENTS.AWK
BEGIN {
Line 371 ⟶ 388:
printf("%d %d = %d\n",n,k,r)
}
</syntaxhighlight>
{{out}}
<pre>
Line 380 ⟶ 397:
=={{header|Batch File}}==
<
if "%~2"=="" ( echo Usage: %~nx0 n k && goto :EOF )
Line 396 ⟶ 413:
for /L %%I in (1, 1, %~3) do set /a coeff /= %%I
endlocal && set "%~1=%coeff%"
goto :EOF</
{{Out}}
Line 419 ⟶ 436:
</pre>
The Windows cmd console only handles 32-bit integers. If a factoral exceeds 2147483647 at any point, <code>set /a</code> will choke and roll over to a negative value, giving unexpected results. Unfortunately, this is as good as it gets for pure batch.
=={{header|BCPL}}==
<syntaxhighlight lang="bcpl">
GET "libhdr"
LET choose(n, k) =
~(0 <= k <= n) -> 0,
2*k > n -> binomial(n, n - k),
binomial(n, k)
AND binomial(n, k) =
k = 0 -> 1,
binomial(n, k - 1) * (n - k + 1) / k
LET start() = VALOF {
LET n, k = ?, ?
LET argv = VEC 20
LET sz = ?
sz := rdargs("n/a/n/p,k/a/n/p", argv, 20)
UNLESS sz ~= 0 RESULTIS 1
n := !argv!0
k := !argv!1
writef("%d choose %d = %d *n", n, k, choose(n, k))
RESULTIS 0
}
</syntaxhighlight>
{{Out}}
Note that with the /p flag to rdargs(), the system will prompt if we don't supply both arguments on the command line.
<pre>
$ cintsys64
BCPL 64-bit Cintcode System (13 Jan 2020)
0.004> nCk 50 25
50 choose 25 = 126410606437752
0.003> nCk 10 5
10 choose 5 = 252
0.004> nCk 100 2
100 choose 2 = 4950
0.000> nCk 100 98
100 choose 98 = 4950
0.004> nCk
n > 5
k > 3
5 choose 3 = 10
</pre>
=={{header|BBC BASIC}}==
<
PRINT "Binomial (5,3) = "; FNbinomial(5, 3)
Line 441 ⟶ 506:
ENDWHILE
= R%
</syntaxhighlight>
{{Out}}
<pre>Binomial (5,3) = 10
Line 448 ⟶ 513:
=={{header|Bracmat}}==
<
n k coef
. !arg:(?n,?k)
Line 464 ⟶ 529:
binomial$(5,3)
10
</syntaxhighlight>
=={{header|Burlesque}}==
<
blsq ) 5 3nr
10
</syntaxhighlight>
=={{header|C}}==
<
#include <limits.h>
Line 516 ⟶ 581:
printf("%lu\n", binomial(67, 31));
return 0;
}</
{{out}}
<pre>10
131282408400
11923179284862717872</pre>
=={{header|C sharp|C#}}==
<
namespace BinomialCoefficients
Line 593 ⟶ 624:
}
}
}</
=={{header|C++}}==
<syntaxhighlight 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 binomialCoefficient(double n, double k)
{
if (abs(n - k) < 1e-7 || k < 1e-7) return 1.0;
if( abs(k-1.0) < 1e-7 || abs(k - (n-1)) < 1e-7)return n;
return Factorial(n) /(Factorial(k)*Factorial((n - k)));
}
</syntaxhighlight>
Implementation:
<syntaxhighlight lang="cpp">int main()
{
cout<<"The Binomial Coefficient of 5, and 3, is equal to: "<< binomialCoefficient(5,3);
cin.get();
}</syntaxhighlight>
{{Out}}
<pre>The Binomial Coefficient of 5, and 3, is equal to: 10</pre>
=={{header|Clojure}}==
<
(let [rprod (fn [a b] (reduce * (range a (inc b))))]
(/ (rprod (- n k -1) n) (rprod 1 k))))</
=={{header|CoffeeScript}}==
<
binomial_coefficient = (n, k) ->
result = 1
Line 611 ⟶ 676:
for k in [0..n]
console.log "binomial_coefficient(#{n}, #{k}) = #{binomial_coefficient(n,k)}"
</syntaxhighlight>
{{Out}}<pre>
Line 622 ⟶ 687:
binomial_coefficient(5, 5) = 1
</pre>
=={{header|Commodore BASIC}}==
<syntaxhighlight lang="freebasic">
10 REM BINOMIAL COEFFICIENTS
20 REM COMMODORE BASIC 2.0
30 REM 2021-08-24
40 REM BY ALVALONGO
100 Z=0:U=1
110 FOR N=U TO 10
120 PRINT N;
130 FOR K=Z TO N
140 GOSUB 900
150 PRINT C;
160 NEXT K
170 PRINT
180 NEXT N
190 END
900 REM BINOMIAL COEFFICIENT
910 IF K<Z OR K>N THEN C=Z:RETURN
920 IF K=Z OR K=N THEN C=U:RETURN
930 P=K:IF N-K<P THEN P=N-K
940 C=U
950 FOR I=Z TO P-U
960 C=C/(I+U)*(N-I)
980 NEXT I
990 RETURN
</syntaxhighlight>
=={{header|Common Lisp}}==
<
(defun choose (n k)
(labels ((prod-enum (s e)
Line 630 ⟶ 731:
(fact (n) (prod-enum 1 n)))
(/ (prod-enum (- (1+ n) k) n) (fact k))))
</syntaxhighlight>
=={{header|D}}==
<
if (k > (n / 2))
k = n - k;
Line 648 ⟶ 749:
writefln("(%3d %3d) = %s", d[0], d[1], binomial(d[0], d[1]));
writeln("(100 50) = ", binomial(100.BigInt, 50.BigInt));
}</
{{out}}
<pre>( 5 3) = 2
Line 655 ⟶ 756:
(100 50) = 1976664223067613962806675336</pre>
The above wouldn't work for me (100C50 correctly gives 100891344545564193334812497256).
{{trans|C#}}
<syntaxhighlight lang="d">T BinomialCoeff(T)(in T n, in T k)
{
T nn = n, kk = k, c = cast(T)1;
Line 677 ⟶ 781:
BinomialCoeff(10UL, 3UL).writeln;
BinomialCoeff(100.BigInt, 50.BigInt).writeln;
}</
{{out}}
<pre>120
Line 683 ⟶ 787:
=={{header|dc}}==
<
Demonstration:
<syntaxhighlight lang
<tt>10</tt>
Annotated version:
<
[sx [ x is our dump register; get rid of extraneous copy of n we no longer need]sx
1 [ return value is 1 ]sx
Line 722 ⟶ 826:
] sb
5 3 lb x p [print(5 choose 3)]sx</
=={{header|Delphi}}==
<
{$APPTYPE CONSOLE}
Line 753 ⟶ 857:
Writeln('C(5,3) is ', BinomialCoff(5, 3));
ReadLn;
end.</
=={{header|EasyLang}}==
<syntaxhighlight>
func binomial n k .
if k > n / 2
k = n - k
.
numer = 1
for i = n downto n - k + 1
numer = numer * i
.
denom = 1
for i = 1 to k
denom = denom * i
.
return numer / denom
.
print binomial 5 3
</syntaxhighlight>
=={{header|Elixir}}==
{{trans|Erlang}}
<
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)
Line 767 ⟶ 890:
IO.inspect RC.choose(5,3)
IO.inspect RC.choose(60,30)</
{{out}}
Line 776 ⟶ 899:
=={{header|Erlang}}==
<
choose(N, 0) -> 1;
choose(N, K) when is_integer(N), is_integer(K), (N >= 0), (K >= 0), (N >= K) ->
Line 785 ⟶ 908:
choose(N, K, I, Acc) ->
choose(N, K, I+1, (Acc * (N-I+1)) div I).
</syntaxhighlight>
=={{header|ERRE}}==
<syntaxhighlight lang="text">PROGRAM BINOMIAL
!$DOUBLE
Line 815 ⟶ 938:
PRINT("Binomial (33,17) = ";BIN)
END PROGRAM
</syntaxhighlight>
{{out}}
<pre>Binomial (5,3) = 10
Line 821 ⟶ 944:
Binomial (33,17) = 1166803110
</pre>
=={{header|F Sharp|F#}}==
<syntaxhighlight lang="fsharp">
let choose n k = List.fold (fun s i -> s * (n-i+1)/i ) 1 [1..k]
</syntaxhighlight>
=={{header|Factor}}==
<
: fact ( n -- n-factorial )
dup 0 = [ drop 1 ] [ dup 1 - fact * ] if ;
Line 839 ⟶ 967:
: choose-fold ( n k -- n-choose-k )
2dup 1 + [a,b] product -rot - 1 [a,b] product / ;
</syntaxhighlight>
=={{header|
The binomial function is built in.
<syntaxhighlight lang="fermat">Bin(5,3)</syntaxhighlight>
{{out}}<pre>10</pre>
=={{header|Forth}}==
<
5 3 choose . \ 10
33 17 choose . \ 1166803110</
=={{header|Fortran}}==
=== Direct Method ===
{{works with|Fortran|90 and later}}
<
implicit none
Line 884 ⟶ 1,014:
end function choose
end program test_choose</
{{Out}}<pre>10</pre>
=== Avoiding Overflow ===
Of course this method doesn't avoid overflow completely just delays it. It could be extended by adding more entries to the '''primes''' array
<syntaxhighlight lang="fortran">
program binomial
integer :: i, j
do j=1,20
write(*,fmt='(i2,a)',advance='no') j,'Cr = '
do i=0,j
write(*,fmt='(i0,a)',advance='no') n_C_r(j,i),' '
end do
write(*,'(a,i0)') ' 60C30 = ',n_C_r(60,30)
end do
stop
contains
pure function n_C_r(n, r) result(bin)
integer(16) :: bin
integer, intent(in) :: n
integer, intent(in) :: r
integer(16) :: num
integer(16) :: den
integer :: i
integer :: k
integer, parameter :: primes(*) = [2,3,5,7,11,13,17,19]
num = 1
den = 1
do i=0,r-1
num = num*(n-i)
den = den*(i+1)
if (i > 0) then
! Divide out common prime factors
do k=1,size(primes)
if (mod(i,primes(k)) == 0) then
num = num/primes(k)
den = den/primes(k)
end if
end do
end if
end do
bin = num/den
end function n_C_r
end program binomial
</syntaxhighlight>
{{Out}}
1Cr = 1 1
2Cr = 1 2 1
3Cr = 1 3 3 1
4Cr = 1 4 6 4 1
5Cr = 1 5 10 10 5 1
6Cr = 1 6 15 20 15 6 1
7Cr = 1 7 21 35 35 21 7 1
8Cr = 1 8 28 56 70 56 28 8 1
9Cr = 1 9 36 84 126 126 84 36 9 1
10Cr = 1 10 45 120 210 252 210 120 45 10 1
11Cr = 1 11 55 165 330 462 462 330 165 55 11 1
12Cr = 1 12 66 220 495 792 924 792 495 220 66 12 1
13Cr = 1 13 78 286 715 1287 1716 1716 1287 715 286 78 13 1
14Cr = 1 14 91 364 1001 2002 3003 3432 3003 2002 1001 364 91 14 1
15Cr = 1 15 105 455 1365 3003 5005 6435 6435 5005 3003 1365 455 105 15 1
16Cr = 1 16 120 560 1820 4368 8008 11440 12870 11440 8008 4368 1820 560 120 16 1
17Cr = 1 17 136 680 2380 6188 12376 19448 24310 24310 19448 12376 6188 2380 680 136 17 1
18Cr = 1 18 153 816 3060 8568 18564 31824 43758 48620 43758 31824 18564 8568 3060 816 153 18 1
19Cr = 1 19 171 969 3876 11628 27132 50388 75582 92378 92378 75582 50388 27132 11628 3876 969 171 19 1
20Cr = 1 20 190 1140 4845 15504 38760 77520 125970 167960 184756 167960 125970 77520 38760 15504 4845 1140 190 20 1
21Cr = 1 21 210 1330 5985 20349 54264 116280 203490 293930 352716 352716 293930 203490 116280 54264 20349 5985 1330 210 21 1
22Cr = 1 22 231 1540 7315 26334 74613 170544 319770 497420 646646 705432 646646 497420 319770 170544 74613 26334 7315 1540 231 22 1
23Cr = 1 23 253 1771 8855 33649 100947 245157 490314 817190 1144066 1352078 1352078 1144066 817190 490314 245157 100947 33649 8855 1771 253 23 1
24Cr = 1 24 276 2024 10626 42504 134596 346104 735471 1307504 1961256 2496144 2704156 2496144 1961256 1307504 735471 346104 134596 42504 10626 2024 276 24 1
25Cr = 1 25 300 2300 12650 53130 177100 480700 1081575 2042975 3268760 4457400 5200300 5200300 4457400 3268760 2042975 1081575 480700 177100 53130 12650 2300 300 25 1
60C30 = 118264581564861424
=={{header|FreeBASIC}}==
<
Function factorial(n As Integer) As Integer
Line 918 ⟶ 1,124:
Print
Print "Press any key to quit"
Sleep</
{{out}}
Line 942 ⟶ 1,148:
Frink has a built-in efficient function to find binomial coefficients.
It produces arbitrarily-large integers.
<
println[binomial[5,3]]
</syntaxhighlight>
=={{header|FunL}}==
FunL has pre-defined function <code>choose</code> in module <code>integers</code>, which is defined as:
<
choose( n, k ) | k < 0 or k > n = 0
choose( n, 0 ) = 1
Line 955 ⟶ 1,161:
println( choose(5, 3) )
println( choose(60, 30) )</
{{out}}
<pre>
Line 963 ⟶ 1,169:
Here it is defined using the recommended formula for this task.
<
def
binomial( n, k ) | k < 0 or k > n = 0
binomial( n, k ) = factorial( n )/factorial( n - k )/factorial( k )</
=={{header|GAP}}==
<
Binomial(5, 3);
# 10</
=={{header|Go}}==
<
import "fmt"
import "math/big"
Line 982 ⟶ 1,188:
fmt.Println(new(big.Int).Binomial(5, 3))
fmt.Println(new(big.Int).Binomial(60, 30))
}</
{{out}}
<pre>
Line 991 ⟶ 1,197:
=={{header|Golfscript}}==
Actually evaluating n!/(k! (n-k)!):
<
{),(;{*}*}:f; # Define a factorial function
.f@.f@/\@-f/</
But Golfscript is meant for golfing, and it's shorter to calculate <math>\prod_{i=0}^{k-1} \frac{n-i}{i+1}</math>:
<
1\,@{1$-@\*\)/}+/</
=={{header|Groovy}}==
Solution:
<
assert x > -1
x == 0 ? 1 : (1..x).inject(1G) { BigInteger product, BigInteger factor -> product *= factor }
Line 1,010 ⟶ 1,216:
assert n >= k
factorial(n).intdiv(factorial(k)*factorial(n-k))
}</
Test:
<
assert combinations(20, 10) == (combinations(19, 9) + combinations(19, 10))
assert combinations(5, 3) == 10
println combinations(5, 3)</
{{Out}}
<pre>10</pre>
=={{header|GW-BASIC}}==
<syntaxhighlight lang="gwbasic">10 REM BINOMIAL CALCULATOR
20 INPUT "N? ", N
30 INPUT "P? ", P
40 GOSUB 70
50 PRINT C
60 END
70 C = 0
80 IF N < 0 OR P<0 OR P > N THEN RETURN
90 IF P < N\2 THEN P = N - P
100 C = 1
110 FOR I = N TO P+1 STEP -1
120 C=C*I
130 NEXT I
140 FOR I = 1 TO N-P
150 C=C/I
160 NEXT I
170 RETURN</syntaxhighlight>
=={{header|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]
</syntaxhighlight>
<
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]
</syntaxhighlight>
Or using "caching":
<
where
next ns = zipWith (+) (0:ns) $ ns ++ [0]
main = print $ coeffs !! 5 !! 3</
=={{header|HicEst}}==
<
FUNCTION factorial( n )
Line 1,059 ⟶ 1,284:
FUNCTION BinomCoeff( n, k )
BinomCoeff = factorial(n)/factorial(n-k)/factorial(k)
END</
=={{header|Icon}} and {{header|Unicon}}==
<
procedure main()
write("choose(5,3)=",binocoef(5,3))
end</
{{Out}}
<pre>choose(5,3)=10</pre>
Line 1,074 ⟶ 1,299:
[http://www.cs.arizona.edu/icon/library/src/procs/factors.icn factors provides factorial].
<
k := integer(k) | fail
Line 1,100 ⟶ 1,325:
return i
end</
=={{header|IS-BASIC}}==
<
110 PRINT "Binomial (5,3) =";BINOMIAL(5,3)
120 DEF BINOMIAL(N,K)
Line 1,115 ⟶ 1,340:
200 LOOP
210 LET BINOMIAL=R
220 END DEF</
=={{header|J}}==
Line 1,122 ⟶ 1,347:
'''Example usage:'''
<
10</
=={{header|Java}}==
<
// precise, but may overflow and then produce completely incorrect results
Line 1,196 ⟶ 1,421:
demo(1000, 300);
}
}</
{{Out}}
<pre>5 3 10 10 10.0 10
Line 1,203 ⟶ 1,428:
Recursive version, without overflow check:
<
{
private static long binom(int n, int k)
Line 1,219 ⟶ 1,444:
System.out.println(binom(5, 3));
}
}</
{{Out}}
<pre>10</pre>
=={{header|JavaScript}}==
<
var coeff = 1;
var i;
Line 1,237 ⟶ 1,462:
}
console.log(binom(5, 3));</
{{Out}}
<pre>10</pre>
=={{header|jq}}==
<
def binomial(n; k):
if k > n / 2 then binomial(n; n-k)
Line 1,254 ⟶ 1,479:
([5,3], [100,2], [ 33,17]) | task
</syntaxhighlight>
{{out}}
5 C 3 = 10
Line 1,264 ⟶ 1,489:
'''Built-in'''
<syntaxhighlight lang
'''Recursive version''':
<
n ≥ k || return 0 # short circuit base cases
(n == 1 || k == 0) && return 1
Line 1,274 ⟶ 1,499:
end
@show binom(5, 3)</
{{out}}
Line 1,281 ⟶ 1,506:
=={{header|K}}==
<
10</
Alternative version:
<
10</
Using Pascal's triangle:
<
pascal 5
(1
Line 1,299 ⟶ 1,524:
{[n;k](pascal n)[n;k]} . 5 3
10</
=={{header|Kotlin}}==
<syntaxhighlight lang
fun binomial(n: Int, k: Int) = when {
Line 1,317 ⟶ 1,533:
n == k -> 1L
else -> {
val kReduced = min(k, n - k) // minimize number of steps
var denominator = 1
while (denominator <= kReduced)
result = result * numerator-- / denominator++
result
}
}
Line 1,329 ⟶ 1,549:
println()
}
}</
{{out}}
Line 1,349 ⟶ 1,569:
1 14 91 364 1001 2002 3003 3432 3003 2002 1001 364 91 14 1
</pre>
=={{header|Lambdatalk}}==
<syntaxhighlight lang="scheme">
{def C
{lambda {:n :p}
{/ {* {S.serie :n {- :n :p -1} -1}}
{* {S.serie :p 1 -1}}}}}
-> C
{C 16 8}
-> 12870
1{S.map {lambda {:n} {br}1
{S.map {C :n} {S.serie 1 {- :n 1}}} 1}
{S.serie 2 16}}
->
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
</syntaxhighlight>
=={{header|Lasso}}==
<
#k == 0 ? return 1
local(result = 1)
Line 1,362 ⟶ 1,617:
binomial(5, 3)
binomial(5, 4)
binomial(60, 30)</
{{Out}}
Line 1,368 ⟶ 1,623:
5
118264581564861424</pre>
=={{header|Liberty BASIC}}==
<syntaxhighlight lang="lb">
' [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
</syntaxhighlight>
=={{header|Logo}}==
<
if :k = 0 [output 1]
output (choose :n :k-1) * (:n - :k + 1) / :k
Line 1,376 ⟶ 1,657:
show choose 5 3 ; 10
show choose 60 30 ; 1.18264581564861e+17</
=={{header|Lua}}==
<
if k > n then return nil end
if k > n/2 then k = n - k end -- (n k) = (n n-k)
Line 1,388 ⟶ 1,670:
end
return numer / denom
end</
Additive recursion with memoization by hashing 2 input integer.
Lua 5.3 support bit-wise operation; assume 64 bit integer implementation here.
<
__call = function(self,n,k)
local hash = (n<<32) | (k & 0xffffffff)
Line 1,422 ⟶ 1,704:
})
print( Binomial(100,50)) -- 1.0089134454556e+029
</syntaxhighlight>
=={{header|Maple}}==
<
binomial(5,3);</
{{Out}}
<pre> factorial(n)
Line 1,463 ⟶ 1,718:
=={{header|Mathematica}} / {{header|Wolfram Language}}==
<
(Local) Out[1]= 10</
=={{header|MATLAB}} / {{header|Octave}}==
Line 1,470 ⟶ 1,725:
Solution:
<
ans =
10</
Alternative implementations are:
<
r = diag(rot90(pascal(n+1))); % vector of all binomial coefficients for order n
r = r(k);
end; </
<
prod((n-k+1:n)./(1:k))
end; </
<
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:
<
coefficients = zeros(numel(n),numel(k)); %Preallocate memory
Line 1,512 ⟶ 1,767:
end
end %binomialCoeff</
Sample Usage:
<
ans =
Line 1,553 ⟶ 1,808:
ans =
10</
=={{header|Maxima}}==
<
binomial(-5, 3); /* -35 */
binomial( 5, -3); /* 0 */
Line 1,568 ⟶ 1,823:
binomial(a, b); /* binomial(a, b) */
makegamma(%); /* gamma(a + 1)/(gamma(-b + a + 1)*gamma(b + 1)) */</
=={{header|min}}==
{{works with|min|0.19.3}}
<
('dup dip dup ((fact) () (- fact) (fact * div)) spread) :binomial
5 3 binomial puts!</
{{out}}
<pre>
10
</pre>
=={{header|MINIL}}==
<
00 0E Go: ENT R0 // n
01 1E ENT R1 // r
Line 1,621 ⟶ 1,869:
1D C9 JNZ Next
1E 03 R0 = R3
1F 80 JZ Go // Display result</
This uses the recursive definition:
Line 1,630 ⟶ 1,878:
which results from the definition of ncr in terms of factorials.
=={{header|МК-61/52}}==
<syntaxhighlight lang="text">П1 <-> П0 ПП 22 П2 ИП1 ПП 22 П3
ИП0 ИП1 - ПП 22 ИП3 * П3 ИП2 ИП3
/ С/П ВП П0 1 ИП0 * L0 25 В/О</syntaxhighlight>
''Input'': ''n'' ^ ''k'' В/О С/П.
=={{header|Nanoquery}}==
{{trans|Python}}
<
result = 1
for i in range(1, k)
Line 1,643 ⟶ 1,898:
if main
println binomialCoeff(5,3)
end</
=={{header|Nim}}==
Note that a function to compute these coefficients, named “binom”, is available in standard module “math”.
<syntaxhighlight lang="nim">proc binomialCoeff(n, k: int): int =
result = 1
for i in 1..k:
result = result * (n-i+1) div i
echo binomialCoeff(5, 3)</
{{Out}}
<pre>10</pre>
=={{header|Oberon-2}}==
{{works with|oo2c}}
<
MODULE Binomial;
IMPORT
Line 1,679 ⟶ 1,935:
Out.Int(For(5,2),0);Out.Ln
END Binomial.
</syntaxhighlight>
{{Out}}
<pre>10</pre>
=={{header|OCaml}}==
<syntaxhighlight lang="ocaml">
let binomialCoeff n p =
let p = if p < n -. p then p else n -. p in
Line 1,695 ⟶ 1,951:
else res in
cm 1. n 1.
</syntaxhighlight>
=== Alternate version using big integers ===
<
open Num;;
Line 1,707 ⟶ 1,963:
else a (succ j) ((v */ (Int (n - j))) // (Int (succ j)))
in a 0 (Int 1)
;;</
=== Simple recursive version ===
<
let rec binomial n k = if n = k then Int 1 else ((binomial (n-1) k) */ Int n) // Int (n-k)</
=={{header|Oforth}}==
<
{{out}}
Line 1,726 ⟶ 1,981:
=={{header|Oz}}==
{{trans|Python}}
<
fun {BinomialCoeff N K}
{List.foldL {List.number 1 K 1}
Line 1,735 ⟶ 1,990:
end
in
{Show {BinomialCoeff 5 3}}</
=={{header|PARI/GP}}==
<syntaxhighlight lang
=={{header|Pascal}}==
Line 1,744 ⟶ 1,999:
=={{header|Perl}}==
<
use bigint;
my ($r, $n, $k) = (1, @_);
Line 1,751 ⟶ 2,006:
}
print binomial(5, 3);</
{{out}}
Line 1,757 ⟶ 2,012:
Since the bigint module already has a binomial method, this could also be written as:
<
use bigint;
my($n,$k) = @_;
(0+$n)->bnok($k);
}</
For better performance, especially with large inputs, one can also use something like:
{{libheader|ntheory}}
<
print length(binomial(100000,50000)), "\n";</
{{out}}
<pre>30101</pre>
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).
=={{header|Phix}}==
There is a builtin choose() function which does this. From builtins/factorial.e (an autoinclude):
<!--<syntaxhighlight lang="phix">-->
<span style="color: #008080;">global</span> <span style="color: #008080;">function</span> <span style="color: #000000;">choose</span><span style="color: #0000FF;">(</span><span style="color: #004080;">integer</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">k</span><span style="color: #0000FF;">)</span>
<span style="color: #004080;">atom</span> <span style="color: #000000;">res</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">1</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">k</span> <span style="color: #008080;">do</span>
<span style="color: #000000;">res</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">(</span><span style="color: #000000;">res</span><span style="color: #0000FF;">*(</span><span style="color: #000000;">n</span><span style="color: #0000FF;">-</span><span style="color: #000000;">i</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">))/</span><span style="color: #000000;">i</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">return</span> <span style="color: #000000;">res</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<!--</syntaxhighlight>-->
Example:
<!--<syntaxhighlight lang="phix">(phixonline)-->
<span style="color: #0000FF;">?</span><span style="color: #7060A8;">choose</span><span style="color: #0000FF;">(</span><span style="color: #000000;">5</span><span style="color: #0000FF;">,</span><span style="color: #000000;">3</span><span style="color: #0000FF;">)</span>
<!--</syntaxhighlight>-->
{{out}}
<pre>
10
</pre>
However errors will creep in should any result or interim value exceed 9,007,199,254,740,992 (on 32-bit), so
{{libheader|Phix/mpfr}}
<!--<syntaxhighlight lang="phix">(phixonline)-->
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>
<span style="color: #008080;">include</span> <span style="color: #000000;">builtins</span><span style="color: #0000FF;">\</span><span style="color: #004080;">mpfr</span><span style="color: #0000FF;">.</span><span style="color: #000000;">e</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">tests</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{{</span><span style="color: #000000;">5</span><span style="color: #0000FF;">,</span><span style="color: #000000;">3</span><span style="color: #0000FF;">},{</span><span style="color: #000000;">100</span><span style="color: #0000FF;">,</span><span style="color: #000000;">50</span><span style="color: #0000FF;">},{</span><span style="color: #000000;">60</span><span style="color: #0000FF;">,</span><span style="color: #000000;">30</span><span style="color: #0000FF;">},{</span><span style="color: #000000;">1200</span><span style="color: #0000FF;">,</span><span style="color: #000000;">120</span><span style="color: #0000FF;">}}</span>
<span style="color: #004080;">mpz</span> <span style="color: #000000;">r</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">mpz_init</span><span style="color: #0000FF;">()</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">tests</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
<span style="color: #004080;">integer</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">n</span><span style="color: #0000FF;">,</span><span style="color: #000000;">k</span><span style="color: #0000FF;">}</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">tests</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span>
<span style="color: #7060A8;">mpz_bin_uiui</span><span style="color: #0000FF;">(</span><span style="color: #000000;">r</span><span style="color: #0000FF;">,</span><span style="color: #000000;">n</span><span style="color: #0000FF;">,</span><span style="color: #000000;">k</span><span style="color: #0000FF;">)</span>
<span style="color: #0000FF;">?</span><span style="color: #7060A8;">mpz_get_str</span><span style="color: #0000FF;">(</span><span style="color: #000000;">r</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<!--</syntaxhighlight>-->
{{out}}
<pre>
Line 1,828 ⟶ 2,066:
"1004576581793084916475353119318331966507299414258370667602185866686463289093457468590558508056798211449853806741873396451735444387513582540860551330127062642417424083600"
</pre>
Note that I have re-implemented mpz_bin_uiui() mainly for the benefit of pwa/p2js, and some tweaks may be in order (please ask if needed) to match gmp proper for -ve n.
=={{header|PHP}}==
<
$n=5;
$k=3;
Line 1,839 ⟶ 2,078:
$binomial_coefficient=factorial($n)/(factorial($k)*factorial($n-$k));
echo $binomial_coefficient;
?></
Alternative version, not based on factorial
<syntaxhighlight lang="php">
function binomial_coefficient($n, $k) {
if ($k == 0) return 1;
Line 1,851 ⟶ 2,090:
return $result;
}
</syntaxhighlight>
=={{header|Picat}}==
===Iterative===
<syntaxhighlight lang="picat">binomial_it(N,K) = Res =>
if K < 0 ; K > N then
R = 0
else
R = 1,
foreach(I in 0..K-1)
R := R * (N-I) // (I+1)
end
end,
Res = R.</syntaxhighlight>
===Using built-in factorial/1===
<syntaxhighlight lang="picat">binomial_fac(N,K) = factorial(N) // factorial(K) // factorial(N-K).</syntaxhighlight>
===Recursion (tabled)===
<syntaxhighlight lang="picat">table
binomial_rec(_N, 0) = 1.
binomial_rec(0, _K) = 0.
binomial_rec(N, K) = binomial_rec(N-1,K-1) + binomial_rec(N-1,K).</syntaxhighlight>
===Test===
<syntaxhighlight lang="picat">go =>
Tests = [[10,3],[60,30],[100,50],[400,200]],
foreach([N,K] in Tests)
println([N,K,binomial_it(N,K)])
end,
nl.
</syntaxhighlight>
All methods prints the same result.
{{out}}
<pre>
[10,3,120]
[60,30,118264581564861424]
[100,50,100891344545564193334812497256]
[400,200,102952500135414432972975880320401986757210925381077648234849059575923332372651958598336595518976492951564048597506774120]</pre>
binomial_rec/2 is a little slower than the two other (0.036s vs 0.002s on these tests).
=={{header|PicoLisp}}==
<
(let f
'((N)
Line 1,860 ⟶ 2,143:
(/
(f N)
(* (f (- N K)) (f K)) ) ) )</
{{Out}}
<pre>: (binomial 5 3)
Line 1,866 ⟶ 2,149:
=={{header|PL/I}}==
<syntaxhighlight lang="pl/i">
binomial_coefficients:
procedure options (main);
Line 1,889 ⟶ 2,172:
end fact;
end binomial_coefficients;
</syntaxhighlight>
{{Out}}
<pre>
Line 1,896 ⟶ 2,179:
=={{header|PowerShell}}==
<syntaxhighlight lang="powershell">
function choose($n,$k) {
if($k -le $n -and 0 -le $k) {
Line 1,914 ⟶ 2,197:
choose 10 2
choose 10 8
</syntaxhighlight>
<b>Output:</b>
<pre>
Line 1,925 ⟶ 2,208:
=={{header|PureBasic}}==
<
Protected Result=1
While n>0
Line 1,945 ⟶ 2,228:
Print("Press ENTER to quit"): Input()
CloseConsole()
EndIf</
'''Example
Enter value n: 5
Line 1,953 ⟶ 2,236:
=={{header|Python}}==
===Imperative===
<
result = 1
for i in range(1, k+1):
Line 1,960 ⟶ 2,243:
if __name__ == "__main__":
print(binomialCoeff(5, 3))</
{{Out}}
<pre>10</pre>
===Functional===
<
from functools import reduce
Line 1,987 ⟶ 2,270:
else:
return ( reduce( mul, range((n - r + 1), n + 1), 1)
// reduce( mul, range(1, r + 1), 1) )</
Line 1,993 ⟶ 2,276:
{{Works with|Python|3.7}}
<
from functools import reduce
Line 2,052 ⟶ 2,335:
# TESTS ---------------------------------------------------
if __name__ == '__main__':
main()</
{{Out}}
<pre>10
Line 2,059 ⟶ 2,342:
Compare the use of Python comments, (above); with the use of Python type hints, (below).
<
from functools import reduce
from operator import mul
Line 2,083 ⟶ 2,366:
print(binomialCoefficient(5)(3))
# k=0 to k=5, where n=5
print(list(map(binomialCoefficient(5), enumFromTo(0)(5))))</
{{Out}}
<pre>10
[1, 5, 10, 10, 5, 1]</pre>
=={{header|Quackery}}==
<syntaxhighlight lang="quackery"> [ tuck - over
1 swap times
[ over i + 1+ * ]
nip swap times
[ i 1+ / ] ] is binomial ( n n --> )
5 3 binomial echo</syntaxhighlight>
{{out}}
<pre>10</pre>
=={{header|R}}==
R's built-in choose() function evaluates binomial coefficients:
<syntaxhighlight lang
{{Out}}
Line 2,096 ⟶ 2,394:
=={{header|Racket}}==
<
#lang racket
(require math)
(binomial 10 5)
</syntaxhighlight>
=={{header|Raku}}==
(formerly Perl 6)
For a start, you can get the length of the corresponding list of combinations:
<syntaxhighlight lang="raku" line>say combinations(5, 3).elems;</syntaxhighlight>
{{out}}
<pre>10</pre>
This method is efficient, as Raku will not actually compute each element of the list, since it actually uses an iterator with a defined <tt>count-only</tt> method. Such method performs computations in a way similar to the following infix operator:
<syntaxhighlight lang="raku" line>sub infix:<choose> { [*] ($^n ... 0) Z/ 1 .. $^p }
say 5 choose 3;</syntaxhighlight>
A possible optimization would use a symmetry property of the binomial coefficient:
<syntaxhighlight lang="raku" line>sub infix:<choose> { [*] ($^n ... 0) Z/ 1 .. min($n - $^p, $p) }</syntaxhighlight>
One drawback of this method is that it returns a Rat, not an Int. So we actually may want to enforce the conversion:
<syntaxhighlight lang="raku" line>sub infix:<choose> { ([*] ($^n ... 0) Z/ 1 .. min($n - $^p, $p)).Int }</syntaxhighlight>
And ''this'' is exactly what the <tt>count-only</tt> method does.
=={{header|REXX}}==
The task is to compute ANY binomial coefficient(s), but these REXX examples are limited to 100k digits.
===idiomatic===
<
numeric digits 100000 /*be able to handle gihugeic numbers. */
parse arg n k . /*obtain N and K from the C.L. */
Line 2,112 ⟶ 2,431:
/*──────────────────────────────────────────────────────────────────────────────────────*/
comb: procedure; parse arg x,y; return !(x) % (!(x-y) * !(y))
!: procedure; !=1; do j=2 to arg(1); !=!*j; end /*j*/; return !</
'''output''' when using the input of: <tt> 5 3 </tt>
<pre>
Line 2,125 ⟶ 2,444:
This REXX version takes advantage of reducing the size (product) of the numerator, and also,
<br>only two (factorial) products need be calculated.
<
numeric digits 100000 /*be able to handle gihugeic numbers. */
parse arg n k . /*obtain N and K from the C.L. */
Line 2,133 ⟶ 2,452:
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 /*j*/; return !</
'''output''' is identical to the 1<sup>st</sup> REXX version.
Line 2,140 ⟶ 2,459:
=={{header|Ring}}==
<
numer = 0
binomial(5,3)
Line 2,153 ⟶ 2,472:
next
return numer
</syntaxhighlight>
=={{header|RPL}}==
RPL has a <code>COMB</code> instruction which returns the result directly. If a home-made function is preferred, there are many possibilities.
Using the recommended formula and the stack:
≪ - LAST ! SWAP ! SWAP ROT ! * / ≫ ‘'''CHOOS'''’ STO
Using the formula with local variables:
≪ → n k ≪ n ! n k - ! / k ! / ≫ ≫ ‘'''CHOOS'''’ STO
To avoid data overflow for high values of n, using the formula simplified by (n-k)! :
≪ → n k ≪ 1 n k - 1 + n '''FOR''' j j * '''NEXT''' k ! / ≫ ≫ ‘'''CHOOS'''’ STO
All the above functions are called the same way and return the same result:
5 3 '''CHOOS'''
{{out}}
<pre>
10
</pre>
=={{header|Ruby}}==
Line 2,159 ⟶ 2,494:
{{works with|Ruby|1.8.7+}}
<
# binomial coefficient: n C k
def choose(k)
Line 2,171 ⟶ 2,506:
p 5.choose(3)
p 60.choose(30)</
result
<pre>10
Line 2,178 ⟶ 2,513:
another implementation:
<
def c n, r
(0...r).inject(1) do |m,i| (m * (n - i)) / (i + 1) end
end
</
<
=={{header|Run BASIC}}==
<
print "binomial (5,2) = "; binomial(5, 2)
print "binomial (5,3) = "; binomial(5, 3)
Line 2,202 ⟶ 2,537:
next i
binomial = coeff
end function</
{{Out}}
<pre>binomial (5,1) = 5
Line 2,211 ⟶ 2,546:
=={{header|Rust}}==
<
let mut f:u64 = n as u64;
for i in 2..n {
Line 2,229 ⟶ 2,564:
fn main() {
println!("{}", choose(5,3));
}</
{{Out}}
<pre>10</pre>
Line 2,235 ⟶ 2,570:
Alternative version, using functional style:
<
let factorial=|x| (1..=x).fold(1, |a, x| a * x);
factorial(n) / factorial(k) / factorial(n - k)
}</
=={{header|Scala}}==
<
def main(args: Array[String]): Unit = {
val n=5
Line 2,251 ⟶ 2,586:
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)
}</
{{Out}}
<pre>The Binomial Coefficient of 5 and 3 equals 10.</pre>
Line 2,257 ⟶ 2,592:
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:
<
def binomialCoefficient(n: Int, k: Int) =
(BigInt(n - k + 1) to n).product /
Line 2,264 ⟶ 2,599:
val Array(n, k) = args.map(_.toInt)
println("The Binomial Coefficient of %d and %d equals %,3d.".format(n, k, binomialCoefficient(n, k)))
}</
{{Out}}
Line 2,271 ⟶ 2,606:
Using recursive formula <code>C(n,k) = C(n-1,k-1) + C(n-1,k)</code>:
<
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))</
{{Out}}
<pre>bico(5,3) = 10</pre>
Line 2,282 ⟶ 2,617:
=={{header|Scheme}}==
{{Works with|Scheme|R<math>^5</math>RS}}
<
(define (*factorial n acc)
(if (zero? n)
Line 2,293 ⟶ 2,628:
(display (choose 5 3))
(newline)</
{{Out}}
<pre>10</pre>
Line 2,299 ⟶ 2,634:
Alternatively a recursive implementation can be constructed from Pascal's Triangle:
<
(cond ((= i 0) 1)
((= j 0) 1)
Line 2,310 ⟶ 2,645:
(display (choose 5 3))
(newline)</
{{Out}}
<pre>10</pre>
Line 2,319 ⟶ 2,654:
E.g.: <tt>(-6) ! 10</tt> evaluates to 3003.
<
const proc: main is func
Line 2,332 ⟶ 2,667:
writeln;
end for;
end func;</
{{Out}}
Line 2,364 ⟶ 2,699:
for the type [http://seed7.sourceforge.net/manual/types.htm#bigInteger bigInteger]:
<
result
var bigInteger: binom is 0_;
Line 2,390 ⟶ 2,725:
end if;
end func;
</syntaxhighlight>
Original source [http://seed7.sourceforge.net/algorith/math.htm#binomial_coefficient].
Line 2,397 ⟶ 2,732:
Simplest Solution:
<syntaxhighlight lang="sequencel">
choose(n, k) := product(k + 1 ... n) / product(1 ... n - k);
</syntaxhighlight>
Tail-Recursive solution to avoid arithmetic with large integers:
<syntaxhighlight lang="sequencel">
choose(n,k) := binomial(n, k, 1, 1);
Line 2,409 ⟶ 2,744:
result when i > k else
binomial(n, k, i + 1, (result * (n - i + 1)) / i);
</syntaxhighlight>
=={{header|Sidef}}==
Straightforward translation of the formula:
<
n! / ((n-k)! * k!)
}
say binomial(400, 200)</
Alternatively, by using the ''Number.nok()'' method:
<syntaxhighlight lang
=={{header|Smalltalk}}==
{{works with|Smalltalk/X}}
Having a small language but a big class library in my bag, we can write:
<syntaxhighlight lang="smalltalk">Transcript showCR: (5 binco:3).
Transcript showCR: (400 binco:200)</syntaxhighlight>
{{out}}
<pre>10
102952500135414432972975880320401986757210925381077648234849059575923332372651958598336595518976492951564048597506774120</pre>
A naïve implementation (in the Integer class) might look like:
<syntaxhighlight lang="smalltalk">binco:arg
^ (self factorial) / (arg factorial * (self-arg) factorial)</syntaxhighlight>
=={{header|Standard ML}}==
<syntaxhighlight lang="standardml">
fun binomial n k =
if k > n then 0 else
let fun f (_, 0) = 1
| f (i, d) = f (i + 1, d - 1) * i div d
in f (n - k + 1, k) end
</syntaxhighlight>
=={{header|Stata}}==
Use the [http://www.stata.com/help.cgi?comb comb] function. Notice the result is a missing value if k>n or k<0.
<
10</
=={{header|Swift}}==
<syntaxhighlight lang="swift">func factorial<T: BinaryInteger>(_ n: T) -> T {
guard n != 0 else {
return 1
}
return stride(from: n, to: 0, by: -1).reduce(1, *)
}
func binomial<T: BinaryInteger>(_ x: (n: T, k: T)) -> T {
let nFac = factorial(x.n)
let kFac = factorial(x.k)
return nFac / (factorial(x.n - x.k) * kFac)
}
print("binomial(\(5), \(3)) = \(binomial((5, 3)))")
print("binomial(\(20), \(11)) = \(binomial((20, 11)))")</syntaxhighlight>
{{out}}
<pre>binomial(5, 3) = 10
binomial(20, 11) = 167960</pre>
=={{header|Tcl}}==
This uses exact arbitrary precision integer arithmetic.
<
proc binom {n k} {
# Compute the top half of the division; this is n!/(n-k)!
Line 2,446 ⟶ 2,828:
# Integer arithmetic divide is correct here; the factors always cancel out
return [expr {$pTop / $pBottom}]
}</
Demonstrating:
<
puts "60_C_30 = [binom 60 30]"</
{{Out}}
<pre>5_C_3 = 10
60_C_30 = 118264581564861424</pre>
=={{header|TI-57}}==
{| class="wikitable"
! Machine code
! Comment
|-
|
'''Lbl 9'''
STO 2
x⮂t
STO 1
SBR 0
STO 3
RCL 1
-
RCL 2
=
SBR 0
INV Prd 3
RCL 2
SBR 0
Inv Prd 3
RCL 3
R/S
RST
'''Lbl 0'''
C.t
x=t
1
STO 0
'''Lbl 1'''
RCL 0
×
Dsz
GTO 1
1
=
INV SBR
|
'''program binomial(x,t)''' // x is the display register
r2 = x
swap x and t
r1 = x
x = factorial(x)
r3 = x
x = r1 - r2
x = factorial(x)
r3 /= x
x = r2
x = factorial(x)
r3 /= x
x = r3
end program
reset pointer
'''program factorial(x)'''
t=0
if x=0 then
x=1
r0 = x
loop
multiply r0 by what will be in the next loop
decrement r0 and exit loop if r0 = 0
end loop
complete the multiplication sequence
return x!
end sub
|}
<code> 5 </code> <code>x⮂t</code> <code> 3 </code> <code>GTO</code> <code> 9 </code> <code>R/S</code>
{{out}}
<pre>
10.
</pre>
=={{header|TI-83 BASIC}}==
Builtin operator nCr gives the number of combinations.
<syntaxhighlight lang
{{out}}
<pre>
Line 2,466 ⟶ 2,924:
Builtin function.
<syntaxhighlight lang
=={{header|TXR}}==
Line 2,472 ⟶ 2,930:
nCk is a built-in function, along with the one for permutations, nPk:
<
15504</
<
20274183401472000</
=={{header|UNIX Shell}}==
<
n=5;
k=3;
Line 2,499 ⟶ 2,957:
binomial_coefficient=$(expr $n_factorial \/ $k_factorial \* 1 \/ $n_minus_k_factorial )
echo "Binomial Coefficient ($n,$k) = $binomial_coefficient"</
=={{header|Ursala}}==
A function for computing binomial coefficients (<code>choose</code>) 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.
<
choose = ~&ar^?\1! quotient^\~&ar product^/~&al ^|R/~& predecessor~~</
The standard library functions <code>quotient</code>, <code>product</code> and <code>predecessor</code> pertain to natural numbers in the obvious way.
* <code>choose</code> is defined using the recursive conditional combinator (<code>^?</code>) as a function taking a pair of numbers, with the predicate <code>~&ar</code> testing whether the number on the right side of the pair is non-zero.
Line 2,517 ⟶ 2,973:
* The product of these values is then divided (<code>quotient</code>) by the right side (<code>~&ar</code>) of the original argument and returned as the result.
Here is a less efficient implementation more closely following the formula above.
<
* <code>choose</code> is defined as the <code>quotient</code> of the results of a pair (<code>^</code>) of functions.
* The left function contributing to the quotient is the <code>factorial</code> of the left side (<code>@l</code>) of the argument, which is assumed to be a pair of natural numbers. The <code>factorial</code> function is provided in a standard library.
Line 2,525 ⟶ 2,981:
* A composition (<code>+</code>) of this function with the <code>product</code> 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 (<code>~~</code>) operator.
<
test program:
<
main = choose* <(5,3),(60,30)></
{{Out}}
<pre><10,118264581564861424></pre>
=={{header|VBScript}}==
<
binomial = factorial(n)/(factorial(n-k)*factorial(k))
End Function
Line 2,554 ⟶ 3,010:
'calling the function
WScript.StdOut.Write "the binomial coefficient of 5 and 3 = " & binomial(5,3)
WScript.StdOut.WriteLine</
{{Out}}
<pre>the binomial coefficient of 5 and 3 = 10</pre>
=={{header|Wren}}==
{{libheader|Wren-fmt}}
{{libheader|Wren-math}}
<syntaxhighlight lang="wren">import "./fmt" for Fmt
import "./math" for Int
var binomial = Fn.new { |n, k|
if (n < 0 || k < 0) Fiber.abort("Arguments must be non-negative integers")
if (n < k) Fiber.abort("The second argument cannot be more than the first.")
if (n == k) return 1
var prod = 1
var i = n - k + 1
while (i <= n) {
prod = prod * i
i = i + 1
}
return prod / Int.factorial(k)
}
var limit = 14
System.write("n/k |")
for (k in 0..limit) System.write(Fmt.d(5, k))
System.print()
System.write("----+" + "-----" * (limit + 1))
System.print()
for (n in 0..limit) {
System.write("%(Fmt.d(3, n)) |")
for (k in 0..n) System.write(Fmt.d(5, binomial.call(n, k)))
System.print()
}</syntaxhighlight>
{{out}}
<pre>
n/k | 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
----+---------------------------------------------------------------------------
0 | 1
1 | 1 1
2 | 1 2 1
3 | 1 3 3 1
4 | 1 4 6 4 1
5 | 1 5 10 10 5 1
6 | 1 6 15 20 15 6 1
7 | 1 7 21 35 35 21 7 1
8 | 1 8 28 56 70 56 28 8 1
9 | 1 9 36 84 126 126 84 36 9 1
10 | 1 10 45 120 210 252 210 120 45 10 1
11 | 1 11 55 165 330 462 462 330 165 55 11 1
12 | 1 12 66 220 495 792 924 792 495 220 66 12 1
13 | 1 13 78 286 715 1287 1716 1716 1287 715 286 78 13 1
14 | 1 14 91 364 1001 2002 3003 3432 3003 2002 1001 364 91 14 1
</pre>
=={{header|XPL0}}==
<
func Binomial(N, K);
Line 2,582 ⟶ 3,089:
CrLf(0);
];
] \Mr. Pascal's triangle!</
{{Out}}
Line 2,598 ⟶ 3,105:
</pre>
=={{header|Zig}}==
A reasonable implementation for a fixed word size is to precompute all possible values of nCk, since even on a 64 bit machine there's only 67 rows of Pascal's triangle to consider, or ~18K of data.
In Zig it's possible to compute all values of nCk at compile time, so that at runtime it's only necessary to do a table lookup. Zig also supports nullable values, so nCk can return a null value if the programmer requests a value that's out of range. Finally, since this code uses addition to compute the table, all entries that can fit in 64 bits can be computed, in contrast to some other code examples that may overflow before the maximum representable value (67 choose 33) is reached. For example, the largest value the BCPL version can compute is 61 choose 31.
<syntaxhighlight lang="zig">
const std = @import("std");
pub fn binomial(n: u32) ?[]const u64 {
if (n >= rmax)
return null
else {
const k = n * (n + 1) / 2;
return pascal[k .. k + n + 1];
}
}
pub fn nCk(n: u32, k: u32) ?u64 {
if (n >= rmax)
return null
else if (k > n)
return 0
else {
const j = n * (n + 1) / 2;
return pascal[j + k];
}
}
const rmax = 68;
const pascal = build: {
@setEvalBranchQuota(100_000);
var coefficients: [(rmax * (rmax + 1)) / 2]u64 = undefined;
coefficients[0] = 1;
var j: u32 = 0;
var k: u32 = 1;
var n: u32 = 1;
while (n < rmax) : (n += 1) {
var prev = coefficients[j .. j + n];
var next = coefficients[k .. k + n + 1];
next[0] = 1;
var i: u32 = 1;
while (i < n) : (i += 1)
next[i] = prev[i] + prev[i - 1];
next[i] = 1;
j = k;
k += n + 1;
}
break :build coefficients;
};
test "n choose k" {
const expect = std.testing.expect;
try expect(nCk(10, 5).? == 252);
try expect(nCk(10, 11).? == 0);
try expect(nCk(10, 10).? == 1);
try expect(nCk(67, 33).? == 14226520737620288370);
try expect(nCk(68, 34) == null);
}
</syntaxhighlight>
Rather than write driver code, it's possible to run the unit test for this module.
{{Out}}
<pre>
$ zig test binomial.zig
All 1 tests passed.
</pre>
=={{header|zkl}}==
Using 64 bit ints:
<
{{out}}
<pre>
Line 2,611 ⟶ 3,183:
=={{header|ZX Spectrum Basic}}==
{{trans|BBC_BASIC}}
<
20 LET r=1: LET d=n-k
30 IF d>k THEN LET k=d: LET d=n-k
Line 2,620 ⟶ 3,192:
80 GO TO 40
90 PRINT r
100 DEF FN m(a,b)=a-INT (a/b)*b</
|