组合数学 (Fall 2024)/Problem Set 1: Difference between revisions
Jump to navigation
Jump to search
Created page with "== Problem 1 == How many <math>n\times m</math> matrices of <math>0</math>'s and <math>1</math>'s are there, such that every row and column contains an even number of <math>1</math>'s? An odd number of <math>1</math>'s? == Problem 2 == * There is a set of <math>2n</math> people: <math>n</math> male and <math>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 a..." |
|||
| (8 intermediate revisions by 2 users not shown) | |||
| 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 == | ||
* Let <math>S(n,k)</math> denote a Stirling number of the second kind. Give a generating function proof that <math>S(n,k)\equiv \binom{n-j-1}{n-k} \pmod 2</math>. | * 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. | ||
* 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''' | * 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
(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.