Counting Integer Partitions using Type Vectors

92 Views Asked by At

Use type vectors to establish the bijection between partitions of n into k parts with the smallest part equal to 1 and partitions of n-1 into k-1 parts.

Okay, I'm going to be honest and say I have no clue how to start. I know all the pre-requisite knowledge but can't seem to put the dots together.

Any and all help is appreciated! Thanks in advance :)

1

There are 1 best solutions below

0
On BEST ANSWER

Since partitions are lists ( however you want to encode them) of $k$ non-increasing natural numbers summing to $n$, if the minimum part is fixed to be $1$ it means that the last number of the list is just $1$ and you are left with an initial portion of the string of $k-1$ elements summing to $n-1$