The (US) ATP prep book I'm currently wading through quotes 14 CFR 121.391 and says...
One or more flight attendants are required on each passenger carrying airplane that has more than nine passenger seats. The number of flight attendants is determined by the number of installed passenger seats - not by the actual number of passengers on board.
One flight attendant is required on airplanes that can seat from 10 to 50 passengers. Two flight attendants are required on airplanes having a seating capacity from 51 through 100 seats. After that, an additional flight attendant is required for each unit (or partial unit) of 50 seats above 100.
The odd thing is I also though the lower limit was 19. This however refers to "A public address system and a separate crewmember interphone system must be installed on all airplanes with a seating capacity of more than 19 seats"