An increase in the total number of seats to be apportioned causes a state to lose a seat.
The Alabama Paradox first surfaced after the 1870 census. With 270 members in the House of Representatives, Rhode Island got 2 representatives but when the House size was increased to 280, Rhode Island lost a seat. After the 1880 census,C. W. Seaton (chief clerk of U. S. Census Office) computed apportionments for all House sizes between 275 and 350 members. He then wrote a letter to Congress pointing out that if the House of Representatives had 299 seats, Alabama would get 8 seats but if the House of Representatives had 300 seats, Alabama would only get 7 seats.
An increase in a states population can cause it to lose a seat.
The Population Paradox was discovered around 1900, when it was shown that a state could lose seats in the House of Representatives as a result of an increase in its population. (Virginia was growing much faster than Maine--about 60% faster--but Virginia lost a seat in the House while Maine gained a seat.)
New States Paradox
Adding a new state with its fair share of seats can affect the number of seats due other states.
The New States Paradox was discovered in 1907 when Oklahoma became a state. Before Oklahoma became a state, the House of Representatives had 386 seats. Comparing Oklahoma's population to other states, it was clear that Oklahoma should have 5 seats so the House size was increased by five to 391 seats. The intent was to leave the number of seats unchanged for the other states. However, when the apportionment was mathematically recalculated, Maine gained a seat (4 instead of 3) and New York lost a seat (from 38 to 37).