Python tuple operaciones y recuento

Tengo la siguiente tupla. Quiero construir una cadena que produzca resultados como se indica en la salida. Quiero contar todos los elementos correspondientes a 'a', es decir, cuántos k1 se produjo wrt 'a' y así sucesivamente. hacer esto

a=[('a','k1'),('b','k2'),('a','k2'),('a','k1'),('b','k2'),('a','k1'),('b','k2'),('c','k3'),('c','k4')]

La salida debe estar en una cadena de salida = ""

 a k1  3
 a k2  1
 b k1  1
 b k2  3
 c k3  1
 c k4  1

Respuestas a la pregunta(2)

Su respuesta a la pregunta