3
votes
1answer
32 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 ...
1
vote
3answers
84 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 ...
2
votes
1answer
41 views

Simplifying a generating function in two variables with two binomial coefficients

I'm trying to to make the below expression simpler, and it would be great if it could be expressed as something like $(x+y)^k$. $$ \sum_{i=0}^k\binom{n+1}i\binom{m+1}{k-i}x^iy^{k-i} $$ The number ...
1
vote
2answers
41 views

Upper bound on $ \binom{a}{m+1}\sum ^m_{j=0} \binom{a-m-1}{j}/\binom{b}{j+m+1}$

Given $a,b,m$ such that $0<2m<a<b$. I would like to find out upper bound of $$S = \binom{a}{m+1}\sum ^m_{j=0} \frac{\binom{a-m-1}{j}}{\binom{b}{j+m+1}}$$ Anyone can help me please? Thank you ...
0
votes
1answer
21 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$ ...
1
vote
1answer
54 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 ...
0
votes
2answers
60 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<1$ is constant. Thanks a lot.
1
vote
1answer
30 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 ...
1
vote
1answer
41 views

Is there a set of 69 length-6-sets out of 46 numbers [1..46] so that those length-6-sets “cover” all possible 1035 length-2-sets of 46 numbers?

1.) For this question, we have 46 numbers (balls, cards, whatever): {1,2,3,4 .... 45,46} ======================= 2.) Each length-6-set of 46 numbers ( e.g. {1,2,3,4,5,6} or {1,13,16,17,32,46 } ...
4
votes
2answers
64 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 ...
3
votes
1answer
38 views

How to calculate the number of integer solution of a linear equation with constraints?

If an equation is given like this , $$x_1+x_2+...x_i+...x_n = S$$ and for each $x_i$ a constraint $$0\le x_i \le L_i$$ How do we calculate the number of Integer solutions to this problem?
3
votes
1answer
67 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\}$.
3
votes
1answer
48 views

Solving a recurrence (with the form of a convolution) involving binomial coefficients

While dealing with a problem related to intersection of hyperplanes I have come across the following recurrence to obtain the values of $K_{j}$ \begin{array}{cccccccccc} 1 & = & ...
3
votes
2answers
83 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 ...
5
votes
1answer
111 views

Combinations mod $n$ property

So after some "fooling around" I came across this property in Pascal's triangle (which seems to repeat, and makes a lot of sense): $\begin{pmatrix} n \\ k \end{pmatrix} \mod n = \begin{cases} n ...
1
vote
0answers
34 views

A Vandermonde like identity for binomial coefficients

