We consider a particular case of upper Hessenberg matrices, in which all subdiagonal elements are -1. We investigate three type of matrices related to polynomials, generalized Fibonacci numbers, and special compositions of natural numbers. We give the combinatorial meaning of the coefficients of the characteristic polynomials of these matrices.