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

Table of contents
- Solution c

Solution

Partitions of the vertices into independent blocks are the unlabeled colour-class partitions counted by the Graphical Stirling number. Therefore

χ_{P_{n}} (x) = \sum_{k} {n k}_{P_{n}} x^{\underline{k}} .

Since

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

, the ordinary Stirling identity applied to

x - 1

gives

x (x - 1)^{n - 1} = \sum_{k} {n - 1 k - 1} x^{\underline{k}} .

Uniqueness in the falling-factorial basis proves the claim.

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