Coefficients involved in the Binomial Theorem. $\binom{n}{k}$ counts the subsets of size $k$ of a set of size $n$.

learn more… | top users | synonyms (1)

0
votes
2answers
80 views

How many routes are there that pass through at most one congested intersection

I am trying to solve the following problem, but i am not quite sure how to attack. Problem Description A taxi drives from the intersection labeled A to the intersection labeled B in the grid of ...
1
vote
3answers
95 views

Finite summation with binomial coefficients, $\sum (-1)^k\binom{r}{k} \binom{k/2}{q}$

I came across the following finite sum involving (generalized) binomial coefficients: $$ 2^q \sum_{k=0}^r \binom{r}{k} \binom{k/2}{q} (-1)^k .$$ Putting this into Mathematica gives me: $$ (-1)^q ...
5
votes
5answers
151 views

How to find $ \binom {1}{k} + \binom {2}{k} + \binom{3}{k} + … + \binom{n}{k} $

Find $$ \binom {1}{k} + \binom{2}{k} + \binom{3}{k} + ... + \binom {n}{k} $$ if $0 \le k \le n$ Any method for solving this problem? I've not achieved anything so far. Thanks in advance!
0
votes
1answer
27 views

$X_n = \sqrt[k]{n^{p}+an^{q}+1}-\sqrt[k]{n^{p}+bn^{q}+1} $

For what given p and q below sequence is bounded? $X_n = \sqrt[k]{n^{p}+an^{q}+1}-\sqrt[k]{n^{p}+bn^{q}+1} $ where $0\leq q<p$ and $a\ne b$ My try ...
2
votes
4answers
43 views

Find the value of $ \sum _{r=0} ^{2n} r ( ^{2n}C _r) ( \frac 1{r+2} ) $

Find the value of $$ \sum _{r=0} ^{2n} r ( ^{2n}C _r ) ( \frac 1{r+2} )$$ In order to solve this I am trying to make the term(s) of the series independent of $r$. However I'm unable to solve ...
3
votes
3answers
86 views

A combinatorial identity: $\sum _{i + j = k} (-1)^i {n \choose i} {n + j - 1 \choose n - 1 } = 0 $

I proved this combinatorial identity while doing some linear algebra. For any positive integer $k$, $$ \sum _{i + j = k} (-1)^i {n \choose i} {n + j - 1 \choose n - 1 } = 0 $$ I was wondering what ...
3
votes
0answers
148 views

Sum problem involving Factorials

