Combinatorics

[bbmath]

Hello all!

I am new to the forum, but I am in desperate need of help. I am new in a combinatorics class, and I'm needing a little help getting the ball rolling on some proofs.

The first problem asks for a proof by induction. Show that the number of n-letter words that can be formed from letters a,b,c, and d when the letter d occurs an odd number of times is 1/2(4^n-2^n).

I know I need to proceed by weak mathematical induction. I can establish the base case, but when I go into the induction step, I get stuck after defining what an odd number is. Any suggestions?

My other question is how to distribute 17 identical objects into 5 separate boxes if the number of objects in the 1st box is a multiple of 4?

I figure there will be 5 cases each with a multiple of 4 in the first box. (0,4,8,12,16) Then after establishing the 5 cases, it is as simple as figuring out the count of the other 4 boxes within each case.

Does this sound right?

Any help anyone can provide is greatly appreciated!

 

[soroban]

Hello, bbmath!

Welcome aboard!

Here's some help with the second problem.

How to distribute 17 identical objects into 5 separate boxes if the number of objects in the 1st box is a multiple of 4?

I figure there will be 5 cases each with a multiple of 4 in the first box: (0,4,8,12,16).
Then, after establishing the 5 cases, it is as simple as figuring out the count of the other 4 boxes within each case.

Does this sound right? . Yes!

"Figuring out the count of the other 4 boxes" may not be a simple as we would like.
. . I have an approach to this.

I'll consider one case only . . . You can work out the others.


Suppose there 8 objects in the first box.
Then the other 9 objects are distributed among the other four boxes.
How many ways are there?

Place the 9 objects in a row, leaving a space before, after and between them.
. . \(\displaystyle \_\;\circ\,\_\,\circ\,\_\,\circ\,\_\,\circ\,\_\,\circ\,\_\,\circ\,\_\,\circ\,\_\,\circ\,\_\,\circ\,\_\)

We will place 3 "dividers" in the 10 spaces.
. . Each division represents a distribution of the 9 objects.


Examples:

. . \(\displaystyle \circ\,|\,\circ\,\circ\,|\,\circ\,\circ\,\circ\,\circ\,|\,\circ\,\circ\:\text{ represents }[1,2,4,2]\)

. . \(\displaystyle \circ\, \circ\, \circ\, \circ\,||\, \circ\, \circ\,|\, \circ \, \circ\, \circ\:\text{ represents }[4,0,2,3]\)

. . \(\displaystyle |\,\circ\, \circ\, \circ\, \circ\, \circ\, \circ\,||\, \circ \, \circ\, \circ\:\text{ represents }[0.6.0.3]\)

. . \(\displaystyle \circ\, \circ\, \circ\, \circ\,|||\, \circ\, \circ\, \circ \, \circ\, \circ\:\text{ represents }[4,0,0,5]\)


\(\displaystyle \text{For each of the 3 dividers, there are 10 choices for locations.}\)

\(\displaystyle \text{Hence, there are: }\:10^3 = 1000\text{ ways when there are 8 in the first box.}\)


Get the idea?