Given two nonnegative integers n,k such that 0 <= k <= n, return the binomial coefficient
c(n,k) := (n!) / (k! * (n-k)!)
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
Catalan Numbers Compute the multinomial coefficient Generate Pascal's triangle m-nomial coefficient
f=(n,k)=>k?n*f(n-1,k-1)/k:1
l~S*\0e]e!,
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.
n#0=1
0#k=1
n#k=(n-1)#(k-1)*n`div`k
Binomial
Yup. Sample usage: Binomial[13,5] or 13~Binomial~5 to obtain 1287.
There is a builtin for this calculation:
nchoosek
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.
!
3!5
10
5!13
1287
pCi
i
C is the built-in for binomial coefficients, the is are replaced with one input each, p prints the result.
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.
.cF
A program that takes input in the form n,k and prints the result.
How it works
This simply folds c(n,k) over the input.
{+combinations $^n,$^p}
{[*] ($^n...0)Z/1..$^p}
( Both are were based on code found at examples.perl6.org, and RosettaCode )
:i:&G-:h/p
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)