got the following problem to prove for $n \in \mathbb{N}$ and $1 \leq i \leq n$: \begin{equation} \sum_{k=1}^{n-i} \frac{(2n-1-i-2k)! 2^{2k}}{(n-i-k)! (n-k)! 2}=\sum_{k=1}^{n-i} \frac{(2n-1-i-k)! ...
1
vote
1answer
132 views

Need help finding a closed form for complicated sum

I'm trying to find a closed form expression for the following sequence: $$a_n=\sum_{i=1}^{n}\frac{(n-1-i+d)!}{(n-2i)!(i)!}=\sum_{i=1}^{\frac{n}{2}}\frac{(n-1-i+d)!}{(n-2i)!(i)!}$$ Where $n$ and $d$ ...
2
votes
2answers
133 views

Binomial coefficients identity: $\sum i \binom{n-i}{k-1}=\binom{n+1}{k+1}$

I am trying to prove $ \sum_{i=1}^{n-k+1} i \binom{n-i}{k-1}=\binom{n+1}{k+1} $ Whichever numbers for $k,n$ I try, the terms equal, but when I try to use induction by n, I fail to prove the ...
3
votes
0answers
45 views

An inequality concerning non-negative integer matrices with constant row and column sums

I'd appreciate any suggestions for how to prove (or disprove) the inequality described below. Some notation first: for positive integers $k$ and $M$, let ${\mathcal D}_{k,M}$ denote the set of all $k ...
1
vote
0answers
158 views

Sum concerning Catalan triangle and binomials

I am trying to prove the following relation. For $k \in \mathbb{N},k \geq 2$ and $i=1,\ldots,k-1$ \begin{equation} {2k-2-i \choose k-1-i}=\sum \limits_{l=0}^{k-1-i} 2^{2l} T(k-2-l,k-1-i-l)-2 \sum ...
3
votes
4answers
120 views

Closed form for a formula with a summation over $i\binom{n-i}{k-1}$, and combinatorial proof?

I was trying to simply an expression in an exercise related to randomized algorithms. Here is the expression which I have obtained at the end. $$ \displaystyle\frac{\displaystyle\sum_{i=1}^{n+k-1} i ...
1
vote
2answers
90 views

Using Binomial coefficient to solve a problem with unfair coins

I have 5 fair coins and 10 unfair coins in a bag. For the unfair coins, there is 80% chance of getting a head and 20% for tails. What's the probability of flipping 4 heads out of 6 flips? Each flip is ...
5
votes
1answer
102 views

Inequality with sum of Binomial coefficients.

Prove that for every positive integer $n \ge 2$$$\sum^n_{k=1}k \sqrt{\begin{pmatrix}n\\ k\end{pmatrix}}\leq\sqrt{2^{n-1}n^3}$$ I tried it by induction but I didn't know how to end it.
2
votes
1answer
132 views

Evaluate $\sum_{k=1}^{n} (2k-1){n \choose k}$ using calculus

Evaluate $\sum_{k=1}^{n} (2k-1) {n \choose k} $ using calculus I found out the value by the following method: $$T_r= (2r-1) {n\choose r}$$ $$S_r= \sum^n _{r=1} \left(2r {n\choose r} - {n\choose ...
1
vote
1answer
43 views

Inequality involving binomial coefficients

I recently stumbled upon an inequality involving binomial coefficients. There is reason to suspect that it holds for all $l\in\mathbb{N}$. It states that $$ (2l+1)^{2l+1} < \sum_{m = 0}^{l} ...
1
vote
0answers
34 views

Maximizing expected value when distribution is binomial

Consider the following problem: $$\max_{n\in\mathbb N}\;f(n)= \frac12 \left[v_0 \sum_{i=\lceil k_n \rceil}^n \binom{n}{i}p^i (1-p)^{n-i} + v_1\sum_{i=1}^{\lfloor k_n ...
10
votes
1answer
438 views

New Year Combinatorics

In the spirit of the festive period and in appreciation of the encouraging response to my X'mas Combinatorics problem posted recently, here's one for the New Year! Express the following as a ...
3
votes
1answer
58 views

Sum of squares of Binom(n,p) values

Let $x_{n,p}(j)$ be the probability that a random variable distributed according to a binomial distribution with parameters $n \in \mathbf{N}_+$ and $p \in (0,1)$ takes the value $j \in ...
0
votes
0answers
33 views

Closed form equation with binomial coefficients

I need a closed form for the sum $\sum\limits_{i=0}^{\infty}{n-iT-1 \choose i}x^i$ $n$, $T$ are constants and positive but may not be integers. However, they can take nearest integer values, if not ...
3
votes
1answer
64 views

Do these ratios of the Eulerian number triangle converge to the logarithm of x?

Consider the matrix $A_3$ with the definition if $n=k$ then $A_3(n,k)=\binom{n-1}{k-1}=1$, else if $n\ge k$ then $A_3(n,k)=\frac{\binom{n-1}{k-1}}{1-x}$ else $A_3(n,k)=0$. $\binom{n-1}{k-1}$ means the ...
9
votes
2answers
192 views

Number of ways to arrange $n$ items in $m$ positions having exactly $k$ items adjacent to each other

It was over 20 years since I studied maths and I am stuck. I'd really appreciate some help understanding this (probably quite simple) problem. I have $n$ items that I can place on $m$ positions. $m$ ...
0
votes
1answer
59 views

The limit of an infinite product involving the squares of $\binom{n}{j}x^j(1-x)^{n-j}/k$

Some months ago, me and a friend tried to solve the following $"~natural~"$ question: Given weights $p_{1},\ldots,p_{m}$ and distinct points in $S_{0} := \left\{\, x_{1},\ldots,x_{n}\,\right\}$ of ...
2
votes
0answers
73 views

Consecutive numbers in rows of Pascal's triangle …

The fourteenth row of Pascal's triangle has an interesting property. $$\begin{align} \binom{14}{4}+\binom{14}{5} &= 1001+2002 \\ =\binom{14}{6} &= 3003 \end{align}$$ This begs the ...
12
votes
7answers
1k views

How do I prove that there infinitely many rows of Pascal's triangle with only odd numbers?

This is exercise number $59$ from Chapter $2$ of Hugh Gordon's Discrete Probability. Show that there are infinitely many rows of Pascal's Triangle that consist entirely of odd numbers. ...
0
votes
2answers
49 views

How $(r-k){r \choose r-k}$ becomes $r{r-1 \choose r-k-1}$?

I'm reading Knuth/Graham/Patashnik's Concrete Mathematics: I don't understand how he goes from $(r-k){r \choose r-k}$ to $r{r-1 \choose r-k-1}$ using $(5.6)$. The mentioned property has a $k$ ...
6
votes
1answer
106 views

Is $(n+\ell)^{-1}\binom{kn}{n}$ an integer for only $(\ell,k)=(1,2)$?

Find all pairs $(\ell,k)$ of natural numbers, such that the number $\dfrac1{n+\ell}\dbinom{kn}{n}$ is an integer for all natural $n$. Is $(\ell,k)=(1,2)$ the only solution?
2
votes
1answer
54 views

How to use $\binom a k = \frac{\alpha(a-1)(a-2)\cdots(a-k+1)}{k(k-1)(k-2)\cdots 1}$ to check that ${-1\choose 0}=1$?

I'm trying to use the binomial coefficient: $$\binom{x}k=\begin{cases} \frac{x^{\underline k}}{k!},&\text{if }k\ge 0\\\\ 0,&\text{if }k<0\;, \end{cases}$$ To check that ${-1\choose 0}=1$. ...
1
vote
1answer
37 views

How to use $\binom a k = \frac{\alpha(a-1)(a-2)\cdots(a-k+1)}{k(k-1)(k-2)\cdots 1}$ to check that $ {-n \choose -n}=0$?

I am trying to use this definition of the binomial coefficient: $$\binom \alpha k = \frac{\alpha^{\underline k}}{k!} = \frac{\alpha(\alpha-1)(\alpha-2)\cdots(\alpha-[k-1])}{k(k-1)(k-2)\cdots 1}$$ To ...
1
vote
1answer
75 views

Why $ {-1\choose 3}=-1$?

Having the following definition: $$\binom \alpha k = \frac{\alpha^{\underline k}}{k!} = \frac{\alpha(\alpha-1)(\alpha-2)\cdots(\alpha-k+1)}{k(k-1)(k-2)\cdots 1}\tag{1}$$ Why $\bbox[1px,border:1px ...
0
votes
2answers
69 views

Sum of binomial coefficients $\sum _{ x=r-2 }^{ n-2 } \binom{x}{r-2}$

$$\sum _{ x=r-2 }^{ n-2 } \binom{x}{r-2}$$ I can't find the sum of the following series. I would appreciate if anyone can show me this problem's solution.
6
votes
2answers
82 views

Is there a “counting groups/committees” proof for the identity $\binom{\binom{n}{2}}{2}=3\binom{n+1}{4}$?

This is exercise number $57$ in Hugh Gordon's Discrete Probability. For $n \in \mathbb{N}$, show that $$\binom{\binom{n}{2}}{2}=3\binom{n+1}{4}$$ My algebraic solution: ...
6
votes
5answers
189 views

Combinatoric proof for $\sum_{k=0}^n{n\choose k}\left(-1\right)^k\left(n-k\right)^4 = 0$ ($n\geqslant5$)

I'm trying to proove the following: $For\space every\space n \ge 5$: $$\sum_{k=0}^n{n\choose k}\left(-1\right)^k\left(n-k\right)^4 = 0$$ I've tried cancelling one $(n-k)$, and got this: ...
27
votes
1answer
1k views

X'mas Combinatorics

Inspired the various** algebraic X'mas greetings sent to me over the festive period, I thought I would try to devise one of my own. $$\Large ...
6
votes
6answers
171 views

How to compute $\sum^n_{k=0}(-1)^k\binom{n}{k}k^n$

When trying to answer this question I arrived at $$\int^\infty_0\frac{\sin(nx)\sin^n{x}}{x^{n+1}}dx=\frac{\pi}{2}\frac{(-1)^n}{n!}\sum^n_{k=0}(-1)^k\binom{n}{k}k^n$$ After using Wolfram Alpha to ...
1
vote
3answers
53 views

If a word appears with probability $0.05$, how many words are needed so that it appears with probability $0.99$?

Probability of a specific word appearing in a language is $0.05$. How many words must there be in a text, so that the word appears at least once with a probability of $0.99$? My understanding is ...
1
vote
3answers
171 views

What is the value of $\sum_{n=0}^{\infty}(-\frac{1}{8})^n\binom{2n}{n}$

What is the value of $$\sum_{n=0}^{\infty}\left(-\frac{1}{8}\right)^n\binom{2n}{n}\;?$$ EDIT I bumped into this series when inserting $\overrightarrow{r_1}=\left(\begin{array} ...
3
votes
1answer
75 views

Good approximation for $\binom{N}{\frac{N}{2}}$

$$\log_2\binom{N}{\frac{N}{2}}\approx N\log_2N - 2(N-\frac{N}{2})\log_2(N-\frac{N}{2})=N\log_2N - 2\frac{N}{2}\log_2(\frac{N}{2})$$ $$=N\log_2N - {N}{}\log_2({N}) + {N}{}=N$$ ...
6
votes
1answer
65 views

An identity involving partial fractions decompositions

In Vladimir A. Smirnov's book Analytic Tools for Feynman Integrals (page 38), the following identity is suggested to perform partial fractions decompositions $$ \begin{split} ...
3
votes
0answers
69 views

Asymptotics of integer compositions

A (weak) composition of a positive integer $n$ into $k$ parts is an ordered sequence of nonnegative integers $(a_1, a_2, \ldots, a_k)$ such that $ \sum_{i=1}^k a_i = n $. I am interested in the case ...
0
votes
1answer
26 views

expressing canonical base of univariate polynomials in binomial base

Two bases are fairly standard for ${\mathbb Q}[X]$ : the canonical base $(X^j)_{j\geq 0}$ and the binomial base $(b_j(X))_{j\geq 0}$ where $b_j(X)=\binom{X}{j}=\frac{X(X-1)\ldots (X-(j-1))}{j!}$ (thus ...
2
votes
2answers
120 views

Binomial theorem.

I first saw this thing (admittedly much to late in life) in a third year class entitled non-linear dynamics and chaos theory. There if i am remembering correctly we used to look for non-zero terms to ...
0
votes
4answers
144 views

How to prove that the sum of squared binomials equals $\binom{2n}{n}$ [duplicate]

I've stumbled upon this lemma a few times in my textbook: $$\sum_{k=0}^{n}\begin{pmatrix}n\\k\end{pmatrix}^2=\begin{pmatrix}2n\\n\end{pmatrix}$$ I've been trying to prove it, but I simply can't seem ...
0
votes
2answers
31 views

Congruence with binomial

I tried to prove this by induction on $k$. But I did not manage Let $p$ be a prime. For every $k\in\{0,\cdots,p-1\}$, one has $$\binom{p-1}k\equiv(-1)^k\pmod p.$$ By Wilson theorem, it suffices to ...
-2
votes
0answers
94 views

If $k, m, n$, are natural numbers and $k \leq n$ What is the final answer of this : [duplicate]

If $k, m, n$, are natural numbers and $k \leq n$ What is the final answer of this: $$\sum_{r=0}^{m}\frac{k\binom{m}{r}\binom{n}{k}}{(r+k)\binom{m+n}{r+k}}$$
-3
votes
3answers
161 views

Binomial-coefficients if, k, m, n natural numbers and k \leq n the result of [closed]

If $k, m, n$, are natural numbers and $k \leq n$ What is: $$\sum_{r=0}^{m}\frac{k\binom{m}{r}\binom{n}{k}}{(r+k)\binom{m+n}{r+k}}$$
2
votes
2answers
48 views

If given $\sum_{r=1}^{m-1}\binom r3$, how does the summation evaluate when $n<r$ in $\binom nr$?

Correct me if I'm running the summation correctly - $$\sum_{r=1}^{m-1}\binom r3=\binom 13+\sum_{r=2}^{m-1}\binom r3$$ $$\sum_{r=1}^{m-1}\binom r3=\binom 13+\binom 23+\sum_{r=3}^{m-1}\binom r3$$ ...
11
votes
1answer
125 views

How find all postive integer number such $(n+k)\nmid \binom{2n}{n}$

Question: Find the all integer $k$,such there are exist infinitely many $n$ such $$(n+k)\nmid \binom{2n}{n}$$ This is china 2014 (CMO problem 4),it's have been end exam three hours ago. I ...
6
votes
1answer
167 views

How to transform the product to sum?

I just wonder that how to prove that $$ \prod_{m=1}^{n}\Big(x-2\cos\frac{m\pi}{n+1}\Big)=\sum_{k=0}^{[n/2]}(-1)^{k}\binom{n-k}{k}x^{n-2k}. $$ Similarly, how to transform the product $$ ...
0
votes
1answer
66 views

Can this binomial summation be simplified?

I got something like $\displaystyle\sum_{i=0}^K{ \binom{n+i}{i} \cdot \alpha^i} $ where $n,\ K,\ \alpha$ are definite values, $\binom{n+i}{i}$ is the Combinatorial number that choose $i$ from ...