组合数学 (Fall 2024)/Problem Set 1: Difference between revisions

From TCS Wiki
Jump to navigation Jump to search
Gispzjz (talk | contribs)
Gispzjz (talk | contribs)
 
(4 intermediate revisions by 2 users not shown)
Line 10: Line 10:


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


== Problem 5 ==
== Problem 5 ==
For the following problems, provide a formula and your answer.
For the following problems, provide a formula and explain your answer.
* Count the number of ways to place <math>n</math> chess pieces on an <math>n\times n</math> chessboard such that each row, each column, and '''the main diagonal''' have at least one chess piece.
* Count the number of ways to place <math>n</math> chess pieces on an <math>n\times n</math> chessboard such that each row, each column, and '''the main diagonal''' have at least one chess piece.
* Let <math>n</math> be even. Count the number of ways to place <math>n</math> chess pieces on an <math>n\times n</math> chessboard such that each row, each column, and '''both diagonal''' have at least one chess piece.
* Let <math>n</math> be even. Count the number of ways to place <math>n</math> chess pieces on an <math>n\times n</math> chessboard such that each row, each column, and '''both diagonals''' have at least one chess piece.

Latest revision as of 12:14, 20 March 2024

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.