7
$\begingroup$

This is my first question here.

I'm given $3$ white flowers and $6m$ red flowers, for some $m \in \mathbb{N}$. I want to make a circular garland using all of the flowers. Two garlands are considered the same if they can be rotated to be the same. My question is: how many different garlands can I make?

I tried an approach in which I divided the question into three parts:

  1. No. of ways in which the white flowers are all together
  2. No. of ways in which two white flowers are together
  3. No. of ways in which no two white flowers are together

Can you please help?

The answer is $3m^2+3m+1$ in the book that I saw

Thanks

$\endgroup$
9
  • 1
    $\begingroup$ (1) The question should always be in the body. (2) Not everybody knows what a garland is. I know what a garland is, and it still isn't clear to me what it means to be a different way to make one - there are several different definitions that occur to me. And (3) I assume the $m$ in $6m$ is a typo, and not indicate there are six million red flowers. $\endgroup$ Commented Dec 19, 2014 at 13:05
  • $\begingroup$ @ThomasAndrews 'm' refers to any integer...should I change it to 'n'? Also..The different ways mean that the no. of different garlands that can be formed from the same flowers...Please suggest any changes you want made...As I said I am new to posting questions $\endgroup$
    – user202236
    Commented Dec 19, 2014 at 13:09
  • $\begingroup$ @ThomasAndrews I added (circular) in the title to make the mathematically relevant characteristic of a garland clear. I think I fixed the other two problems as well. $\endgroup$ Commented Dec 19, 2014 at 13:37
  • $\begingroup$ @user202236 Is my assumption that the garland is circular correct? Or were you thinking that the garland had two ends? In the latter case we could think of it as a line of flowers, so that the answer would just be the binomial coefficient $$\binom{3 + 6m}{3}$$ $\endgroup$ Commented Dec 19, 2014 at 13:39
  • $\begingroup$ Define any location as first and its previous one last. Assume the first flower to be red. It then becomes easy to calculate in how many ways the other 2 flowers can be placed. The only problem is that there will be repeated solutions (as the array is cyclic), so I don't know how to account for those. Maybe you just divide the answer by 3. $\endgroup$ Commented Dec 19, 2014 at 13:39

5 Answers 5

5
$\begingroup$

My answer would be $\frac{1}{3}\left(\binom{6m+2}{2}-1\right)+1$.

$\binom{6m+2}{2}$ is the number of ways of writing $6m$ as the sum of three non-negative integers.

We count the one case where all the values are the same seperately. That yields one garland.

The other cases, the equations:

$$6m=a+b+c=b+c+a=c+a+b$$ are all the same garland, so we have to divide those cases by $3$.

Simplified:

$$\begin{align} \frac{1}{3}\left(\binom{6m+2}{2}-1\right)+1& = \frac{1}{3}\left((3m+1)(6m+1)-1\right)+1\\ &=6m^2+3m+1 \end{align}$$

in general, if there were $p$ white flowers and $pn$ red, with $p$ prime, then the number of garlands would be:

$$\frac{1}{p}\left(\binom{np+p-1}{p-1}-1\right)+1$$

In this case, $n=2m$ and $p=3$.

$\endgroup$
7
  • $\begingroup$ This is the same final answer as mine. Nice alternate approach! +1 $\endgroup$ Commented Dec 19, 2014 at 14:28
  • 2
    $\begingroup$ I'd say "same result." The answer is the journey :) $\endgroup$ Commented Dec 19, 2014 at 14:29
  • $\begingroup$ @ThomasAndrews Taking m=1, I have arranged white flowers first which created three gaps. Now I am able to make only 7 cases for these gaps. $(0,0,6),(0,5,1),(0,4,2),(0,3,3),(1,2,3),(1,1,4),(2,2,2)$ but there must be 10 cases as per the answer. What am I missing? $\endgroup$ Commented Sep 27, 2017 at 16:05
  • 1
    $\begingroup$ $(0,5,1)$ and $(0,1,5)$ are different garlands, in my reading of the question. @Mathematics You cannot get one from the other by rotations of the flowers, but you can by flipping the garland over. So the missing garlands are $(0,1,5), (0,2,4),(1,3,2)$ $\endgroup$ Commented Sep 27, 2017 at 16:12
  • 3
    $\begingroup$ @ThomasAndrews Yeah got your point. The book from which user asked considered $(0,5,1)$ and $(0,1,5)$ as same. That is why answer given by user i.e. $3m^2+3m+1$ gives 7 for m=1. $\endgroup$ Commented Sep 27, 2017 at 16:15
4
$\begingroup$

I discussed this question with my colleagues and the answer is $3m^2+3m+1$

Writing $6m$ as the sum of three non-negative integers is $\binom{6m+2}{2}$ which is equal to $18m^2+9m+1$

$$6m=a+b+c=b+c+a=c+a+b$$ Cases where a,b and c are not different

$0 \le 6m-2i$

We get $i \le 3m$ & $0 \le i$

