You can have a total party of 4, so in a single player game thats 1+3 companions.
You can get new ones, and you can get old ones back. If you go back to where you found the red prince he will go there after you send him away.