Combin.PS1

My Solution for Combinatorics for the Fall 2015 semester, Problem Set 1. Keep your Academic Integrity plz.

Try Firefox if your web browser (e.g. Chrome, IE) does not support MathML, a part of HTML5.

Combinatorics: Problem Set 1

Himemiya

1 Problem 1

1.1

Which is equivalent to distribute n distinct balls into k distinct bins unrestrictedly. Therefore the answer is

kn.

1.2

Which is equivalent to distribute n distinct balls into k distinct bins such that every bin contains at most 1 ball. Therefore the answer is

Pkn=k!(kn)!.

1.3

Everyone has (kr) ways to receive postcards. The n distinct persons implies exponent n. Therefore the answer is

(kr)n.

1.4

Which is equivalent to distribute m identical balls into n distinct bins unrestrictedly. Therefore the answer is

((mn))=(m+n1n1).

1.5

The m kinds of postcards implies the answer satisfyes the product rule. Therefore we multiply them all,

i=1k((min))=i=1k(mi+n1n1).

2 Problem 2

Assuming we chose i blue balls, then once we choose j red balls satisfying 2n(i+j)n and jn, i.e. nijn, we fixed a way to select 2n balls. Therefore the answer is

i=0nj=nin1 =i=0n(n(ni)+1)
=i=0n(i+1)
=(1+(n+1))n+12
=12(n+1)(n+2).

3 Problem 3

3.1

Consider the powerset of [n]. a2[n], ia, we connect an edge from a to a{i}. Then the LHS denotes the number of the edges in our graph.

Our graph contains 2n vertices, each vertex has degree of n. Therefore the number of edges is 2n×n/2, i.e.

i=0ni(ni)=k=1nk(nk)=n2n1.

3.2

k=1n+1k2(n+1k) =k=1nk2(n+1k)+(n+1)2
=k=1nk2(nk)n+1n+1k+(n+1)2
=(n+1)[k=1nk(nk1)+n+1]
=(n+1)[(1(n0)+2(n1)++(n+1)(nn))]
=(n+1)[k=0nk(nk)+i=0n(ni)]
=(n+1)[n2n1+2n].

Therefore

k=1nk2(nk)=n[(n1)2n2+2n1].

4 Problem 4

4.1

Let f0(i) denote the number of ’/’ in the left of x=i, and f1(i) denote the number of ’\’ in the left of x=i. Since the line can not be under x-axis, i,f0(i)f1(i). This implies the Catalan number. Therefore the answer is

(2nn)n+1.

4.2

Any line which consists of n ’/’ and n\’ and starts at (0,0) must end at (2n,0). Then the answer is 2n choose n, i.e.

(2nn).

5 Problem 5

Consider one of the ends of the rectangle, there can be a 2×1 block or a 2×2 block or two 1×2 blocks. Therefore

f(n)=f(n1)+2f(n2).

Notice that f(1)=1, f(2)=3, then f(0)=1. Let G(x) be the generating function we need, then

G(x) =n0f(n)xn
=1+x+n2f(n)xn
=1+x+n2(f(n1)+2f(n2))xn
=1+x+x2n0(f(n+1)+2f(n))xn
=1+x+x2(1+n1(f(n)+2f(n1))xn)+2x2G(x)
=1+x+x2(G(x)+2xG(x))+2x2G(x)
=1+x+3x2G(x)+2x3G(x)
G(x) =1+x13x22x3
=11x2x2
=1(1+x)(12x)
=13(212x+11+x)
=13(2n0(2x)n+n0(x)n).

Therefore

f(n)=13(2n+1+(1)n).

6 Problem 6

6.1

Let f0(n) denote the number of strings end with 0 and are at length of n. Similarly, f1(n) denote the strings end with 1. Notice that

f0(n)=f0(n1)+f1(n1)=sn1 (appending a 0)
f1(n)=f0(n1)=sn2 (appending a 1)
sn=f0(n)+f1(n)=sn1+sn2.

Since s1=2, s2=3, sn is the Fibonacci number begins with s0=1, s1=2.

6.2

Let f0(n) denote the number of strings end with 0 and are at length of n. Similarly, f1(n) denote the strings end with 01 and f2(n) denote 011. Notice that

f0(n)=f0(n1)+f1(n1)+f2(n2)=tn1 (appending a 0)
f1(n)=f0(n1)=tn2 (appending a 1)
f2(n)=f1(n1)=tn3 (appending a 1)
tn=f0(n)+f1(n)+f2(n)=tn1+tn2+tn3
t1=2
t2=4
t3=7
t0=1

Let G(x) denote the generating function we need, then

G(x) =n0tnxn
=1+2x+4x2+n3(tn1+tn2+tn3)xn
=1+2x+4x2+xn3tn1xn1+x2n3tn2xn2+x3n3tn3xn3
=1+2x+4x2+x(G(x)12x)+x2(G(x)1)+x3G(x)
G(x) =1+x+x21xx2x3.

7 Problem 7

7.1 Assuming the votes is distinguishable

Enumerate a vote of Han Meimei as the first vote, then the problem is reduced to p1 and q votes and we have to make sure the votes of Han Meimei is not less than votes of Li Lei in the whole vote counting process. This implies the Catalan numbers. We assign orders to q-th Catalan numbers and then insert the remaining votes of Han Meimei into the votes sequence. Hence the number of ways is

pCqq!q!i=2q+ip+q1i =pi=q+22qiq!q!q!i=2q+1p+q1
=(p+q1)!pq+1.

And the probability is

p(p+q1)!(q+1)(p+q)!=p(q+1)(p+q).

7.2 Assuming the votes is indistinguishable

Let f(p,q) denote the number of ways we desired. Consider p and q represent a location in Cartesian coordinate system, f(p,q) represents number of paths that start from (0,0) goto (p,q) and consisted of up or right and do not cross three line segments: (0,0)(1,0), (1,0)(1+q,q) and (q+1,q)(p,q). Observation:

f(p,q)={1(p=q=0)0(pqp<0)f(p1,q)+f(p,q1).

Then we observe that f(p,q)=i=0qf(p1,i)=i=qpf(i,q1).

I can not figure out a solution for this recursion. According to [1], the answer is C(p1,q) where C(n,k)=(n+kn)nk+1n+1 is the Catalan’s triangle. Therefore the answer we desired is

(p+q1q)pqp.

And the probability is

(p+q1q)pqp(p+qp)=pqp+q.

References

  • 1 Knuth, Donald E. ”The Art of Computer Programming, Volume 4: Generating All Trees; History of Combinationatorial Generation, Fascicle 4.” (2006).

CC BY-SA 4.0 Combin.PS1 by himemeizhi is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.