Sticks and stones

I have a vivid memory of a moment as a 13-year-old, aperch at the edge of a rickety wooden chair in a Starbucks cafe, a small offshoot of a local Barnes and Noble bookstore. The rows of bookshelves melted seamlessly into the warm aroma of brewed coffee and sugar crystals. I am staring down at a math book, filled with bite-size problems designed for middle school math competitions. These were the days when MATHCOUNTS and AMC dominated my mathematical education (iykyk).

The small, almost pocketsize math textbook is frayed at the edges, filled with highlighter marks and smudged pencil notes, evidence of my battle scars. “Sticks and stones,” the subheader reads. If I have 6 donuts and 4 flavors, how many ways can I order the donuts? Spoiler: \(\binom{9}{3} = 84\) because we can treat this as 9 sticks and 3 stones.

14 years later, here I am again, seeing the concept of sticks and stones reemerge into my life again. It’s funny how little moments like these bubble up and resurface, punctuating the continuity of my daily life. I also clearly remember thinking that 26 was such an old age. Joke’s on me.

This time, the concept is disguised under “stars and bars” after a quick query to ChatGPT. The context came up as I was reading a nice paper called “Why does deep and cheap learning work so well?” https://arxiv.org/pdf/1608.08225 which describes how neural networks can approximate polynomials with much fewer parameters, given some physical assumptions. The paper stated the basic fact that “there are \((n + d)!/(n!d!)\) coefficients in a generic polynomial of degree \(d\) in \(n\) variables,” which is when my flashback to sticks and stones arose. Since we basically need to distribute \(d+1\) degrees among \(n\) variables, we get the expression \(\binom{n+d}{n} = (n + d)!/(n!d!)\).

An echo from the past. Funny how cute formulas like this can trigger such memories of a life that seemed like just yesterday.