Using generating functions to translate a word problem into a recurrence relation?

81 Views Asked by At

There are n job candidates that are being considered for a job and must complete a certain task to move forward. They are divided randomly into 2 groups, A and B. The interviewees in group A must take a test in one of 4 languages while those in group B must arrange themselves around a circular table and discuss one of 3 given topics (two circular arrangements are considered to be the same if each student has the same person sitting on his/her left in the two arrangements).

I am wondering how to go about translating this problem into a product of generating functions?

Any help here? I know that the number of ways to arrange people around a circular table is $(n-1)!$ but how to combine all the pieces above to come up with a product is not so clear to me...

Edit: Since the problem is poorly worded, I have edited out the last component and left it as is so the answer below is satisfactory.

1

There are 1 best solutions below

2
On BEST ANSWER

Since the candidates are divided randomly, you want exponential generating functions. For the group A task that is $\sum_{n\ge 0}4^n\frac{x^n}{n!}=e^{4x}$, if we're interpreting the problem correctly. For the group B task it seems to be

$$1+\sum_{n\ge 1}3(n-1)!\frac{x^n}{n!}=1+3\sum_{n\ge 1}\frac{x^n}n=1-3\ln(1-x)\;.$$

The product is $e^{4x}\big(1-\ln(1-x)\big)$, and the coefficient of $x^n$ is

$$4^n+3\sum_{k=0}^{n-1}\binom{n}k4^k(n-k-1)!=4^n+3\sum_{k=1}^n\binom{n}k4^{n-k}(k-1)!\;.$$

I don't at the moment see either a series expansion of the product or a nice recurrence, and it's 3:30 a.m. here, so I'll post this in case it's of some use and take another look tomorrow.