1
vote
2answers
37 views

Inequality with two binomial coefficients

I am having trouble seeing why $$ \binom{k}{2} + \binom{n - k}{2} \le \binom{1}{2} + \binom{n - 1}{2} = \binom{n - 1}{2} $$
1
vote
3answers
39 views

Sum of certain binomial coefficients

$$\sum_{k=0}^{m} \frac{(q+k)!}{k!q!}$$ I do not know how to even start this problem. Any general tips on these types of problems will also be welcomed.
4
votes
3answers
181 views

How to closed the sum $\displaystyle \sum_{k=0}^n \dfrac{(-1)^k(2k+1)!!}{(n-k)!k!(k+1)!}$

How to closed the sum $\displaystyle S=\sum_{k=0}^n \dfrac{(-1)^k(2k+1)!!}{(n-k)!k!(k+1)!}$ I'm trying divide two cases $n$ odd and $n$ even. I predict that ...
0
votes
0answers
19 views

closed form of a specific crazy summation?

How can I find the closed form of $f_2 + f_4 + ...+ f_{2m}$ where $\sum\limits_{m=1}^\infty f_{2m} = u_{2m-2}- u_{2m} $ where $u_{2m} = \binom{2m}{m} 2^{-(2m)}$ and $u_{2m-2} = \binom{2m-2}{m-1} ...
4
votes
0answers
76 views

How to prove this indentity $\binom{100}{0}^2-\binom{100}{1}^2+\binom{100}{2}^2-…-\binom{100}{99}^2+\binom{100}{100}^2=\binom{100}{50}$ [duplicate]

I don't know how to prove this identity: $\binom{100}{0}^2-\binom{100}{1}^2+\binom{100}{2}^2-\binom{100}{3}^2+...-\binom{100}{99}^2+\binom{100}{100}^2=\binom{100}{50}$
1
vote
1answer
33 views

Simplifying Sum of Subsets

