Count posts within a custom post type and specific taxonomy and terms?

An alternative solution using WP_Query would be:

$args = array(
  'cat' => 4,
  'post_type' => 'videos'
);
$the_query = new WP_Query( $args );
echo $the_query->found_posts;