I think there´s something random about mercenary appearance, but an active war going on close to the inns location seems to increase the chance of mercs´ availability.