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)

4
votes
1answer
229 views

Research: Looking for a sequence that produce variation's of Pascal's triangle

Prologue I am an undergraduate so if my terminology or approach seem inappropriate/confusing please explain in the comments. I created a notation where $$F(0 \rightarrow n,x) = [\hspace{1mm}F(0 ,...
1
vote
2answers
30 views

Notation for binomial coefficient set

I've been searching for a way to express "the set of all combinations generated by taking $\binom{n}{k}$ items". For example, if I have the set $\{3,7,6,5,9\}$, and I want the set of all sets that ...
-1
votes
1answer
53 views

A binomial sum identity

Let \begin{align*} f(n, r, \pi, k) &= \sum_{z=0}^{n}\sum_{s=0}^{r}\binom{z}{s}\binom{n}{z}\binom{n-z}{r-s}(-1)^{r+s}\left(\frac{\pi}{1-\pi}\right)^{r/2-s}\pi^{z}(1-\pi)^{n-z}z^k \end{align*} I am ...
2
votes
5answers
50 views

Counting arguments Given one prove the other identity

Given: $${n \choose 0} + {n \choose 1} + {n \choose 2} + \cdots + {n \choose n} = 2^n$$ Prove the following in 2 ways. $$ {n \choose 1} + 2 {n \choose 2} + 3 {n \choose 3} + \cdots + n{n\choose n} =...
1
vote
3answers
32 views

Problem related to series of binomial coefficients

Problem related to series of binomial coefficients in which each term is a product of two binomial coefficients. In this question: Prove that $$\binom{n}0^2+\binom{n}1^2+\ldots+\binom{n}n^2=\...
14
votes
10answers
9k views

Proving Pascal's Rule : ${{n} \choose {r}}={{n-1} \choose {r-1}}+{{n-1} \choose r}$ when $1\leq r\leq n$

I'm trying to prove that ${n \choose r}$ is equal to ${{n-1} \choose {r-1}}+{{n-1} \choose r}$ when $1\leq r\leq n$. I suppose I could use the counting rules in probability, perhaps combination= ${{n}...
0
votes
1answer
14 views

Prove that: ${^{n}\mathrm{C}_{k}} = {^{n-1}\mathrm{C}_{k-1}}+{^{n-1}\mathrm{C}_{k}}$ [duplicate]

Question asks to prove: ${^{n}\mathrm{C}_{k}} = {^{n-1}\mathrm{C}_{k-1}}+{^{n-1}\mathrm{C}_{k}}$ My Steps: $$\begin{align*}\frac{(n-1)!}{(n-k-2)!(k-1)!} + \frac{(n-1)!}{(n-k-1)!(k)!} & = \...
0
votes
1answer
49 views

Closed formula for ${r \choose 1}+{r \choose 2}\cdots{r \choose w}$ where $w < r$ [on hold]

Let $r,w \in \mathbb{N}$. Are there some formula for the next sum? $${r \choose 1}+{r \choose 2}\cdots{r \choose w}$$ where $w<r$?
3
votes
3answers
64 views

Combinatorial identity's algebraic proof without induction. [duplicate]

How would you prove this combinatorial idenetity algebraically without induction? $$\sum_{k=0}^n { x+k \choose k} = { x+n+1\choose n }$$ Thanks.
3
votes
2answers
79 views

Finite summation including binomial coefficients and double factorials

I came across the following summation: $$ \sum_{k=0}^n\frac{(-1)^k(2k)!!}{(2k+1)!!}\dbinom{n}{k}\,\,\,\,(n\in\mathbb{N}). $$ $\tbinom{n}{k}$ are binomial coefficients, $n!/k!(n-k)!$. Mathematica told ...
0
votes
2answers
38 views

How to prove that ${l \choose a_1,…,a_n}\le n^{l-1} $ , when $a_1+…+a_n=l$.

In the proof of (Corollary 8 chap. 3 ) in the book "Sobolev Spaces on Domains" by Burenkov the following inequality is used : given $a_1,...,a_n \in \mathbb{N}$ such that $a_1+...+a_n=l$, then $${l \...
6
votes
6answers
110 views

Proving that ${x +y+n- 1 \choose n}= \sum_{k=0}^n{x+n-k-1 \choose n-k}{y+k-1 \choose k} $

How can I prove that $${x +y+n- 1 \choose n}= \sum_{k=0}^n{x+n-k-1 \choose n-k}{y+k-1 \choose k} $$ I tried the following: We use the falling factorial power: $$y^{\underline k}=\underbrace{y(y-1)(...
7
votes
3answers
109 views

Inverse of the Pascal Matrix

Let $P_n$ be the $(n+1) \times (n+1)$ matrix that contains the numbers of Pascal's triangle in the upper triangle. For example in the case of $n=3$ $$ P_3 = \begin{pmatrix} 1 & 1 & 1 & 1 \...
-1
votes
0answers
26 views

Bound on binomial summation

The bound for $\sum_{i=1}^n\binom{n}{i}2^i$ is $O(3^n)$ but what will be the bound for $\sum_{i=1}^{\frac{n}{2}}\binom{n}{i}2^i$. Any idea how should I proceed.
4
votes
1answer
25 views

Find an explicit map with certain combinatorial properties

The following combinatorial problem popped up in a totally uncombinatorial context: Let $\mathcal{P}$ denote the power set of a set and let $k \in \mathbb{N}$. Is there a map $c: \mathcal{P}(\{1,2,\...
1
vote
1answer
17 views

Find a map on a power set with certain combinatorial properties

The following combinatorial problem popped up in a totally uncombinatorial context: Let $\mathcal{P}$ denote the power set of a set and let $k \in \mathbb{N}$. Is there a map $c: \mathcal{P}(\{1,2,\...
6
votes
3answers
6k views

A fair coin is tossed $n$ times by two people. What is the probability that they get same number of heads?

Say we have Tom and John, each tosses a fair coin $n$ times. What is the probability that they get same number of heads? I tried to do it this way: individually, the probability of getting $k$ ...
1
vote
0answers
53 views

Combinatorics problem involving binomial coefficient

I found this interesting problem in a Romanian mathematical magazine while preparing for the USAMO. Let $k$ be a non-zero natural number. Determine $x,y,z \in \Bbb N$ such that $$\binom {z+k}{x+y} - \...
1
vote
2answers
74 views

Is there a closed form for this binomial sum?

I am looking for a closed form of this sum:$\sum\limits_{j=k}^n\binom{j}{k}(-1)^j$ I know that this sum has a closed form: $\sum\limits_{j=k}^n\binom{j}{k}=\binom{n+1}{k+1}$ I can get this closed ...
1
vote
1answer
37 views

A sum involving binomial coefficients and its evaluation using the Gamma function [duplicate]

Does anyone know how to prove (or a reference for) the following identity for positive integers $r$: $$\sum_{i=0}^r (-1)^i{r\choose i}\frac{1}{ir+1}= \frac{\Gamma(1+1/r)\Gamma(r+1)}{\Gamma(r+1+1/r)}$$
5
votes
1answer
650 views

Calculating the Shapley value in a weighted voting game.

Given a special case of WVG (Weighted Voting Game) of $a$ 1s and $b$ 2s and a quota q, $ [q:1,1,1,1..1,2,2,..2] $. I need help with calculating the Shapley value of a player with a weight of $2$ and a ...
2
votes
1answer
33 views

Binomial identity for bijection $\mathbb N\times\mathbb N\to\mathbb N$

In a book I'm currently reading it is said (without proof) that, for an enumeration $d$ of $\mathbb N\times\mathbb N$ defined by $$d(0)=(0,0),\ d(1)=(0,1),\ d(2)=(1,0),\ d(3)=(0,2),\ d(4)=(1,1),\ d(5)=...
5
votes
2answers
74 views

How to find$\sum_{i,j,k\in \mathbb{Z}}\binom{n}{i+j}\binom{n}{j+k}\binom{n}{i+k}$ for $n \in \mathbb{N}$

Yeah, it's $$\sum_{i,j,k\in \mathbb{Z}}\binom{n}{i+j}\binom{n}{j+k}\binom{n}{i+k}$$ and we are summing over all possible triplets of integers. It appears quite obvious that result is not an infinity. ...
1
vote
1answer
47 views

Algorithm for calculating multiset permutations

I have this algorithm to calculate multiset combinations: $$\mathcal P(k; m_1, m_2, \ldots, m_n) = \Sigma \binom{c(i_1)}{\lambda_1}\ \binom{c(i_2)-\lambda_1}{\lambda_2} \cdots \binom{c(i_s)-\lambda_1-...
0
votes
0answers
32 views

Given $n$ heads out of $n$ tosses. What is the posterior probability that coin is fair? [closed]

I am given an $\sigma$-fair coin with the probability of head $(\theta)$ being in the interval $[\frac{1}{2} - \sigma, \frac{1}{2} + \sigma]$. Also I am given: For a Bayesian analysis of the ...
2
votes
2answers
48 views

Using the Binomial Identity, prove that ${n\choose k}+2{n\choose k+1}+{n\choose k+2}={n+2\choose k+2}$

Using the Binomial Identity, prove that: $${n\choose k}+2{n\choose k+1}+{n\choose k+2}={n+2\choose k+2}$$Because this is in the form of a Binomial Coefficient, I can break down the LHS further:$$\left(...
5
votes
5answers
120 views

Prove that $\sum_{k=0}^n \binom{3n-k}{2n}=\binom{3n+1}{n}$

Prove that $$\sum_{k=0}^n \binom{3n-k}{2n}=\binom{3n+1}{n}$$ I've tried multiple things that didn't work. Maybe this would help $$\sum_{k=0}^n \binom{3n-k}{2n}=\sum_{k=0}^n \binom{3n-(n-k)}{2n}=\...
1
vote
2answers
108 views

Combinatorial proof of $\sum_{k=0}^{n}(-1)^{k}\binom{n}{k}(l-k)^n=n!$, using inclusion-exclusion

If $l$ and $n$ are any positive integers, is there a proof of the identity $$\sum_{k=0}^{n}(-1)^{k}\binom{n}{k}(l-k)^n=n!\;$$ which uses the Inclusion-Exclusion Principle? (If necessary, ...
11
votes
6answers
778 views

Expressing a factorial as difference of powers: $\sum_{r=0}^{n}\binom{n}{r}(-1)^r(l-r)^n=n!$?

The successive difference of powers of integers leads to factorial of that power. Here's the formula: $$\sum_{r=0}^{n}\binom{n}{r}(-1)^r(n-r)^n=n!$$ Can anyone give a proof of this result? Note:...
11
votes
2answers
466 views

Differentiating the binomial coefficient

I took a lecture in combinatorics this semester and the professor did the following step in a proof: He showed that function $f: x \mapsto \binom{x}{r}$ is convex for $x > r - 1$ (in order to use ...
6
votes
2answers
918 views

Relation between different ways of accessing bernoulli numbers

Bernoulli numbers can easily be expressed by linear algebra equations. For example just using the recursion formula $$\sum_{k=0}^{n-1}{n\choose k}B_k=0$$ which is equation (34) from the MathWorld ...
5
votes
4answers
323 views

Sum of sum of binomial coefficients $\sum_{j=1}^{n}{\sum_{k=0}^{j}{{n}\choose{k}}}$

I know there is no simple way to solve the sum: $$\sum_{k=0}^{j}{{n}\choose{k}}$$ But what about the equation: $$\sum_{j=1}^{n}{\sum_{k=0}^{j}{{n}\choose{k}}}$$ Are there any simplifications or ...
0
votes
2answers
55 views

Asymptotics of $ f_c(n)=\sum_{k=0}^{\lfloor cn\rfloor}{n\choose k} $

Define $$ f_c(n)=\sum_{k=0}^{\lfloor cn\rfloor}{n\choose k} $$ for some fixed constant $c$ (say, $0<c<1/2$). What are the asymptotics of $f_c(n)$ as $n\to\infty$? It seems that this should be ...
0
votes
3answers
107 views

Alternating sum with binomial coefficients $\sum_{k=0}^{49}(-1)^k\binom{99}{2k}$

$$\sum_{k=0}^{49}(-1)^k\binom{99}{2k} = ?$$ I've tried expanding the binomial coefficient in its factorial form and can't seem to get to manipulate it in a way that solves the expression. $C_{99}^{...
6
votes
1answer
306 views

Sum of product of binomial coefficients and exponential function: $\sum^{n}_{k=0}2^k{{n+1}\choose k}{{r-n-2}\choose {n-k}}$

I would like to know how to obtain (if it exists) a closed form expression of the sum $$S=\sum^{n}_{k=0}2^k{{n+1}\choose k}{{r-n-2}\choose {n-k}}$$ So far, I have tried to use the method of ...
0
votes
1answer
153 views

Simplifying sum of binomial coefficients $\sum_{j=m+n+1}^{8S+1}{8S+1 \choose j}$ where $S$ is a half-integer

I'd like to simplify the following sum: $$\sum_{j=m+n+1}^{8S+1}{8S+1 \choose j},$$ where $S\in\{1/2,1,3/2,2,5/2,\ldots\}$ and $\ m,n\in\{1,3,5,7,9,\ldots,4S-1\}$. By simplifying I mean ...
2
votes
0answers
401 views

Double sum with binomial coefficients $\sum_{1\le i<j\le m} \sum_{\substack{1\le k,l\le n \\ k+l\le n}}{n\choose k} {n-k\choose l} (j-i-1)^{n-k-l}$

Find a closed form formula for this sum: $$\sum_{1\le i<j\le m} \sum_{\substack{1\le k,l\le n \\ k+l\le n}}{n\choose k} {n-k\choose l} (j-i-1)^{n-k-l}$$ It's quite likely that it can be done ...
1
vote
2answers
91 views

Finding the summation of a product of the particular binomial coefficients: $\sum_{j=0}^{k} \binom{n-j}{p} \binom{m+j}{q}$

How can I simplify the following expression? $$\sum_{j=0}^{k} \binom{n-j}{p} \binom{m+j}{q}$$ where $n,m,p,q,k$ are positive constants such that $n-k \ge p$ and $m \ge q$.
2
votes
1answer
418 views

A Curious Binomial Coefficient Sum: $\sum_{j = 0}^{k} \binom{k}{j} \binom{j + n -\ell + 1}{n}$

Let $k, \ell \leq n$ be non-negative integers. Does the following identity simplify? \begin{align} \sum_{j = 0}^{k} \binom{k}{j} \binom{j + n -\ell + 1}{n} = \binom{n - \ell + 1}{n} \phantom1_{2}\...
47
votes
2answers
4k views

Identity for convolution of central binomial coefficients: $\sum_{k=0}^n \binom{2k}{k}\binom{2(n-k)}{n-k}=2^{2n}$

It's not difficult to show that $$(1-z^2)^{-1/2}=\sum_{n=0}^\infty \binom{2n}{n}2^{-2n}z^{2n}$$ On the other hand, we have $(1-z^2)^{-1}=\sum z^{2n}$. Squaring the first power series and comparing ...
3
votes
0answers
110 views

Simplifying the sum with binomial coefficients: $\sum_{k=0}^n {2k\choose k}{2n-2k\choose n-k}$ [duplicate]

Possible Duplicate: Identity involving binomial coefficients Simplify the sum: $$\sum_{k=0}^n {2k\choose k}{2n-2k\choose n-k}$$ So we can denote $a_n=\sum_{k=0}^n {2k\choose k}{2n-2k\...
5
votes
4answers
644 views

Sum of reciprocals of binomial coefficients: $ \sum\limits_{k=0}^{n-1}\dfrac{1}{\binom{n}{k}(n-k)} $

I'm trying to find a closed solution to the following binomial sum, without success. I would appreciate any assistance towards a solution. $$ \sum\limits_{k=0}^{n-1}\dfrac{1}{\binom{n}{k}(n-k)} $$ ...
3
votes
3answers
114 views

Sum of products of binomial coefficients: $ \sum_{l=0}^{n-j} \binom{M-1+l}{l} \binom{n-M-l}{n-j-l} = \binom{n}{j} $

In a proof I've come across the following identity: $$ \sum_{l=0}^{n-j} \binom{M-1+l}{l} \binom{n-M-l}{n-j-l} = \binom{n}{j} $$ I see that it's right, when plugging in numbers, but I don't see ...
2
votes
3answers
96 views

Combinatorial Identity with Binomial Coefficients: $ {{a+b+c-1}\choose c} = \sum_{i+j=c} {{a+i-1}\choose i}{{b+j-1}\choose j} $

I got the following identity from commutative algebra. I am curious to see elegant elementary methods. $$ {{a+b+c-1}\choose c} = \sum_{i+j=c} {{a+i-1}\choose i}{{b+j-1}\choose j} $$
2
votes
4answers
60 views

Find a binomial coefficient equal to ${n\choose k} + 3 {n\choose k-1} + 3{n \choose k-2} + {n\choose k-3}$

Exercise. Find a binomial coefficient equal to: $${n\choose k} + 3 {n\choose k-1} + 3{n \choose k-2} + {n\choose k-3}.$$ I don't really understand what we are asked to do when we are told to ...
1
vote
2answers
162 views

Proving a combinatorics equality: $\binom{r}{r} + \binom{r+1}{r} + \cdots + \binom{n}{r} = \binom{n+1}{r+1}$

How to prove the following? Should I use induction or something else? Let $n$ and $r$ be positive integers with $n \ge r$. Prove that $$\binom{r}{r} + \binom{r+1}{r} + \cdots + \binom{n}{r} = \...
2
votes
4answers
53 views

Proving binomial coefficients identity: $\binom{r}{r} + \binom{r+1}{r} + \cdots + \binom{n}{r} = \binom{n+1}{r+1}$ [duplicate]

Let $n$ and $r$ be positive integers with $n \ge r$. Prove that: $$\binom{r}{r} + \binom{r+1}{r} + \cdots + \binom{n}{r} = \binom{n+1}{r+1}.$$ Tried proving it by induction but got stuck. Any ...
0
votes
1answer
79 views

Compute the double sum with binomial coefficients: $ \sum_{1\leq i,j\leq n, \ i+j\leq n }\binom{i+j}{i} x^i y^j $

I'm trying to compute the double sum : $$ \sum_{1\leq i, j\leq n, \ i+j\leq n }\binom{i+j}{i} x^i y^j $$ Here $(x,y) \in \mathbb{R}^2$, although it is not mentioned in the source. Note: a typo ...
1
vote
1answer
124 views

Every integer is the unique sum of a “decreasing” sequence of binomial coefficients

I need some advice as I am struggling with the following combinatorics exercise. Let $k$ be a given positive integer. Show that any non-negative integer $N$ can be written uniquely in the form ...
0
votes
3answers
61 views

Why are the coefficients equal in expansions for $(1+x)^{m+n}$ and $(1+x)^m (1+x)^n$?

I don't understand a step of a solution: Let $m,n\in\mathbb{N}$ and $r\in\{1,\dots,m+n\}$ then $$(1+x)^{n+m}=\left(\sum\limits_{i=0}^m \binom{m}{i}x^i\right)\left(\sum\limits_{j=0}^n \binom{n}{j}x^j\...