Skip to main content

New answers tagged

0 votes

Trying to prove equivalence of combinatorial formula and nested summations

The nested summation counts integer tuples $(x_1,x_2,\dots,x_r)$ such that $1 \le x_1 \le x_2 \le \dots \le x_r \le n-r+1$. Performing a change of variables \begin{align} y_1 &= x_1 - 1 \\ y_2 &...
RobPratt's user avatar
  • 46.9k
0 votes

Trying to prove equivalence of combinatorial formula and nested summations

First, I'd like to clarify your question: you want to prove that $$\left(\begin{array}{c}n\\r\end{array}\right)=\sum_{k_1=1}^{n-r+1}\sum_{k_2=1}^{k_1}\sum_{k_3=1}^{k_2}\dots\sum_{k_{r-1}=1}^{k_{r-2}}\...
Kolakoski54's user avatar
1 vote

Deriving equation (3-66) of Papoulis and Pillai

We have the sequence $$ P_{2n} = \sum\limits_{k=n+1}^{2n} \binom{2n}{k} p^k q^{2n-k}. $$ It contains the terms of $(p+q)^{2n}$ for powers of $q$ from $0$ to $n-1$. One concise way to formulate it is $$...
Oleksandr  Kulkov's user avatar
1 vote

$(1-x)^{n+a} \sum_{j=0}^\infty \binom{n+j-1}{j}\binom{n+j}{a} x^j = \sum_{j=0}^a \binom{n}{a-j}\binom{a-1}{j} x^j$

We need to show $$ (1-x)^{n+a} \sum_{m=0}^\infty \binom{n+m-1}{m}\binom{n+m}{a} x^m = \sum_{j=0}^a \binom{n}{a-j}\binom{a-1}{j} x^j. $$ Instead, let's move $(1-x)^{n+a}$ to the RHS using a standard ...
Oleksandr  Kulkov's user avatar
1 vote

$(1-x)^{n+a} \sum_{j=0}^\infty \binom{n+j-1}{j}\binom{n+j}{a} x^j = \sum_{j=0}^a \binom{n}{a-j}\binom{a-1}{j} x^j$

We seek to show that with $n$ and $a$ natural numbers, $$(1-x)^{n+a} \sum_{j\ge 0} {n+j-1\choose j} {n+j\choose a} x^j = \sum_{j=0}^a {n\choose a-j} {a-1\choose j} x^j.$$ Note that we may assume that $...
Marko Riedel's user avatar
3 votes
Accepted

$(1-x)^{n+a} \sum_{j=0}^\infty \binom{n+j-1}{j}\binom{n+j}{a} x^j = \sum_{j=0}^a \binom{n}{a-j}\binom{a-1}{j} x^j$

