Coefficients involved in the Binomial Theorem. $\binom{n}{k}$ counts the subsets of size $k$ of a set of size $n$.

learn more… | top users | synonyms (1)

20
votes
0answers
717 views

$f(x)=\sum_{t}{x \choose t}{n-x \choose k-t}$ - even or odd?

The following function popped in my research: $$f(x)=\sum_{\array{0\le t\le k \\ t\equiv_p a}}{x \choose t}{n-x \choose k-t}$$ Where: n,k are natural numbers and $k\le n$. t is taken over all ...
12
votes
0answers
95 views

Prove a matrix of binomial coefficients over $\mathbb{F}_p$ satisfies $A^3 = I$.

(This problem is problem $1.16$ in Stanley's Enumerative Combinatorics Vol. 1). Let $p$ be a prime, and let $A$ be the matrix $A = \left[\binom{j+k}{k} \right]_{j,k = 0}^{p-1}$, taken over the ...
10
votes
0answers
146 views

Is the given binomial sum almost everywhere negative as $K\to\infty$?

The binomial sum is as follows: $$\mathcal {L}^K(\theta)= \sum_{i=\lceil{K/2}\rceil}^K \binom{K}{i}\theta^i\left((1-\theta)^{K-i}-\frac{1}{2}(1-\theta)^{-K}(1-2\theta)^{K-i}\right)$$ which can also ...
8
votes
0answers
74 views

Generalizing Bellard's “exotic” formula for $\pi$ to $m=11$

Bellard's "exotic" pi formula has the form, $$a\pi+b = \sum_{n=1}^\infty \dfrac{P(n)}{{\displaystyle \binom{mn}{2n}2^{n-1}}}$$ where $a,b,m$ are integers and he uses $m=7$. However, it seems there ...
8
votes
0answers
160 views

Solution of $\large\binom{x}{n}+\binom{y}{n}=\binom{z}{n}$ with $n\geq 3$

I found this question in an old problem set. There's no hint or solution mentioned. For $n \geq 3$, prove or disprove the existence of $(x,y,z) \in \mathbb N^3, ...
7
votes
0answers
144 views

Characterization of Sequences with Integral Binomial Coefficients

For any sequence of positive integers $\{ a_i \}_{i \ge 1}$ we can define the generalized binomial coefficients $\binom{n}{k}_{a}$ as follows: $$m!_a = a_1 a_2 \cdots a_m, \binom{n}{k}_a = ...
7
votes
0answers
164 views

Calculating $\sum_{y=0}^x \Pr[Y= y] \Pr[Z\leq k-y]^2$ when Y,Z are binomially distributed?

Remark: I recently rewrote this post, hoping to get answers! I am analyzing the following experiment: Pick an $x \in \{0,\ldots,2k\}$ uniformly at random Pick $(2k+1)$-bit bitstring $b_1=(u,v_1)$ ...
6
votes
0answers
545 views

Proof for an identity involving a sum of binomial coefficients

I am moving through a On The Average Height of Planted Plane Trees by Knuth, de Bruijn and Rice, 1972), and I would like to trade a weaker result for simpler mathematical tools, because my skills are ...
6
votes
0answers
194 views

Partial sum over $M$, of ${m+j \choose M} {1-M \choose m+i-M}$?

Is there (likely to be) any formula for $$ \sum_{m' \geq m} {m+j \choose m'} {B - m' \choose m+i-m'} $$ ? I am mainly interested in the case $B=1$ (or a prime power), if that's any ...
5
votes
0answers
231 views

Formula for composition of formal power series with binomial coefficient

