Tagged Questions
3
votes
2answers
29 views
Distribution of $n$ balls to 10 cells; Inclusion-exclusion problem
So I got another ( :[ ) problem I got stuck with. So before I get going with that, I would like to know if you know any places where I can learn the principles of these subjects (compositions, ...
10
votes
3answers
142 views
Combinatorial proof of $\sum^{n}_{i=1}\binom{n}{i}i=n2^{n-1}$.
Prove
$$\sum^{n}_{i=1}\binom{n}{i}i=n2^{n-1}$$
I can't find counting interpretations for either of the sides. A hint of "if $S$ is a subset of $\{1, . . . , n\}$ and $S^\prime$ is its complement ...
3
votes
1answer
54 views
How to prove the identity $(n-k)! \sum _{i=0}^{n-k} \frac{(k+i-1)!}{i!} = \frac{n!}{k}$?
I am stuck in proving the following :
$$(n-k)! \sum _{i=0}^{n-k} \frac{(k+i-1)!}{i!} = \frac{n!}{k}$$
NOTE: I don't want any combinatorial proof. I think it is some algebraic manipulation.
2
votes
4answers
61 views
Binomial Coefficients for $(x+1)^4$
Find $(x + 1)^4$ using binomial coefficients.
I'm confused as to how to start this, as I thought binomial coefficients were things like $9 \choose 2$.
3
votes
1answer
31 views
Binomial coefficient help?
I'm studying for my exams and would appreciate any help with binomial coefficients. I think I got the idea but having trouble with a specific one:
Q) If a there are 11 dogs and 9 cats:
a) How many 7 ...
0
votes
2answers
39 views
Two identities with binomial coefficients
I found two interesting identities with binomial coefficients on wikipedia. I'm wondering how can I prove them with combinatorial interpretation and still no idea. They seem nice so I suppose ...
4
votes
2answers
122 views
How many 9 letter strings are there that contain at least 3 vowels?
I'm studying for my exams and stuck on this one question.
The way I'm thinking of doing this is by:
$$26^9 - \binom{26}3-\binom{26}2-\binom{26}1-\binom{26}0= 5,429,503,676,728$$
But that seems ...
4
votes
2answers
135 views
Compact form of sum (binomial coefficients)
Find compact formula of the following sum:
$$ \sum_{i,j,k \in \Bbb Z} {{n}\choose{i+j}}{{n}\choose{j+k}}{{n}\choose{k+i}} $$
Could you give me any HINT how to start it?
I've tried this way:
$$ ...
0
votes
1answer
57 views
Calculating a recursive power term binomial sum
Could someone please help me or give me a hint on how to calculate this sum:
$$\sum_{k=0}^n \binom{n}{k}(-1)^{n-k}(x-2(k+1))^n.$$
I have been trying for a few hours now and I start thinking it may ...
12
votes
4answers
304 views
How to prove $\sum\limits_{k=0}^n{n \choose k}(k-1)^k(n-k+1)^{n-k-1}= n^n$?
How do I prove the following identity directly?
$$\sum_{k=0}^n{n \choose k}(k-1)^k(n-k+1)^{n-k-1}= n^n$$
I thought about using the binomial theorem for $(x+a)^n$, but got stuck, because I realized ...
6
votes
0answers
76 views
Binomial formula for $(x+1)^{1/3}$ (related to Newton's binomial theorem)
I know that
$$\displaystyle \sqrt{1+x} = \sum_{j=0}^{\infty}\left( \frac{(-1)^{(j-1)}}{2^{2j-1}\cdot(2j-1)}\binom{2j-1}{j}x^j\right). $$
Now, I want to evaluate $\sqrt[3]{1+x}$ but stuck at some ...
0
votes
1answer
37 views
What is the probability of drawing kings
A hand H of 5 cards is chosen randomly from a standard deck of 52. Let $E_1$ be the
event that H has at least one King and let $E_2$ be the event that H has at least 2 Kings.
What is the conditional ...
0
votes
2answers
70 views
Why is $C(n + r − 1, r) = C(n + r − 1, n − 1)$, specifically why is $r$ equivalent to $n-1$?
I have this theorem in my discrete math textbook:
There are $C(n + r − 1, r) = C(n + r − 1, n − 1)$ r-combinations from a set with n elements when repetition of elements is allowed.
I can't figure ...
1
vote
1answer
52 views
Binomial identity for $4^k$ using previous results and sums
I have the following equation from a previous post:
\begin{equation}
\left(\dfrac{1}{\sqrt{1-4x}}\right) = \sum\limits_{k=0}^\infty{2k\choose k}x^k
\end{equation}
I want to square the equation:
...
3
votes
3answers
135 views
Help with combinatorial proof of binomial identity
Consider the following identity:
\begin{equation}
\sum\limits_{k=1}^nk^2{n\choose k}^2 = n^2{2n-2\choose n-1}
\end{equation}
Consider the set $S$ of size $2n-2$. We partition $S$ into two sets $A$ ...
5
votes
3answers
84 views
Closed formula for linear binomial identity
I have the following identity:
\begin{equation}
m^4 = Z{m\choose 4}+Y{m\choose 3}+X{m\choose 2}+W{m\choose 1}
\end{equation}
I solved for the values and learned of the interpretation of W, X, Y, and ...
2
votes
1answer
90 views
Dividing objects in equal parts
What are the number of ways of dividing $n_1$ objects of type $1$, $n_2$ objects of type $2,\ldots,n_k$ objects of type $k$ into 2 equal parts?
Note: take $\sum n_i=2n$ so that each part contains ...
0
votes
2answers
40 views
Dividing objects into 2 parts.
What are the number of ways of dividing $n_1$ objects of type $1$, $n_2$ objects of type $2,\ldots,n_k$ objects of type $k$ into $2$ parts?
0
votes
0answers
23 views
separation of semi-distinguishable objects.
I have $n_1$ objects of type $1$, $n_2$ objects of type $2$, ..., $n_k$ objects of type $k$.
Now, What are the numbers of ways of making $p$ objects out of these $n=\sum n_i$ semi-distinguishable ...
2
votes
4answers
139 views
Binomial Theorem identities, evaluate the sum
This is a homework problem, please don't blurt out the answer! :)
I've been given the following, and asked to evaluate the sum:
$$\sum_{k = 0}^{n}(-1)^k\binom{n}{k}10^k$$
So, I started out trying ...
4
votes
4answers
164 views
Closed form for $\sum_{k=0}^{n} \binom{n}{k}\frac{(-1)^k}{(k+1)^2}$
How can I calculate the following sum involving binomial terms:
$$\sum_{k=0}^{n} \binom{n}{k}\frac{(-1)^k}{(k+1)^2}$$
Where the value of n can get very big (thus calculating the binomial ...
4
votes
2answers
140 views
Combinatorial Proof Of Binomial Double Counting
Let $a$, $b$, $c$ and $n$ be non-negative integers.
By counting the number of committees
consisting of $n$ sentient beings that can
be chosen from a pool of $a$ kittens, $b$
crocodiles and $c$ emus ...
0
votes
4answers
78 views
Identity in surjective functions from N to X, up to a permutation of N
I'm studying the combinatorics "twelvefold way", and found an identity that cannot explain myself.
The case,
$$
{x-1 \choose b-1}
$$
as far as I understand is derived the following way:
$$
{(x-b)+b-1 ...
2
votes
2answers
295 views
Number of triangles inside given n-gon?
How many triangles can be drawn all of whose vertices are vertices of a given n-gon and all of whose sides are diagonals ( not sides ) of the n-gon ?
How many k-gons can be drawn in such a way ?
11
votes
1answer
396 views
Factorial canceling on expansion of binomial coefficients on Concrete Mathematics
On Concrete Mathematics section 5.5, which is teaching the hypergeometric functions, generalized factorials is defined as:
\[
\frac 1 {z!} = \lim_{n \to \infty} \binom{n+z}{n}n^{-z}
\]
where
\[
...
5
votes
2answers
254 views
Elementary bound of binomial coefficient
I'm working my way through an Erdös paper from the sixties and some of the elementary bounds he claims seem to be just beyond my reach. The expression looks horrendous but maybe there is a clever ...
1
vote
0answers
36 views
Inexpressibility of certain coefficients and discrete versions of Hölder's theorem
In an answer to a recent question, I noted that there were probably no explicit formulas for Stirling numbers (of the first kind, specifically) and speculated that this might be coupled to a sort of ...
1
vote
3answers
518 views
Sum with binomial coefficients
I'm repeating material for test and I came across the example that I can not do. How to calculate this sum:
$\displaystyle\sum_{k=0}^{n}{2n\choose 2k}$?
3
votes
2answers
342 views
How to prove it by means of a combinatorial argument?(A combinatorial exercise) [duplicate]
Possible Duplicate:
Proof that $\binom{n}{\smash{0}}^2+\binom{n}{1}^2+\cdots+\binom{n}{n}^2=\binom{\smash{2}n}{n}$ using a counting argument
It is an exercise in a book on discrete ...
1
vote
1answer
118 views
Summation of a multinomial coefficient
I was looking for a combinatorical explenation for this identity
$$\sum_{x_1+x_2+x_3 \le18}\binom{18}{x_1,x_2,x_3} = 4^{18}$$
A simple explenation would be enough,
Thanks
3
votes
2answers
179 views
Calculating a binomial sum
I came across this excercise in an old exam (in discrete math), and I don't know how to approach it:
$$\sum_{k=0}^{10}\left(\frac{1}{2}\right)^k\left(-1\right)^k\binom{10}{k}$$
I know the answer is ...
1
vote
1answer
773 views
How many n-digit binary sequences contain exactly k 1s?
A) How many n-digit binary $(0,1)$ sequences contain exactly k "1"s?
B) How many n-digit ternary $(0,1,2)$ sequences contain exactly k "1"s?
I am familiar with the equations $\frac{n(n-1)}{2}$ and ...
0
votes
2answers
84 views
What is the minimum number of friends Sally can have if she can invite a different group of friends to her house every night for a year?
The question: Sally has $N$ friends and likes to invite them over in small groups for dinner. She calculated that she can invite a different group of $3$ friends to dinner at her house every night for ...
4
votes
1answer
105 views
Convergence of a sequence of partial binomial sums
I have a sequence
$$a_n = (1-p)^n \sum_{\frac{n}{2}\le k \le n} \binom{n}{k} \left( \frac{p}{1-p} \right)^k.$$
I want to show that $a_n\to 0$ when $n\to\infty$ if $0\le p < \frac{1}{2}$. Here's a ...
0
votes
0answers
41 views
Solving the equation $n(n-1)\cdot\cdot\cdot(n-k+2)(n-k+1) = a$ [duplicate]
Possible Duplicate:
How to reverse the $n$ choose $k$ formula?
I want to calculate reverse binomial coefficients. Given a number $m$, I want to compute all possibilites how $m$ could be ...
5
votes
1answer
537 views
Asymptotics for a partial sum of binomial coefficients
Good afternoon,
I would like to ask, if anyone knows how to evaluate a sum
$$\sum_{k=0}^{\lambda n}{n \choose k}$$
for fixed $\lambda < 1/2$ with absolute error $O(n^{-1})$, or better.
In ...
1
vote
0answers
237 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
1answer
534 views
Counting the number of directed graphs with $N$ vertices and $E$ edges?
Does any body who has good back ground in graph theory tells me that how many possible directed graphs will be there with $N$ vertices and $E$ edges. I need all the possible combinations even even ...
1
vote
2answers
2k views
How many solutions are there to the equation $x + y + z + w = 17$?
How many solutions are there to the equation $x + y + z + w = 17$?
I don't know if I'm doing this right, but I guessed that the solution would be $\binom{20}{3}$, which equals $1140$. Am I doing ...
2
votes
3answers
170 views
Closed form for a sum involving binomial coefficient [duplicate]
Possible Duplicate:
How can I compute $\sum\limits_{k = 1}^n \frac{1} {k + 1}\binom{n}{k} $?
How to derive the following equality?
$$\sum_{j=0}^n \binom{n}{j} \frac1{j+1} = ...
10
votes
2answers
637 views
Good upper bound for $\sum\limits_{i=1}^{k}{n \choose i}$?
I want an upper bound on $$\sum_{i=1}^k \binom{n}{i}.$$
$O(n^k)$ seems to be an overkill -- could you suggest a tighter bound ?
13
votes
2answers
546 views
Combinatorial interpretation of Binomial Inversion
It is known that if $f_n = \sum_{i=0}^{n} g_i \binom{n}{i}$ for all $0 \le n \le m$, then $g_n = \sum_{i=0}^{n} (-1)^{i+n} f_i \binom{n}{i}$ for $0 \le n \le m$. This sort of inversion is called ...
6
votes
1answer
621 views
Relation between different ways of accessing bernoulli numbers with matrices
First Variant:
Bernoulli numbers can easily be expressed by linear algebra equations. For example just using the recursion formula
$$\sum_{k=0}^{n-1}{n\choose k}B_k=0$$
which is equation (34) from ...
3
votes
3answers
263 views
What does the notation $\binom{n}{i}$ mean?
What do the parentheses next to the summation involving the binomial coefficients mean? Like this:
$$\sum _{i=0}^{n} \binom{n}{i}a^{(n-i)}b^i=\left(a+b\right)^n $$
12
votes
2answers
7k views
A comprehensive list of binomial identities?
Is there a comprehensive resource listing binomial identities? I am more interested in combinatorial proofs of such identities, but even a list without proofs will do.
