Combinatorics - Summary

Related: Catalan Number - Summary
https://www.mathsisfun.com/combinatorics/combinations-permutations.html

Without repetition our choices get reduced each time.

But when we want to select just 3 we don't want to multiply after 14. How do we do that? There is a neat trick: we divide by 13!

16 × 15 × 14 × 13 × 12 ...13 × 12 ...  =  16 × 15 × 14

That was neat. The 13 × 12 × ... etc gets "cancelled out", leaving only 16 × 15 × 14.

The formula is written:

n!(n − r)!

where n is the number of things to choose from, and we choose r of them, no repetitions, order matters.

Combinations without Repetition

The easiest way to explain it is to:

• assume that the order does matter (ie permutations),
• then alter it so the order does not matter.

We already know that 3 out of 16 gave us 3,360 permutations.

But many of those are the same to us now, because we don't care what order!

For example, let us say balls 1, 2 and 3 are chosen. These are the possibilites:

Order does matter	Order doesn't matter
1 2 3 1 3 2 2 1 3 2 3 1 3 1 2 3 2 1	1 2 3

So, the permutations have 6 times as many possibilites.

In fact there is an easy way to work out how many ways "1 2 3" could be placed in order, and we have already talked about it. The answer is:

3! = 3 × 2 × 1 = 6

(Another example: 4 things can be placed in 4! = 4 × 3 × 2 × 1 = 24 different ways, try it for yourself!)