With standard notations (Pochhammer's symbol, Gaussian Hypergeometric Function, $\Gamma$-function and Roy's strategy in https://dx.doi.org/10.2307/2323500 ) the left hand side is essentially $$ \sum_{...
R. J. Mathar's user avatar
  • 2,855
3 votes

Deriving equation (3-66) of Papoulis and Pillai

We have that $$P_{2n} = \sum_{k=0}^{n-1} {2n\choose k} p^{2n-k} q^k = p^{2n} [z^{n-1}] \frac{1}{1-z} (1+qz/p)^{2n} \\ = p^2 [z^{n-1}] \frac{1}{1-p^2z} (1+pqz)^{2n} = p^2 [z^{n+1}] z^2 \frac{1}{1-p^2z} ...
Marko Riedel's user avatar
2 votes

Deriving equation (3-66) of Papoulis and Pillai

Here is my development of the argument given in Papoulis and Pillai. First,we may use the binomial expansion to write $$(p+q)^{2n}=\sum_{k=0}^{2n}\binom{2n}{k}p^k q^{2n-k}=\sum_{k=0}^{n}\binom{2n}{k}p^...
Semiclassical's user avatar
2 votes

The upper bound of $\sum_{k=0}^{m} \binom{n}{k}x^k(1-x)^{n-k}$

Here is an approximation approach. Instead of refering to a beta distribution, consider a binomial $Bin(n,p)$ random variable $X$. In this framework : $$\sum_{k=0}^{m} \binom{n}{k}x^k(1-x)^{n-k}$$ can ...
Jean Marie's user avatar
  • 83.6k
1 vote

Prove $\sum_{k=0}^{r}\binom{n}{k}\binom{n}{r-k}\left(-1\right)^{k}=\left(-1\right)^{\frac{r}{2}}\binom{n}{\frac{r}{2}}$ for $r$ even.

$\newcommand{\bbx}[1]{\,\bbox[15px,border:1px groove navy]{\displaystyle{#1}}\,} \newcommand{\braces}[1]{\left\lbrace\,{#1}\,\right\rbrace} \newcommand{\bracks}[1]{\left\lbrack\,{#1}\,\right\rbrack} ...
Felix Marin's user avatar
  • 90.7k
2 votes

Is there a general formula for $F(n,k) = \sum_{i=0}^{n}\binom{n}{i}^k$?

For $n=3$, they are the Franel numbers (sequence $A000172$ in $OEIS$). In fact, there is a general formula which involves generalized hypergeometric functions (which are summations up to infinity !!). ...
Claude Leibovici's user avatar
0 votes

Analytical solution for binomial equation

$$p' = q^n + nq^{n-1}p + \binom{n}{2} q^{n-2}p^2$$ Expanding the binomial coefficient and factoring $$p'=q^n\Big(\frac{n(n-1) p^2}{2 q^2} +\frac {np}{q}+1\Big)$$ If $n$ is large enough, ...
Claude Leibovici's user avatar
-1 votes

Prove $z^n + 1/{z^n}$ is rational if $z+1/z$ is rational

Bill Dubuque's and N.S.'s solutions can be combined. Let $x_1=z$, $x_2=\frac1z$, $x_3=x_4=...=0$ be the variables. Consider the power sums $p_n=z^n+\frac1{z^n}, n\geq0$ and elementary symmetric ...
Bob Dobbs's user avatar
  • 11.5k
2 votes

Combinatoric equation involving three unknowns

So after expanding the brackets, moving everything to one side etc., we get: $$k^2(pn^2-np+2nq+p-q-n^2+2n-1)+k(pn^2+2np+2nq+p+2q-5n+5)+(3np+3q-6)=0$$ If this is true $\forall k\in\mathbb{N^*}$, this ...
fikooo's user avatar
  • 409
2 votes
Accepted

Prove $\lim_{n\to\infty}\binom{n}{k}\left(\frac{\mu}{n}\right)^{k}\left(1-\frac{\mu}{n}\right)^{n-k}=\frac{\mu^k}{e^\mu\cdot{k!}}$

Note that $$\frac{n(n-1)\dots(n-k+1)}{\left(\frac{n}{\mu}-1\right)^k}=\mu^k\frac{n^k+(\text{lower degree terms})}{n^k+(\text{lower degree terms})}.$$
Vaskara_GRek_O's user avatar
0 votes

Proof of $\sum_{m=0}^{n}\binom{m}{j}\binom{n-m}{k-j}=\binom{n+1}{k+1}$ (Another form of the Chu–Vandermonde identity)

Given that $$ \frac{x^j}{(1 - x)^{j+1}} = \sum_{m = 0}^\infty \binom{m}{j}x^m, $$ We have \begin{align} \sum_{m_1 + m_2 = n} \binom{m_1}{j} \binom{m_2}{k - j} &= [x^n] \frac{x^j}{(1 - x)^{j + 1}} ...
Sera Gunn's user avatar
  • 27.5k
0 votes

Proof of $\sum_{m=0}^{n}\binom{m}{j}\binom{n-m}{k-j}=\binom{n+1}{k+1}$ (Another form of the Chu–Vandermonde identity)

$\newcommand{\bbx}[1]{\,\bbox[15px,border:1px groove navy]{\displaystyle{#1}}\,} \newcommand{\braces}[1]{\left\lbrace\,{#1}\,\right\rbrace} \newcommand{\bracks}[1]{\left\lbrack\,{#1}\,\right\rbrack} ...
Felix Marin's user avatar
  • 90.7k
3 votes

What is the name of this combinatorial identity?

This is also a restatement of Theorem 2 part II in Qimh Richey Xantcha, Binomial Rings: Axiomatisation, Transfer and Classification, arXiv:1104.1931v4, which is saying that \begin{align*} \dbinom{ab}{...
darij grinberg's user avatar
4 votes
Accepted

Estimate a sum of binomial coefficients

We show the leading term of the asymptotic expansion of the sum is \begin{align*} \sum_{1\leq k \leq n/3 } \binom{2k}{k}\binom{n-2k-1}{k-1} \color{blue}{\sim \frac{2^{n-1}}{\sqrt{n\pi}}}\tag{1} \end{...
Markus Scheuer's user avatar
2 votes

Lower Bound on the ratio of binomial coefficients

$$A(k,n,m)=\frac{\binom{k-m}{n-m}}{\binom{k}{n}}=\frac{\Gamma (n+1)\,\, \Gamma(k-m+1)}{\Gamma (k+1)\,\, \Gamma(n-m+1)}$$ Let $n=a k$ and $m=b k$ (with $1>a>b$ and, as usual, take logarithms and ...
Claude Leibovici's user avatar
2 votes
Accepted

Lower Bound on the ratio of binomial coefficients

It is well known that $$\binom{k}{n}\binom{n}{m}=\binom{k}{m}\binom{k-m}{n-m}. \tag1\label1$$ For a combinatorial proof, consider $A \subseteq B \subseteq [k]$ with $|A|=m$ and $|B|=n$. Rewriting \...
RobPratt's user avatar
  • 46.9k
2 votes

Estimate a sum of binomial coefficients

This is not an answer since no proof Let $$a_n=2 \,\,\, _4F_3\left(\frac{3}{2},\frac{3-n}{3},\frac{4-n}{3 },\frac{5-n}{3};2,\frac{3-n }{2},\frac{4-n}{2};-27\right)$$ A bit of heuristics and ...
Claude Leibovici's user avatar
4 votes
Accepted

Identity regarding the sum of products of binomial coefficients.

Instead of $D = B-A$, consider $D+n = B + (n-A)$. This is the number of heads that B gets, plus the number of tails that A gets, so $D+n$ is a binomial with $2n+1$ trials and probability $\frac12$. ...
Misha Lavrov's user avatar
5 votes
Accepted

Closed form for a sum of binomial coefficients

It's always a good idea to try writing $\binom{a+i}{b+i}$ as $\binom{a+i}{b-a}$ in a sum over $i$; that way, only one parameter of the binomial coefficient varies with $i$. By doing that here, and ...
Misha Lavrov's user avatar
1 vote

Expansion of a function $(1-x)^{-n}$

We begin by recalling that $ \displaystyle \frac {1}{1 - x} = \sum_{k \ge 0} {x}^{k}. $ Differentiate both sides: $ \displaystyle \frac {1}{{\left( 1 - x \right)}^{2}} = \sum_{k \ge 1} k {x}^{k - 1}. $...
Simon's user avatar
  • 804
1 vote

What is the number of lattice paths of length 16 from the point (0,0) to (8,8) that go through (4,4) but don't go through (1,1), (2,2), (3,3)

It's fairly easy to find the number of valid paths from $(0,0)$ by filling in the number of paths in an array starting at $(0,0)$ (one path) and working to the right and up, adding one row of numbers ...
awkward's user avatar
  • 14.9k
0 votes
Accepted

How to Derive the Binomial Coefficient Upper Bound and Final Inequality in "Scheduling Multithreaded Computations by Work Stealing"?

For the first question, start with $\binom{m(P-1)}{\Delta}\le \binom{mP}{\Delta}$, and then use the result in this question to conclude that $\binom{mP}{\Delta}\le \left(\frac{emP}{\Delta}\right)^\...
Mike Earnest's user avatar
  • 77.4k
4 votes

Alternating sum involving binomial coefficients

$\newcommand{\bbx}[1]{\,\bbox[15px,border:1px groove navy]{\displaystyle{#1}}\,} \newcommand{\braces}[1]{\left\lbrace\,{#1}\,\right\rbrace} \newcommand{\bracks}[1]{\left\lbrack\,{#1}\,\right\rbrack} ...
Felix Marin's user avatar
  • 90.7k
7 votes

Alternating sum involving binomial coefficients

Seeking to evaluate $$\frac{(-1)^n}{n!} \sum_{q=0}^n {n\choose q} (-1)^q (1+\alpha q)^n$$ we obtain $$(-1)^n [z^n] \sum_{q=0}^n {n\choose q} (-1)^q \exp((1+\alpha q)z) \\ = (-1)^n [z^n] \exp(z) \sum_{...
Marko Riedel's user avatar
1 vote

What is the number of lattice paths of length 16 from the point (0,0) to (8,8) that go through (4,4) but don't go through (1,1), (2,2), (3,3)

Ordinarily, if the constraints were merely against crossing $~(1,1), ~(2,2),~$ and $~(3,3),~$ then I would say that the indirect approach of Inclusion-Exclusion is best. See this article for an ...
user2661923's user avatar
  • 36.8k
2 votes
Accepted

What is the number of lattice paths of length 16 from the point (0,0) to (8,8) that go through (4,4) but don't go through (1,1), (2,2), (3,3)

The number of paths of length $2n$ from $(0, 0)$ to $(n, n)$ that do not go over $y = x$ is known to be the $n$th Catalan number $$ C_n = \frac{1}{n+1}\binom{2n}{n} = \binom{2n}{n} - \binom{2n}{n-1}. ...
Sammy Black's user avatar
  • 25.9k
1 vote

Find constant for asymptotic equivalence (Stirling's formula)

Hint We can just as well look for a constant $A$ that satisfies $n! {n^2 \choose n} \sim A n^{2 n}$, or $$\frac{(n^2)!}{(n^2 - n)!} \sim A n^{2 n}.$$ Now, Stirling's approximation can be written as $$\...
Travis Willse's user avatar
1 vote

Evaluate: $\sum_{i=1}^{\lfloor (n+1)/2\rfloor}i\binom{n-i+1}{i}$

Consider the generating function of the sum: $$ F(x) = \sum\limits_{n=0}^\infty x^n \sum\limits_{i=1}^\infty i \binom{n-i+1}{i} = \sum\limits_{i=1}^\infty i \sum\limits_{n=0}^\infty \binom{n-i+1}{i} x^...
Oleksandr  Kulkov's user avatar
0 votes

Proof of $\sum_{m=0}^{n}\binom{m}{j}\binom{n-m}{k-j}=\binom{n+1}{k+1}$ (Another form of the Chu–Vandermonde identity)

thanks to How to apply Vandermonde's Identity regarding summation bounds ? $\sum_{t=0}^n\binom{-k-1}{t-k}\binom{-j-1}{n-t-j}=\binom{-k-j-2}{n-j-k}$ for explaining the technique of changing ...
Mr. Doge's user avatar
  • 123
1 vote

Find constant for asymptotic equivalence (Stirling's formula)

We have \begin{align} \binom{n^2}{n}&=\frac{(n^2)!}{(n^2-n)!n!} =\frac{(n^2)^{n^2}e^{-n^2}\sqrt{2\pi n^2}}{ (n^2-n)^{n^2-n} e^{-(n^2-n)}\sqrt{2\pi (n^2-n)}\cdot n^n e^{-n}\sqrt{2\pi n} }(1+o(1)) \...
van der Wolf's user avatar
  • 3,367
1 vote

Evaluate: $\sum_{i=1}^{\lfloor (n+1)/2\rfloor}i\binom{n-i+1}{i}$

Let $$S_n=\sum_{i=0}^{\lfloor n/2\rfloor} i\binom{n-i}{i}.$$ Your sum is just $S_{n+1}$. This sum is related to the Fibonacci numbers, $F_n$, defined by $F_0=0,F_1=1$ and $n\in \mathbb Z\implies F_n=...
Mike Earnest's user avatar
  • 77.4k
3 votes

Evaluate: $\sum_{i=1}^{\lfloor (n+1)/2\rfloor}i\binom{n-i+1}{i}$

Trying to use a combinatorial interpretation seems difficult, as it requires having an interpretation of $\binom{n+1-i}{i}$, but because the $i$ appears in both the top and the bottom, none of the ...
Aaron's user avatar
  • 24.4k
0 votes

Lower bound for a relative of the central binomial coeff

$$T(2m, m) = \sum_{r=1}^{m} \binom{2m-r-1}{m-1} \,F(r)$$ $$T(2m, m) = \sum_{r=1}^{m}\frac{\left(\left(\frac{1}{2} \left(1+\sqrt{5}\right)\right)^r-\left(\frac{1}{2} \left(1-\sqrt{5}\right)\...
Claude Leibovici's user avatar
1 vote

Limit of $\sum_{j=0}^n (1-j){n\choose j} \frac{1}{(n-1)^j}\left( \frac{n-j}{n} \right)^k$ as $n\to \infty$ (and $k=n$)

$\newcommand{\bbx}[1]{\,\bbox[15px,border:1px groove navy]{\displaystyle{#1}}\,} \newcommand{\braces}[1]{\left\lbrace\,{#1}\,\right\rbrace} \newcommand{\bracks}[1]{\left\lbrack\,{#1}\,\right\rbrack} ...
Felix Marin's user avatar
  • 90.7k
1 vote

Limit of $\sum_{j=0}^n (1-j){n\choose j} \frac{1}{(n-1)^j}\left( \frac{n-j}{n} \right)^k$ as $n\to \infty$ (and $k=n$)

I just realised: doesn't this follow from the Dominated Convergence Theorem? We can put the indicator $\mathbb{1}_{j<n}$ in there and let the sum go all the way to infinity (or actually the ...
ploosu2's user avatar
  • 9,523
3 votes
Accepted

How to apply Vandermonde's Identity regarding summation bounds ? $\sum_{t=0}^n\binom{-k-1}{t-k}\binom{-j-1}{n-t-j}=\binom{-k-j-2}{n-j-k}$

Recall that $$\binom{v}{m} = 0 \quad m>v \; \textrm{ or} \; m<0 $$ Note that in $$S=\sum_{t=0}^n\binom{-k-1}{t-k}\binom{-j-1}{n-t-j}$$ If $$ t<k \implies \displaystyle \binom{-k-1}{t-k}=0$$ ...
Bertrand87's user avatar
  • 3,562
0 votes

A game requires 2 players opposite 2 other players, with 6 people available, how many distinct games can take place?

A more pedestrian approach: you need to select 4 people out of 6, for the first one you have six possibilities, second: five etc. But then you need to rule out some permutations: one within each pair, ...
TAR86's user avatar
  • 103
4 votes

A game requires 2 players opposite 2 other players, with 6 people available, how many distinct games can take place?

With the tennis season heating up, we can look at it like arranging doubles tennis matches. $4$ individuals can be selected in $\binom64 = 15$ ways and the tallest among them can be paired with any ...
true blue anil's user avatar
5 votes

A game requires 2 players opposite 2 other players, with 6 people available, how many distinct games can take place?

Your pairs overlap. It's no good taking $(p_1, p_2)$ and $(p_1,p_3)$ as your two pairs, right? To repair your calculation: Having chosen one pair, there are now $4$ people left to choose from, and $\...
lulu's user avatar
  • 71.5k
1 vote

Reducing product of powers of logarithm

In polynomial terms, we need to (dis)prove that for each $n,m$ there are $A(x),\dots,D(x)$ such that $$ x^n y^m = A(x-y)+B(x+y)+C(x)+D(y). $$ Note that only $a_{k},\dots,d_{k}$ for $k=n+m$ actually ...
Oleksandr  Kulkov's user avatar
1 vote

Prove the following combinatorics equality

Here we have Chu-Vandermonde's identity in disguise. We obtain \begin{align*} \color{blue}{\sum_{j=k+1}^{n-m}}&\color{blue}{\binom{j-1}{k}\binom{n-j}{m}}\\ &=\sum_{j=0}^{n-m-k-1}\binom{j+k}{k}...
Markus Scheuer's user avatar
1 vote

Seeking Reference for Identity Involving Binomial Coefficients

You won't find any reference, the claim is not true. $$ 1\leq 2\\ 1+3\leq 2+2\\ $$ but $$ 3=\binom{1}{2}+\binom{3}{2}\not\leq \binom{2}{2}+\binom{2}{2}=2. $$
Sil's user avatar
  • 16.9k

Top 50 recent answers are included