For questions about the study of finite or countable discrete structures, specifically how to count or enumerate elements in a set (perhaps of all possibilities) or any subset. It includes questions on permutations, combinations, bijective proofs, and generating functions.

learn more… | top users | synonyms (4)

2
votes
1answer
439 views

number of lattice points in an n-ball

I have faced a problem in my work and I will appreciate any hint/reference as I am not much into the lattice problems. Assume an n-dimensional lattice $\Lambda_n$ with generator matrix $G$. Note that ...
5
votes
2answers
444 views

Counting Lattice Points with Ehrhart Polynomials

Let $\bar{\mathcal{P}}$ denote the closed, convex polytope with vertices at the origin and the positive rational points $(b_{1}, \dots, 0), \dots, (0, \dots, b_{n})$. Define the Ehrhart quasi-...
0
votes
2answers
441 views

Counting lattice points interior to a polygon

If I define an integer lattice $\Lambda \subseteq \mathbb{Z}^2$ with a basis given by $$\omega_{1} = a \hat{i} + b\hat{j}, \;\;\; \omega_{2} = -b \hat{i} + a\hat{j}$$ How can I count how many lattice ...
2
votes
2answers
48 views

Find least number of radial-subgraph of a graph

Background: Here is a group G of a people, one maybe another's friend. How to select least number of people to be a leader of a subgroup, so that everyone in the group G has a friend as a leader? ...
0
votes
2answers
57 views

In AB + BC + AC = N, how can I find all possibilities for A, B and C in less than n³ computational time?

The problem is the one on the title. Given a N, find all possibilies for A, B and C that make this true: $AB+BC+AC = N$when $A \ge B \ge C$. This code in C do the job: ...
1
vote
4answers
50 views

Bayesian probability problem?

Problem: In a city there are three types of taxis which drive towards the airport. 30% are blue, 20% green, 50% yellow. They take there customers too late with probabilities 0.1,0.2,0.3 respectively. ...
0
votes
3answers
36 views

Prove that if a collection of subsets of {1,..,n} that each pair of subsets has at least one element in common, there are at most $2^{n-1}$ subsets

Full question: Prove that if a collection of subsets of {1,2,...,n} has the property that each pair of subsets has at least one element in common, then there are at most $2^{n-1}$ subsets in the ...
5
votes
5answers
122 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
2answers
467 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 ...
5
votes
4answers
325 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 ...
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
646 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
4answers
47 views

Prove the identity $\sum_{r=0}^n r^2 \binom {n}{r} p^r q^{n-r}=npq+n^2p^2$ when $p+q = 1$

If $p+q=1$, then show that $$\sum_{r=0}^n r^2 \binom {n}{r} p^r q^{n-r}=npq+n^2p^2.$$ I was able to solve this by differentiating the expression twice and then relating the given variables. But the ...
3
votes
3answers
115 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 ...
6
votes
1answer
81 views

Sequences where each number is a divisor of one less than the next

