I want to introduce formal linear combinations in an upper-level undergraduate combinatorics class. By this I mean expressions like $7 \operatorname{cat} + 5 \operatorname{dog} - \sqrt{2} \operatorname{molerat}$ (and infinite versions thereof), as well as (situation-dependent) rules of multiplication on such expressions.
Formally speaking, this means that I have a commutative ring $R$ and define the free $R$-module $R^{(I)}$ for a set $I$ (usually not $\left\{1,2,\ldots,n\right\}$) and its "completion" $R^I$, and define some $R$-algebra structures on these modules. I will briefly introduce commutative rings first, but I cannot expect anyone to have prior experience with them, and so I would like to avoid direct sum, direct products, universal properties, etc.. The two examples I really want to get to are the following:
The polynomial ring $R\left[X\right]$ and the ring $R\left[\left[X\right]\right]$ of formal power series. (A major pain point with US student audiences is having to unteach the misconceptions that polynomials are polynomial functions and that power series have to converge.)
The group ring $R\left[S_n\right]$ of the symmetric group. (The students have seen a lot of permutations; my plan is to let them have some fun with sums of permutations -- e.g., Young-Jucys-Murphy elements, Tsetlin libraries, etc.)
But I am interested in other, motivating examples -- ideally baby versions of these objects I can have them play around with that show the structure and give some hint of its usefulness (which means, in particular, that there should be a multiplication -- linear combinations per se are boring). I know of only one for now:
- The Hardy-Weinberg principle can be proven using a tailor-made non-associative ring: Consider the free module with basis $\left(a,A\right)$, and define a (non-associative) multiplication on it by $a^2 = a$ and $A^2 = A$ and $aA = Aa = \dfrac{1}{2}\left(a+A\right)$. This multiplication is literal multiplication, as in "be fruitful and multiply", as $xy$ is the (probability distribution of) the allele of the offspring of an individual with allele $x$ with an individual with allele $y$. Now, the Hardy-Weinberg principle boils down to the identity $\left(pa+qA\right)^2 = \left(p+q\right)\left(pa+qA\right)$ in this ring, which is easily checked.
I suspect this is just an example for more general probability-type implications -- is there such a thing as a Markov chain with several transition matrices?