Given sets $A$ and $R$ such that $R \subseteq A$ and a number $x \leq |A|$, I am trying to simplify the following sum: $$\begin{equation*} \sum_{R \subseteq W \subseteq A : |W| = x} \Big( \sum_{Y ...
2
votes
5answers
59 views

How to find the coefficient of $x^8$ in $\prod\limits_{i=1}^{10}{\left(x-i\right)}$?

How to find the coefficient of $x^8$ in $(x-1) (x-2) . . .(x-10)$. Is there any general formula to solve this kind of problems?
2
votes
0answers
32 views

Binomial coefficients inequality

It seems to me that there should be a simple way to prove that $$ \binom{n}{s+1+a} + \binom{n}{a} \leq \binom{n}{s} $$ For $s > n/2$ and $a < n-s$. However it looks like I'm missing it. Any ...
-1
votes
0answers
26 views

No. of odd and even numbers in binomial expansion

For a given number n, there would be n+1 terms in binomial expansion. Out of them how many will be odd valued?
1
vote
2answers
81 views

Binomial Expansion.

So I had a question: Prove that for $n \geq 1$, $${n \choose 1} + 2{n \choose 2} + 3{n \choose 3} + ...+ n{n \choose n} = n2^{n-1}$$ So my idea was to take the binomial expansion of $(1+1)^n$ which ...
1
vote
1answer
30 views

Binomial Coefficient Recusions

Let m and j be non-negative integers. Define $S^{0}_{m} = 1$ and: $ S^{j}_{m} = \displaystyle\sum\limits_{i=1}^{m} S_{i}^{j-1}$ Show via induction: $ S_{m}^{j} = {m+j-1 \choose j} $ I can ...
1
vote
0answers
24 views

Chu-Vandermonde-like combinatorial identity

I am looking for a simple combinatorial proof of the binomial identity: $$\sum_{j=0}^n \binom{2j}{j}\binom{2n-2j}{n-j} = 4^n.\tag{1}$$ The standard way I know is to exploit the generating function: ...
1
vote
1answer
45 views

Finding the coefficient of a generating function

Given $f(x) = x^4\left(\frac{1-x^6}{1-x}\right)^4 = (x+x^2+x^3+x^4+x^5+x^6)^4$. This is the generating function $f(x)$ of $a_n$, which is the number of ways to get $n$ as the sum of the upper faces of ...
2
votes
0answers
47 views

How to prove these indentities?

How to prove these indentities? $\displaystyle \sum \limits_{k\geq0} {2n\choose 2k-1}{k-1\choose m-1}=2^{2n-2m+1}{2n-m\choose m-1}$ $\displaystyle \sum \limits_{k=0}^{m} {m\choose k}{n+k\choose ...
2
votes
1answer
33 views

Calculate sum wtih binomial coefficients

I need help with finding the sum of $\sum \limits_{k=0}^{n} \frac{1}{k+1}{n\choose k}x^{k+1}$
0
votes
1answer
40 views

Function returning number of subsets of size $k$ of a set of size $n$.

I am looking for a function that returns the number of subsets of size $k$ of a set of size $n$. Ideally, the function is commonly used. I took a look at the binomial coefficient. However, there ...
1
vote
1answer
38 views

In a lottery of $90$ numbers a man adds extra $1,2,3$

Consider a lottery where $5$ balls are chosen randomly among $90$ balls numbered from $1$ to $90$. A man cheats adding to the $90$ balls, before the draw, three more balls numbered $1,2,3$. We say ...
2
votes
2answers
76 views

How do you prove ${n \choose k}$ is maximum when k is $ \lceil \frac n2 \rceil$ or $ \lfloor \frac n2\rfloor $?

How do you prove ${n \choose k}$ is maximum when k is $ \lceil \frac{n}{2} \rceil $ or $ \lfloor \frac{n}{2} \rfloor$ ? This link provides a proof of sorts but it is not satisfying. From what I ...
7
votes
2answers
142 views

How to count matrices with rows and columns with an odd number of ones?

I proved that $\displaystyle \left(\sum_{k\, \rm odd}\binom{m}{k}\right)^{n-1}=\left(\sum_{k\;{\rm odd}}\binom{n}{k}\right)^{m-1}$ by counting matrices of size $n\times m$ with entries in $\{0,1\}$ ...
3
votes
1answer
35 views

A combinatorics question on a sequence of binomial coefficents

On a past-paper of a Combinatorics exam I will be taking they ask the question: Prove that for $k$ odd and greater than 1, the sequence of numbers $\binom{k}{1}, \binom{k}{2}, ..., ...
5
votes
1answer
241 views

Are these two binomial sums known? Proven generalization to the Hockey Stick patterns in Pascal's Triangle

English translation. You can see the original - deprecated - in Portuguese here Hi, I arrived at a generalization for the Hockey Stick Patterns, from our beloved Pascal's Triangle. This ...
2
votes
1answer
31 views

Integer valued polynomials in two variables

The ring of integer valued polynomials, $\{ f \in \mathbb{Q}[x] : f(\mathbb{Z}) \subseteq \mathbb{Z} \}$ is fairly well-known to be generated as Abelian group by the binomial coefficients, $f_k(n) = ...
2
votes
3answers
59 views

Probability of 5 cards drawn from shuffled deck

Five cards are drawn from a shuffled deck with $52$ cards. Find the probability that a) four cards are aces b) four cards are aces and the other is a king c) three cards are tens and ...
2
votes
1answer
45 views

Using combinatorial reasoning to show $n!=\binom{n}{0}D_n+\binom{n}{1}D_{n-1}+\dots+\binom{n}{n}D_0$

How can one use combinatorial reasoning to show that $$n!=\dbinom{n}{0}D_n+\dbinom{n}{1}D_{n-1}+\dbinom{n}{2}D_{n-2}+....+\dbinom{n}{n-1}D_1+\dbinom{n}{n}D_0$$ Now $D$ stands for deranged which is a ...
2
votes
2answers
114 views