Let $f=\sum\limits_{n\geq 0}{f_n x^n}$ and $g=\sum\limits_{n\geq 1}{g_n x^n}$ be formal power series. The $x^n$ coefficient of $f(g)$ is $$ \sum\limits_{\mathbb{i} \in \mathcal{C}_{n}} {f_k ...
5
votes
0answers
102 views

Binomial triplets

Solutions to the equation $$\dbinom{a}{n}+\dbinom{b}{n}=\dbinom{c}{n}$$ I will refer to as 'Binomial triplets of order $n$'. These triplets describe simplicial $n$-polytopic numbers that can be ...
5
votes
0answers
100 views

Why does this sum of binomial coefficient ratios equal 1?

In the course of doing some calculations comparing unrepeatable sets of event trials, I ended up with the following identity. If my reasoning and my math are correct then this ought to be true, and ...
5
votes
0answers
142 views

Some rare binomial identities

Long ago , I once saw a nontrivial appealing binomial type of identity that I never saw again. It was something along the line of $\Sigma$$\binom{a(x)}{b(y)}$= where $a$ and $b$ where polynomials not ...
4
votes
0answers
70 views

On a unique(?) binomial property of $3003$

Given the triangular number, $$T_k = \frac{k(k+1)}{2}$$ and remembering that, $$\binom{n}{m}=\binom{n}{n-m}$$ Excluding $a_0=1$, we then have the six-fold (at least) equalities, $$\begin{aligned} ...
4
votes
0answers
152 views

Generating functions to solve number of integer solution problem

If I have $x_1 + x_2 + x_3 =10$ with $1\leq x_1 \leq 5, \; 2 \leq x_2 \leq 6, \;3 \leq x_3 \leq 9$ I know that I compute $(t^1+\dots + t^5)(t^2 +\dots + t^6)(t^3+\dots +t^9)$ and look at the ...
4
votes
0answers
185 views

How to prove that $\sum_{k=0}^\infty \binom{x}{x-k}\cdot\binom{x}{k-x} = 1$?

How to prove this: $$\sum_{k=0}^\infty \binom{x}{x-k}\cdot\binom{x}{k-x} = 1$$ For all $x\in\mathbb R_{\ge0}$ and with $\binom{x}{r}=\frac{\Gamma(x+1)}{\Gamma(r+1)\cdot\Gamma(x-r+1)}$ It is obviously ...
4
votes
0answers
155 views

Proving an equation involving binomial coefficients

Prove that $$\sum_{q=0}^v \binom{v}{q}\frac{q!}{v^{q+1}} = \sum_{q=0}^{v-1} \binom{v-1}{q} \frac{(q+2)!}{v^{q+2}}$$ Thanks. Below are what I have tried: Approach 1: $$\sum_{q=0}^{v-1} ...
4
votes
0answers
100 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$) ...
4
votes
0answers
139 views

Binomial-like sum involving falling factorials

We know that $\sum_{k=0}^n a^k \frac{n^{\underline k}}{k!} = (1+a)^n$. Is there a known (preferably closed) form for $\sum_{k=0}^n a^k n^{\underline k}$?
4
votes
0answers
80 views

Binomial coefficient sum over top index

I am trying to evaluate a sum over binomial coefficients which is giving me some problems. Specifically I want to calculate: $$\sum_{r=0}^{c-1}\binom{r+n}{n}\frac{1}{c-r}$$ My main thought was to ...
4
votes
0answers
163 views

How to transform series of series into series

I need to prove this equation. $$ \sum_{k=0}^{i-2} \left( e \space α(k+1)\space\frac{(-1)^{i+k+2}}{(i-k-2)!} \right) = \sum_{k=0}^{i-2} \frac{(i-k)^k}{k!} \space e^{i-k} (-1)^k\space where,\space α(i) ...
4
votes
0answers
203 views

Simplifying an expression involving binomial coefficients

Consider $$ \prod_{j=0}^{i-1}\binom{n-2j}{2}\left[1+\sum_{k=0}^{N-1}{\left( \prod_{l=0}^{k} \dfrac{N-l}{M-l}\right)\left(1 + \sum_{m=k+1}^{N-1} \prod_{p=k+1}^m \dfrac{N-p}{M-p}\right)+1}\right] $$ ...
4
votes
0answers
241 views

How fast does $\binom{n}{k}$ grow when $k \le n/2$?