Number of cases with two terms be same is (3m)*$\frac{3!}{2!}$=9m we count {2m,2m,2m} as 1

Number of cases wirh different value of a,b and c is

$18m^2+9m+1-[9m+1]$=$18m^2$ When a,b and c there are 3! Case so number of garland forn with different a,b & c is $\frac{18m^2}{3!}=3m^2$

Number of cases with two similar values is 3m

Number of cases with a=b=c is 1.

Hence total number of garland is $3m^2+3m+1$ which is correct and this has been checked by an expert.

$\endgroup$
1
  • $\begingroup$ @Thomas Andrews Please have a look at my answer and this is correct. I also checked it with an expert in mathematics from a premier institute. $\endgroup$ Commented Oct 5, 2017 at 23:55
3
$\begingroup$

First I will dramatically overcount. Then I will overcompensate for my overcounting. Then I will compensate for my overcompensation to reach the final answer.


Imagine the garland as a fixed circle, with a total of $3+6m$ positions for flowers. Then the number of possible garlands is simply the number of ways to choose the $3$ positions of the white flowers. This is the binomial coeffient $$\binom{3+6m}{3} = \frac{(6m+1)(6m+2)(6m+3)}{6}$$

But we've agreed that garlands that can be rotated to be the same fixed garland are considered the same garland. Each garland can be rotated in $3+6m$ ways, so we have to divide our answer above by $3+6m$, to get

$$\frac{(6m+1)(6m+2)}{6}$$

This is N.F.Taussig's answer, but it's missing a little something. This is the one garland that remains the same when rotated by an angle less than $2\pi$. This special garland has the white flowers arranged in an equilateral triangle, and any rotations by $2\pi/3$ do not change the garland. There are $1+2m$ fixed versions of this garland, and we've counted them each $1/(3+6m)$ times. That means we've counted $\frac{1+2m}{3+6m} = 1/3$ of these garlands, when there is actually a full $1$ garland of this type. We need to add $2/3$ to our previous answer, to get our final answer of

$$\frac{(6m+1)(6m+2)}{6}+\frac{2}{3} \,= \,\boxed{6m^2 + 3m+1} \,\,\text{ garlands}$$

$\endgroup$
2
  • 1
    $\begingroup$ Zubin, thank you for the clarification. This problem is more subtle than I realized. $\endgroup$ Commented Dec 19, 2014 at 21:28
  • $\begingroup$ @Zubin Mukerjee I have solved it , please suggesr if it is correct. $\endgroup$ Commented Oct 5, 2017 at 18:11
0
$\begingroup$

I always try to promote the Polya Enumeration Theorem because it has many applications from simple to very sophisticated, and with this in mind I would like to apply it here. Once you have placed the three white flowers there are three slots for the $6m$ red ones, with every slot holding some number of red flowers including the case of zero red flowers. The group acting on these slots is the cyclic group on three elements, whose cycle index can be calculated with pen and paper and turns out to be $$Z(C_3) = \frac{1}{3}( a_1^3 + 2a_3).$$ It follows the answer is given by $$[z^{6m}] Z(C_3)\left(\frac{1}{1-z}\right).$$ This is $$\frac{1}{3} [z^{6m}] \frac{1}{(1-z)^3} + \frac{2}{3} [z^{6m}] \frac{1}{1-z^3}$$ which is $$\frac{1}{3} {6m+2\choose 2} + \frac{2}{3} = \frac{1}{6} (6m+2)(6m+1) + \frac{2}{3} = 6m^2 + 3m + 1.$$

$\endgroup$
0
$\begingroup$

I first placed all the white flowers creating 3 spaces, each between a pair. The question can now be seen as the number of non-negative integer solutions of

$x+y+z=6m$

the number of solutions can be given as

$\binom{6m+3-1}{3-1} = 18m^2 + 9m + 1$

but this $18m^2 + 9m +1$ contains three types of solutions:

$αβγ,ααβ,ααα$ where

  • $αβγ$ is counted 6 times $(3!=6)$
  • $ααβ$ is counted thrice $(\frac{3!}{2!} = 3)$
  • $ααα$ is counted once.

But, since it is a garland, we need solutions of each form counted only once.

Let $N(αβγ$) represent the number of solutions of the type $αβγ$.
Therefore, the required answer is

$N(αβγ)+N(ααβ)+N(ααα)$

where $N(ααα)=1$(obvious)

For the solutions of the type $ααβ$ we can find the number of solutions of the equation $2x+y=6m$.

The number of solutions of this equation will consist of solutions of the type $ααβ$ and $ααα$.

The number of solutions will be = $\frac{6m}{2} +1 = 3m+1$ (Number of solutions for 2x+y=N)

$=>N(ααβ)+N(ααα)=3m+1$
Now,

$18m^2+9m+1=1+3(3m)+6N(αβγ)$
Hence, $N(αβγ)=3m^2$

Therefore, the required expression, $N(αβγ)+N(ααβ)+N(ααα)=$

$3m^2+3m+1$

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .