8
\$\begingroup\$

This question already has an answer here:

Given two nonnegative integers n,k such that 0 <= k <= n, return the binomial coefficient

c(n,k) := (n!) / (k! * (n-k)!)

Test cases

Most languages will probably have a built in function.

c(n,0) = c(n,n) = 1 for all n
c(n,1) = c(n,n-1) = n for all n 
c(5,3) = 10
c(13,5) = 1287

Related challenges

Catalan Numbers Compute the multinomial coefficient Generate Pascal's triangle m-nomial coefficient

\$\endgroup\$

marked as duplicate by feersum, Digital Trauma code-golf Dec 11 '16 at 4:25

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • 4
    \$\begingroup\$ Surely this is a dup codegolf.stackexchange.com/questions/1744/… or am I missing something? \$\endgroup\$ – Digital Trauma Dec 11 '16 at 3:31
  • 1
    \$\begingroup\$ I was not aware of that, and I did a thorough search / had it in the sandbox for quite a long time. Too bad it doesn't contain the keyword binomial coefficient... \$\endgroup\$ – flawr Dec 11 '16 at 10:02

15 Answers 15

5
\$\begingroup\$

JavaScript (ES6), 27 bytes

f=(n,k)=>k?n*f(n-1,k-1)/k:1
\$\endgroup\$
5
\$\begingroup\$

MATL, 2 bytes

Xn

try it online!

\$\endgroup\$
3
\$\begingroup\$

Jelly, 1 byte

c

Try it online!

\$\endgroup\$
3
\$\begingroup\$

CJam, 11 bytes

l~S*\0e]e!,

Try it online!

Explanation

This uses a trick that (I think) I first used for the Catalan numbers challenge. CJam doesn't have a built-in for this, and computing three factorials is too expensive. But the binomial coefficient c(n,k) is the number of ways we can select k out of n elements. That is, it's equal to the number of permutations of a list of n elements where k of them have one value and the remaining have another.

l~   e# Read and evaluate input. Dumping n and k on the stack.
S*   e# Get a string of k spaces.
\0e] e# Pad to length n with zeros.
e!   e# Get the unique permutations.
,    e# Count the number of such permutations.
\$\endgroup\$
2
\$\begingroup\$

Haskell, 37 35 bytes

n#0=1
0#k=1
n#k=(n-1)#(k-1)*n`div`k
\$\endgroup\$
2
\$\begingroup\$

Mathematica, 8 bytes

Binomial

Yup. Sample usage: Binomial[13,5] or 13~Binomial~5 to obtain 1287.

\$\endgroup\$
2
\$\begingroup\$

Matlab, 8 bytes

There is a builtin for this calculation:

nchoosek
\$\endgroup\$
2
\$\begingroup\$

Haskell, 34 bytes

n#k|k<1||k>=n=1|m<-n-1=m#(k-1)+m#k

Usage example: 13#5 -> 1287.

A variant with the same size for the k<1||k>=ntest is n*k-k*k<1.

\$\endgroup\$
  • \$\begingroup\$ ​Very​ ​clever!​​​​ \$\endgroup\$ – flawr Dec 11 '16 at 10:01
1
\$\begingroup\$

Jellyfish, 6 bytes

pCi
 i

Try it online!

C is the built-in for binomial coefficients, the is are replaced with one input each, p prints the result.

\$\endgroup\$
1
\$\begingroup\$

Python 2, 33 bytes

f=lambda n,k:k<1or n*f(n-1,k-1)/k

Note that this will return True if k = 0, which seems to be allowed by default.

Try it online!

\$\endgroup\$
1
\$\begingroup\$

Pyth, 3 bytes

.cF

A program that takes input in the form n,k and prints the result.

Test

How it works

This simply folds c(n,k) over the input.

\$\endgroup\$
1
\$\begingroup\$

J, 1 byte

!

Usage:

   3!5
10
   5!13
1287
\$\endgroup\$
1
\$\begingroup\$

Actually, 1 byte

Input is of the form k<newline>n. Try it online!

\$\endgroup\$
0
\$\begingroup\$

Perl 6, 23 bytes

{+combinations $^n,$^p}
{[*] ($^n...0)Z/1..$^p}

( Both are were based on code found at examples.perl6.org, and RosettaCode )

\$\endgroup\$
0
\$\begingroup\$

MATL, 10 bytes

:i:&G-:h/p

Try it online!

This does the computation manually, without the builtin:

:     % Take input n implicitly. Range
      % STACK: [1 2 ... n]
i:    % Take input k. Range
      % STACK: [1 2 ... n], [1 2 ... k]
&G-   % Push n and k again. Subtract
      % STACK: [1 2 ... n], [1 2 ... k], n-k
:     % Range
      % STACK: [1 2 ... n], [1 2 ... k], [1 2 ... n-k]
h     % Concatenate the top two arrays horizontally
      % STACK: [1 2 ... n], [1 2 ... k 1 2 ... n-k]
/     % Element-wise division
      % STACK: [1/1 2/2 ... k/k (k+1)/1 (k+2)2 ... n/(n-k)]
p     % Product of array. Implicitly display
      % STACK: 1/1 * 2/2 * ... * k/k * (k+1)/1 * (k+2)2 * ... * n/(n-k)
\$\endgroup\$

Not the answer you're looking for? Browse other questions tagged or ask your own question.