How fast does $\binom{n}{k}$, $n$ fixed, grow when $k \le n/2$? Especially, I'm interested in the growth of the "inverse" of binomial coefficient $B_n(x) := \min \{k:\binom{n}{k} \ge x\}$. EDIT: ...
4
votes
0answers
422 views

p-adic numbers and binomial coefficients

Let $\alpha\in \mathbb{Z}_p$ be an $p$-adic integer and define for $n\in \mathbb{Z}_{\geq 0}$ $${\alpha\choose n} := \frac{\alpha(\alpha-1)\cdot\ldots\cdot(\alpha-n+1)}{n!}.$$ This is again a ...
3
votes
0answers
48 views

An interesting property of binomial coefficients that I couldn't prove

So when I was trying to prove the argument in this link I've come up with something. When you extract the left term from the right term, you get the term under them. What is interesting is that as ...
3
votes
0answers
52 views

Can a certain polynomial have all its coefficients in some basis divisible by a prime $p$?

I fix $n\in\mathbf{N}^{*}$ and $n$ elements $\alpha_1,\ldots,\alpha_n$ in $\mathbf{N}^{*}$. Consider the polynomial $$Q(T)=\prod\limits_{1\leq i \leq n} \prod\limits_{0\leq j \leq \alpha_i -1} ...
3
votes
0answers
159 views

Sum problem involving Factorials

