# Tag Info

5

$${k\choose m}{m \choose n} = {k!\over m!(k-m)!}{m!\over n!(m-n)!}={k\choose k-m,n,m-n}$$ so we have $$\sum_{m=0}^k\sum_{n=0}^m{k\choose k-m,n,m-n}=3^k,$$ the number of ways to distribute $k$ objects in $3$ piles.

5

Under the convention that $\binom{n}{k}=0$ if $k\notin\left\{ 0,1,\dots,n\right\}$ we find by means of the triangle of Pascal: \begin{aligned}\sum_{n=k+1}^{\infty}\binom{n}{k+1}\frac{1}{2^{n}} & =\sum_{n=k+1}^{\infty}\binom{n-1}{k}\frac{1}{2^{n}}+\sum_{n=k+1}^{\infty}\binom{n-1}{k+1}\frac{1}{2^{n}}\\ & =\frac{1}{2}\sum_{n=k}^{\infty}\binom{n}{k}\... 3 Recall the classic Cayley's Result that there are n^{n-2} labelled tree on n vertices. https://en.wikipedia.org/wiki/Cayley%27s_formula Choose one of the vertices of a labelled tree and call it the (first) root (r_1); it is clear that there are n^{n-1} rooted trees. Next choose a second vertex (r_2) (possibly the same as the first) and call it ... 2 Starting from (the contribution from k=0 is zero owing to the third binomial coefficient)\sum_{k=1}^n \left(-\frac{1}{4}\right)^k {2k\choose k}^2 \frac{1}{1-2k} {n+k-2\choose 2k-2}$$we seek to show that this is zero when n is odd and$$\left[\left(\frac{1}{4}\right)^m {2m\choose m} \frac{1}{1-2m}\right]^2when n=2m is even. We observe that ... 2 \begin{align} \sum_{n=r}^\infty \binom{n}{r}^{-1} &= \sum_{n=r}^\infty \, (n+1)\int_0^1 x^{n-r} (1-x)^{r}\,dx \\ &= \int_0^1 \left( \sum_{n=r}^\infty (n+1)x^{n-r} \right) (1-x)^r \,dx \\ &= \int_0^1 \frac{1+r-rx}{(1-x)^2} (1-x)^r \,dx \\ &= \frac{r}{r-1} \end{align} 2 The coefficient of x^k in (x+1)\ldots(x+n) is |S_1(n+1,k+1)| where S_1(\cdot,\cdot) are the Stirling numbers of the first kind. 2 Write out what those factorials mean:1\cdot 2\cdot 3\cdots (n-2)(n-1)(n)(n+1) = 110 \cdot 1\cdot 2\cdot 3\cdots (n-2)(n-1).$$What can you cancel from both sides? 2 The sum$$S=\sum_{m=0}^{k} \sum_{n=0}^{m} {k \choose m}{m \choose n}=\sum_{m=0}^{k} {k \choose m}\sum_{n=0}^{m} {m \choose n}= \sum_{m=0}^{k} 2^m {k \choose m}=3^k.$$1 Maybe it's easier to understand backwards: Taking the (d-1)th derivative gives$$ \frac{\mathrm{d}^{(d-1)}}{\mathrm{d}x^{(d-1)}} \left[ \sum_{i=0}^{\infty} x^{i+n+d-1} \right] = \sum_{i=0}^{\infty} \left[ \frac{\mathrm{d}^{(d-1)}}{\mathrm{d}x^{(d-1)}} x^{i+n+d-1} \right] = \sum_{i=0}^{\infty} \frac{(i+n+d-1)!}{(i+n)!} x^{i+n}, $$since each of the (d-1)... 1 The answer given by @saulspatz is correct. I would like to give an alternative way to get to the result that helps understanding what is actually going on. The binomial coefficient \binom{k}{m} is the number of ways in which we can choose m elements out of a set of k elements. In other words, it is the number of elements of the set$$\{f:\{x_1,\ldots,...

1

$\newcommand{\usn}[2]{\begin{bmatrix}#1 \\ #2 \end{bmatrix}}$ It is well known that the unsigned Stirling numbers of the first kind can be written as \begin{align} \usn{x}{x-1}&=\binom{x}{2} \\ \usn{x}{x-2}&=2\binom{x}{3}+3\binom{x}{4} \\ \usn{x}{x-3}&=6\binom{x}{4}+20\binom{x}{5} + 15\binom{x}{6} \\ \usn{x}{x-4}&=24\binom{x}{5}+130\binom{... 1 Another proof: Let us use{n \choose k}={n-1 \choose k}+{n-1 \choose k-1}$$Let$$f_k=\sum_{n=k}^{\infty} {n \choose k} \frac{1}{2^n}= \sum_{n=k}^{\infty} {n-1 \choose k}\frac{1}{2^n}+\sum_{n=k}^{\infty} {n-1 \choose k-1} \frac{1}{2^n}.$$Let n-1=p, then$$\Rightarrow f_k=\sum_{p=k-1}^{\infty} {p\choose k} \frac{1}{2^{p+1}}+\sum_{p=k-1} {p\choose k-1}\...

Only top voted, non community-wiki answers of a minimum length are eligible