Mathematica - Binomial Theorem = Probability, Search algo visualization

Posted on April 4, 2021

Tags: mathematica

1 Binomial Theorem and Probability

Binomial Coefficient tells us:

Number ways to pick k-length subsets of a n-length set
Number of k -> n functions but

Column[Table[Binomial[n, k], {n, 0, 5}, {k, 0, n}], Center] // TeXForm

$$\begin{array}{c} \{1\} \\ \{1,1\} \\ \{1,2,1\} \\ \{1,3,3,1\} \\ \{1,4,6,4,1\} \\ \{1,5,10,10,5,1\} \\ \end{array}$$

Notice the distribution of {1,5,10,10,5,1} looks like a probability distribution

Binomial[5,#1]& /@ Range[0,5]

{1, 5, 10, 10, 5, 1}

Notice sum over $\sum_{k\in 0..n}{n \choose k}$ equals $2^n$

Total[Binomial[5,#1]& /@ Range[0,5]]==Inactivate[2^5] // TeXForm

$$32=2{}^{\wedge}5$$

Row[{ListLinePlot[Binomial[3,#1]& /@ Range[0,3] ],
ListLinePlot[Binomial[7,#1]& /@ Range[0,7] ],
ListLinePlot[Binomial[10,#1]& /@ Range[0,10] ],
ListLinePlot[Binomial[15,#1]& /@ Range[0,15] ],
ListLinePlot[Binomial[25,#1]& /@ Range[0,25] ],
ListLinePlot[Binomial[50,#1]& /@ Range[0,50]&[0] ]
}]

2 Search Algorithms

lets assume we have 1 array
Problem: find if the sum x can be made from 2 numbers from that array
Naive Solution:
- Double nest loop through the array to find the number

Intuitive Solution:

Sort the array
make a 2d matrix that represents the double nested loop of the array
Now navigate the 2d matrix where you can choose to go any direction to find the correct “color” aka number

Partition[Tuples[{Range@5,Range@5}],5] // TeXForm

$$\left( \begin{array}{ccccc} \{1,1\} & \{1,2\} & \{1,3\} & \{1,4\} & \{1,5\} \\ \{2,1\} & \{2,2\} & \{2,3\} & \{2,4\} & \{2,5\} \\ \{3,1\} & \{3,2\} & \{3,3\} & \{3,4\} & \{3,5\} \\ \{4,1\} & \{4,2\} & \{4,3\} & \{4,4\} & \{4,5\} \\ \{5,1\} & \{5,2\} & \{5,3\} & \{5,4\} & \{5,5\} \\ \end{array} \right)$$

tx = RandomInteger[{1,1000},10];

Style[Row[{
MatrixPlot[Table[x+y,{x,tx},{y,tx}],ColorFunction->Hue]
MatrixPlot[Table[x+y,{x,Sort[tx]},{y,Sort[tx]}],ColorFunction -> Hue]
MatrixPlot[Table[x+y,{x,0,10},{y,0,10}],ColorFunction->Hue]
}],ImageSizeMultipliers->{0.4, 0.4}]

Partition[Table[x+y,{x,Sort[tx]},{y,Sort[tx]}],10] // MatrixForm // TeXForm

$$\left( \begin{array}{cccccccccc} \left( \begin{array}{c} 106 \\ 136 \\ 388 \\ 448 \\ 494 \\ 507 \\ 575 \\ 896 \\ 933 \\ 969 \\ \end{array} \right) & \left( \begin{array}{c} 136 \\ 166 \\ 418 \\ 478 \\ 524 \\ 537 \\ 605 \\ 926 \\ 963 \\ 999 \\ \end{array} \right) & \left( \begin{array}{c} 388 \\ 418 \\ 670 \\ 730 \\ 776 \\ 789 \\ 857 \\ 1178 \\ 1215 \\ 1251 \\ \end{array} \right) & \left( \begin{array}{c} 448 \\ 478 \\ 730 \\ 790 \\ 836 \\ 849 \\ 917 \\ 1238 \\ 1275 \\ 1311 \\ \end{array} \right) & \left( \begin{array}{c} 494 \\ 524 \\ 776 \\ 836 \\ 882 \\ 895 \\ 963 \\ 1284 \\ 1321 \\ 1357 \\ \end{array} \right) & \left( \begin{array}{c} 507 \\ 537 \\ 789 \\ 849 \\ 895 \\ 908 \\ 976 \\ 1297 \\ 1334 \\ 1370 \\ \end{array} \right) & \left( \begin{array}{c} 575 \\ 605 \\ 857 \\ 917 \\ 963 \\ 976 \\ 1044 \\ 1365 \\ 1402 \\ 1438 \\ \end{array} \right) & \left( \begin{array}{c} 896 \\ 926 \\ 1178 \\ 1238 \\ 1284 \\ 1297 \\ 1365 \\ 1686 \\ 1723 \\ 1759 \\ \end{array} \right) & \left( \begin{array}{c} 933 \\ 963 \\ 1215 \\ 1275 \\ 1321 \\ 1334 \\ 1402 \\ 1723 \\ 1760 \\ 1796 \\ \end{array} \right) & \left( \begin{array}{c} 969 \\ 999 \\ 1251 \\ 1311 \\ 1357 \\ 1370 \\ 1438 \\ 1759 \\ 1796 \\ 1832 \\ \end{array} \right) \\ \end{array} \right)$$