In this paper, we define new a recurrence relation called k-Tribonacci numbers. Further we also define k-Tribonacci matrix related with the k-Tribonacci numbers. Then we give factorizations of the Pascal matrix involving the k-Tribonacci matrix. Finally we obtain some combinatorial formulas involving k-Tribonacci numbers.