# permutations and combination

• Jan 7th 2011, 03:46 AM
grgrsanjay
permutations and combination
how many different signals can be formed with 3 dots(.),2 dashes(-),4 stars(*)?
• Jan 7th 2011, 04:09 AM
FernandoRevilla
Quote:

Originally Posted by grgrsanjay
how many different signals can be formed with 3 dots(.),2 dashes(-),4 stars(*)?

$\displaystyle PR_{\;9}^{\;3,\;2,\;4}=\dfrac{9!}{3!\;2!\;4!}=\ldo ts$

Fernando Revilla
• Jan 7th 2011, 04:25 AM
grgrsanjay
it isint given that all the nine have to be used

it has certainly more no of ways then what you provided
• Jan 8th 2011, 06:38 AM
awkward
If you are not required to use all the symbols then the problem gets more complicated. I can think of a couple of ways to approach it. One way is to break the problem into cases depending on the number of signals used, say $\displaystyle 0 \leq r \leq 9$. Then for a given r, find all the solutions in non-negative integers to

$\displaystyle x_1 + x_2 + x_3 = r$
where
$\displaystyle 0 \leq x_1 \leq 3$
$\displaystyle 0 \leq x_2 \leq 2$
$\displaystyle 0 \leq x_3 \leq 4$

Given one solution to the equation, the number of signals that can be sent with that number of symbols is
$\displaystyle \binom{r}{x_1 \; x_2 \; x_3} = \frac{r!}{x_1 ! x_2 ! x_3 !}$
(a multinomial coefficient). All this looks pretty tedious, although I guess it can be done.

I'm too lazy to do it that way, so I would prefer a generating function approach. Let $\displaystyle a_r$ be the number of signals that can be sent with r of the symbols and define

$\displaystyle f(x) = \sum_r \frac{1}{r!} a_r x^r$

(an exponential generating function). Then it's clear (once you know how to do it) that

$\displaystyle f(x) = (1 + x + \frac{1}{2!} x^2 +\frac{1}{3!} x^3) (1 + x + \frac{1}{2!} x^2) (1 + x + \frac{1}{2!} x^2 +\frac{1}{3!} x^3 + \frac{1}{4!} x^4)$

Expand f (here it helps to have access to a computer algebra system, or you can use Wolfram Alpha), write the result in exponential generating form as in the definition of f (notice the factors 1/r!), and you have the coefficients $\displaystyle a_r$. Your final answer is then

$\displaystyle \sum_{r=0}^9 a_r$

The case r=0 corresponds to a "signal" of no symbols, so you need to decide whether that is acceptable.