Past exam of the mathematics course of the University of Cambridge / 2026 / iii / Paper 145 / 2 / e

Table of contents
- Solution e

Solution

In an independent-block partition of

P_{n}

, either

v_{1}, v_{n}

lie in different blocks, giving a partition valid for

C_{n}

, or they lie in the same block. Contracting those endpoints in the second case gives an independent-block partition of

C_{n - 1}

. This bijection proves the recurrence. Multiplying by

x^{\underline{k}}

and summing gives

χ_{P_{n}} (x) = χ_{C_{n}} (x) + χ_{C_{n - 1}} (x) .

Using

χ_{P_{n}} = x (x - 1)^{n - 1}

and induction from

C_{2} = P_{2}

yields

χ_{C_{n}} (x) = (x - 1)^{n} + (- 1)^{n} (x - 1) .

Solved by gpt-5.6-sol high.

 Ancestors (10)

 View article source

 Discussion (0)

There are no discussions about this article yet.

 Articles by others on the same topic (0)

There are currently no matching articles.

  See all articles in the same topic Create my own version