# Tagged Questions

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.

643 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)}$$ ...
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 ...
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 ...
81 views

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 ...
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 ...
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 ...
61 views

865 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 ...
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 ...
161 views

96 views

### Counting the number of partitions

Let $P$ be a set of $7$ different prime numbers and $C$ a set of $28$ different composite numbers each of which is a product of two (not necessarily different) numbers from $P$. The set $C$ is divided ...
150 views

### Mathematical Results from Counting Points in Lattices

I'm preparing a talk on lattice point enumeration in polytopes (Ehrhart-Macdonald Theory), and I'd like to have an introduction with a few motivational problems/results which arise from the ...
317 views

### Maximum integer not in $\{ ax+by : \gcd(a,b) = 1 \land a,b \ge 0 \}$

Ryan asked about a variation of the coin problem, which was whether for any coprime natural numbers $x,y$ every sufficiently large natural number is $ax+by$ for some coprime natural numbers $a,b$. ...
Find all such positive integers n that the set $(n,n+1,n+2,n+3,n+4,n+5)$ can be partitioned into two subsets such that product of the two subsets is equal.