Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange
Join us in building a kind, collaborative learning community via our updated Code of Conduct.

Questions tagged [binomial-coefficients]

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

0
votes
0answers
12 views

Given G groups, and X samples per group. Probability of selecting N groups?

We are given a collection of samples (of size $G*X$) that are partitioned in $G$ groups. Each group has $X$ samples. For example, for $G = 3$, $X = 2$ the collection is given by: $(A), (A), (B), (B),...
2
votes
2answers
43 views

I need to find the combinatory formula for this set.

Problem 1. Fix a positive integer $n$. For every integer $S \geq n$, let $N_{n,S}$ denote the number of possible ways in which a sum of $S$ can be obtained when $n$ dice are rolled. For example, for $...
3
votes
0answers
34 views

Odd Multiplicities in Pascal's Triangle

This is more of a knowledge-sharing post, but I would love more insight. I was looking at Pascal's triangle and I was curious which numbers appear precisely an odd number of times. My first ...
-3
votes
1answer
80 views

Define $g(n):=f(n!)$. We want to find a closed formula for $g(n)$ [on hold]

I am trying to understand the following question, and honestly have no idea from where to start it seems like it asking for factorial of $n$ terms in a form of $g(n)$? Define $g(n):=f(n!)$. We want ...
1
vote
0answers
46 views

Fast Evaluation of Multiple Binomial Coefficients

Suppose we have a sequence of binomial coefficients. $$ S = \left\langle \binom{5}{2}, \binom{5}{3}, \binom{6}{3}, \binom{17}{14}, \binom{19}{15} \right\rangle $$ How can we efficiently evaluate all ...
2
votes
0answers
65 views

Combinatorial proof of $ \sum_{k=0}^{n}\frac{1}{\binom{n}{k}} = \frac{n+1}{2^{n+1}}\sum_{k=0}^{n}\frac{2^{k+1}}{k+1}$

A recurrence relation of $$S_n =\sum_{k=0}^{n} \frac{1}{\binom{n}{k}}$$ is $$ \frac{n+2}{\binom{n}{k}} - \frac{2n+2}{\binom{n+1}{k}} = \frac{n-k}{\binom{n}{k+1}} - \frac{n+1-k}{\binom{n}{k}}, \quad 0 ...
3
votes
2answers
79 views

Generating and counting subsets of $\{1,…,100 \}$ with limited pairwise intersection

Suppose we have the set $X = \{1,...,100\}$, and we want a family $\mathscr{A} \subset \mathcal{P}(X)$ where the following hold: 1.) For all $A \in \mathscr{A}$, $|A| = 50$. 2.) For all $A, B \in \...
0
votes
1answer
28 views

Sum of weighted binomial coefficients [duplicate]

