Tagged Questions
1
vote
1answer
46 views
Combinatorics identity sum of
Prove that:
$$\sum^{n}_{k=0}\binom{k}{2n-k}2^k = 2^{2n}$$
By using only combinatorics identities.
3
votes
4answers
56 views
Combinatorial Proof
I have trouble coming up with combinatorial proofs. How would you justify this equality?
$$
n\binom {n-1}{k-1} = k \binom nk
$$
1
vote
1answer
24 views
Prove that the Iwata function is Submodular
The Submodularity property for $f: 2^V \rightarrow \mathbb{R}$ is defined as:
$f(X) + f(Y) \geq f(X \cup Y) + f(X \cap Y)$ where $X, Y \subseteq V$
While the Iwata function is defined as:
...
1
vote
2answers
28 views
Isomorphism of Posets
Let $(X,\le),(Y,\le)$ be posets. $\text{Iso}(X,Y)$ denotes the set of isotones from $X$ to $Y$. $f:X\to Y$ is an isotone if $x_1\le x_2 \implies f(x_1)\le f(x_2)$.
$(A,\le),(B\le),(C,\le)$ are ...
1
vote
2answers
64 views
Catalan number interpretation
I have a $2 \times n$ chessboard where numbers are increasing from left to right and top to bottom. I want to show that the number of arrangements is the $nth$ catalan number.
for example one such ...
3
votes
1answer
46 views
An ordering different from the Gray order (digits change by 1 at each step)
Given $A=\lbrace x_n,\ldots x_1\rbrace$. How would I construct an ordering on the subsets of $A$ such that the immediate successor of a subset is obtained by either adding or deleting one element, and ...
1
vote
3answers
58 views
Generating function with quadratic coefficients.
$h_k=2k^2+2k+1$. I need the generating function $$G(x)=h_0+h_1x+\dots+h_kx^k+\dots$$ I do not have to simplify this, yet I'd really like to know how Wolfram computed this sum as ...
2
votes
3answers
74 views
proof of combinatoric/using pascals theorem
prove that, for even values of $n$, $$\sum_{i=0}^{n/2}\binom{n}{2i}= 2^{n-1}\;.$$
I tried using pascals theorem to help prove this with no success
4
votes
2answers
101 views
Prove by Combinatorial Argument that $\binom{n}{k}= \frac{n}{k} \binom{n-1}{k-1}$
This is a question from my first proofs homework and I am confused about the combinatorial argument aspect. I already did the algebraic proof. I think I am supposed to put into words what both sides ...
2
votes
1answer
55 views
Correct Combinatorial reasoning for constant positions
Suppose we have an array $A$ indexed from $1$ to $n$. Let a constant position be any index $i$ for $1 \leq i \leq n$ of the array such that:
\begin{equation}
A_i = i
\end{equation}
For example the ...
12
votes
4answers
465 views
Proving identities like $\sum_{k=1}^nk{n\choose k}^2=n{2n-1\choose n}$ combinatorially
I have to give a combinatorial proof of
$$\sum_{k=1}^nk{n\choose k}^2=n{2n-1\choose n}.$$
I find it difficult to solve such problems. I'm not a brilliant person and never will be so I need to have ...
1
vote
1answer
52 views
Correctness of proof for finite sum of Stirling numbers of the first kind
it is known that the finite sum of Stirling numbers of the first kind $s_{n,k}$ is $n!$ as defined below.
$$\sum_{k=0}^{n} s_{n,k} = n!\tag{1}$$
I attempt to prove this by induction, where the ...
3
votes
3answers
134 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$ ...
4
votes
1answer
87 views
Combinatorial reasoning for linear binomial identity
I have the following equation:
\begin{equation}
m^4 = Z{m\choose 4}+Y{m\choose 3}+X{m\choose 2}+W{m\choose 1}
\end{equation}
I iteratively took $m=1$ to $m=4$ to solve for the coefficients. I got ...
5
votes
2answers
94 views
Combinatorial argument for the identity $k\binom{n}{k} = n\binom{n-1}{k-1}$
I am looking for the combinatorial argument for the identity:
\begin{equation}
k\binom{n}{k} = n\binom{n-1}{k-1}
\end{equation}
This is easy to show algebraically as:
\begin{equation}
\binom{n}{k} ...
7
votes
7answers
268 views
Prove the following equality: $\sum_{k=0}^n\binom {n-k }{k} = F_n$ [duplicate]
I need to prove that there is the following equality:
$$
\sum\limits_{k=0}^n {n-k \choose k} = F_{n}
$$
where $F_{n}$ is a n-th Fibonacci number.
The problem seems easy but I can't find the way to ...
0
votes
1answer
28 views
Placing reservations on boxes when using the Pigeonhole Principle
I am choosing $m+1$ integers from the set $\lbrace 1,2,\ldots 2m\rbrace$, and I want to use the Pigeonhole Principle to show that two of the numbers chosen differ by $1$. I want to know if my strategy ...
1
vote
1answer
47 views
Simple Summation Proof with identities
Using some of the identities, determine the value of
$\sum_0^5$ ${12 \choose i}$
. You may use the
substitution ${12 \choose 6}$
= 924, but you may not evaluate the individual chooses.
Proofs of ...
2
votes
1answer
608 views
Inductive Proof for Vandermonde's Identity?
I am reading up on Vandermonde's Identity, and so far I have found proofs for the identity using combinatorics, sets, and other methods. However, I am trying to find a proof that utilizes mathematical ...
1
vote
2answers
333 views
Combinatorial proof of an identity [duplicate]
Possible Duplicate:
Combinatorially prove something
I have to give a combinatorial proof of the identity:
$$\sum_{i=0}^{n}{\binom{n}{i}}{2^i}=3^n$$
I can use prove it using the binomial ...
1
vote
1answer
152 views
Combinatorially prove something
So i'm not sure at all how to prove things using a combinatorial proof. Where to do i start? What do i need to think about etc. For example how would i prove
$$\sum_{i=0}^n {n \choose i} 2^i = 3^n ...
1
vote
2answers
159 views
Even and Odd proof
I'm trying to prove for every positive even number, $$x = 2y$$
that
$$\sum_{i=0}^y {x \choose 2i} 2^{2i} = \sum_{i=0}^{y-1} {x \choose 2i + 1}2^{2i+1} + 1$$
Also to find and prove a similar equation ...
3
votes
1answer
110 views
Combinatorial proof of an equation
I was wondering if there is a combinatorial proof of this equation?
$$\sum_{k=0}^{n}k \binom{n+k-1}{k} =n \binom{2n}{n+1}$$
8
votes
3answers
142 views
Combinatorial proof of an equation [duplicate]
Possible Duplicate:
Combinatorial proof for two identities
is there a combinatorial proof of equation below? (parallel summation for binomials):
$$\sum_{k=0}^{n} \binom{n+k-1}{k} = ...
2
votes
1answer
103 views
Sum of Stirling numbers of both kinds
Let $a_k$ be the number of ways to partition a set of $n$ elements $orderly$,which means that order of subsets matters, but order of elements in each subset does not.
My task:
Prove, ...
3
votes
0answers
130 views
Combinatorics and graph theory - counting connected graphs
We denote by $C(n,n+k)$ the number of connected graphs on $n$ vertices with $n+k$ edges. I have 2 problems I wish to prove, but after much effort have gotten nowhere with. I would greatly value some ...
2
votes
6answers
357 views
Dice Probability Problem
Here is a problem I recently found in a book on Probability:
When 'x' fair dice (which have six faces each) are rolled, derive the formula for the probability that the sum of the scores on the dice ...
3
votes
1answer
68 views
Prove or name this identity: the number of factors of $p$ in $\binom{n}{k}$ is $(s_p(k)+s_p(n-k)-s_p(n))/(p-1)$
you can count the number of factors of $p$ that are in $\binom{n}{k}$ for prime $p$. Let $s_p(n)$ be the sum of the digits of $n$ in base $p$. Then, the number of factors of $p$ in $\binom{n}{k}$ is ...
0
votes
1answer
99 views
Algebra on $\binom{k+1}{i} = \binom{k+1}{0} + \binom{k+1}{1} + \cdots + \binom{k+1}{k} + \binom{k+1}{k+1}$ [duplicate]
Possible Duplicate:
Algebraic Proof that $\sum\limits_{i=0}^n \binom{n}{i}=2^n$
I am trying to prove $\sum \limits_{i=0}^n \binom{n}{i} = 2^n$ by induction. I've been all over the net ...
2
votes
1answer
84 views
With what probability is this polynomial equal to zero (mod a prime $p$)?
If we suppose that we have a polynomial $q(x)$ of the following form:
$q(x) = \sum_{i=0}^N{c_i x^i} \text{ where } c_i=0 \text{ or } c_i=1$
In other words, if we are given a polynomial with binary ...
5
votes
5answers
383 views
Algebraic proof that collection of all subsets of a set (power set) of $N$ elements has $2^N$ elements
In other words, is there an algebraic proof showing that $\sum_{k=0}^{N} {N\choose k} = 2^N$? I've been trying to do it some some time now, but I can't seem to figure it out.
0
votes
1answer
85 views
Proving a Recursive Relation
I’m studying for an exam, and have this problem as one of my review questions: I have $p(n)$, which represents the amount of partitions from a set $A$ that has $n$ elements.
I know that if $R$ is an ...
1
vote
1answer
280 views
Problem with proving Hall marriage theorem
I have a question about the proof of this theorem. If modeled with graphs, theorem would go like this:
Marriage problem:
Let $V_1$ and $V_2$ be the disjunct set of vertices in a bipartite graph, ...