How are lopsided binomials (eg $\binom{n}{n+1})?$ defined?

For instance is $\binom{n}{n+1}=0$ always or something else?
2
votes
4answers
85 views

Finding an algebraic proof for $r{n \choose r} = n{n-1 \choose r-1}$ [closed]

I can't seem figure this proof out. How are both sides equal. $$r{n \choose r} = n{n-1 \choose r-1}$$
0
votes
0answers
49 views

Estimation for sum over binomial coefficients

I am trying to show that a certain procedure for resource allocation is approximately efficient. For this I need to show that $$ \lim_{n\rightarrow \infty} \left(\frac{1}{e}\right)^n\sum_{c=2}^n ...
1
vote
3answers
60 views

Number of ways to distribute indistinguishable balls into distinguishable boxes of given size

I need to find a formula for the total number of ways to distribute $N$ indistinguishable balls into $k$ distinguishable boxes of size $S\leq N$ (the cases with empty boxes are allowed). So I mean ...
0
votes
7answers
138 views

Calculating $\binom{1}{2}$

Show $\displaystyle\sum_{i=1}^{n} \binom{i}{2}=\binom{n+1}{3}$. I'm thinking right now (though not getting anywhere with it) that I want to expand out the summation portion to $i!/2!(i-2)!$ and ...
0
votes
1answer
23 views

Strictly increasing maps

For $p\ge n$, how many strictly increasing maps from $N^*_n$ to $N^*_p$ do exist, where $N^*_n = \{1, 2, \dots, n\}$ is the set of the first $n$ integers greater than 0 ? My answer: uncountable many. ...
0
votes
0answers
28 views

Moment generating function with binomial coefficients

I am trying to calculate a moment generating function, and I have obtained the following result: \begin{equation} ...
7
votes
2answers
125 views

Cousin of the Vandermonde binomial identity

The Vandermonde binomial identity can be expressed as \begin{align*} \sum_{i+j=r} \binom{m}{i} \binom{n}{j} = \binom{m+n}{r} && r \leq m +n. \end{align*} While working on an algebra problem, I ...
3
votes
2answers
68 views

Simplify a triple sum

I need to find a closed form for this summation: $$\sum_{j=1}^m\sum_{i=j}^m\sum_{k=j}^m\frac{{m\choose i}{{m}\choose{k}}}{j{m\choose j}}r^{k-j+i}$$ I posted this a long time ago, but today I found out ...
1
vote
3answers
54 views

A particular sum involving product of binomial coefficients

I am encountering a particular sum involving binomial coefficients, and I am looking for a possible closed-form solution. Here is the sum: suppose we are given two real numbers $a \in (0,1)$ and $b ...
2
votes
1answer
97 views

A combinatorial identity $\sum_{i=0}^k \binom ni \binom{-n}{k-i} =0$

Can anyone prove the following identity for me? $\sum_{i=0}^k \begin{pmatrix} n\\ i \end{pmatrix} \begin{pmatrix} -n\\ k-i \end{pmatrix}=0$ for any positive integers $n,k$. I'm pretty sure this is ...
3
votes
1answer
85 views

A generalization of the Vandermonde's convolution

I need to find a closed formula for the following sum: \begin{equation} \sum_{i=0}^{n}i^{k}\left(\begin{array}{c} n\\ i \end{array}\right)\left(\begin{array}{c} n^{2}-n\\ c-i \end{array}\right) ...
3
votes
3answers
155 views

What is the coefficient of the term $x^4 y^5$ in $(x+y+2)^{12}$?

What is the coefficient of the term $x^4 y^5$ in $(x+y+2)^{12}$? How can we calculate this expression ? I've applied the binomial theorem formula and got $91$ terms but I am not sure if it is right ...
0
votes
5answers
150 views

Proof of a binomial identity $\sum_{k=0}^n {n \choose k}^{\!2} = {2n \choose n}.$

