A generalization of the airplane seating puzzle

Let me say immediately that this isn't my puzzle. Someone posted it earlier, and I was working on it when it was deleted. It seems to me to be an excellent puzzle, too good be deleted, so I'm reposting it. If there's a good reason why I should delete this puzzle, please tell me.

In some world, everyone has $k\geq1$ feet. Everyone wears $k$ identical socks, but the socks vary from person. Each person can easily identify his own socks. When the people go to worship, they remove their socks and place them in a communal pile. At the close of the service, each person removes his socks from the pile.

One day, the first person to leave is in a hurry, and grabs $k$ socks uniformly at random. After that, each person removes all of his own socks from the pile, and if any are missing, he randomly picks just enough so that he will have one for each foot.

What is the probability that the last person to leave will find exactly $j$ of his own socks in the pile, for $0\leq j \leq k?$ (When $k=1,$ this is the airline seating puzzle.)

I've done some experimenting by computer simulation for small $n$ and $k,$ and the results lead me to believe that for given $k,$ the answer is independent of the number of people $n\geq2.$ Of course, when $n=2$ the puzzle is trivial, so I guess that the answer is $$ {{k\choose k-j}{k\choose j}\over{2k\choose k}}, 0\leq j\leq k $$ I don't have a clue how to prove this, though. Any ideas?

When the last person looks at the pile, which socks could possibly be there? Their own socks, and the socks of the first person. That's it. Any sock belonging to any other person will have been removed from the pile when that person picked up their socks.

Therefore, the question is simply this: from a set of $k$ black and $k$ white socks, $k$ socks are picked uniformly at random (we know that $k$ socks eventually remain, and everyone is indifferent to picking black or white socks). What is the probability that $j$ white socks remain?

This is clearly answered by your formula.