SELECT COUNT(*) does a scan?

When I do an EXPLAIN SELECT COUNT(*) FROM tablename, I noted that it
does a table scan.  I thought PG had some sort of table stat that kept
track of the current number of rows in a table, but that doesn't appear
to always be the case.

It seems that right after a VACUUM ANALYZE, that command is very fast
(on a table with 100,000+ rows), but it can also get quite slow, as if a
table scan is taking place.

Does this make sense?  Is there an algorithm that says to use the stats
from analyze only until sufficient updates/inserts/deletes have taken
place to make them "out of date"?

David