Interesting question about exponential generating function of the number of partitions under a certain statistic.

Question

Find the exponential generating function of the number of partitions of $[n]$ ( according to) under the statistic of the number of blocks that contain an even number of elements (a block $K$ such that $|K|$ is even).

Then find the expectation (average) of blocks with even number of elements.

There are many questions with similar ideas, but are different.

So, I said

For $n=1$ we have the partition: $\{\{1\}\}$

For $n=2$ we have $\{\{1,2\}\} , \{\{1\},\{2\}\}$

For $n=3$ we have these partitions: $$\{ \{ 1,2,3 \} \}, \{\{1,2\}, \{ 3 \}\} , \{ \{ 1,3 \},\{ 2 \} \} , \{ \{2,3\},\{1\}\}, \{\{ 1 \}, \{ 2 \}, \{3 \} \}$$

If $x$ counts a length of a single number then:

$A_1(x)=x$ , $A_2(x)=2x^2/2!$ , $A_3(x)=5x^3/3!$

Now let $q$ counts the number of blocks with even number of elements.

Then,

$A_1(q,x)=x$

$A_2(q,x)= \frac{x^2}{2 !}(q+1)$

$A_3(q,x)=\frac{x^3}{3!} (3q+2)$

I was not able to find the recurrence relation for $A_n(q)$ ($A_0(q)=1$) in order to find the exponential generating function.

Can you provide me any kind of support.

Answer 1

If I understand correctly, you want $$A_n(q)=\sum _{\pi \vdash [n]}q^{ev(\pi)},$$ where $ev(\pi):=\text{number of even blocks in }\pi.$

Well, suppose you know $A_n,$ then you want to create all blocks with $n+1$ elements. So you want to choose the elements that are going to be in the block of $n+1.$ This corresponds, without the polynomials to the recursion of Bell numbers $$B_{n+1}=\sum _{i=0}^n\binom{n}{i}B_{n-i}.$$ Now, taking care of the polynomial, notice that there are two cases. Either we place $n+1$ in a block with even elements or in an odd one. If we do place it with odd elements we are forming one even block per partition on $B_{n-i}.$ So you have that $$A_{n+1}(q)=q\sum _{i\text{ odd}}\binom{n}{i}A_{n-i}(q)+\sum _{i\text{ even }}\binom{n}{i}A_{n-i}(q).$$ Sage obtains the following polynomials for $n$ up to 10:

x |--> 1
x |--> x + 1
x |--> 3*x + 2
x |--> 3*x^2 + 7*x + 5
x |--> 15*x^2 + 25*x + 12
x |--> 15*x^3 + 60*x^2 + 91*x + 37
x |--> 105*x^3 + 315*x^2 + 329*x + 128
x |--> 105*x^4 + 630*x^3 + 1533*x^2 + 1415*x + 457
x |--> 945*x^4 + 4410*x^3 + 7623*x^2 + 6297*x + 1872