Problem You are given degree sequence \(A\), determine the number of possible caterpillars. We say that the graphs are different if they are not isomorphic. Solution Let us prove first prove the following fact: the degree sequence \(A = (a_1,\ldots, a_n)\) can form a tree if and only if the sum of degree sequence is equal to \(2\cdot (n - 1)\) and that \(\forall i:\, a_i > 0\). The only if direction is true by the definition of tree....
Here is the list of few probabilistic results. Markov’s inequality If \(X\) is a nonnegative random variable and \(a>0\), then the probabilty that \(X\) is at least \(a\) is at most the expectation of \(X\) divided by \(a\): $$P(X\geq a) \leq \frac{E(X)}{a}.$$ Proof $$ \begin{aligned} E(X) &= \int_{-\infty}^\infty f(x)xdx = \int_0^\infty f(x)xdx\\ &= \int_0^a f(x)xdx + \int_a^\infty f(x)xdx\\ &\geq \int_a^\infty f(x)xdx \\ &\geq \int_a^\infty f(x)dx \\ &=a\int_a^\infty f(x)dx \\ &= aP(X\geq a), \end{aligned} $$ which, as you can see, is quite weak bound and proof itself is quite a troll....
The expected value, \(\mathbb E[x]\), is the weighted average of possible values of a random variable, with weights given by their respective theoretical probabilities. The variance, \(\mathbb D[X]\) (or \(\sigma^2,\text{Var}(X)\)), is the expectation of the squared deviation of a random variable from its population mean or sample mean. Bernoulli distribution The Bernoulli distribution essentially models a single trial of flipping a weighted coin. It is the probability distribution of a random variable taking on only two values, \(1\) and \(0\) with complementary probabilities \(p\) and \(1-p\) respectively....