# Manipulating combinatorial structures

I'm reading Knuth et al's Concrete Mathematics, chapter 7 on generating functions. They motivate the discussion by solving a combinatorial problem: find $T_n$, the number of ways in which one can arrange dominoes in a $2\times n$ area. The solution uses dominoes as if they were variables, some kind of abstract algebra. Is that safe? Are there other ways in which one can play with structures and get some useful results?

-
Yes, it’s safe. It’s a simplified version of working with combinatorial species. –  Brian M. Scott Feb 2 '13 at 0:19
Algebraic notation is a notable thing. It handles all kind of abuse in stride. ;-) –  vonbrand Feb 2 '13 at 0:34

Some interesting further readings on generating functions are Pólya's "On Picture Writing", The American Mathematical Monthly 63(10), 689-697 (1956). Pólya also defines series on objects (coins, in his case) and gets suprising answers that way. There is a complete theory of formal series, where you just don't care if the stuff converges, and you can justify rigurously that all the suspect operations that would make your neighborhood calculus teacher cringe are in fact quite kosher. I'm no expert in this, but Kauers and Paule's "The Concrete Tetrahedron", Springer (2011) has a very clear chapter on the matter. The article in Wikipedia on the matter is also nice.

-