The Vandermonde identity is given by $ \left(\begin{matrix} m + n \\ j \end{matrix}\right) = \displaystyle\sum_{j=0}^k \left(\begin{matrix} m \\ j \end{matrix}\right)\left(\begin{matrix} n \\ k-j ...
1
vote
1answer
133 views

What is the count of the strict partitions of n in k parts not exceeding m?

Lets say we had a $k,m,n \in \mathbb{N}$ where $k < m \le n$. How many different sets $X_1,..,X_m$ with $|X_i|=k$ for $i=1,..,m$, where the sets do not include duplicates, for which the sum of ...
1
vote
0answers
53 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 ...
3
votes
0answers
71 views

Combinatorical interpretation of $\binom{15}{5} = \binom{14}{6}$

I was reading up on Sigmaster's conjecture on repeated binomial coefficiencts and I read that $$\binom{15}{5} = \binom{14}{6}$$ Sure, it's possible to prove it non-combinatorically: ...
2
votes
2answers
52 views

Alternating sum of a simple product of binomial coefficients

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 ...
0
votes
2answers
69 views

Show that $\binom{n}{k}< \binom{n}{k+1}$ if and only if $k < (n-1)/2$ [closed]

Show that $\binom{n}{k} < \binom{n}{k+1}$ if and only if $k < \frac{n-1}{2}$ and then use this to deduce that the maximum of $\binom{n}{k}$ for $k=0,1,\dots,n$ is $\binom{n}{\lfloor ...
1
vote
1answer
16 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) ...
2
votes
1answer
26 views

Binomial thereom to figure out coefficents

Use the binomial theorem to find the coefficient of $x^8y^5$ in $(x + y)^{15}$ My textbook shows how to do this looking at the coefficents of Pascal's triangle but, I know theres another way using ...
5
votes
1answer
81 views

Binomial Congruence

How can we show that $\dbinom{pm}{pn}\equiv\dbinom{m}{n}\pmod {p^3}$ for positive integers m and n and p a prime greater than 5? I can do it for mod p^2 but Im stuck here.
1
vote
0answers
48 views

Is there a sharper bound than exponential for $\sum_{k\ge0}\frac{m!(k+n-m)!}{(k+n)!}\frac{s^k}{k!}$?

I am trying find a bound for an expression and I am getting something not quite as convenient as I hoped. Going through my calculations again I think that the only place I use a non sharp bound is ...
1
vote
0answers
23 views

Equation for those level curves?

Related to this question Let $n\in\mathbb{N}^*,\alpha\in\mathbb{R}$. What would be the equation $y=f(x)$ for the curve defined by $\ln\binom{N-y}{x}=\alpha$ That's how they look : TL;DR : What ...
2
votes
0answers
44 views

${n \choose r}=\frac {n!}{r!(n-r)!}$ without using the permutation approach.

I had an idea that would be to first prove Pascal's Rule, $${n \choose r} = {n-1 \choose r-1} + {n-1 \choose r}$$ which can be proved combinatorically whether one particular element(among the $n$) is ...
2
votes
1answer
76 views

A generalized combinatorial identity for a sum of products of binomial coefficients

I have the following question. For given natural numbers $n$ and $d$, let $a_1,a_2,..., a_r$ be fixed integers such that $a_1+\cdots+a_r=d$. Let $A=\{(i_1,..,i_r)~|~0\le i_j\le n~ \text{and}~ ...
0
votes
0answers
41 views

A sum of powers of binomials

For $n$ and $k$ non-negative integers, let $$F(n,k) = \sum_{i=0}^{n}\binom{n}{i}^k.$$ For example, $F(n,0)=n+1$, $F(n,1)=2^n$ and $F(n,2)=\binom{2n}{n}$. Does there exist a general formula for ...
3
votes
4answers
111 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 ...
2
votes
0answers
30 views

Inequality in matroid theory

Working on a proof in matroid theory I found there is a smooth map from an open set of $(\mathbb{C}^{\ast})^{(d−1)(n−d−1)}$ to a disjoint union of tori $(S^{1})^{\binom{n}{d}-n}.$ As a direct ...
1
vote
0answers
30 views

Number of draws that contain at least $k$ red coins

Assume there are $n$ coins in an urn from which $r$ are read. What is the number of draws of $r$ coins that contain at least $k$ red coins? It is obvious that there are ...
0
votes
2answers
44 views

Coefficient of polynomials

Could someone explain to me why $$ [x^{24}](1-2x^6)^{-31} = 2^4 \binom{4 + 31 - 1}{31 - 1} \, ? $$ Reads: The coefficient of $x^{24}$ in $(1-2x^6)^{-31} =$ ...
0
votes
0answers
63 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?
1
vote
1answer
24 views

Equality of binomial coefficients

I have seen that the following equations are equal, but are wondering how this is shown ${n \choose m} \cdot 1 \cdot 3 \cdots (2m-1)\cdot 1 \cdot 3 \cdots (2n-2m-1) = \frac{n!}{2^n} {2m \choose m} ...
4
votes
1answer
63 views

Extracting a coefficient from a generating function

Background: I am working on an exercise relating to Skolem $k-$subsets with index $k$ in Goulden and Jackson's Combinatorial Enumeration text and they broke it down to finding the coefficient of $x^n$ ...
0
votes
2answers
26 views

Probability of special configuration of ones in a binary string

Consider the sequence $(X_i)_{1 \leq i \leq L}$ of i.i.d. random variables, where $X_1 \in \{0,1\}$ and $P(X_1 =1) = p$. For a $k \in \mathbb{N}$ define the event $A_{k,L}$ as "all ones in the ...
0
votes
0answers
42 views

Behavior of this function involving binomial coeffs

I have the function: $$ f(n,m,\ell)=\binom{n+m}{\ell}-\left(n\binom{m}{\ell-1}+\binom{m}{\ell}+\binom{n}{\ell}\right) $$ It represents the number of possible sets of size $\ell\ge 3$ that can be ...
2
votes
1answer
44 views

Number of nodes with an even number of children in an ordered tree (AKA Plane Planted Tree)

I am looking for verification for my attempt at the solution. I have found that my answer disagrees with an answer I found here: Extract Coefficients From A Function Problem at hand: For a plane ...
1
vote
0answers
40 views

Closed form expression sum-product of binomials

Is it possible to find a closed form expression for $$\sum_{j=1}^a\sum_{i=1}^{b} {i+j-1\choose j} {i+j-1\choose i},$$ where $a \geq 1$, and $b \geq 1$ are integers. I couldn't apply any type of ...
10
votes
1answer
204 views

Prove that $\exp(\log(\frac{1}{1-x})) = \frac{1}{1-x}$

I am trying to prove this directly by comparing the coefficients in the two series rather than using formal calculus. Here is what I have so far, but I think I made a mistake: \begin{align*} ...
3
votes
3answers
47 views

Recurrence relation for product of binomial coefficients

We all know the standard recurrence relation for binomial coefficients: $$ \binom{n}{k-1} + \binom{n}{k} = \binom{n+1}{k} $$ Is there any finite-step recurrence relation one can write down for a ...
1
vote
2answers
51 views
1
vote
3answers
68 views

Why is $\sum\limits_{k=0}^{n}(-1)^k\binom{n}{k}^2=(-1)^{n/2}\binom{n}{n/2}$ if $n$ is even? [duplicate]

Why is $\displaystyle\sum\limits_{k=0}^{n}(-1)^k\binom{n}{k}^2=(-1)^{n/2}\binom{n}{n/2}$ if $n$ is even ? The case if $n$ is odd, is clear, since ...
9
votes
3answers
299 views

Help with combinatorial proof of identity: $\sum_{k=1}^{n} \frac{(-1)^{k+1}}{k} \binom{n}{k} = \sum_{k=1}^{n} \frac{1}{k}$

How to prove this identity? Can someone please give me some insight ? $$\sum_{k=1}^{n} \frac{(-1)^{k+1}}{k} \binom{n}{k} = \sum_{k=1}^{n} \frac{1}{k}$$
8
votes
4answers
209 views

Does $\sum_{k=0}^{k=n} {n \choose k} k!$ have a closed form for integers $k,n$?

While doing research in computer system, I came across the following summation: $$S_n = \sum_{k=0}^{n} {n \choose k} k! = \sum_{k=0}^{n} \frac{n!}{(n-k)!}$$ where both $n$ and $k$ are integers. $S_n$ ...
2
votes
0answers
55 views

Prove the following : [duplicate]

Prove the following : $$ {{n}\choose{7}}-\left \lfloor{\frac{n}{7}}\right \rfloor $$ is divisible by 7.
4
votes
1answer
84 views

An inverse binomial summation.

I am looking for a closed form for this summation: $$ \sum_{j=1}^m\frac{r^{-j}}{j{m\choose j}} = \sum_{j=1}^m\frac{r^{-j}}{m{m-1\choose j-1}} = \frac1{rm} \sum_{k=0}^{m-1}\frac{r^{-k}}{{m-1\choose k}} ...
8
votes
3answers
108 views

Asking About Binomial Sum Related to Fibonacci

How would I prove $$ \sum\limits_{i,j\ge 0} {n-i \choose j} {n-j \choose i}=F_{2n+1} $$ where $n$ is a nonnegative integer and $\{F_n\}_{n\ge 0}$ is a sequence of Fibonacci numbers? Thank you very ...
3
votes
0answers
108 views

Proving $\sum_{k=1}^{n}\binom{n-1}{k-1}{\binom{n+k}{k}}^{-1}=\frac 12$ combinatorially

Question : How can we prove the following equations combinatorially? $$\begin{eqnarray}\sum_{k=1}^{n}\frac{\binom{n-1}{k-1}}{\binom{n+k}{k}}&=&\frac ...