1. ## Combinatorics

Hi. It supposed to be easiest part of a whole test but I can't solve it. It drives me crazy and I feel stupid. Please help to solve:
If we make a sequence selecting three elements from three different elements {1, 2, 3} and we permit overlapped elements for the sequence, then the total number of sequences is [1 - ?] . If we do not take into account the order, the total number of the selections is [2 - ?]

So,the first one is easy A=n^3=3^3=27. The second one is I totally do not understand. The right answer should be 27, but I can't figure out how to come to it whatsoever.

Sorry if I've posted thread on the wrong section - That one seemed most relevant.

2. ## Re: Combinatorics

Originally Posted by a13
Hi. It supposed to be easiest part of a whole test but I can't solve it. It drives me crazy and I feel stupid. Please help to solve:
If we make a sequence selecting three elements from three different elements {1, 2, 3} and we permit overlapped elements for the sequence, then the total number of sequences is [1 - ?] . If we do not take into account the order, the total number of the selections is [2 - ?]
I confess that I am not convinced that I read this correctly.
For example I assume that saying "overlapped elements" means that elements can be repeated. In that case the answer is indeed $3^3=27$

Now for the second part, this is a pure guess. "how ways can one select three items from three types where repetitions are allowed?"
For this part, part 2: $<1,2,2>~\&~<2,1,2>$ are not different, where as $<1,2,2>~\&~<2,1,2>$ are different in part 1.
Think of three labeled boxes $~\boxed{~1~},~\boxed{~2~},~\boxed{~3~}$ along with three identical balls, $o,~o,~o$.
How many ways can we place the halls into the boxes? Here are three ways:
i) $o~|o~|o$ one in each box;
ii)$~|oo~|o$ none in box 1, two in box 2, & one in box 3;
iii) $ooo~|~|$ all in box 1.
Now if we simply count the number of ways to arrange the string $~|~|~o~o~o~$: $\dfrac{(2+3)!}{(2!)(3!)}=10$

In general, if we have $N$ different types of objects (each type having $K$ is stock)
the number of ways to select a collect of $J\le K$ of these objects is $\dfrac{(N+J)!}{(N!)(J!)}$

This idea can answer a wide variety of questions.
1) How many non-negative integers solve $s+t+u+v+w+x+y+z=100~?$

2) Using the letters $\{A,B,C,D,E,F,G,H,I,J,K\}$ how many strings of five letters, allowing repetitions, are in alphabetical order? etc.

3. ## Re: Combinatorics

Originally Posted by Plato
I confess that I am not convinced that I read this correctly.
For example I assume that saying "overlapped elements" means that elements can be repeated. In that case the answer is indeed $3^3=27$

Now for the second part, this is a pure guess. "how ways can one select three items from three types where repetitions are allowed?"
For this part, part 2: $<1,2,2>~\&~<2,1,2>$ are not different, where as $<1,2,2>~\&~<2,1,2>$ are different in part 1.
Think of three labeled boxes $~\boxed{~1~},~\boxed{~2~},~\boxed{~3~}$ along with three identical balls, $o,~o,~o$.
How many ways can we place the halls into the boxes? Here are three ways:
i) $o~|o~|o$ one in each box;
ii)$~|oo~|o$ none in box 1, two in box 2, & one in box 3;
iii) $ooo~|~|$ all in box 1.
Now if we simply count the number of ways to arrange the string $~|~|~o~o~o~$: $\dfrac{(2+3)!}{(2!)(3!)}=10$

In general, if we have $N$ different types of objects (each type having $K$ is stock)
the number of ways to select a collect of $J\le K$ of these objects is $\dfrac{(N+J)!}{(N!)(J!)}$

This idea can answer a wide variety of questions.
1) How many non-negative integers solve $s+t+u+v+w+x+y+z=100~?$

2) Using the letters $\{A,B,C,D,E,F,G,H,I,J,K\}$ how many strings of five letters, allowing repetitions, are in alphabetical order? etc.
P.S. EDIT
It should be In general, if we have $N$ different types of objects (each type having $K$ is stock)
the number of ways to select a collect of $J\le K$ of these objects is $\dfrac{(N-1+J)!}{((N-1)!)(J!)}$

4. ## Re: Combinatorics

Now I have a sense of direction and something to work with. Thank you!