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

From TCS Wiki
Jump to navigation Jump to search
Gispzjz (talk | contribs)
Gispzjz (talk | contribs)
Line 7: Line 7:


== Problem 3 ==
== Problem 3 ==
Given <math>0\leq k\leq n</math>, prove that <math>\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>k</math> indistinguishable balls into <math>n</math> boxes, with no more than <math>2</math> balls in each box.)
Given <math>0\leq k\leq n</math>, prove that <center><math>\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>.</center> (Hint: Consider the number of ways to to place <math>k</math> indistinguishable balls into <math>n</math> boxes, with no more than <math>2</math> balls in each box.)


== Problem 4 ==
== Problem 4 ==

Revision as of 12:43, 19 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

  • 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 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.
  • 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 diagonal have at least one chess piece.