3
$\begingroup$

I want to make a generating function for a combinatorics problem with $2$ different simultaneous constraints. In the one variable cases, one of the constraints would use an ordinary generating function, the other an exponential generating function. So I'm not sure how to combine them into a multivariate generating function.

Let's make up the following problem to illustrate:

Using the ten digits $0$-$9$, I can make a length $k$ string, eg. for $k=5$, the string $27485$.

Now say I want the number of $k$-strings (the number of all possible arrangements of length $k$ using the digits $1$-$9$), that satisfy not just one but $2$ conditions, for example:

  1. The $k$-string must have $1$ or $2$ occurrences of the digit "$4$".
  2. The sum of the digits in the $k$-string must be $N$.

Make things concrete: use $k=3$, and $N=10$: If it was the just the first constraint, I think I could use the exponential generating function:

$$g(x) = \left[x + \frac{1}{2!}x^2\right]\cdot\left[1 + x + \frac{1}{2!}x^2 + \frac{1}{3!}x^3\right]^8.$$

The first term for the "$4$" digit which has to occur once or twice, the second term raised to the $8$ is for the other $8$ digits which can occur any number of times. Then I would look for the coefficient of $x^3$ and multiply by $3!$.

And if it were only the $2^{\text{nd}}$ constraint, I think I could do:

$$g(y) = \left[1 + y + y^2\right]\cdot \left[1 + y^2 + y^4\right]\cdot \left[1 + y^3 + y^6\right]\cdots\left[1+y^8+y^{16}\right]\cdot\left[1+y^9+y^{18}\right],$$

then look for the coefficient of $y^N$.

How do I combine these constraints? Do I just multiply them together, $g(x,y) = g(x)g(y)$ and then look for the coefficient of $(1/k!)x^ky^N$?

$\endgroup$
0
$\begingroup$

If we let $x$ be the enumerator for the sum of digits and $y$ be the enumerator for the number of digits then we can form the generating function for occurrences of $4$

$$f(x,y)=(x^4)\frac{y}{1!}+(x^4)^2\frac{y^2}{2!}$$

Powers of $y$ count the number of $4$s in the string and powers of $x$ are multiples of $4$.

Similarly we can form the generating function for occurrences of each digit $0$-$9$ apart from $4$

$$\begin{align}g(x,y)&=\sum_{i\ge 0}(1+x+x^2+\underbrace{x^3+x^5}_{\text{no $x^4$ term}}+\cdots +x^9)^i\frac{y^i}{i!}\\[1ex] &=\sum_{i\ge 0}\left(\frac{1-x^{10}}{1-x}-x^4\right)^i\frac{y^i}{i!}\\[1ex] &=\exp\left(y\left(\frac{1-x^{10}}{1-x}-x^4\right)\right)\end{align}$$

Here powers of $y$ count occurrences of the other digits and $x$ counts the sum of those digits.

Then the desired count for strings length $k$ with sum $N$ is

$$\left[x^N\frac{y^k}{k!}\right]f(x,y)g(x,y)$$

So, for example inputting the following into sage

y=var('y')
f(x,y)=x^4*y+(x^4)^2*y^2/2
g(x,y)= e^(y*((1-x^10)/(1-x)-x^4))
taylor(f(x,y)*g(x,y),(x,0),(y,0),20).coefficient(x^10).coefficient(y^5)*factorial(5)

calculates the coefficient of $x^{10}y^5/5!$ and yields the output

360

So there are $360$ strings that use digits $0$-$9$, have either $1$ or $2$ occurrences of $4$, are length $5$ and have digit sum $10$.

Note that I have allowed for $10$ digits $0$-$9$ because the question mentions both cases of using $10$ digits and using $9$ digits.

This method is easily modified for the latter case: simply remove the leading $1$ from $1+x+x^2+x^3+x^5+\cdots +x^9$ in $g(x,y)$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.