MathDB

Bijective counting of partitions and compositions

Source:

May 5, 2012

combinatorics unsolvedcombinatorics

Problem Statement

Q. For integers

m,n\geq 1

, Let

A_{m,n}

,

B_{m,n}

and

C_{m,n}

denote the following sets:

A_{m,n}=\{(\alpha _1,\alpha _2,\ldots,\alpha _m) \colon 1\leq \alpha _1\leq \alpha_2 \leq \ldots \leq \alpha_m\leq n\}

given that

\alpha _i \in \mathbb{Z}

for all

i

B_{m,n}=\{(\alpha _1,\alpha _2,\ldots ,\alpha _m) \colon \alpha _1+\alpha _2+\ldots + \alpha _m=n\}

given that

\alpha _i \geq 0

and

\alpha_ i\in \mathbb{Z}

for all

i

C_{m,n}=\{(\alpha _1,\alpha _2,\ldots,\alpha _m)\colon 1\leq \alpha _1< \alpha_2 < \ldots< \alpha_m\leq n\}

given that

\alpha _i \in \mathbb{Z}

for all

i

(a)

Define a one-one onto map from

A_{m,n}

onto

B_{m+1,n-1}

.

(b)

Define a one-one onto map from

A_{m,n}

onto

C_{m,n+m-1}

.

(c)

Find the number of elements of the sets

A_{m,n}

and

B_{m,n}

.

Back to Problems View on AoPS