got the following problem to prove for $n \in \mathbb{N}$ and $1 \leq i \leq n$: \begin{equation} \sum_{k=1}^{n-i} \frac{(2n-1-i-2k)! 2^{2k}}{(n-i-k)! (n-k)! 2}=\sum_{k=1}^{n-i} \frac{(2n-1-i-k)! ...
3
votes
0answers
54 views

An inequality concerning non-negative integer matrices with constant row and column sums

I'd appreciate any suggestions for how to prove (or disprove) the inequality described below. Some notation first: for positive integers $k$ and $M$, let ${\mathcal D}_{k,M}$ denote the set of all $k ...
3
votes
0answers
83 views

Consecutive numbers in rows of Pascal's triangle …

The fourteenth row of Pascal's triangle has an interesting property. $$\begin{align} \binom{14}{4}+\binom{14}{5} &= 1001+2002 \\ =\binom{14}{6} &= 3003 \end{align}$$ This begs the ...
3
votes
0answers
71 views

Asymptotics of integer compositions

A (weak) composition of a positive integer $n$ into $k$ parts is an ordered sequence of nonnegative integers $(a_1, a_2, \ldots, a_k)$ such that $ \sum_{i=1}^k a_i = n $. I am interested in the case ...
3
votes
0answers
225 views

Prime factors of binomials

Is it true that for each $n\geq 2$ there are two primes $p, q$ such that (at least) one of them divides $\binom{n}{k}$ for each $1\leq k\leq n-1$? Examples: For $n=6: \binom{6}{1}=6; ...
3
votes
0answers
60 views

Lucas' Theorem for $p$-adic integers?

Does Lucas' Theorem hold for $p$-adic integers? More specifically, does it specifically hold for the case that, given a $p$-adic integer: $$x = x_0 + x_1p + x_2p^2 + \cdots = \sum_{i=0}^\infty ...
3
votes
0answers
89 views

What's so special about binomial coefficients that someone decided to organize them in a triangle?

I know that binomial coefficients are related to figurate numbers (which were studied by Greeks a loooong time ago, because of its connections to geometry). I also understand how the Pascal's triangle ...
3
votes
0answers
166 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
91 views

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

I was reading up on Singmaster'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: ...
3
votes
0answers
153 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 ...
3
votes
0answers
51 views

How to show that $\sum\limits_{k=0}^{\lfloor0.999n\rfloor}\binom{2n}{k} < \binom{2n}{n} $ holds for large n

It seems logical to me since $\binom{2n}{n}$ is in the middle of the row in pascal triangle; therefore, the largest, and for large n the sum adds only the small ones on the left. But I do not have any ...
3
votes
0answers
367 views

How to calculate this triple summation?

I need to calculate the following summation: $$\sum_{j=1}^m\sum_{i=j}^m\sum_{k=j}^m\frac{{m\choose i}{{m-j}\choose{k-j}}}{k\choose j}r^{k-j+i}$$ I do not know if it is a well-known summation or not. ...
3
votes
0answers
49 views

Showing that a number is part of sequence A000275 in OEIS

Consider the sequence of integers defined recursively by $c_0 = 1$ and $$ c_p = \sum_{l = 0}^{p-1} (-1)^{p+l+1} \binom{p}{l}^2 c_l $$ for $p \geq 1$. This is sequence A000275 in the online ...
3
votes
0answers
220 views

Proving identity involving sum

I'm stuck trying to prove the following identity: $$\displaystyle\sum_{i=j}^k\frac{(-1)^{i+j}{k+1 \choose i}{i \choose j}(4S-i-k-3)!(4S-2i-1)}{(4S-i-j-1)!} $$ $$=\frac{(-1)^{j+k}(4S-2k-3)!{k+1 ...
3
votes
0answers
172 views

Prove: $\frac{(2px)!}{((px)!)^2}\equiv\frac{(2x)!}{((x)!)^2}\pmod{p^2}$

How can I prove the following, where $p$ is a prime and $x$ a positive integer? $$\dfrac{(2px)!}{((px)!)^2}\equiv\dfrac{(2x)!}{((x)!)^2}\pmod{p^2}$$ I'm not sure if it is actually true, but I tested ...
3
votes
0answers
256 views

Sums of rows in the Pascal triangle

Assume for simplicity that when $k>n$ we have ${n\choose k}=0$. It is well-known that $\sum_k {n\choose 2k}=\sum_k {n\choose 2k+1}=2^{n-1}$ , i.e. the sum of the odd places in each row in Pascal's ...
3
votes
0answers
197 views

Is this formula for $\zeta(15)$ true?

Apery gave, $\begin{aligned} \zeta(3) &= \frac{5}{2}\,\sum_{k=1}^\infty \frac{(-1)^{k+1}}{k^3\,\binom {2k}k}\end{aligned}$ J. Borwein and D. Bradley found this can be generalized to ...
3
votes
0answers
95 views

max number of times integer $>1$ appears in pascals triangle

$120, 210 ,3003$ appear $6$ times in Pascal's triangle. $120={10\choose3}={16\choose2}={120\choose1}\\$ $210={10\choose4}={21\choose2}={210\choose1}\\$ ...
3
votes
0answers
370 views

Sylvester's Theorem and Schur Theorem

I'll probably end up asking more programming questions on StackExchange forums than math questions, but I'll lead off with a math question. In my Number Theory class this past semester, I worked on a ...
3
votes
0answers
136 views

Defining a signed involution

We define the displacement of $\pi$ as $\mathrm{disp}(\pi)=\sum_{i=1}^n|\pi(i)-i|$. I know that it's even. Could you help me to find a good signed involution of the set of permutation with ...
3
votes
0answers
338 views

Solving a certain binomial sum involving the floor function

Does anybody know of any techniques to solve the following sum (or a fast way (polynomial in N) to compute it): $$\sum_{i=0}^{N} \binom{N-i}{A} \cdot \binom{\lfloor iP/Q \rfloor + 1}{B}$$ where $P$ ...
2
votes
0answers
46 views

Finding a closed form for this summation

I have been trying to derive a few identities using some bell polynomials and a technique i have come up with and i came across this summation: $$ \rho(n,k) = \sum_{j=0}^k {k \choose j} {\frac{-j}{2} ...
2
votes
0answers
18 views

Finding the Value of Ties

THE CHALLENGE If "Winning all the time = 1" "Losing all the time = -1" "Tie all the time = 0" What value would "Winning HALF the time" be? Is there an error in my original variables that would help ...
2
votes
0answers
53 views

Birthday problem, I'm confused by this formula

I've given the following statement (n is given, and equals 100) : Now, I'm quite confused by the second binomial coefficient: how can that represent the days for the birthdays of the remaining 98 ...