Difficulty:

 easy

 moderately difficult

 difficult

[u] unsolved

[?] The result of the problem is known, but I am uncertain whether a combinatorial proof is known.

[∗] A combinatorial proof of the problem is not known. In all cases, the result of the problem is known.

## 1.Elementary Combinatorics

### 1.

PROBLEM: The number of subsets of an -element set is .

PROOF: A way of choosing element can be described as a binary number, and the number of ways is , vice versa.

### 2.

PROBLEM: A composition of is a sequence of positive integers such that . The number of compositions of is .

PROOF: Using “Stars and bars” method, there will be some bars to divide stars, and the space of bars is , so the number is the number of subsets of an -element set which is , vice versa.

### 3.

PROBLEM: The total number of parts of all compositions of is equal to .

PROOF: I consider that using power series is extremely easy, but we can’t use it…

Still using “Stars and bars” method, we consider that a bar in -th position can bring what contribution. If there is a bar in -th position, then other position is arbitrary to take a bar, whose number is , so a bar can take contributions, and while we should find that bars can divide parts, thus the answer is .