View, Nodes categorized by field with counter just right to Category name
Amend your view as follows:

Add the category term as a field to the view, either straight as a field from the node, or as a relationship. Make sure to exclude this category field from display.



Choose your format for the view, and for the format settings, select the hidden category field you just added as 'Grouping Field Nr. 1'.



Your view should now categorise the content with the category as the headings for each group.

Now to add the count.

In the Advanced part of the view, click on Theme: Information. 



This open this window:



Now copy the name of a view override from the row 'Style Output' (underlined in red in screenshot'. The names to the left are to override the view in a very general way, and more the right it will target the view more specifically. Make it specific so that only this view is targeted.

Create a new file in your theme's templates folder with the name you just copied.

Paste this code in your file (it comes from clicking on the blue 'Style output' link in the view's theme information window, with a slight adaption).

&lt;?php

/**
 * @file
 * Default simple view template to display a list of rows.
 *
 * @ingroup views_templates
 */
?&gt;
&lt;?php if (!empty($title)): ?&gt;
  &lt;h3&gt;&lt;?php print $title . ' (' . count($rows) . ' ' . format_plural(count($rows), 'document', 'documents') . ')'; ?&gt;&lt;/h3&gt;
&lt;?php endif; ?&gt;
&lt;?php foreach ($rows as $id =&gt; $row): ?&gt;
  &lt;div&lt;?php if ($classes_array[$id]) { print ' class="' . $classes_array[$id] .'"';  } ?&gt;&gt;
    &lt;?php print $row; ?&gt;
  &lt;/div&gt;
&lt;?php endforeach; ?&gt;


The last thing to do is to clear your cache.