2
votes
3answers
188 views

Wheel of Fortune Problem

The Summation formula is $$\sum_{i=1}^ni =\frac{n(n+1)}2$$ How is it that we know the integers $1,2,...36$ appear exactly $3$ times. And why do we multiply the sum by $3$ in the last part of the ...
0
votes
1answer
49 views

Winning or Non-losing strategy for A or B

Find a winning or a non-losing strategy for the following game: Consider $25$ sticks arranged in a $5$ x $5$ square. Players alternately take any number of sticks from a single row or column. At ...
0
votes
1answer
31 views

Combinatorics Proof

I am having trouble with a combinatorics proof. I need to prove that if $r$ <= $n$ then the number of $r$ - subsets of {1,...,n} is $n!$/$(n-r)!$*$r!$ I really struggle with writing proofs and ...
-1
votes
3answers
50 views

Show that $C(n,k) = C(n-1,k) + C(n-1,k-1)$ [duplicate]

I'm studying for my final for Statistics, and I want to understand literally every problem in my textbook (at least in the first 7 chapters). One of the problems asks to show that ${n}\choose {k}$ ...
3
votes
6answers
487 views

How do I begin proving this binomial coefficient identity?

This is a homework question. I'm asked to prove the identity: $${n\choose 0} - {n\choose 1} + {n\choose 2} - {n\choose 3} + \dots = 0$$ (The sum ends with ${n\choose n} = 1$, with the sign of the ...
0
votes
2answers
78 views

Combinatorics proof of “sum of (k choose m) with k from m up to n is equal to n+1 choose m+1”

I've already proved this statement algrebraically. I'm asked to prove it with combinatorics. So far I came up with, LHS= # ways to choose m apples from a total of m,m+1,...,n RHS= # ways to choose ...
3
votes
3answers
327 views

Prove: Number of Derangement is odd if and only if number of items is even .

let $D_n$ be a number of Derangement of n items . prove that $D_n$ is odd if and only if n is even . i was trying to use induction on the $!n=(n-1)(!(n-1)+!(n-2))$ recurrence relation but i cant ...
0
votes
5answers
223 views

Proof of a binomial identity $\sum_{k=0}^n {n \choose k}^{\!2} = {2n \choose n}.$

Prove that $$\sum_{k=0}^n {n \choose k}^{\!2} = {2n \choose n}.$$ The exercise provides the following hint: $\,\,\displaystyle{n \choose k}={n\choose n-k}$. Any help?
0
votes
3answers
343 views

Sum of $k {n \choose k}$ is $n2^{n-1}$

Proof that $\suṃ̣_{k=1}^{n}k {n \choose k}$ for $n \in \mathbb N$ is equal to $n2^{n-1}$. As a hint I got that $k {n \choose k} = n {n-1\choose k-1} $. I tried solving this by induction but, in the ...
1
vote
1answer
54 views

What is the proper way to format a hypothetical syllogism proof?

Problem: Show that these three statements are equivalent, where $a, b \in R:$ (i) $a < b$, (ii) the average of $a, b,$ is greater than $a,$ and (iii) the average of $a$ and $b$ is less than $b$. ...
2
votes
1answer
111 views

Combinatorial Proof -$\ n \choose r $ = $\frac nr$$\ n-1 \choose r-1$

I'm reading about combinatorics, specifically 'Cohen's Introduction to Combinatorial Theory', and am stuck on one of the problems. I'm looking for a combinatorial proof for the following : $\ n ...
1
vote
2answers
43 views

Combinatorial Proof Question

I'm really iffy on combinatorial proofs in general and now that there is a sum, it's just confused me even more. Can someone try and walk me through this proof? $$ \binom{m + n}{r} = \sum_{k=0}^r ...
2
votes
2answers
98 views

show that $2n\choose n$ is divisible by 2 [duplicate]

I tried using induction, but in the inductive step, I get: If $2n\choose n$ is divisible then I want to see that $2n +2\choose n +1$ $${2n +2\choose n +1} = (2n + 2)!/(n+1)!(n +1)! = {2n\choose n} ...
3
votes
1answer
79 views

I want to figure out how many Topologies are in the set X

I have the set $$X = \{1, 2, 3\}$$ and I want to figure out how many different topologies I can get from the set $X$ so what I have done is assumed that the empty set and the whole set are in $T$ ...
2
votes
1answer
45 views

