Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit

MAT 344

2022 S

Problem Set 1

Strings, Permutations and Combinations

Learning Objectives

These problems relate to the course learning outcomes:

● Prove combinatorial identities by counting a set of objects in two ways,

●  Construct counting problems which show the usefulness or limitations of combinato- rial tools, and

● Describe solutions to iterated processes by relating recurrences to combinatorial identities.

Combinatorial proofs

Give a combinatorial proof, showing that each formula counts the same collection, for these identities. Assume that all variables are non-negative integers.

1.  /m2(+)n、= /2(m)、+/2(n)、+ mn.

2. P (n, k) /、= /m(n)、P (m, k)

Describing solutions

Find a formula that describes the general solution to these counting problems, depending on n and k , and explain why it works.

3. An injective function f  :  [k] -  [n] is called  “up-down” if it is strictly increasing from 1 to j for some j, and strictly decreasing from j to k. The largest value will be f (j), and j is allowed to be 1 or k.  For example, if k = 3 and n = 8, the function f (1) = 3, f (2) = 7, f (3) = 5 is injective and up-down, and there are 224 possible injective, up-down functions. When k = 2, every injective function is also up-down, so there are n(n _ 1) of them. How many functions are injective and up-down?

4. If k divides n, how many ways can n people be split into k groups? For example, if k = 2 and n = 4, there are 3 ways: →AB, CD{, →AC, BD{, →AD, BC{. If k = 2 and n = 6, there are 10 ways, while if k = 3 and n = 6, there are 15.

5. How many positive integers are there less than 10n  with a digit sum of 10? There are 9 less than 102 , and 63 less than 103 .

Problem writing

6. Give an example of a counting problem that can be solved using strings, permutations, or combinations, and explain your solution.