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)

2
votes
0answers
45 views

Integers in the form $\sum_{j=0}^n a_j2^j3^{n-j}$

Let $n>0$ be an integer. Let also $a_j$ be some integer in the set $\{0,1,\ldots,\binom{n}{j}\}$ for all $j=0,1,\ldots,n$. Then, how many integers can be written in the form $$2^n ...
1
vote
1answer
25 views

Hillman and Hoggat's Binomial Generalization

In proving Gould's "Star of David" conjecture, Hillman and Hoggat generalized the binomial coefficient. First, they demand that $a_n$ be a sequence with the two properties that $$\gcd(a_m, a_n) \mid ...
2
votes
2answers
117 views

Combinatorial proof for $ \sum _{r=1} ^n r^3 \binom nr = n^2(n+3) 2^{n-3}$

Find the combinatorial proof for $$ \sum _{r=1} ^n r^3 \binom nr = n^2(n+3) 2^{n-3}$$ After proving it using algebra, I'm unable to find a combinatorial argument for the above statement. Help ...
0
votes
2answers
72 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
91 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
143 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
26 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
41 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
82 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
141 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
129 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
122 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
44 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
155 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
117 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
83 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
93 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
117 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
40 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
33 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
434 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
57 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
62 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 ...
8
votes
2answers
168 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
58 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
64 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
47 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
103 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
36 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
73 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
67 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
80 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
187 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
166 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
166 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
73 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
62 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
67 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
25 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
114 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
139 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
160 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
47 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$$ ...