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)

5
votes
4answers
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)} $$ ...
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
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 ...
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
260 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
355 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 [on hold]

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
758 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
323 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
402 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
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 ...
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
919 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
37 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
127 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 ...
0
votes
0answers
16 views

Number of multinomial terms whose exponents are not divisible by a given divisor I

I have a sum $\sum_{i_{1}+i_{2}+...+i_{k}=n}p_{1}^{i_{1}}p_{2}^{i_{2}}...p_{k}^{i_{k}}$ wherein all the $p_{i}$ are different. That means the vectors $[i_{1},i_{2},...,i_{k}]$ are the weak ...
2
votes
1answer
148 views

Whitney numbers of the Divisor Lattice

I'm computing Whitney numbers of the Divisor lattice of an integer $n = \prod_{p \mid n} p^{\text{ord}_{p}(n)} = p_1^{n_1} \cdots p_{q}^{n_{q}}$ using the formula quoted in Erdos and Szekely's "...
3
votes
3answers
111 views

The greatest common divisor of multiple numbers

What is the cardinality of the following set $\{{\bf x}=(x_1,\ldots,x_d): \text{each } x_i\in \{ 1,\dots,n \},\text{ and } \gcd({\bf x})=1\}$, where $\gcd({\bf x})$ is the greatest common divisor of ...
3
votes
0answers
39 views

Counting couples of square-free polynomials over finite fields

I have a curve defined by the following equations over the finite field $\mathbb{F}_q$ with $q=p^r$ with $p \geq 3$: $$C_{h_1,h_2}:\begin{cases} y_1^2=h_1(t) & \\ y_2^2=h_2(t) &...
2
votes
1answer
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 ...
3
votes
1answer
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 ...
11
votes
1answer
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$. ...
2
votes
1answer
49 views

combinatorics to partition set in two subsets of equal product [closed]

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.
1
vote
1answer
25 views

Calculating intersection cardinalities of cover sets

I'm having trouble automating calculation of intersection cardinalities of particular sets. Here are some definitions. Number of available elements is $n$, size of a particular set $S \in \...
0
votes
3answers
65 views

Find the number of sums that you will get A, when A=100?

Problem: Take any number $A \in \Bbb{N} = \{1, 2, 3, \dots\}$, and then take $x, y \in \Bbb{N}$, where $x \ne y$ and $x + y = A$. Find the number of possible choices for $x$ and $y$ when $A=100$. ...
37
votes
6answers
810 views

You have to estimate $\binom{63}{19}$ in $2$ minutes to save your life.

This is from the lecture notes in this course of discrete mathematics I am following. The professor is writing about how fast binomial coefficients grow. So, suppose you had 2 minutes to save ...
1
vote
2answers
48 views

Problem 14, Ch. 1 from Blitzstein and Hwang, Intro to Probability

You are ordering two pizzas. A pizza can be small, medium, large or extra large, with any combination of 8 possible toppings (getting no toppings is also allowed, as is getting all of 8). How many ...
8
votes
5answers
342 views

Proving $\sum_{m=0}^M \binom{m+k}{k} = \binom{k+M+1}{k+1}$

Prove that $$\sum_{m=0}^M \binom{m+k}{k} = \binom{k+M+1}{k+1}$$ by computing the coefficient of $z^M$ in the identity $$(1 + z + z^2 + \cdots ) \cdot \frac{1}{(1-z)^{k+1}} = \frac1{(1-z)^{k+2}}.$$ I ...
0
votes
0answers
26 views

Problem 13, Ch1 from Blitzstein and Hwan, Intro to Probability

A certain casino uses 10 standard decks of cards mixed together into one big deck, which we will call a superdeck. Thus, a superdeck has $52{\cdot}10=520$ cards, with 10 copies of each card. How many ...
14
votes
2answers
218 views

“Binomiable” numbers

Is there a nice criterion to determine whether a given natural $m$ can be written as a binomial number $\binom{n}{k}$ with $1 < k < n-1$? I've been thinking on this problem with a friend and ...
-4
votes
2answers
52 views

b) How many onto functions are there from A to C? [duplicate]

Let $A=\{1,2,3,4\}$ Let $B= \{a,b\}$ Let $C= \{ \text{hiking, baseball, hockey} \}$ a) How many onto functions from A to B $(1,a) (1,b) (2,a) (2,b) (3,a) (3,b) (4,a) (4,b)$ Thus 8. b) How many ...