Была на Руси в древние времена свадебная хороводная игра, называлась она "А мы просо сеяли". Игра сопровождалась девичьей песней.
В ней были такие строчки: А вашего полку убыло, убыло, - Ой, дид-ладо, убыло, убыло! (распевали незамужние девушки)- А нашего полку прибыло, прибыло, - Ой, дид-ладо, прибыло, прибыло! (вторили юным девицам их подруги, выданные замуж).
Их поют, когда участницы одной из играющих сторон берут в плен другую.
Смысл происходящего заключался в переходе недавно вышедших замуж девушек в статус замужних женщин и круг семейных дам.
Отсюда и появилось выражение "в нашем полку прибыло".
А русское слово "полк" произошло от немецкого "Folk" (в переводе - народ), т.е. означало в данном фразеологизме прибавление в рядах определенной группы народа.