MathDB

Number of permutations

Source: Japan Mathematical Olympiad Finals 1998, Problem 4

August 3, 2007

algebra proposedalgebra

Problem Statement

Let

c_{n, m}

be the number of permutations of

\{1, \ldots, n\}

which can be written as the product of

m

transpositions of the form

(i, i+1)

for some

i=1, \ldots, n-1

but not of

m-1

suct transpositions. Prove that for all

n \in \mathbb{N}

,

\sum_{m=0}^\infty c_{n, m}t^{m}= \prod_{i=1}^{n}(1+t+\cdots+t^{i-1}).

Back to Problems View on AoPS