Difficulty:

[1] easy

[2] moderately difficult

[3] 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.[1]

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

proof

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

2.[1]

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

proof

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.[2]

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

proof

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 .