# Tagged Questions

1answer
44 views

### Prove $\sum_{i=0}^{i=x} {x \choose i} {y+i \choose x}+\sum_{i=0}^{i=x} {x \choose i} {y+1+i \choose x}$

How to prove that $$\sum_{i=0}^{i=x} {x \choose i} {y+i \choose x}+\sum_{i=0}^{i=x} {x \choose i} {y+1+i \choose x}=\sum_{i=0}^{i=x+1} {x+1 \choose i} {y+i \choose x}$$ ? I tried to break the right ...
2answers
85 views

### Sums of binomial coefficients

Does anyone know something about the following sums? $$S_m(n)=\sum\limits_{k=o}^n(-1)^k{mn\choose mk}$$ Notice that $S_m(n)=0$ for odd $n$, so we only consider $S_m(2n)$. It holds that $S_0(2n)=1$, ...
1answer
22 views

### In how many ways can you paint 90 distinct buckets?

In how many ways can you paint 90 distinct buckets, if 25 of them must be painted red, 40 of them must be painted blue, and 25 of them must be painted green? I am right to assume that these object ...
1answer
29 views

### Giving a closed expression to $\sum_{i=0}^b (-1)^{b-i} \binom{b}{i}\frac{1}{a+b-i}$

I want to prove $\sum_{i=0}^b (-1)^{b-i} \binom{b}{i}\frac{1}{a+b-i} = \frac{(a-1)! b!}{(a+b)!}$ yet I feel like I don't know how to even approach this problem. Any hints are welcome.
5answers
112 views

1answer
41 views

3answers
101 views

### Evaluate the sum

I need to evaluate the following sum, which depends on $n \in \mathbb N$ (call it $S(n)$ if you will) $$\sum_{i=0}^{n} (-1)^{n-i} \binom{n}{i} f(i)$$ where $f$ defined over $\mathbb N$ is ...
4answers
63 views

### Exotic proofs of $\sum_{j=0}^{n-1}\binom{p+j}{p}=\binom{p+n}{p+1}$

Let $p,n$ be positive integers. The following identity $\displaystyle \sum_{j=0}^{n-1}\binom{p+j}{p}=\binom{p+n}{p+1}$ may be proved by induction or by successive uses of Pascal's rule (both ...
5answers
117 views

### Computing $\sum_{i=0}^{\infty}\frac{i}{2^{i+1}}$

I came across this while trying to solve Google's boys & girls problem, and although I know now it's not the right approach to take, I'm still interested in summing ...
2answers
75 views

### Alternating sum of binomial coefficients is equal to zero [duplicate]

Prove without using induction that the following formula:$$\sum_{k=0}^n (-1)^k\binom{n}{k}=0$$ is valid for every $n\ge1$. Progress For each odd $n$ we can use the ...
1answer
35 views

3answers
144 views

