Combination

k-combination (n choose k)

$C(n,k)=\left(\genfrac{}{}{0ex}{}{n}{k}\right)=\left(\genfrac{}{}{0ex}{}{n}{n-k}\right)=\frac{n!}{k!(n-k)!}$

• The number of ways to choose $k$ elements from a set of size $n$ (without regard to the order of choice).
• Binomial Coefficient

Combination with Repetitions

$\left(\left(\genfrac{}{}{0ex}{}{n}{k}\right)\right)=\left(\genfrac{}{}{0ex}{}{n+k-1}{n-1}\right)=\left(\genfrac{}{}{0ex}{}{n+k-1}{k}\right)=\frac{(n+k-1)!}{k!(n-1)!}$

• aka: n multichoose k, or multiset coefficient
• The number of multisets of cardinality $k$, with elements taken from a finite set of cardinality $n$.
• The number of ways to distribute $k$ identical balls into $n$ distinct boxes
• The number of weak compositions of $k$ into $n$ parts
• The number of nonnegative integer solutions of $x_1+\cdots +x_n=k$ (with regard to the order of variables. i.e. $x_1+x_2=k$ and $x_2+x_1=k$ are considered as two different solutions. for consider them as a single solution use in Generating Functions)

Identities

• $\left(\left(\genfrac{}{}{0ex}{}{n}{k}\right)\right)=\frac{n^{\overline{k}}}{k!}$ (where $n^{\overline{k}}=n(n+1)\cdots (n+k-1)$ is a rising factorial)
• $\left(\left(\genfrac{}{}{0ex}{}{n}{k}\right)\right)=(-1{)}^k(\genfrac{}{}{0ex}{}{-n}{k})$
• $\left(\left(\genfrac{}{}{0ex}{}{n}{k}\right)\right)=\left(\left(\genfrac{}{}{0ex}{}{k+1}{n-1}\right)\right)$

Special Case: $k=n$

$\left(\left(\genfrac{}{}{0ex}{}{n}{n}\right)\right)=\left(\genfrac{}{}{0ex}{}{2n-1}{n-1}\right)=\left(\genfrac{}{}{0ex}{}{2n-1}{n}\right)=\frac{(2n-1)!}{n!(n-1)!}$

This is the A088218 sequence, which is total number of leaves in all rooted ordered trees with n edges. $1,1,3,10,35,126,462,1716,6435,24310,...$

k-composition of n

$\left(\genfrac{}{}{0ex}{}{n-1}{k-1}\right)$

• The number of positive integer solutions of $x_1+\cdots +x_k=n$ (without regard to the order of variables)
• The $k$-composition of $n$

$\sum _{k=1}^n\left(\genfrac{}{}{0ex}{}{n-1}{k-1}\right)=2^{n-1}$ is the number of all compositions of $n$. (i.e. $k=1,2,\dots ,n$)

Solutions with Restrictions

Minimum restrictions

• for $t_1$. solutions for $t_1+\cdots +t_n=k$ such that $t_1\ge p$. $\left(\genfrac{}{}{0ex}{}{n+k-p-1}{k-p}\right)$

• solutions for $t_1+\cdots +t_n=k$ such that $t_i\ge p$. for each $i\le m$ $\left(\genfrac{}{}{0ex}{}{n+k-(p\cdot m)-1}{k-(p\cdot m)}\right)$

Maximum restrictions

• by Generating Functions
• by Inclusion–exclusion principle with Minimum restrictions. for e.g, the solutions for $t_1+\cdots +t_n=k$ such that $t_i<p$. for each $i\le n$ ${\sum }_{i=0}^n(-1{)}^i(\genfrac{}{}{0ex}{}{n}{i}\left)\right(\genfrac{}{}{0ex}{}{n+k-pi-1}{n-1})$

Number of Solutions of Inequality

$\left(\genfrac{}{}{0ex}{}{(n+1)+k-1}{(n+1)-1}\right)=\left(\genfrac{}{}{0ex}{}{n+k}{n}\right)$

• The number of nonnegative integer solutions of the inequality $t_1+\cdots +t_n\le k$

Other

• The number of nonnegative integer solutions of $x_1+\cdots +x_n=k$, such that $x_1+\dots +x_a\ge b$. ${\sum }_{i=0}^{a-1}\left(\genfrac{}{}{0ex}{}{a+b+i-1}{b+i}\right)\left(\genfrac{}{}{0ex}{}{n-a+k-(b+i)-1}{k-(b+i)}\right)$