# Number of ways to put n distinct balls into k distinct bins with one bin always have an even number of balls

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)

• bumppppppppppppppppp – Hoang Nguyen Sep 25 '16 at 21:55
• 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? – Nick Peterson Sep 25 '16 at 22:33
• Or "exactly one bin contains an even number"? – Nick Peterson Sep 25 '16 at 22:34

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!