I have some question about the paper of which name is Spanning trees: Let me count the ways. The question concerns about $\sum_{k=0}^{\lfloor\frac{n-1}{2} \rfloor} (-1)^{k} {n \choose k} {2n-2k ... 2answers 69 views ### Why does this sum equal to (4^n -1) How do I get to this solution?$\sum _{k=1}^n\left(\binom nk 3^{n-k}\right)=\left(4^n-1\right)$I believe it's connected to this, which I know is true:$\sum \:_{k=1}^n\binom nk=2^n-1$3answers 120 views ### How to count the$r$-tuples of subsets of$\{1,\dots,n\}$that are cyclically disjoint? I want to count the following, $$\#\{S_1,S_2,\dots, S_r\subseteq[n]\;|\; S_i\cap S_{i+1}=\emptyset \text{ for } 1\leq i\leq r-1 \mbox{ and } S_1\cap S_r=\emptyset\}=A_{n,r},$$ Then$A_{n,1}=2^n$, ... 1answer 69 views ### Multiple sum involving binomial factors Let$n$and$m$be positive integers and let$0 \le j \le n-m-1. Show that: \begin{align} \sum\limits_{l=m}^{n-j-1} \binom{n-l-1}{j} \binom{l}{m} \binom{n+l}{j} &=\sum\limits_{p=0}^j ... 1answer 77 views ### A double sum with combinatorial factors Letn$,$p$and$j$be integers. As a byproduct of some other calculations I have discovered the following identity: \sum\limits_{p=0}^{j} \sum\limits_{p_1=0}^j \binom{p+p_1}{p_1} ... 1answer 38 views ### How to simplify a sum with binomial coefficients multiplied by$k^3/2^k$? The sum is $$\sum_{k=5}^{\infty}\binom{k-1}{k-5}\frac{k^3}{2^{k}}$$ The first thing I thought of was the binomial coefficient. So I re-indexed it ... 3answers 92 views ### Simplifying$\displaystyle\sum_{k=0}^{20}(k+4)\binom{23-k}{3}$In trying to simplify my answer to a problem posted recently, I am trying to show that$\displaystyle\sum_{k=0}^{20}(k+4)\binom{23-k}{3}=8\binom{24}{4}$. I know that ... 1answer 29 views ### Probability$\sum_{j=n+1}^{2n+1} {M \choose m+1}{M-m-1 \choose j-m-1}/{N \choose j} $I have a prob. problem: A school has$N$students in which$M$students are leader (of each class in school), and$N>M$. There are$2n+1$balls in the black box including$n+1$blue balls and$n$... 1answer 57 views ### An upper bound and simplification for expression I would like to find the upper bound (or simplification) of this expression: $$\sum_{j=1}^{n+1}\sum_{i=0}^{j-1} a^{j+i} {j+i \choose i}{n+1\choose j}{n \choose i}/{2n+1 \choose j+i}$$ where ... 2answers 64 views ### Simplify the expression of binom Any one knows how to simplify this expression or finding upper bound of this expression: $$\sum_{j=1}^{n+1}\sum_{i=0}^{j-1} a^{j+i} {j+i \choose i}$$ where$0<a<1is constant. Thanks a lot. 0answers 27 views ### Simplifying a combinatorial sum Show that \begin{align} y\sum\limits_{i=1}^dx^iz^i\sum\limits_{j=1}^iq^{i-j}G_d(x,y,q\mid j) = y\sum\limits_{i=1}^d(x^iz^i+\cdots+x^dz^dq^{d-i})G_d(x,y,q\mid i) \end{align} where \begin{align} ... 1answer 33 views ### Extracting the coefficient ofx^n$from a fraction I need help extracting the coefficient of$x^n$from a$\frac{1-x}{1-2x}. So far I have that \begin{align} \frac{1-x}{1-2x} &= \frac{1}{1-2x} - x\frac{1}{1-2x}\\ &= \sum\limits_{k=0}(2x)^k ... 1answer 32 views ### Upper bound of\sum\limits_{j=1}^{n+1} \sum\limits_{i=0}^{j-1}{n+1 \choose j}{n \choose i}$I would like to find max (or sup.) of the sum: $$S=\sum\limits_{j=1}^{n+1} \sum\limits_{i=0}^{j-1}{n+1 \choose j}{n \choose i}.$$ I found$S\le \frac{1}{\sqrt{\pi n}}.2(n+1).4^n$but It seems it's ... 3answers 88 views ### Ordered partitions of an integer (with a twist) I would like to know how to prove (preferably algebraically) that$P_1(2,n)=F_{2n+1}$, where$P_1(2,n)$is what I define to be the number of ordered partitions of an integer, where the number$1$has ... 1answer 40 views ### Sum of nth powers and generalized polynomial sum So this is a 2-part question (both parts I believe are closely related): How exactly does on express the sum $$\sum_{i=0}^{k}{i^n} = Q(n,k)$$ in a closed form For arbitrary positive integers ... 1answer 73 views ### Upper bound of$S=\sum_{k=1}^{P}k!\binom{P}{k}\binom{Q}{k}$EDIT: How can I find a good upper bound to this quantity ? $$S_{n,m}=\sum_{k=1}^{P}k!\binom{P}{k}\binom{Q}{k}$$ where$P=\min\{m,n\}$et$Q=\max\{m,n\}$. 1answer 45 views ### How to calculate the sum of combinatorial numbers For my work on an almost completely unrelated field I came across the following formula. I know that I have learned that all in high school. But since this is more than 15 years ago in which I never ... 6answers 220 views ### Finding$\binom{n}{0} + \binom{n}{3} + \binom{n}{6} + \ldots $Help me to simplify:$$\binom{n}{0} + \binom{n}{3} + \binom{n}{6} + \ldots$$ I got a hunch that it will depend on whether$n$is a multiple of$6$and equals to$\frac{2^n+2}{3}$when$n$is a ... 2answers 90 views ### Prove by induction that$A_k = \sum\limits_{n=2k}^{3k}\binom{3k}{n}\cdot{(\frac{60}{100})}^n\cdot{(\frac{40}{100})}^{3k-n}$is decreasing I want to prove that the following sequence is monotonously decreasing:$A_k = \sum\limits_{n=2k}^{3k}\binom{3k}{n}\cdot{(\frac{60}{100})}^n\cdot{(\frac{40}{100})}^{3k-n}$I think it should be ... 0answers 59 views ### Showing that two sums are equivalent given \begin{gather} U_d(x,y,q\mid i_1,\ldots,i_k)=\sum\limits_{n,m\geq0}x^ny^m\sum\limits_{\sigma = i_1\ldots i_k\sigma_{k+1}\ldots\sigma_m\in C_{[d]}(n,m)}q^{v(\sigma)}. \end{gather} show ... 0answers 42 views ### The sum of palindromes from 100 to 900 I'm working with palindromes from$100-999$. I'm having trouble with the step highlighted in red. Can someone explain the algebra to me? Taken from: Discrete and Combinatorial Mathematics: An ... 1answer 35 views ### What is Vandermonde's formula with multisets? I need Vandermonde's formula in multi-set form. I modified the original formula but I get a mess with too many letters everywhere, is there a nice representation? Here's the original: $$... 0answers 73 views ### Sum of product of binomial coefficients and exponential function 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 ... 1answer 100 views ### Big Mathematics Challenge on Set and Summation? [closed] please be aware that this is not homework. it's past PHD entrance Exam on 2011. Suppose:$$B=\{(A_1,A_2,A_3) \mid \forall i; 1\le i \le 3; A_i \subseteq \{1,\ldots,20\}\}$$if we have: ... 2answers 31 views ### Find value of n with given conditions The 4-digit positive number n's digit sum is 20. The sum of the first two digits is 11, the sum of the first and the last digit as well. The first digit is the last digit +3. What is the ... 2answers 98 views ### How to evaluate the sum \sum_{k = 0}^{n}2^k {{n}\choose {k}} [duplicate] How do I evaluate the sum:$$\sum_{k = 0}^{n}2^k {{n}\choose {k}}$$I know that 2^k = {n \choose 0} + {n \choose 1} + {n \choose 2} + {n \choose 3}... {n \choose k}, but I don't know how to proceed ... 1answer 27 views ### Proving an identity involving binomial coefficients and fractions I've been trying to prove the following formula (for n > 1 natural, a, b non-zero reals), but I don't know where to start.$$\sum_{j=1}^n \binom{n-1}{j-1} \left( \frac{a-j+1}{b-n+1} \right) ... 4answers 130 views ### Proving Combinatorical Summation:$n!=\sum_{k=0}^n(-1)^k\binom{n}{k}(n-k)^n$[duplicate] been stuck with this question for the last few hours, any help would be appreciated. $${\large n! = \sum_{k = 0}^{n}\left(-1\right)^{k}{\,n\, \choose \,k\,} \left(\,n - k\,\right)^{n}}$$ what I ... 3answers 36 views ### Sum of combination equilvalence Could someone explain to me why the identity $$\sum_{i=0}^n\binom{i+k-1}{k-1}=\binom{n+k}{k}$$ holds? 0answers 64 views ### What's the interpretation of$\sum_{i,j} i \cdot j \cdot \binom{2n}{i}\cdot \binom{2n}{j} \cdot \binom{2n}{3n-i-j}\$?

I'm having problems with finding the combinatorial interpretation of this sum: $$\sum_{i,j} i \cdot j \cdot \binom{2n}{i}\cdot \binom{2n}{j} \cdot \binom{2n}{3n-i-j}$$ Can anyone help, please?