Let’s see: how to make it intuitive? I am not sure I have a satisfying answer, except to note that the simplest example of this phenomenon is Pascal’s triangle itself: sketch out what happens if the entries on the left of all but the bottom row are 0’s and the entry on the left of the bottom row is 1. Actually draw this out! After a time, a slice of Pascal’s triangle will appear, turned on its side. The entries along the top row will be C(n,k) (where there are k rows); we can think of this as a polynomial in n, or as a combination in n, either way.

The more general case is just a linear combination of multiples of this example, for different k’s. 

Don’t know that that is much more satisfying, though!

A really terrific reference on closely related topics (particularly, Stirling numbers) is in the beginning of Chapter 1, Vol 1 of Donald Knuth’s The Art of Computer Programming; don’t overlook the exercises!

The reference that tipped us off to this, but says less than we have said here, is Martin Gardner’s Colossal Book of Mathematics.