?

Combinatorics

Free Version

Upgrade subject to access all content

Moderate

Bijection Between Compositions and Subsets

COMBIN-BXLQEJ

A composition of $n$ into $k$ parts is a list of $k$ positive integers that sums to $n$. The number of compositions of $n$ into $k$ parts can be expressed as a binomial coefficient.

This suggests a bijection between the compositions of $n$ into $k$ parts and specified subsets of some set.

To setup the bijection, we think of lining up $n$ identical objects and then putting dividers between them to break them into blocks.

Based upon this idea, which of the below can you put into bijective correspondence with the compositions of $n$ into $k$ parts?

A

$k-1$ element subsets of the set of $n-1$ spaces between objects.

B

$k$ element subsets of the set of $n-1$ spaces between objects.

C

$k$ element subsets of the set of $n+1$ spaces between objects.

D

$k+1$ element subsets of the set of $n+1$ spaces between objects.