Prove that $$\sum_{k=0}^n {n \choose k}^{\!2} = {2n \choose n}.$$ The exercise provides the following hint: $\,\,\displaystyle{n \choose k}={n\choose n-k}$. Any help?
0
votes
2answers
69 views

Prove the identity $\sum_{{{\underset{k-even}{k=0}}}}^{n}{n \choose k}2^{k}=\frac{3^{n}+(-1)^{n}}{2}$

I need to prove the following identity: $\sum_{{{\underset{k-even}{k=0}}}}^{n}{n \choose k}2^{k}=\frac{3^{n}+(-1)^{n}}{2}$ I know that - $\sum_{k=0}^{n}{n \choose k}2^{k}=3^{n}$ but don't know ...
5
votes
2answers
269 views

Proving $\sum_{k=1}^n{2k-1\choose k}{2n-2k+1\choose n-k+1}=4^n-{2n+1\choose n+1}$

Some background. I was asked to find an arithmetic function $f$ such that $f*f=\mathbf 1$ where $\mathbf 1$ is the constant function 1 and $*$ denotes Dirichlet convolution. I was able to prove that ...
2
votes
2answers
76 views

Infinite Sum with Combination

I am trying to figure out what the following sum converges to: $$\sum_{n=0}^\infty {6+n\choose n}x^n(6+n),\qquad\qquad0<x<1$$ An answer would be great, but if you have an explanation, that'd ...
2
votes
0answers
76 views

How to prove this combinatorial identity

I am wondering how to prove the following identity: $$\sum_{k=0}^r {r-k \choose m} {s \choose k-t} (-1)^{k-t} = {r-t-s \choose r-t-m}$$ It seems that I can negating the upper index of ${s \choose k-t} ...
1
vote
1answer
53 views

A combinatorial identity?

Is there a combinatorial identity for the following: $$\sum_{k=0}^{i}\binom{n}{k} $$ for arbitrary integers $n, i$ with $n > i$? If so, what is this identity called?
2
votes
1answer
55 views

Question about balls in urns

Suppose there are $n$ balls in an urn, and $r$ of them are red. I select $m$ balls from this urn at random. What is the probability that at least $k$ of them are red? $m$ must be less than $n$, but ...
3
votes
0answers
36 views

Verification of a Combinatorial Identity

I have a challenge for you combinatorial mathematicians. Is anyone willing to verify the following combinatorial identity? ...
1
vote
1answer
67 views

Solving Binomial Coefficients with Double Counting

I have a problem that I am trying to solve two different ways. The problem is: The following equality holds, for a positive integer $n$: $$\dbinom{2n}{2} = 2\dbinom{n}{2} + n^2$$ Show that ...
1
vote
2answers
50 views

To provide a combinatorial argument for a combinatorics equality.

Prove that, $${n \choose m}+2{n-1 \choose m}+\ldots+(n-m+1){m \choose m}={n+2 \choose m+2}$$ My work: I thought it would be better to use combinatorial argument than trying to provide a rigorous ...
2
votes
3answers
51 views

$2^n$ choose something

Let $m$ be a positive integer, and let $n=2^m$. Prove that the numbers $$ \binom{n}{1}, \binom{n}{2}, \dots , \binom{n}{n-1} $$ are all even. -Source: ASMP sample problems Counting Strategies number ...
2
votes
2answers
44 views

Counting two ways, $\sum \binom{n}{k} \binom{m}{n-k} = \binom{n+m}{n}$

prove by counting two ways: I though to prove the right hand side I would say: Let n represent a number of boys and m a number of girls. We want to choose a group of n from boys and girls. But for ...
3
votes
1answer
35 views

Bounding one binomial coefficient with another

For given $n$ and $m$, I am interested in finding an expression for the smallest $r$ such that the following holds: ${r \choose m} \geq \frac{1}{2} {n \choose m}$. Is such an expression, or at least ...