color 6 vertical stripes with 4 colors--
i) adjacent stripes must have different colors
ii) use ALL 4 colors
the 1st part of the question has been asked before (Flag making with 6 vertical stripes)
i also obtained the answer 4*3^5
by considering the corresponding coloring problem of
6 vertex tree a---b---c---d---e---f ;
however i am getting different answers for the second part:--
MUST use all 4 colors
P(G,k)=k(k-1)^5 being the chromatic polynomial,
i tried this:
2 colors at most
= 2 colors EXACTLY (is minimum for tree) 2(2-1)^5 =2
3 colors at most 3(3-1)^5 = 96
4 colors at most 4(4-1)^5 = 972
now i needed to consider that each case counts all lower numbered cases also; hence:
exactly 3 colors = max 3 colors - (3C2)*exactly 2 colors = 96 - 3*2 = 90
exactly 4 colors = max 4 colors - (4C3)*exactly 3 colors - (4C2)*exactly 2 colors
exactly 4 colors = 972 - 4*90 - 6*2 = 600
unfortunately; when i was provided with a different solution; it seems logical but gives a different answer:--
6 stripes 4 colors & each color used at least once
=== integer decomposition of 6 into 4 parts
=== (1+1+2+2); (1+1+1+3) neglecting relative order;
(1+1+2+2) has 84 arrangements
(1+1+1+3) has 12 arrangements
hence considering "choice of colors to repeat"
(1+1+2+2)--> (4C2) choices & (1+1+1+3)--> (4C1) choices
hence total 84*6 + 12*4 = 552
so i am getting 600 OR 552
any ideas or hints to confirm or correct either solution will be appreciated
Asked
Active
Viewed 75 times
1
ADG
- 11
-
Hint: Use PIE to exclude those with 1, 2, or 3 colors only. – Calvin Lin May 04 '20 at 14:41
-
Your answer is correct. I set up an Excel spreadsheet to list all of the 4096 ways to color 6 strips with four colors. Then, I counted the number that satisfied the two constraints, and I got 600. – SlipEternal May 04 '20 at 14:42
-
@InterstellarProbe i started doing that, gave up half way, thanks for the confirmation PS: is there a quick excel (preferably non-VBA) way to do this enumeration? – ADG May 04 '20 at 15:22
-
@CalvinLin thanks i did use PIE to find that (1+1+2+2) case (84 ways) and (1+1+1+3) case (12 ways); unable to catch what mistake is giving me different answers 552 vs 600 – ADG May 04 '20 at 15:26
-
@ADG I used the following formulas: Cells $\text{A1:F1}$ have the number 1. Then I used the following formulas: $$\text{A2: =IF(SUM(B1:F1)=20,A1+1,A1)} \ \text{B2: =IF(SUM(C1:F1)=16,IF(B1=4,1,B1+1),B1)} \ \text{C2: =IF(SUM(D1:F1)=12,IF(C1=4,1,C1+1),C1)} \ \text{D2: =IF(E1+F1=8,IF(D1=4,1,D1+1),D1)} \ \text{E2: =IF(F1=4,IF(E1=4,1,E1+1),E1)} \ \text{F2: =IF(F1=4,1,F1+1)} \ \text{G1: =AND(A1<>B1,B1<>C1,C1<>D1,D1<>E1,E1<>F1,COUNTIF(A1:F1,1)>0,COUNTIF(A1:F1,2)>0,COUNTIF(A1:F1,3)>0,COUNTIF(A1:F1,4)>0)}$$ I copied $\text{A2:F2 to A2:F4096}$. Then I copied $\text{G1}$ to $\text{G1:G4096}$ – SlipEternal May 04 '20 at 15:54
-
Finally, in $\text{H1}$, I put the formula $\text{=COUNTIF(G:G,TRUE)}$. – SlipEternal May 04 '20 at 15:54
-
@InterstellarProbe thanks, this will help me a lot as sometimes in spite of the formulas, direct enumeration really clears the picture PS: double thanks for doing it without VBA :) – ADG May 04 '20 at 16:11
1 Answers
2
There are 24 ways for the (1+1+1+3) case.
This gives us $ 84 \times 6 + 24 \times 4 = 600$.
I'm guessing that you missed out $ABCADA, ABACDA$ as possible ways, and only considered $ABACAD, BACADA$ (but don't really know since you didn't list out what you're doing)
Calvin Lin
- 68,864
-
heh, you are a mind reader :) i only considered A_A_A_ and _A_A_A exactly.... totally missed the DISPLACEMENT possibility thanks, i have been gazing at the opened excel file for so long, simply could NOT see where i was going wrong – ADG May 04 '20 at 15:59
-
@ADG In my comment, I was hinting at applying PIE directly: $=1\times 4\times3^5 - 4\times(3\times2^5)+6\times(2\times1^5)-4\times(1\times0^5) = 600$. That is similar to what you did for the first approach (but without the additional steps). – Calvin Lin May 04 '20 at 16:03
-
-
@SMSheikh By PIE, $6!/2^2 - 2 \times 5!/2 + 4! = 84$. Can you decode that? – Calvin Lin May 05 '20 at 01:54
-