4
$\begingroup$

I've been struggling with this problem for a while now, but I'm not sure how to proceed :

Given a set of $n$ distinct objects, we seek to find the number of ways we can distribute all of the elements belonging to this set to $3$ kinds of people.

$a$ of them want to get an odd number of objects, $b$ of them want to get an even number of objects and $c$ of them don't care about the parity of the objects they receive.

In how many ways can this division be performed, such that everybody is satisfied? Some of the people may not receive an object.

Since this problem has no label in my textbook, I'm not sure how to place it in a category, but I'm fairly certain it's a combinatorial problem.

I've been thinking by writing the solution as a sum of products of binomial coefficients, but I haven't been able to get an useful form. I guess that each term would be comprised by two factors, where the first one would mean in how many ways we can get an odd number of objects and the second one would be the number of ways we can choose an even number of objects from the remaining ones.

How would you solve this?

$\endgroup$
2
$\begingroup$

The general solution for distinct objects requires exponential generating functions.

We use $e^x, \sinh x,$ and $\cosh x$:

$$e^x=1+x+\frac{x^2}{2!}+\frac{x^3}{3!}+...\\\sinh x = x + \frac {x^3} {3!} + \frac {x^5} {5!} + \frac {x^7} {7!} +\cdots\\\cosh x = 1 + \frac {x^2} {2!} + \frac {x^4} {4!} + \frac {x^6} {6!} + \cdots$$

In the first, $x^k$ represents the assignment of $k$ objects to one person, in the second an odd number of objects to one person, and in the third an even number to one person.

Thus the answer is $n!$ times the coefficient of $x^n$ in the Taylor series expansion of $$\sinh^a x\cdot \cosh^b x \cdot e^{cx}$$ at $x=0$.

For $(a,b,c)=(1,1,0)$, this is $\sinh x\cosh x=\tfrac12\sinh 2x$ and the coefficient of $x^3$ is $\tfrac4{3!}$ as expected.


What if the objects are indistinguishable? To find out, we'll continue the answer of user453887.

Because we are only interested in the coefficient of $x^n$ in the result, we can simplify things a bit by making them infinite series:

$$(x+x^3+...)^a\cdot(1+x^2+...)^b\cdot(1+x+x^2+...)^c$$

This becomes $$\left(\frac{x}{1-x^2}\right)^a\left(\frac{1}{1-x^2}\right)^b \left(\frac{1}{1-x}\right)^c$$ $$=\quad x^a\left(\frac{1}{1-x^2}\right)^{a+b}\left(\frac{1}{1-x}\right)^c$$

Now by the (generalized) binomial theorem, $$\frac{1}{(1-x)^z}=\sum_{i=0}^\infty \binom{z-1+i}{i}x^i$$ So cross-multiplying the two series, the coefficient of $x^n$ must be $${\large\sum_{a+2i+j\ =\ n\atop i,\ j\ \ge\ 0}}\binom{a+b-1+i}{i}\binom{c-1+j}{j}$$ with as many terms as there are solutions $(i,j)$ in non-negative integers of $2i+j=n-a$.

$\endgroup$
  • $\begingroup$ This can't be right, at least I can't see where's my mistake. Take for example the case with $n = 3, a = 1, b = 1, c = 0$. The answer should be $4$, yet your expression would have some pretty weird factors when substituting the values for $(i, j)$. In this case they would be $(1, 0)$ and $(0, 2)$, and some of the binomial coefficients don't make sense using these values... $\endgroup$ – programmer101 Jun 10 '17 at 14:47
  • $\begingroup$ In that example, there are two ways to distribute the objects: one plus two, or three plus zero. For $(1,1,0)$ the formula gives $\tbinom21\tbinom{-1}0+\tbinom10\tbinom12=2\cdot1+1\cdot0=2$. I think $\tbinom{-1}0=1$ is the only generalized binomial coefficient the formula might need. $\endgroup$ – Andrew Woods Jun 10 '17 at 15:21
  • $\begingroup$ Why two ways? There are $n = 3$ different objects (let's denote them by $A, B, C$); $a = 1$ people who want an odd number of objects, $ b = 1$ people who want an even one, and $c = 0$ people who don't care. You could do the following distributions : $\text{({A}, {B, C})}; (\text{{B}, {C, A}}); (\text{{C}, {A, B}}); (\text{{A, B, C}, $\emptyset$})$. $\endgroup$ – programmer101 Jun 10 '17 at 15:39
  • $\begingroup$ Ah, I see. I will delete this answer and start over. $\endgroup$ – Andrew Woods Jun 10 '17 at 15:45
  • $\begingroup$ Yup, this is quite a tough problem ... Thank you so much for your help. $\endgroup$ – programmer101 Jun 10 '17 at 15:48
0
$\begingroup$

I am also struggling :D My progress: $$A(x)=(x^1+x^3+ \dots +x^{2n+1})^a(x^0+x^2+ \dots +x^{2n})^b(x^0+x^1+ \dots +x^n)^c=x^a(x^0+x^2+ \dots +x^{2n})^{a+b}(x^0+x^1+ \dots +x^n)^c= \frac{x^a} {(1-x^2)^{a+b}(1-x)^c}=\frac{x^a} {(1+x)^{a+b}(1-x)^{a+b+c}}=\sum_{n=0}^{\infty} c_nx^n. \frac{1} {(1+x)^{a+b}(1-x)^{a+b+c}}=\sum_{n=0}^{\infty} c_nx^{n-a}$$ need to find $$c_n$$

$\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.