Density of natural numbers

Let $A \subset \mathbb{N}$ and $D_A(n) = \dfrac{|A \cap [1,n]|}{n}$. One says $A$ has density if $\lim_n D_A(n)$ exists and is finite. I know there exist sets with and without density, and that ...
4
votes
1answer
91 views

Combinatorial Identity Proof

What is a combinatorial proof for this identity: $1 \times 1! + 2 \times 2! + ... + n \times n! = (n + 1)! - 1$ I am trying to figure out what are both sides trying to count.
0
votes
1answer
81 views

Prove that there exist at least two stable matches between the men and the women.

Suppose that more than one woman receives her lowest-ranked choice when the men propose. How do you prove that there exist at least two stable matches between the men and the women?
1
vote
1answer
89 views

Derangement Identity Proof

Use the following identity $$ (-1)^k\frac{(n-k)}{k!} = (-1)^k\frac{n}{k!}+(-1)^{k-1}\frac{1}{(k-1)!}$$ to prove that $$Qn=D(n)+D(n-1)$$ (n=2,3,...) D(n) is the number of derangements of an ...
0
votes
1answer
81 views

Finding a combinatorial proof of this identity: $n!=\sum_{i=0}^n \binom{n}{n-i}D_i$

Can someone prove this. Let $D_n$ be the number of derangements of $n$ objects. Find a combinatorial proof of the following identity: $$n!=\sum_{i=0}^n \binom{n}{n-i}D_i$$
1
vote
1answer
75 views

Prove that this expression is an integer

Prove that $$ \frac{(p - 1)!}{(p - k)! \cdot k!} $$ is an integer if $0 < k < p$ and $p$ is prime.
2
votes
1answer
131 views

Proof of summation of Stirling's Numbers of the first kind

"Stirling's number of the first kind $s(n,k)$ is the number of permutations of ${1,2,...,n}$ with $k$-cycles. Prove that $n! = \sum s(n,k)$ (from k = 1 to $\infty$) " After checking a the first few ...
4
votes
4answers
615 views

Prove that $\sum_{k=0}^r {m \choose k} {n \choose r-k} = {m+n \choose r}$ [duplicate]

Prove that $$\sum_{k=0}^r {m \choose k} {n \choose r-k} = {m+n \choose r}.$$ This problem is in the chapter about discrete random variables, but I have no idea what to go about substituting. I can't ...
0
votes
2answers
1k views

Prove that $n+1 \choose k$ = $n \choose k$ + $n \choose k-1$

As the title says. Prove that $n+1 \choose k$ = $n \choose k$ + $n \choose k-1$ It looks to me like induction but since there are two variables, I'm not really sure how to even set up a base case. ...
1
vote
3answers
61 views

Uncertain how to proceed with combinatorics proof

The problem is as follows: let $n_1, n_2,..., n_t$ be positive integers. Prove that if $n_1+n_2+...+n_t-t+1$ objects are placed into $t$ boxes, then for some $i, i=1, 2, ..., t$, the $i$th box ...
1
vote
3answers
638 views

Prove that $P(X)$ has exactly $\binom nk$ subsets of $X$ of $k$ elements each.

Let set $X$ consist of $n$ members. $P(X)$ is power set of $X$. Prove that set $P(X)$ has exactly $$\binom nk = \frac{n!}{k!(n-k)!}$$ subsets of $X$ of $k$ elements each. Hence, show that $P(X)$ ...
0
votes
1answer
130 views

Problem with proving Catalan number

This is how my professor derived it: Taking the case of all valid arrangements of $n$ '(' and $n$ ')', he says that for every invalid arrangement, there will be a ')' at some $k^{th}$ position where ...
4
votes
3answers
111 views

Proof that $n \in \mathbb{N}$ by combinatorial analogue?

