1
vote
1answer
46 views

Proof that ordinary multinomial coefficients rise monotonically to a maximum and then decrease monotonically

While most computations of ordinary multinomial coefficients for the following case require recursive summations, I found here a closed-form solution: $$(1+x+x^2+\cdots+x^q)^L = \sum_{a \geq 0} ...
2
votes
1answer
53 views

Reverse Hex board game winning strategy

I just wanted to know the winning strategy to this question: In a reverse Hex board game I know it means where the player who first forms a path between his/her edges loses. Find a winning ...
0
votes
1answer
52 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 ...
1
vote
2answers
87 views

Hex game winning strategy

I was teaching myself how to play a hex board game by reading some books a couple days ago. I learned how to do $2$ x $2$ and $3$ x $3$ hex games by starting at the principal diagonal. I wanted to ...
0
votes
2answers
43 views

Prove a formula about binoms

I want to prove that $\binom{n}{n/2} \leq 2^{n-1}$ [Assuming $n$ is even] I've tried to do that but I didn't succeed.
5
votes
1answer
66 views

Using Plancherel's Theorem to Prove the Gauss Sum

I'm interested in proving the following: Where $p$ is an odd prime and $z$ is a primitive $p$th root of unity, we let $Q(p)=\sum^{p−1}_{k=0}z^{k^2}$. Prove: $|Q(p)|=\sqrt{p}$. Specifically, I want ...
2
votes
1answer
62 views

Help Needed Showing that $\chi(\overline{G \times H}) \leq \chi(\overline{G}) \times \chi(\overline{H})$

