1
$\begingroup$

The no. of ways that the garland can be made out of $6$ red and $4$ white roses so that all white roses not come together.

$\bf{My\; Solution::}$ First we will form a garlad using $6$ red roses, This can be done in $\displaystyle (6-1)!$ ways.

Now we will arrange $4$ white roses in $6$ gap produced by $6$ red roses, This can be done in $\displaystyle \binom{6}{4}\times 1$

because all roses are white.

So Total no. of ways is $ = \displaystyle 5! \times \binom{6}{4}$

But my answer is wrong.

please explain me in detail where my answer is wrong

Thanks

$\endgroup$
  • $\begingroup$ First, a garland is circular (not a line). Second, most likely all red roses are considered the same, as are all white roses. $\endgroup$ – vadim123 May 13 '14 at 4:54
  • $\begingroup$ are rotations the same? $\endgroup$ – user148697 May 13 '14 at 4:58
  • $\begingroup$ It is not clear from the wording whether all white roses must be separated, or whether the only thing that is forbidden is $4$ whites together. $\endgroup$ – André Nicolas May 13 '14 at 5:32
  • $\begingroup$ To André Nicolas, I have confirmed it from original source., Thanks $\endgroup$ – juantheron May 15 '14 at 3:02
1
$\begingroup$

This problem can be solved with the Polya Enumeration Theorem (PET). We assume that garlands that can be transformed into each other by rotations or reflections are considered the same. Furthermore we do not treat the problem where the forbidden garlands are precisely those that contain four white roses all in one block, as that is a trivial variation on the ordinary bracelet / necklace problem. We will solve the slightly more general problem of having $n$ red roses where $n\ge 4.$

First place the four white roses on the garland, leaving some space between them. These spaces are where the red roses go but there must be at least one red rose in every one of the four spaces. The dihedral group $D_4$ acts on these slots and therefore the answer is given by $$[z^n] Z(D_4)\left(\frac{z}{1-z}\right).$$

We compute $Z(D_4)$ next. The rotations contribute $$a_1^4+a_2^2+2a_4$$ and the reflections $$2a_1^2 a_2 + 2 a_2^2$$ for a total result of $$Z(D_4) = \frac{1}{8} \left(a_1^4 + 3 a_2^2 + 2 a_1^2 a_2 + 2a_4\right).$$ The substituted cycle index becomes $$Z(D_4)\left(\frac{z}{1-z}\right) \\= \frac{1}{8} \left( \left(\frac{z}{1-z}\right)^4 + 3 \left(\frac{z^2}{1-z^2}\right)^2 + 2 \left(\frac{z}{1-z}\right)^2\left(\frac{z^2}{1-z^2}\right) + 2 \left(\frac{z^4}{1-z^4}\right)\right).$$

Introduce the predicate $$q_m(n) = \begin{cases} 1 & \quad\text{if}\quad m|n \\ 0 & \quad\text{otherwise.} \end{cases}.$$

Extracting coefficients from the inner terms we get for the first term $${n-4 +3\choose 3} = {n-1\choose 3}.$$ For the second term we get $$q_2(n)\left(\frac{n}{2}-1\right).$$ For the third term we obtain (use e.g. the partial fraction decomposition) $$\frac{1}{4} n^2 - n + \frac{7}{8} + \frac{1}{8} (-1)^n.$$ Finally the last term contributes $$q_4(n).$$

Collecting all contributions we get $$\frac{1}{48} n^3 - \frac{1}{16} n^2 - \frac{1}{48} n + \frac{3}{32} + \frac{1}{32} (-1)^n + \frac{3}{8} q_2(n)\left(\frac{n}{2}-1\right) + \frac{1}{4} q_4(n).$$

This yields the following sequence (starting at $n=1$): $$0, 0, 0, 1, 1, 3, 4, 8, 10, 16, 20, 29, 35, 47, 56, 72, 84, 104, 120, 145,\ldots$$ which is OEIS A005232. In particular with six red beads there are $3$ garlands, which are (first distribute four red roses into the spaces as that is the minimum, leaving two red roses): one, the two red roses go into the same slot, two, the two red roses go into adjacent slots and three, the two red roses go into opposite slots.

$\endgroup$
0
$\begingroup$

First, do circular permutation of 6 red and thus we have 6 places for arranging 4 reds in six places linearly. Hence,

(6-1)!=120 and then after linear permutation 6P4=360

This can be clockwise and also anti-clockwise thus total types=120 * 360/2 =21600

$\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.