SF2708 KOMBINATORIK, 2008
PROBLEM SET 2/4
Each exercise is worth ¯ve points. You may get partial credit for non-useless,
non-perfect solutions. Hand in your solutions no later than April 11.
1.Letkandnbe positive integers. Prove that the following are all equal:
²The number of partitions ofnwhere each part occurs at most 2k¡1 times.
²The number of partitions ofnwith no part divisible by 2k.
²The number of partitions ofnwhere parts that are divisible bykoccur at
most once each.
2.Give a combinatorial proof of the recursionD(n) = (n¡1)(D(n¡1)+D(n¡2))
for the derangement numbers (Stanley'sx2, equation 14).
3.In this exercise you shall reprove the principle of inclusion-exclusion using gen-
erating functions.
Letf; g: 2
[n]
!Rbe functions that satisfyg(S) =
P
T¶S
f(T) for allSµ[n].
De¯ne
G(x1; x2; : : : ; xn) =
X
Sµ[n]
f(S)(1 +x1)
ÂS(1)
(1 +x2)
ÂS(2)
: : :(1 +xn)
ÂS(n)
;
whereÂS: [n]! f0;1gis the characteristic function which is one on elements ofS
and zero elsewhere.
a)Show thatG(x1; : : : ; xn) =
P
Sµ[n]
g(S)x
ÂS(1)
1
: : : x
ÂS(n)
n.
b)ConsiderG(x1¡1; : : : ; xn¡1) and deduce a formula forf(S) in terms ofg.
4.LetMm;nbe the set of 0;1-matrices of sizem£nsuch that every row and every
column contains at least one 0. Show that
jMm;nj=
n
X
k=0
(¡1)
k
µ
n
k
¶
(2
n¡k
¡1)
m
:
5.Find the number of ways to choosekpoints from a collection ofmdistinguishable
points arranged in a circle if each pair of chosen points must be separated by at
leastdpoints.

2
6.Letf(n) be the number of permutations¼2S2nsuch that¼(i)> n¡ifor all
i2[2n]. Show that
f(n) =
n
X
k=0
(¡1)
n+k
S(n; k)(n+k)!:
7.Given any functionf: [m]![n] andi2[n], letf
¡1
(i) denote the setfj2[m]j
f(j) =ig. Letk2N. Show that the number of functionsf: [m]![n] such that
jf
¡1
(i)j 6=kfor alli2[n] is
n
X
j=0
(¡1)
j
µ
n
j
¶µ
m
k; : : : ; k; m¡kj
¶
(n¡j)
m¡kj
;
where \k; : : : ; k" in the multinomial coe±cient means thatkappearsjtimes.
8.Letp=p(x1; : : : ; xn)2R[x1; : : : ; xn] be a polynomial of degreen. Given
k2 f0;1; : : : ; ng, de¯ne¾
k
(p)2R[x1; : : : ; xn] to be the sum of the
¡
n
k
¢
polynomials
obtained by lettingkvariables inpvanish in all possible ways. That is,
¾
k
(p) =
X
1·i1<¢¢¢<ik·n
pjxi
1
=¢¢¢=xi
k
=0:
Prove that
n
X
k=0
(¡1)
k
¾
k
(p) =cx1: : : xn;
wherecis the coe±cient in front ofx1: : : xninp.
9.Consider the complete bipartite graphKn;n,n¸2. Remove from it the edges
that belong to some ¯xed Hamiltonian cycle. How many complete matchings does
the resulting graph have?
1
1
Let us recall some graph-theoretic terminology. The graph Kn;nhas vertex set
fx1; : : : ; xn; y1; : : : ; yngand edgesfxi; yjgfor all (i; j)2[n]
2
. AHamiltonian cycleis a con-
nected subgraph containing all the vertices in which each vertex is contained in precisely two
edges. Acomplete matchingis a subgraph containing all the vertices in which each vertex is
contained in precisely one edge.