Where $\chi(G)$ denotes the chromatic number, $\overline{G}$ the graph complement, and $\times$ the Cartesian Graph Product: I need to show that $(\forall G,H)( \chi(\overline{G \times H}) \leq ...
0
votes
0answers
29 views

How to Devise Combinatorial Arguments for Proving Identities

What are some strategies or tips for contriving/devising combinatorial arguments? Combinatorial proof for $\binom{n}{a}\binom{a}{k}\binom{n-a}{b-k} = \binom{n}{b}\binom{b}{k}\binom{n-b}{a-k}$? I ...
8
votes
2answers
277 views

An expression for $U_{h,0}$ given $U_{n,k}=\frac{c^n}{c^n-1}(U_{n-1,k+1})-\frac{1}{c^n-1}(U_{n-1,k})$

Let $c\in\mathbb{R}\setminus\{ 1\}$, $c>0$. Let $U_i = \left\lbrace U_{i, 0}, U_{i, 1}, \dots \right\rbrace$, $U_i\in\mathbb{R}^\mathbb{N}$. We know that ...
4
votes
5answers
201 views

Non-inductive, not combinatorial proof of $\sum_{i \mathop = 0}^n \binom n i^2 = \binom {2 n} n$

I've seen the identity $\displaystyle \sum_{i \mathop = 0}^n \binom n i^2 = \binom {2 n} n$ used here recently. I checked for proofs here ...
5
votes
2answers
214 views

$\binom{n}{k}\binom{n}{n - k}$ vs $\binom{n}{k}$ - Differences? Similarities?

So the # of ways to choose an $n$ set with $k$ kiwis is $\binom{n}{k}\binom{n}{n - k} = \binom{n}{k}^2$. AlexR wrote No, picking exactly $k$ kiwis means you discount the $n-k$ remaining ...
3
votes
6answers
510 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 ...
1
vote
1answer
59 views

What exactly does $\vdash_T G_T \leftrightarrow \lnot \exists y$ Prf$(\ulcorner G_T \urcorner, y)$ mean?

To me this translates to: $G_T$ is provable in $T$ if and only if there doesn't exist a $y$ such that $y$ is a witness to the provability of $\ulcorner G_T \urcorner$. But I'm not entirely sure what ...
0
votes
0answers
31 views

A nowhere zero point in a linear mapping and Research Resources

Conjecture: If $\mathbb{F}$ is a finite field with at least 4 elements and $A$ is an invertible $n\times n$ matrix with entries in $\mathbb{F}$, then there are column vectors $x,y \in \mathbb{F^n}$ ...
1
vote
2answers
37 views

$K$ events that are $(K-1)$-wise Independent but not Mutually/Fully Independent

I had the following question: Construct a probability space $(\Omega,P)$ and $k$ events, each with probability $\frac12$, that are $(k-1)$-wise, but not fully independent. Make the sample space as ...
0
votes
2answers
41 views

Solving Problem by different Method ( non-induction)

I have this problem , which I was able to prove it by induction, but I wonder could be solve by direct method ( for example combinatorial method). I want to find number of solution for $$0 \le ...
0
votes
1answer
76 views

Combinatorial proofs - how?

I'm suppose to proof the following with combinatorial proofs. 1)$$\sum_{i=0}^{n} {a+i \choose i} = {a+n+1 \choose n}$$ 2)$$\sum_{i=0}^{n} i{n \choose i} = n2^{n-1}$$ 3)$$\sum_{i=0}^{n} {n \choose ...
1
vote
1answer
57 views

Proving a Bound for Oddtown-Eventown or Clubtown

Suppose we have a town with a set of residents $V$, where $|V| = n$. The residents like forming clubs, and we have clubs $C_1,C_2,\ldots,C_m \subseteq V$. We are interested in the maximum number of ...
0
votes
1answer
46 views

An n-bit boolean function maps 0/1 strings to 0 or 1

$f: \{0,1\}^n -> \{0,1\}$ The function "depends on i" if there exists two $o/1$ strings (A and B) where A and B differ only at position i and $f(A) \not= f(B)$. How many n-bit Boolean functions ...
0
votes
1answer
54 views

Prove it is possible to pick 11 integers whose sum is divisible by 11 [closed]

I'm not sure how to write a formal proof for this problem. I can come up with multiple examples, but I need to prove formally that there exists a subset of 11 integers whose sum is divisible by 11. ...
1
vote
1answer
49 views

Prove combinatorial identity

Prove the following identity: $$ {{i+j}\choose{i}}\left\{{n}\atop{i+j}\right\} = \sum_{k=0}^n{{n}\choose{k}}\left\{{k}\atop{i}\right\}\left\{{n-k}\atop{j}\right\} $$
0
votes
2answers
79 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 ...
0
votes
1answer
33 views

Binomial coefficient proof2

Having difficulty with starting off this proof. Let n be a positive whole number. Prove that $$n\dbinom{2n}{n}=(n+1)\dbinom{2n}{n-1}$$. Any help would be greatly appreciated.
7
votes
2answers
211 views

How to count matrices with rows and columns with an odd number of ones?

I proved that $\displaystyle \left(\sum_{k\, \rm odd}\binom{m}{k}\right)^{n-1}=\left(\sum_{k\;{\rm odd}}\binom{n}{k}\right)^{m-1}$ by counting matrices of size $n\times m$ with entries in $\{0,1\}$ ...
10
votes
3answers
688 views

A very challenging probability question

In a certain 2-player game, the winner is determined by rolling a single 6-sided die in turn, until a 6 is shown, at which point the game ends immediately. Now, suppose that k dice are now rolled ...
2
votes
4answers
98 views

Finding an algebraic proof for $r{n \choose r} = n{n-1 \choose r-1}$ [closed]

I can't seem figure this proof out. How are both sides equal. $$r{n \choose r} = n{n-1 \choose r-1}$$
0
votes
2answers
57 views

How do I prove this bijection?

The number of $n$-digit binary numbers with exactly $k$ $1$s equals the number of $k$-subsets of $[n]$. I think i'm on the right track, but I'm confused on how to write how it's onto and 1-1. This ...
3
votes
3answers
332 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 ...
-1
votes
5answers
728 views

Find the number of integers between 1 and 100 that are divisible by both 3 and 4.

Question in proofs homework in our "sets" unit. I'm not sure if I need to use unions/intersects. Just confused as how to begin to solve this question. Help please!
0
votes
1answer
53 views

Prove $C(n) = \frac{1}{\sqrt{5}}((\frac{1 + \sqrt{5}}{2})^{n + 2} - (\frac{1 - \sqrt{5}}{2})^{n + 2})$

Given: $1 + \frac{1 + \sqrt{5}}{2} = (\frac{1 + \sqrt{5}}{2})^{2}$ $1 + \frac{1 - \sqrt{5}}{2} = (\frac{1 - \sqrt{5}}{2})^{2}$ If C(n) is the number of 0/1 strings of length n that do not contain ...
1
vote
2answers
111 views

Proving ${n \choose k}={n \choose n-k}$ using a bijection

Let $S$ be an $n$-order set. Prove by bijection that the number of $k$-order subsets is equal to the number of $(n-k)$-order subsets: $${n \choose k}={n \choose n-k}.$$ Could someone help me ...
2
votes
1answer
118 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
1answer
54 views

Prove that for all integers $n > 3$, $y_{n+1} = 2 x_n$

Let $x_n$ be the number of 0/1 strings of length $n$, not including the sequence 010. Let $y_n$ be the number of 0/1 strings of length $n$, not including 0011 or 1100. Prove that for all integers $n ...
0
votes
1answer
22 views

Proving by induction propositions of the type $P(n_1, n_2, …, n_k)$, where $n_1, n_2, …,$ and $n_k$ are natural numbers

For example: I've seen proofs of the multinomial theorem that use induction in the number of terms that are elevated at some power, but none that use induction in the exponent instead of using it in ...
3
votes
1answer
91 views

$K_{1,3}$ packing in a triangulated planar graph

I am trying to show that every planar triangulated graph $G=(V,E)$ with $|V| \ge 5$ has an edge decomposition into $|V| - 2$ groups of $K_{1,3}$. In other words, that we can pack $|V| - 2$ instances ...
2
votes
4answers
109 views

Show Pascal triangle properties

I need to prove two pascal triangle properties: 1) $\sum_{k=0}^{n}\binom{p+k}{k}=\binom{p+n+1}{n}$ 2) $\sum_{k=0}^{n}\binom{k}{p}=\binom{n+1}{p+1}$ I need some advice on how to approach to this ...
2
votes
4answers
80 views

