1
$\begingroup$

I am trying to find the total number of signals that can be created from $3$ pink, $3$ white and $2$ black flags when arranged in a straight line. But, only $5$ flags are allowed in a signal.

I know how to find permutations in this situation when all are taken at a time i.e. a signal has $8$ flags, which would be $\frac{8!}{3! \cdot 3! \cdot 2!}$, but cannot see how to start solving a scenario where all are not taken at the same time.

Formula when all are taken at a time with some like objects

$$\frac{n!}{a! \cdot b! \cdot c! \cdot d!...}$$

Question

Is there a modified formula that will give permutations of $n$ objects taken $r$ at a time when some of these objects are alike and $r < n$?

$\endgroup$
1
$\begingroup$

Let's generalize the problem slightly and find the number of signals with $r$ flags, say $a_r$. Let $f(x)$ be the exponential generating function for $a_r$, i.e. $$f(x) = \sum_{r=0}^{\infty} \frac{1}{r!} a_r x^r$$ Since there are 3 pink, 3 white, and 2 black flags, $$f(x) = \left( 1 + x + \frac{1}{2!} x^2 + \frac{1}{3!} x^3 \right)^2 \left( 1 + x + \frac{1}{2!} x^2 \right)$$ Expanding this polynomial (I cheated and used a computer algebra system), we find

$$f(x) = 1+3 x+\frac{9 x^2}{2}+\frac{13 x^3}{3}+\frac{35 x^4}{12}+\frac{17 \ x^5}{12}+\frac{35 x^6}{72}+\frac{x^7}{9}+\frac{x^8}{72}$$ so the number of signals with 5 flags is $$5! \; \frac{17}{12} = 170$$

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Can you explain the formula you have used? I do not understand what you are doing. What exactly are the terms in the formula besides r. $\endgroup$ – Sunil Jan 22 '17 at 6:11
  • $\begingroup$ @Sunil, generating functions are too big a subject to cover in a comment. They are discussed in many combinatorics texts. One source you can find online is the book "generatingfunctionology" by Herbert S. Wilf, or you can use google to find notes and video lectures. $\endgroup$ – awkward Jan 24 '17 at 1:25
  • $\begingroup$ No problems. I will take a look at some online stuff. $\endgroup$ – Sunil Jan 24 '17 at 3:05
0
$\begingroup$

I was able to solve this problem but not sure if there is a better and shorter method. I used a $case$ approach to solving this by listing all possible groups of 5 flags using the original collection of 8 flags and then within each group of 5 flags we apply the formula for permutations of 5 objects at a time.

Is there a better and shorter approach to this problem?

Since there are 3 W(hite), 3 P(ink) and 2 B(lack) balls, so the cases are as below. We start with cases having the maximum of each type of flag and then decrease the maximum of each flag type by 1 till we reach 1 count for each flag type. In each case we get a group of 5 flags which we simply arrange 5 at a time using standard formula.

The sum of all ways i.e. arrangements of 5 flags is the sum of all cases, which is 170. This is also the answer given at the back of the book.

Case 1: 3W

3W+2P : 5!/(3!.2!) = 10 ways

3W+2B : 5!/(3!.2!) = 10 ways

3W+1P+1B : 5!/(3!.1!.1!) = 20 ways

Case 2: 3P

3P+2W : 5!/(3!.2!) = 10 ways

3P+2B : 5!/(3!.2!) = 10 ways

3P+1B+1W: 5!/(3!.1!.1!) = 20 ways

Case 3: 2B

2B+3W

2B+3P

2B+1P+2W : 5!/(2!.2!.1!) = 30 ways

2B+2P+1W : 5!/(2!.2!.1!) = 30 ways

Case 4: 1W

1W+3P+1B

1W+2P+2B

Case 5: 2W

2W+2P+1B: 5!/(2!.2!.1!) = 30 ways

2W+1P+2B

Case 6: 1W

1W+3P+1B

1W+2P+2B

Case 7: 2P

2P+1W+2B

2P+2W+1B

Case 8: 1P

1P+2W+2B

1P+3W+1B

Case 9: 1B

1B+2W+2P

1B+3W+1B

1B+1W+3B

| cite | improve this answer | |
$\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.