So we adjust our permutations formula to reduce it by how many ways the objects could be in order (because we aren't interested in their order any more):

Combinations with Repetition

Let us say there are five flavors of icecream: banana, chocolate, lemon, strawberry and vanilla.

We can have three scoops. How many variations will there be?

Let's use letters for the flavors: {b, c, l, s, v}. Example selections include

• {c, c, c} (3 scoops of chocolate)
• {b, l, v} (one each of banana, lemon and vanilla)
• {b, v, v} (one of banana, two of vanilla)

(And just to be clear: There are n=5 things to choose from, and we choose r=3 of them.
Order does not matter, and we can repeat!)

Now, I can't describe directly to you how to calculate this, but I can show you a special techniquethat lets you work it out.

Think about the ice cream being in boxes, we could say "move past the first box, then take 3 scoops, then move along 3 more boxes to the end" and we will have 3 scoops of chocolate!

So it is like we are ordering a robot to get our ice cream, but it doesn't change anything, we still get what we want.

We can write this down as  (arrow means move, circle means scoop).

In fact the three examples above can be written like this:

{c, c, c} (3 scoops of chocolate):
{b, l, v} (one each of banana, lemon and vanilla):
{b, v, v} (one of banana, two of vanilla):

OK, so instead of worrying about different flavors, we have a simpler question: "how many different ways can we arrange arrows and circles?"

Notice that there are always 3 circles (3 scoops of ice cream) and 4 arrows (we need to move 4 times to go from the 1st to 5th container).

So (being general here) there are r + (n−1) positions, and we want to choose r of them to have circles.

This is like saying "we have r + (n−1) pool balls and want to choose r of them". In other words it is now like the pool balls question, but with slightly changed numbers. And we can write it like this:

where n is the number of things to choose from, and we choose r of them repetition allowed, order doesn't matter.

Interestingly, we can look at the arrows instead of the circles, and say "we have r + (n−1)positions and want to choose (n−1) of them to have arrows", and the answer is the same:

https://en.wikipedia.org/wiki/Combinatorics
https://zh.wikipedia.org/wiki/%E7%BB%84%E5%90%88%E6%95%B0%E5%AD%A6

从${\displaystyle n}$个元素中取出${\displaystyle k}$个元素，${\displaystyle k}$个元素的排列数量为：

${\displaystyle P_{k}^{n}={\frac {n!}{(n-k)!}}}$

以赛马为例，有8匹马参加比赛，玩家需要在彩票上填入前三胜出的马匹的号码，从8匹马中取出3匹马来排前3名，排列数量为：

${\displaystyle P_{3}^{8}={\frac {8!}{(8-3)!}}=8\times 7\times 6=336}$

因为一共存在336种可能性，因此玩家在一次填入中中奖的概率应该是：

${\displaystyle P={\frac {1}{336}}=0.00298}$

不过，中国大陆的教科书^{[来源请求]}则是把从n取k的情况记作${\displaystyle P_{n}^{k}}$或${\displaystyle A_{n}^{k}}$（A代表Arrangement，即排列^[1]）。

上面的例子是建立在取出元素不重复出现状况。

从${\displaystyle n}$个元素中取出${\displaystyle k}$个元素，${\displaystyle k}$个元素可以重复出现，这排列数量为：

${\displaystyle U_{k}^{n}=n^{k}}$^[2]

以四星彩为例，10个数字取4个数字，因可能重复所以排列数量为：

${\displaystyle U_{4}^{10}=10^{4}=10000}$

这时的一次性添入中奖的概率就应该是：

${\displaystyle P={\frac {1}{10000}}=0.0001}$

https://zhuanlan.zhihu.com/p/41855459

P 和 C 的本质区别在于：决策的顺序对结果有没有影响。

我们的任务是：将这 3 个奖牌颁发给 8 个人中的 3 个，先颁发金牌，再颁发银牌，再颁发铜牌。问颁发奖牌的不同方式总共有哪些？

第一步：颁发金牌🏅️，可以在8个人中任选一个，有8种选择。A可以被替换为 B C D E F G H中的任何一个。

第二步：颁发银牌🥈，可以在除去已经获得金牌的人之外的7个人中任选一个，有7种选择。

第三步：颁发铜牌🥉，在已经获得金牌、银牌的两个人之外的6个人中任选一个，有6种选择。

那么很明显，总共的颁奖方式有

8 * 7 * 6 种

以此类推，假如我们现在要颁发 8 个奖牌给 8个人，那么我们会按照上述方法，每次颁发一种奖牌，直到奖牌被颁发完为止，这样，颁发奖牌的方式总共有：

8 * 7 * 6 * 5 * 4 * 3 * 2 * 1 种

但是，我们只颁发 3 个奖牌就不颁发了呀，怎么才能在乘到 5 那里停止呢？很明显，摆脱 5 * 4 * 3 * 2 * 1 我们只需要把这个尾巴除掉即可！

也就是：

那么在 8 个人当中选 3 个人颁发一样的可乐瓶，有多少种颁发方法呢？

在上面排列的基础上，也就是给三个人颁发的是不同的奖杯，最终选出的三个人，拿奖是有顺序的，也就是，最后计算出来的所有方法中，把三个奖杯的放置顺序进行了排列。

但是现在，如果颁发的是可乐瓶，那么，获奖的顺序变得不再重要，谁先得，谁后得，结果都是一样的。上面排列的结果已经把不同颁发顺序视作不同颁发方法了，现在，3 个人中，不同的颁发顺序都是同一种！

所以，我们只需要把「上一步排列获得的结果」除以「不同颁发顺序的总数」，得到的就是可乐瓶颁发方法的总数。

不同颁发顺序的总数有 3！种

所以，总共有这么多种：

继续，如果要想在 n 个物品中，选择 k 个物品出来，选择的顺序无所谓，那么选择的方式总共有这么多种：

https://en.wikipedia.org/wiki/Binomial_coefficient

the binomial coefficients are the positive integers that occur as coefficients in the binomial theorem. Commonly, a binomial coefficient is indexed by a pair of integers n ≥ k ≥ 0 and is written ${\displaystyle {\tbinom {n}{k}}.}$ It is the coefficient of the x^k term in the polynomial expansion of the binomial power (1 + x)ⁿ, and it is given by the formula

${\displaystyle {\binom {n}{k}}={\frac {n!}{k!(n-k)!}}.}$

For example, the fourth power of 1 + x is

${\displaystyle {\begin{aligned}(1+x)^{4}&={\tbinom {4}{0}}x^{0}+{\tbinom {4}{1}}x^{1}+{\tbinom {4}{2}}x^{2}+{\tbinom {4}{3}}x^{3}+{\tbinom {4}{4}}x^{4}\\&=1+4x+6x^{2}+4x^{3}+x^{4},\end{aligned}}}$

and the binomial coefficient ${\displaystyle {\tbinom {4}{2}}={\tfrac {4!}{2!2!}}=6}$ is the coefficient of the x² term.

Arranging the numbers ${\displaystyle {\tbinom {n}{0}},{\tbinom {n}{1}},\ldots ,{\tbinom {n}{n}}}$ in successive rows for ${\displaystyle n=0,1,2,\ldots }$ gives a triangular array called Pascal's triangle, satisfying the recurrence relation

${\displaystyle {\binom {n}{k}}={\binom {n-1}{k}}+{\binom {n-1}{k-1}}.}$

The binomial coefficients occur in many areas of mathematics, and especially in combinatorics.

二项式系数是二项式定理中各项的系数。一般而言，二项式系数由两个非负整数 n 和 k 为参数决定，写作 ${\displaystyle {\tbinom {n}{k}}}$，定义为 ${\displaystyle (1+x)^{n}}$的多项式展开式中，${\displaystyle x^{k}}$项的系数，因此一定是非负整数。如果将二项式系数 ${\displaystyle {\binom {n}{0}},{\binom {n}{1}},\dots ,{\binom {n}{n}}}$写成一行，再依照 ${\displaystyle n=0,1,2,\dots }$顺序由上往下排列，则构成帕斯卡三角形。

Program to calculate value of nCr

https://www.geeksforgeeks.org/program-calculate-value-ncr/

https://stackoverflow.com/questions/2201113/combinatoric-n-choose-r-in-java-math

We know that the formula for (N choose K) is:

    N!
 --------
 (N-K)!K!

Therefore, the formula for (N choose K+1) is:

       N!                N!                   N!               N!      (N-K)
---------------- = --------------- = -------------------- = -------- x -----
(N-(K+1))!(K+1)!   (N-K-1)! (K+1)!   (N-K)!/(N-K) K!(K+1)   (N-K)!K!   (K+1)

That is:

(N choose K+1) = (N choose K) * (N-K)/(K+1)

We also know that (N choose 0) is:

 N!
---- = 1
N!0!

So this gives us an easy starting point, and using the formula above, we can find (N choose K) for any K > 0 with K multiplications and K divisions.

https://www.geeksforgeeks.org/binomial-coefficient-dp-9/

1. A binomial coefficient C(n, k) can be defined as the coefficient of X^k in the expansion of (1 + X)^n.
2. A binomial coefficient C(n, k) also gives the number of ways, disregarding order, that k objects can be chosen from among n objects; more formally, the number of k-element subsets (or k-combinations) of an n-element set.

The value of C(n, k) can be recursively calculated using following standard formula for Binomial Coefficients.

   C(n, k) = C(n-1, k-1) + C(n-1, k)
   C(n, 0) = C(n, n) = 1

    static int binomialCoeff(int n, int k)

    {

    int C[][] = new int[n+1][k+1];

    int i, j;

      

        // Calculate  value of Binomial Coefficient in bottom up manner

    for (i = 0; i <= n; i++)

    {

        for (j = 0; j <= min(i, k); j++)

        {

            // Base Cases

            if (j == 0 || j == i)

                C[i][j] = 1;

       

            // Calculate value using previosly stored values

            else

                C[i][j] = C[i-1][j-1] + C[i-1][j];

          }

     }

       

    return C[n][k];

    }




    static int binomialCoeff(int n, int k)

    {

        int C[] = new int[k + 1];

         

        // nC0 is 1

        C[0] = 1;  

       

        for (int i = 1; i <= n; i++)

        {

            // Compute next row of pascal 

            // triangle using the previous row

            for (int j = Math.min(i, k); j > 0; j--)

                C[j] = C[j] + C[j-1];

        }

        return C[k];

    }