Let $N,k$ be fixed. Call a sequence of positive integers $a_1,a_2,\dots,a_k$ good if for each $i$, $a_i$ is a divisor of $a_{i-1}-1$. Consider the set $$S = \{x : \text{$x$ occurs in some good ...
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\...
0
votes
0answers
67 views

How to evaluate the sum of binomial coefficients $\sum_{k=m}^n {k\choose m}^2$?

I know the following identity according to wiki (the one before eq (9)) $$\sum_{k=m}^n {k\choose m}={n+1\choose m+1}$$ Is there an identity for the following sum? $$\sum_{k=m}^n {k\choose m}^2$$ ...
3
votes
2answers
262 views

Alternating sum of a simple product of binomial coefficients: $\sum_{k=0}^{m} (-1)^k \binom m k \binom n k .$

I would like to evaluate the following alternating sum of products of binomial coefficients: $$\sum_{k=0}^{m} (-1)^k \binom m k \binom n k .$$ I had the idea to use Pascal recursion to re-express $\...
3
votes
4answers
4k views

Vandermonde's Identity: $\sum_{k=0}^{n}\binom{R}{k}\binom{M}{n-k}=\binom{R+M}{n}$

How can we prove that $$\sum_{k=0}^{n}\binom{R}{k}\binom{M}{n-k}=\binom{R+M}{n}?$$ (Presumptive) Source: Theoretical Exercise 8, Ch 1, A First Course in Probability, 8th ed by Sheldon Ross.
3
votes
1answer
203 views

Combinatorial Proof of a Binomial Identity $\sum_k {m\choose k} {n \choose k} = {m+n \choose n}$

$$\sum_k {m\choose k} {n \choose k} = {m+n \choose n}$$ In this identity we seem to be choosing subsets that do $\it not$ contain k of type m and type n for all possible k. In the style of ...
1
vote
1answer
356 views

Combinatorial Proof of Sum of Binomial Coefficients $\sum_{m=k}^{n-k}\binom{m}k\binom{n-m}k=\binom{n+1}{2k+1}$ [duplicate]

I was curious if anyone might be able to give me a hint as to how one might show the following identity combinatorially: $$\sum_{m=k}^{n-k}\binom{m}k\binom{n-m}k=\binom{n+1}{2k+1}$$ For the left ...
1
vote
1answer
195 views

Use double counting to show the identity $\binom{2n}{2} = 2\binom{n}{2} + n^2$

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$: $$\binom{2n}{2} = 2\binom{n}{2} + n^2$$ Show that ...
7
votes
1answer
177 views

How many binomial coefficients are equal to a specific integer ($\binom{n}{r} = 2013$ or $\binom{n}{r} = 2014$)?

Find the number of ordered pairs $(n,r)$ which satisfy $\binom{n}{r} = 2013$. Find the number of ordered pairs $(n,r)$ which satisfy $\binom{n}{r} = 2014$. My Attempt for $(1)$: By simple ...
0
votes
1answer
36 views

Least distance between two points in an equilateral triangle [closed]

Five points lie inside an equilateral triangle of side 2 units.Prove that at least 2 points are no more than a unit distance apart.
3
votes
2answers
1k views

A sum of a product of binomial coefficients: $\sum^{n}_{i=0}{(-1)^{i}\binom{n}{ i}\binom{n +m - i}{j-i}}$

I am supposed to manipulate the equation $\sum^{n}_{i=0}{(-1)^{i}\binom{n}{ i}\binom{n +m - i}{j-i}}$, where n,m,j are natural numbers and $n \leq j \leq n+m$ into something without a sum. The only ...
4
votes
2answers
760 views

Sum of product of binomial coefficients: $\sum_{k=0}^{n}(-1)^k\binom{n}{k}\binom{n + k}{k} = (-1)^n$

Based on the binomial expansion of $(1+x)^n$, show that: $$\sum_{k=0}^{n}(-1)^k\binom{n}{k}\binom{n + k}{k} = (-1)^n.$$ This is a question from a very old high school exam paper I came across. ...
0
votes
1answer
231 views

Evaluating a sum with binomial coefficients: $\sum_{k=1}^n {n \choose k} \frac{1}{k^r} a^k b^{n-k}$

I have come across the following sum evoking the binomial theorem: $$\sum_{k=1}^n {n \choose k} \frac{1}{k^r} a^k b^{n-k},$$ where $r > 0$ is a positive real constant and $a,b \in \mathbb{R}$ are ...
5
votes
3answers
729 views

A Binomial Coefficient Sum: $\sum_{m = 0}^{n} (-1)^{n-m} \binom{n}{m} \binom{m-1}{l}$

In my work on $f$-vectors in polytopes, I ran across an interesting sum which has resisted all attempts of algebraic simplification. Does the following binomial coefficient sum simplify? \begin{align} ...
3
votes
4answers
324 views

Computing a sum of binomial coefficients: $\sum_{i=0}^m \binom{N-i}{m-i}$

Does anyone know a better expression than the current one for this sum? $$ \sum_{i=0}^m \binom{N-i}{m-i}, \quad 0 \le m \le N. $$ It would help me compute a lot of things and make equations a ...
3
votes
3answers
403 views

Closed form for a sum involving binomial coefficient $\sum_{j=0}^n \binom{n}{j} \frac1{j+1} = \frac{2^{n+1}-1}{n+1}$ [duplicate]

Possible Duplicate: How can I compute $\sum\limits_{k = 1}^n \frac{1} {k + 1}\binom{n}{k} $? How to derive the following equality? $$\sum_{j=0}^n \binom{n}{j} \frac1{j+1} = \frac{2^{n+1}-1}{n+...
5
votes
2answers
868 views

How can I compute $\sum\limits_{k = 1}^n \frac{1} {k + 1}\binom{n}{k} $?

This sum is difficult. How can I compute it, without using calculus? $$\sum_{k = 1}^n \frac1{k + 1}\binom{n}{k}$$ If someone can explain some technique to do it, I'd appreciate it. Or advice ...
3
votes
2answers
881 views

How to show $\sum_{n=0}^m \frac{1}{n+1}\binom{m}{n} = \frac{2^m-1}{m+1}$

This is the homework, and it shouldn't be difficult, but I can't find the proper identity that would help me simplify this sum: $$\sum_{n=0}^m \frac{1}{n+1}\binom{m}{n}$$ Through calculating the ...
0
votes
1answer
161 views

What value of $m$ maximizes $\sum_{i=0}^{n}\binom{10}{i}.\binom{20}{m-i}?$

Using combinatorial methods, how can I solve the following problems? What value of $m$ maximizes: $$\sum_{i=0}^{n}\binom{10}{i}.\binom{20}{m-i}?$$ What is the value of the sum: $$\binom{30}{0}...
2
votes
1answer
642 views

Solving equations in binomial coefficients like $\binom {16}{x+1}+\binom {16}{x+2}=50 $

I'm trying to solve equations that have binomial coefficients (or combinations) inside. Like this one: $$\binom {16}{x+1}+\binom {16}{x+2}=50 $$ I need to LEARN how to do them. I googled but I can't ...
4
votes
5answers
146 views

Evaluate an increasing sum of binomial coefficients: $\sum_{k=1}^nk\binom{m+k}{m+1}$

I've been working on a problem and got to a point where I need the closed form of $$\sum_{k=1}^nk\binom{m+k}{m+1}.$$ I wasn't making any headway so I figured I would see what Wolfram Alpha ...
19
votes
5answers
922 views

A strange combinatorial identity: $\sum\limits_{j=1}^k(-1)^{k-j}j^k\binom{k}{j}=k!$ [duplicate]

In reading about A polarization identity for multilinear maps by Erik G F Thomas, I am led to prove the following combinatorial identity, which I cannot find anywhere, nor do I have any idea how to ...
3
votes
1answer
32 views

How to find number of integral solutions, containing large number of cases?

Number of positive unequal integral solutions of the equation $x+y+z=12$ can be found out knowing the cases it involves: $(1, 2, 9) , (1,3,8), (1,4,7), (1,5,6), (2,3,7), (2,4,6) and (3,4,5)$. Thus, ...
0
votes
1answer
38 views

Picking balls from boxes, a logical approach?

You have a box with ten purple balls, five red balls, five blue balls, three yellow balls. You pick out four balls at random. What is the probability of all four balls being the same color? I've ...
0
votes
1answer
128 views

Counting Game Question, 2 players

Players A and B play the following game. Two integers, m and n, are written on the board. On each turn, a player selects one of the numbers on the board, erases it, and writes down a positive divisor ...