I am struggling with computing the following sums: $$\sum_{k=1}^{n}k\binom{n}{k}=\binom{n}{1}+2\binom{n}{2}+...+n\binom{n}{n}$$ and $$\sum_{k=0}^{n}\frac{1}{k+1}\binom{n}{k}=\binom{n}{0}+\frac{...
2
votes
2answers
76 views

$\binom{2k+1}{k}$ is odd when $k=2^m-1 (m \in \mathbb{N})$, otherwise $\binom{2k+1}{k}$ is even.

What could be a possible approach to find the proof of: $\binom{2k+1}{k}$ is odd when $k=2^m-1$, otherwise $\binom{2k+1}{k}$ is even. I have seen some similar problems in https://math....
0
votes
2answers
38 views

Doubt about $r$th Term in Binomial theorem

When asked about $10$th term in expansion of $(a+b)^{15}$ we have $$T_{10}=\binom{15}{10}a^5b^{10}$$ But we can also write the binomial as $(b+a)^{15}$ and say $10$th term as $$T_{10}=\binom{15}{10}...
1
vote
1answer
39 views

Number of Non negative integer solutions of $3a+2b+c+d=19$

Find Number of Non negative integer solutions of $3a+2b+c+d=19$ My attempt: we have $$2b+c+d=19-3a$$ Required solutions is coefficient of $t^{19-3a}$ in $$( 1-t^2)^{-1}(1-t)^{-1}(1-t)^{-1}=\frac{...
0
votes
0answers
38 views

Bounds on $\sum_{l=0}^j (-1)^l 3^{j-l}\binom{j}{l}\sum_{k=0}^{\alpha n} \binom{n-j}{k-l}$

In the course of solving some optimization, I encountered the following sum: $\sum_{l=0}^j (-1)^l 3^{j-l}\binom{j}{l}\sum_{k=0}^n \binom{n-j}{k-l}=2^n, \quad j\in\left\{0,1,\dots,n\right\}$. I am ...
0
votes
2answers
39 views

Find the limit of a finite sum involving binomial coefficients [on hold]

I am trying to evaluate the following limit, where $n$ and $q$ are non-negative integers, and $n > q$. $$\lim_{m→∞}{\frac{1}{2^m}}∑_{k}{m\choose{nk+q}} $$ Does it exist? If so, what is the value?
1
vote
1answer
58 views

Evaluate the Sum $S=\frac{1}{4}+\frac{1.3}{4.6}+\frac{1.3.5}{4.6.8}+\cdots \infty$ [duplicate]

Evaluate the Sum $$S=\frac{1}{4}+\frac{1.3}{4.6}+\frac{1.3.5}{4.6.8}+\cdots \infty$$ My try: We have the $n$ th term as $$T_n=\frac{1.3.5. \cdots (2n-1)}{4.6.8 \cdots (2n+2)}$$ $\implies$ $$T_n=...
1
vote
1answer
43 views

Mathematical induction on binomial coefficients

I need to prove the following statement (Pascals Identity) on binomial coefficients using mathematical induction only $$\binom{n}{r} = \binom{n-1}{r}+\binom{n-1}{r-1}$$ My doubt is Whether I need ...
-1
votes
1answer
65 views

Prove that product of n consecutive numbers is divisible by n!

Prove that product of n consecutive numbers is divisible by n! That is, If $ P = (a) (a+1)...(a + n -1)$ Then, $n!|P$ Prove it in two ways, one without induction and another with induction. I ...
-3
votes
0answers
32 views

What would be the coefficient of x^4 in (1+x+x^2)^3*(1-x)^-1 for -1<x<1? [closed]

Answer is given like this (1-x^3)^3 *(1-x)^-4 so 7c3 - 3 * 4c3 = 7c3 - 12 = 35 -12 =23 I need proper explanation
0
votes
0answers
37 views

Closed form for expansion involving binomial coefficients

Consider the following expansion in terms of binomial coefficients $\sum\limits_{i=1}^{u} \binom{k-i}{k-r} (r+2)^{i-1}$ Is there any closed form for this expression?
0
votes
2answers
60 views

Number of positive integer solutions of $x+y+z+w=26$ such that $x \lt y \lt z$

Number of positive integer solutions of $x+y+z+w=26$ such that $x \lt y \lt z$ my try: Let $y=x+p$ and $z=x+q$ where $p \ge 1$ and $q \ge 2$ Then we have $$3x+p+q+w=26$$ $\implies$ $$p+q+w=26-3x$$...
1
vote
0answers
40 views

Sum of product of binomial coefficients & powers: closed-form?

The following sum has emerged in my research: $ \sum_{j=k}^{n}\frac{1}{2^j}{j\choose k}{n+k+2\choose n-j}; $ I am looking for a closed form for this sum (without hypergeometric series). I have ...
0
votes
0answers
37 views

Finding a Closed-Form Formula for the Binomial Sum $\sum_{k=0}^{n} \binom{n}{k} 2^{k^2}$. [duplicate]

I have tried to find a closed-form formula for the following binomial sum, but to no avail. Any ideas? $$\sum_{k=0}^{n} \binom{n}{k} 2^{k^2}$$ If possible, it would be helpful to have a closed-...
3
votes
1answer
48 views

Binomial Coefficients inequality simplifying to answer involving “e”

In doing some analysis, my professor wrote \begin{align*} \begin{pmatrix} n+ m \\ m \end{pmatrix} &= \frac{(n+m)!}{m!n!} \\ &= \frac{(n+m)(n+m-1)...(n+1)n!} {m!n!} \\ &= \frac{(n+m)}{m} \...
0
votes
0answers
52 views

Binomial series for $|z|=1$?

The binomial series is given by $$(*) \quad (1-z)^{-\alpha}=\sum_{k=0}^{\infty}\frac{\Gamma(k+\alpha)}{\Gamma(\alpha)\, k!} \, z^{k}; \,\, |z|<1,$$ where $\alpha \in \mathbb {C}$ is an arbitrary ...
0
votes
1answer
36 views

Simplify $^{ 3 4 } C _ 5 + \sum _ { r = 0 } ^ { 4 } $ $ ^ { 3 8 - r } C _ 4$

Simplify $^{ 3 4 } C _ 5 + \sum _ { r = 0 } ^ { 4 } $ $ ^ { 3 8 - r } C _ 4$ Any hints are appreciated.
4
votes
2answers
58 views

In how many ways a student can get $2m $ Marks

An examination contains four Question papers each paper carrying maximum marks as $m$. Find number of ways a student appearing for all the four papers gets a total of $2m$ Marks. I used generating ...
-1
votes
1answer
47 views

Why does $\binom{2n}{n} = \prod_{i=1}^n (\frac{n+i}{i} )$

I cannot understand why are you able to generalize this like this $$\binom{2n}{n} = \frac{2n × (2n−1) × ... × (n+ 2) × (n+ 1)}{n ×(n−1)×...×2×1} =\prod_{i=1}^n (\frac{n+i}{i}) $$ I get that $$\binom{...
1
vote
3answers
48 views

Strengthening an inequality of exponential series

A question posits that, show: $$(1+x_1)(1+x_2)\ldots(1+x_n)\\ \leq 1+\dfrac{S}{1!}+\dfrac{S^2}{2!}+\ldots\dfrac{S^n}{n!}$$ Where $S=\sum x_i$, $x_i\in\mathbb{R}$ Now, the RHS looked like the ...
0
votes
1answer
71 views

Maximum $n$ such that ${n \choose k} \,2^{1 - {k \choose 2}} < 1$ (where $k$ is a constant)

Maximum value of $n$ such that the expression given below does not exceed 1. ($k$ is a constant) $${n \choose k} 2^{1 - {k \choose 2}} < 1$$ Any hints on how to approach this problem. Thanks. ...
2
votes
1answer
94 views

entropy of the sum of binomial distributions

Suppose that one has $X_1 \sim Bin(n,p)$ and $X_2 \sim Bin(n,1-p)$ and that $Z$ is distributed s.t: $$ P(Z = k) = .5 P(X_1=k) + .5P(X_2=k) $$ How do we compute the entropy? For a binomial ...
1
vote
2answers
28 views

algebraic derivation of sum of binomial coefficients

I've seen the standard combinatorial and algebraic proofs that $\sum_{k=0}^n {n \choose k}=2^n$, where the algebraic proof uses induction and Pascal's identity: $${n\choose k}+{n\choose k+1}={n+1\...
4
votes
2answers
319 views

Binomial Coefficient Identity Conjecture

The following (conjectured) identity has come up in a research problem that I am working on: for even $a$ $$\sum_{i=0}^{a-1} (-1)^{a-i}\binom{a}{i} \binom{2m-i-2}{m-i-1}=0;$$ and for odd $a$ $$\sum_{...
3
votes
3answers
101 views

What's the probability of completing the illustrated “binomial walk” without ever visiting a node above the baseline?

Consider the illustrated binomial (not binary) tree with $n$ steps (drawn for $n=5$, but consider $n$ variable). Start a random walk at the left-hand node, and at each step you have probability $p$ of ...
0
votes
3answers
73 views

Prove $\binom{2n}{n}~=~\sum_{k=0}^n \binom{n}{k}^2$

Within another answer to a question concerning a sums of the type $$\sum_{k=0}^n \binom{n}{k}^2$$ there was a simple indetity given which reduces this sum to a simple binomial coefficient, to be ...
0
votes
1answer
45 views

Is it true that $\sum_{j=k}^{2k} {2k \choose j}\big(\frac{1}{2}\big)^{2k}-\frac{1}{2}=\frac{1}{2}\Big({2k \choose k}\big(\frac{1}{2}\big)^{2k}\Big)$?

On the first page of Lionel Penrose's 1946 paper "The Elementary Statistics of Majority Voting," Penrose claims that "the amount by which [an individual voter's] chance of winning exceeds one half" (...
2
votes
2answers
67 views

$\lim_{n \to \infty} \sum_{k=1}^{\left\lfloor\frac{n}{2}\right\rfloor}{\binom{n-k}{k}\frac{1}{2^{n-k}}}$?

Consider the following limit: $$\lim_{n \to \infty} \sum_{k=0}^{\left\lfloor\frac{n}{2}\right\rfloor}{\binom{n-k}{k}\frac{1}{2^{n-k}}}.$$ I can find the limit numerically, but is it possible to ...
-2
votes
1answer
42 views

Having trouble with a Binomial proof by mathematical induction question: $\sum_{j=3}^n \binom{j-1}{2} = \binom{n}{3}$ [closed]

I can't work out how to prove this equation is true by proof of mathematical Use mathematical induction to prove that, for $n \ge 3$ $$\sum_{j=3}^n \binom{j-1}{2} = \binom{n}{3}$$ Please help, ...
0
votes
0answers
33 views

What composite number can be represented as $\binom{n}{k}$ for $k\neq1$ or $n-1$

This is a problem I came up with when I was working with binomial coefficients. Let's call the title statement $(*)$. Obviously for any primes do not satisfy $(*)$, therefore we only need to focus on ...
4
votes
0answers
109 views

Compute $\sum_{k=0}^n {n\choose k}^2 = {2n\choose n}$ using Fourier series method.

I'm trying to prove the binomial identity $$\sum_{k=0}^n {n\choose k}^2 = {2n\choose n}.$$ This is a problem from "Fourier Series and Integrals" by Mckean. So far, I have computed sums of the form $\...
2
votes
2answers
62 views

Prove that $\binom{2n}{n}\equiv (-1)^n \pmod{(2n+1)}$ if and only if $2n+1$ is a prime number.

I have conjectured that $$\binom{2n}{n}\equiv (-1)^n \pmod{(2n+1)}$$ if and only if $2n+1$ is a prime number, based on a short program that I wrote verifying this up to $n=100$. I know that by ...
4
votes
2answers
55 views

Combinatorial proof of Negative Binomial Identity

For the (usual) Binomial theorem with positive integer exponent, there is a well known nice combinatorial proof. I am eager to learna similar argument for the proof of negative binomial series: $$(1+...
0
votes
3answers
56 views

For any odd integer $n > 2$, show that there isn't any positive integer $x$, such that $x^n + (x+1)^n = (x+2)^n$.

For any odd integer $n > 2$, show that there isn't any positive integer $x$, such that: $$x^n + (x+1)^n = (x+2)^n$$ Writing it using Newton's binom, we obtain: $$x^n = \sum_{i=1}^{n} \binom{n}{i} \...
4
votes
3answers
137 views

a tough sum of binomial coefficients

Find the sum: $$\sum_{i=0}^{2}\sum_{j=0}^{2}\binom{2}{i}\binom{2}{j}\binom{2}{k-i-j}\binom{4}{k-l+i+j},\space\space 0\leq k,l\leq 6$$ I know to find $\sum_{i=0}^{2}\binom{2}{i}\binom{2}{2-i}$, I need ...
5
votes
3answers
120 views

Sum of Squares of Binomial Coefficients Using Residue Theorem

I ran across this interesting question recently that I have an idea for, but am unable to complete. Basically, we use the residue formula to find $$ \sum\limits_{k=0}^n {n\choose k}^2$$ We define $f$ ...
1
vote
1answer
37 views

Which monomials in $p$ and $q$ can be a probability in a finite coin experiment?

The question generate event with $6.75\space p^2q$, $20\space p^3q^2$, $3.9\space pq$? prompted me to think more generally about which expressions of this form can be a probability in a finite coin ...
1
vote
1answer
36 views

Prove the identity with Stirling numbers.

For arbitrary integer $m, t, s<n$ prove the identity $$ \sum_{i=s+1}^{n}(i!)^2 \left\{ {n \atop i}\right\} \left\{ {m \atop i}\right\} \binom{s}{i}\binom{t}{i}=0, $$ here $\displaystyle \left\{ {...
2
votes
0answers
81 views

Is there a simple formula for this polynomial sum?

The following seemingly arbitrary polynomial has popped up in my research on period polynomials of modular forms, and I would like to try to understand it a little better. I hope it is OK to ask about ...
1
vote
0answers
23 views

Formula for the coefficients of $m$th order the central difference scheme

In a paper I'm reading, I found the following formula for the coefficients of the $m$th order central difference scheme. For all $\ell \in \{-m,-m+1, \dots, m-1,m\}$: $$a_{\ell} = \begin{cases} \frac{(...
6
votes
1answer
138 views

$n$-element subsets of the set $\{1,2, …, 2n\}$.

There are $\binom{2n} {n}$, $n$-element subsets of the set $\{1,2, ..., 2n\}$. I am studying the question whether one can choose from these subsets $\frac12\binom{2n} {n}$ subsets such that: i) each ...
0
votes
1answer
46 views

Alternating sum of binomial coefficient times logarithm

This question relates to a statistics question on CrossValidated.SE where the following summation appeared in an answer: $$I(n) \equiv \ln n + \sum_{k=1}^{n} {n \choose k} (-1)^k \ln k \quad \quad \...
0
votes
0answers
39 views

Binomial inequality

I have two binomial expressions. \begin{align} mm_{1}\binom{N(d+1)+n}{n}\tag{1}\\ \binom{N+n+1}{n+1}\tag{2} \end{align} wher $n,m,m_1,d$ are constants and only $N$ varies. Now we have the ...