Let $C_n$ be the number of ways to color a set of $n$-labelled balls using red, white and green where an even number of balls are to be colored red and an odd number of balls are to be colored green. Construct EGF for a formula of $C_n$


My Understanding

I superficially understand that we use EGF with so called "structures" when we are asked to find for each $n$ the number of ways to arrange the elements of an n-element set into such a structure given. (However still I don't know how the structure mathematically formalized.)

We have

$$F(x) = \sum_n^\infty f(n){x^n\over n!}$$ where $f(n)$ is the number of structures on an n-element. Thus may be in given problem, there are two or three structures depending on how we define the concept of structure.


I had searched bunch of example sturctues like following:

(1) The trivial structure of “set”: $F(x) = e^x$ .
(2) The trivial “1-element set” structure: $F(x) = x$.
(3) The trivial “empty set” structure: $F(x) = 1$.
(4) The trivial “non-empty set” structure: $F(x) = e^x − 1$.
(5) The trivial “even-size set” structure: $F(x) = \cosh(x) = (e x + e −x )/2.$
(6) The trivial “odd-size set” structure: $F(x) = sinh(x) = (e x − e −x )/2.$

With well-mathematically formulated structure, I think we can do addition or multiply to yield comprised version of EGF. However, still, to do addition or product, we first need to reveal a disjointness between what we want to add and multiply. Back to the problem, the bold-faced three structure - 1) colored in one of red/white/green 2) even number of reded 3) odd number of greened - looks not disjoint obviously.

Anyone can provide me any proper suggestion?


1 Answer 1


Hint: You might want to take a look at chapter 2: Labelled structures and exponential Generating functions of Analytic Combinatorics by P. Flajolet and R. Sedgewick.

This is a great presentation of admissible structures and their corresponding EGFs, mathematically formalized which might please you.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .