In deb
based distribution perf
is usually provided by a package with a name starting with linux-tools
and yes, the version X of perf
it's not designed to run on the kernel number Y, it's a program that is strictly tied to the kernel.
For example on Debian/Ubuntu you can write
sudo apt-get install linux-tools-$(uname -r)