MathDB

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}).

4