组合数学 (Fall 2024)/Problem Set 1

Problem 1

How many [math]\displaystyle{ n\times m }[/math] matrices of [math]\displaystyle{ 0 }[/math]'s and [math]\displaystyle{ 1 }[/math]'s are there, such that every row and column contains an even number of [math]\displaystyle{ 1 }[/math]'s? An odd number of [math]\displaystyle{ 1 }[/math]'s?

Problem 2

• There is a set of [math]\displaystyle{ 2n }[/math] people: [math]\displaystyle{ n }[/math] male and [math]\displaystyle{ n }[/math] female. A good party is a set with the same number of male and female. How many possibilities are there to build such a good party?
• Try to express the answer using one binomial coefficient and provide a combinatorial proof.

Problem 3

Given [math]\displaystyle{ 0\leq k\leq n }[/math], prove that

[math]\displaystyle{ \sum_{i=0}^{\lfloor k/2\rfloor} \binom{n}{k-i}\binom{k-i}{i} = \sum_{j=0}^{\lfloor k/3\rfloor}(-1)^j\binom{n}{j}\binom{k-3j+n-1}{n-1} }[/math].

(Hint: Consider the number of ways to to place [math]\displaystyle{ k }[/math] indistinguishable balls into [math]\displaystyle{ n }[/math] boxes, with no more than [math]\displaystyle{ 2 }[/math] balls in each box.)

Problem 4

• Suppose [math]\displaystyle{ n,k\geq 1 }[/math] and [math]\displaystyle{ j=\lfloor k/2\rfloor }[/math]. Let [math]\displaystyle{ S(n,k) }[/math] denote a Stirling number of the second kind. Give a generating function proof that [math]\displaystyle{ S(n,k)\equiv \binom{n-j-1}{n-k} \pmod 2 }[/math].
• State and prove an analogous result for Stirling numbers of the first kind.

Problem 5

For the following problems, provide a formula and explain your answer.

• Count the number of ways to place [math]\displaystyle{ n }[/math] chess pieces on an [math]\displaystyle{ n\times n }[/math] chessboard such that each row, each column, and the main diagonal have at least one chess piece.
• Let [math]\displaystyle{ n }[/math] be even. Count the number of ways to place [math]\displaystyle{ n }[/math] chess pieces on an [math]\displaystyle{ n\times n }[/math] chessboard such that each row, each column, and both diagonals have at least one chess piece.