In this paper, we define the complex-type Padovan-$p$ sequence and then give the relationships between the Padovan-$p$ numbers and the complex-type Padovan-$p$ numbers. Also, we provide a new Binet formula and a new combinatorial representation of the complex-type Padovan-$p$ numbers by the aid of the $n$th power of the generating matrix of the complex-type Padovan-$p$ sequence. In addition, we derive various properties of the complex-type Padovan-$p$ numbers such as the permanental, determinantal and exponential representations and the finite sums by matrix methods.