Proof strategy to show $\large \sum_{0 \ \le \ x \ \le \ a} \normalsize \binom{a}{x} \binom{b}{n+x} = \binom{a+b}{a+n} $

The following two combinatorial identities are taken from a textbook. $$\begin{align} &\large \sum_{0\ \le \ x \ \le \ n} \normalsize \binom{a}{x} \binom{b}{n-x} = \binom{a+b}{n} \tag{10} \\ ...
2
votes
2answers
67 views

combinatorics proof with i - Peter J. Cameron book

I'm working through Peter J. Cameron's combinatorics book and I'm having trouble understanding one of his proofs. In proposition 3.3.3, he states: "If n is a multiple of $8$, then the number of sets ...
0
votes
1answer
68 views

Finishing proof of identity $\sum_{k=b}^{n} \binom{n}{k} \binom{k}{b} = 2^{n-b} \binom{n}{b}$

The identity $$ \sum_{k=b}^{n} \binom{n}{k} \binom{k}{b} = 2^{n-b} \binom{n}{b}\ $$ is one of a few combinatorial identities I having been trying to prove, and it has taken me way too long. I am ...
0
votes
1answer
62 views

Find the number of subsets $S$ of $X$ (of any size) that satisfy the following property

Let $X=\{1,2,\dots,10\}$ define the relation $R$ on $X$ by: for all $a,b\in X$, $a\mathrel{R}b \iff ab$ is even. 1) Find the number of subsets $S$ of $X$ (of any size) that satisfy the ...
1
vote
1answer
45 views

how many elements does Ia have?

Let $A=\{1,2,3,4\}$. Let $F$ be the set of all functions from $A$ to $A$. Let $R$ be the relation on $F$ defined by $f,g \in F$ $f R g \Leftrightarrow |f(A)|=|g(A)|$ $f(A)=\{f(x): x\in A\}$ ...
0
votes
2answers
77 views

Let S = {1,2…10} Let R be the relation on P(S), the power set of S, defined by: for any X,Y ∈ P(S),

Let S = {1,2....10} Let R be the relation on P(S), the power set of S, defined by: for any X,Y ∈ P(S), XRY <=> X∩Y=∅ is it true that ∀X∈P(S),∃Y∈P(S) so that (X,Y)∈R? I dont know what is (X,Y)? ...
1
vote
1answer
134 views

How to prove that if n and k are integers with 1 ≤ k ≤ n, then k*(n C k)=n(n−1 C k−1) combinatorally?

I am having with combinatorial proofs. My professor says to come up with a scenario so that we can connect both sides by double counting but I am clueless.
0
votes
1answer
58 views

Convergence of formal power series substitution

Prove that the substitution of formal power series $F(G(x))=\sum_{k\geq0}f_k \frac{G(x)^k}{n!}$ converges for every $F$ if and only if $G(0)=0$
3
votes
2answers
353 views

Formal power series, the Chain Rule and the Product Rule.

Definitons Let $$\mathbb{C}[[x]] := \left\{ \sum_{n\geq 0} a_n x^n : a_n \in \mathbb{C} \right\}$$ be the set of formal power series of $x$. Exercise i) If $F_1(x)$ and $F_2(x)$ are power series ...
1
vote
4answers
218 views

For all positive integers n,m,k where $n\ge m\ge k$ , $\binom {n}{m}\binom {m}{k}=\binom {n}{k}\binom {n-k}{n-m}$ [duplicate]

For all positive integers n,m,k where $n\ge m\ge k$ , $\binom {n}{m}\binom {m}{k}=\binom {n}{k}\binom {n-k}{n-m}$ Prove the following statements using combinatorial proofs. I can't come up ...
2
votes
1answer
136 views

Stirling numbers of second type [duplicate]

How can I do a combinatoric proof that for Stirling number of second type the equality if true: $${n\brace k} = \frac{1}{k!}\sum_{i=0}^{k}{k \choose i}i^n(-1)^{k-i}$$
5
votes
4answers
590 views

How to prove that $\sum_{k=0}^n \binom nk k^2=2^{n-2}(n^2+n)$ [duplicate]

I know that $$\sum_{k=0}^n \binom nk k^2=2^{n-2}(n^2+n),$$ but I cannot find a way how to prove it. I tried induction but it did not work. On wiki they say that I should use differentiation but I do ...
0
votes
2answers
61 views

Pigeonhole question and generalization

Let H be a regular hexagon with side length 1 unit. (a) Show that if more than 6 points are speci ed inside H then the points of at least one pair of them are at most 1 unit apart. (b) State and ...
2
votes
2answers
91 views

Pigeonhole Principle Exercise

Show that any subset of $\{1, 2, 3, ..., 200\}$ having more than $100$ members must contain at least one pair of integers which add to $201$. I think it is doable using the Pigeonhole Principle.