0
$\begingroup$

Can anyone help me with this problem? What is the number of ways to put n distinct balls into k distinct bins with one bin always have an even number of balls? (The order of terms matter here)

$\endgroup$
  • $\begingroup$ bumppppppppppppppppp $\endgroup$ – Hoang Nguyen Sep 25 '16 at 21:55
  • $\begingroup$ Can you be more precise in your language? Do you mean that "at least one of the bins contains an even number of balls"? Or, perhaps, a specific one of the bins must contain an even number of balls? $\endgroup$ – Nick Peterson Sep 25 '16 at 22:33
  • $\begingroup$ Or "exactly one bin contains an even number"? $\endgroup$ – Nick Peterson Sep 25 '16 at 22:34
0
$\begingroup$

I'd probably look at this via a recurrence relation.

Let $o_n$ be the number of ways to paint $n$ poles such that an odd number are green; let $e_n$ be the number of ways such that an even number are green. We, of course, would like a formula for $e_n$.

Start by noting that for a sequence with an even number of green poles, one of two things happens: either the last pole is green, or it isn't. If it is green, then poles $1,\ldots,n-1$ must contain an odd number of green poles; if it is not, then $1,\ldots,n-1$ must contain an even number of green poles. So, we get the system of recurrences $$ e_n=3e_{n-1}+o_{n-1} $$ (because there are $3$ ways to choose the color of pole $n$ if it isn't green).

Now, how else can we relate these quantities? Well, for any $n$, $$ e_n+o_n=4^n, $$ because every coloring of the $n$ poles has either an even number or an odd number of green poles. So, we can write $o_{n-1}=4^{n-1}-e_{n-1}$, and therefore $$ e_n=3e_{n-1}+4^{n-1}-e_{n-1}=2e_{n-1}+4^{n-1}. $$ Now, you can follow any method you like to solve this recurrence relation; my personal preference would be a quick application of ordinary generating functions, but suit yourself!

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