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)!}$

See also: Binomial Coefficient

Combination with Repetitions

Number of ways to distribute $k$ identical Balls into $n$ distinct Boxes ^[https://en.wikipedia.org/wiki/Combination#Number_of_combinations_with_repetitionr צירופים עם חזרות.]

$D(n,k)=\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)!}$

Counting solutions of equation

can also be used for number of nonnegative solutions of equation $t_1+\cdots +t_n=k$. i.e. the number of solutions is: $\left(\genfrac{}{}{0ex}{}{n+k-1}{k}\right)=\left(\genfrac{}{}{0ex}{}{n+k-1}{n-1}\right)$.

(for the equation $x_1+x_2=10$, there are also solution $6+4=10$ and $4+6=10$ and these are considered as two solution. for consider them as a single solution use in generating function )

Restrictions

Minimum restrictions

• positive integers (strictly) solutions ($t_i\ge 1$ for any $i\le n$) for $t_1+\cdots +t_n=k$ need to add $-1\cdot n$ to $k$ $\left(\genfrac{}{}{0ex}{}{k-1}{n-1}\right)$

See also: [[Binomial Coefficient#compositions-of-n|Compositions of n]]

• 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 solutions of inequality

number of nonnegative solutions of equation $t_1+\cdots +t_n\le k$. i.e. the number of solutions is: $\left(\genfrac{}{}{0ex}{}{(n+1)+k-1}{(n+1)-1}\right)=\left(\genfrac{}{}{0ex}{}{n+k}{n}\right)$

Sum of $a$ first terms greater than or equal to $b$

• nonnegative solutions for $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)$

Combination with Repetitions ($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,...$