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 ...