(Disclaimer: I'm a high school student, and my highest knowledge of mathematics is some elementary calculus. This may not be the correct terminology.) A while ago, I saw the following problem: prove, ...
2
votes
0answers
71 views

Checking an inductive proof on a combinatorial product

Consider the following product, for $n, k, i \in \Bbb Z_+, k \geq 2$: $$ {\prod_{\ell = 1}^i {n + k - \ell \choose k } \over \prod_{\ell = 1}^{i-1} { k + \ell \choose k}} \tag{$*$} $$ It has been my ...
7
votes
2answers
214 views

maximum number of edges to be removed to possess a property

I am working on a problem. We know that on squaring a cycle, degree of every vertex is 4. For squares of cycles, we know if we delete any arbitrary edge then still eccentricity is same for all ...
1
vote
2answers
173 views

How to do a combinatorial proof

I have a question which asked for a combinatorial proof. I have no clue how to do do a combinatorial proof. The question is prove that the total number of subsets in $\{x_1, x_2, x_3, ... ,x_n\}$ is ...
2
votes
1answer
127 views

Short proof of Hall's theorem

Studying the proof of Hall's theorem in my book I started to wonder if there is a shorter way to prove it. Following is an attempt that I think works but (being short) makes me wonder if I made a ...
2
votes
2answers
86 views

eccentricity in vertex transitive graphs

I am trying to prove the following.. If $G$ is a veretx transitive graph, then how can we prove that eccentricity of every vertex is same? Getting no idea from where to start? How to prove the same ...
1
vote
1answer
82 views

Why no cut-vertices or cut edges in a graph where eccentricity is same for all vertices

I need help to prove the following statement. There are no cut-vertices or cut-edges(bridges) in a graph where eccentricity is same for all vertices. I am getting that if the graph contains a ...
1
vote
1answer
69 views

Proving $\forall f\in \mathscr F\exists g\in \mathscr F $ so that $g(f(1)) = 2$.

Let $\mathscr F$ denote the set of all functions from $\{1,2,3\}$ to $\{1,2,3\}$. Prove or disprove. (a) $\forall f\in \mathscr F\exists g\in \mathscr F $ so that $g(f(1)) = 2$. (b) $\forall f\in ...
2
votes
1answer
110 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 ...
1
vote
1answer
48 views

Counting Card hands with various restrictions

I would like to know if my solutions are correct for the following three combinatorial card questions. In each question, assume we have a standard deck of cards (13 ranks, and 4 suits). How many ...
1
vote
1answer
84 views

Special case of combinatorial onto functions

Let $[n]$ be the set of integers $\{1, 2, \ldots, n\}$. I want to find the number of onto functions from $[m]$ to $[3]$. The answer I found was $3!\cdot (3)^{m-3}$ My reasoning is: We have a ...
1
vote
1answer
47 views

Combinatorial Correctness of one-to-one functions

Let $\lbrack k\rbrack$ be the set of integers $\{1, 2, \ldots, k\}$. What is the number of one-to-one functions from $m$ to $n$ if $m \leq n$? My answer is: $\dfrac{n!}{(n-m)!}$ My reasoning is the ...
0
votes
2answers
147 views

Stuck with two questions.

Hello i had new 6 questions but i cant solve this two any help will be appreciated thanks Question 4 (15%) A-) Give an one-line proof for $ n^r \ge C(n+r-1,r) $ [Hint: direct proof] B-) ...
0
votes
2answers
82 views

Strong inducti0n with 3- and 5-peso notes and can pay any number greater than 7.

A bank has an unlimited supply of 3-peso and 5-peso notes. Prove that it can pay any number of pesos greater than 7. So i'm not completely sure how to use strong induction, but the base case is ...
0
votes
1answer
143 views

Prove that $p\mid \binom{p}{k},\ 0< k< p$

Prove that: $$p \,\,\left|\, {p \choose k} \right., \quad 0< k \lt p$$ if $p$ is prime. how to prove that with direct proof?
6
votes
1answer
2k 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
3answers
209 views

Need help with $n \choose k$ problem

I'm new to the discrete math, but I'm trying to prove this algebraically and some help would be cool. $$ \binom{a}{b} \binom{b}{c}= \binom{a}{c} \binom{a-c}{b-c},\quad c \leqslant b \leqslant a ...
0
votes
3answers
67 views

Prove how many distinct elements in the set $\{ax \pmod{m}:a\in\{0,…,m-1\}\}$

There are $\dfrac{m}{\gcd(m,x)}$ distinct elements in the set $\{ax \pmod{m}:a\in\{0,...,m-1\}\}$ I have only known these by using a computer to generate the number of distinct elements. But I am not ...
2
votes
2answers
732 views

Combinatorial proof of binomial coefficient summation

While doing some Computer Science problems, I found one which I thought could be solvable using combinatorics instead of programming: Given two positive integers $n$ and $k$, in how many ways do $k$ ...