0

In how many ways can the letters of the word VANESSA be arranged so that no two vowels are together?

The answer is $900$ but I get:

$2!/2!\cdot\binom{3}{2}\cdot 2!/2! = 3$.

Start wearing purple
  • 53,234
  • 13
  • 164
  • 223
OGC
  • 2,305

2 Answers2

3

Let's lay down the consonants first. There are $4!/2!=12$ ways to arrange the letters $V,N,S,S$.

Let's take $SNVS$ for example. How can we insert the vowels? $$*S*N*V*S*$$

Each $*$ represents either $1$ or $0$ vowels. We need to pick three of these stars to place our vowels, and the other two will just be "empty." There are $\binom 5 3 = 10$ ways to choose three stars.

Let's take $*SN*V*S$ for example.

Now we need to place the vowels $A, A, E$ into the 3 stars. There are $3!/2!=3$ ways to do that.

So, $12 \cdot 10 \cdot 3 = 360$

...can someone find my mistake?

So it seems that the question is asking for the complement (thanks Douglas!): how many arrangements have [at least] two adjacent vowels. Simply take the total number of arrangements , which is $\frac{7!}{2!2!}=1260$ and subtract our former answer: $1260-360=\boxed{900}$.

angryavian
  • 89,882
  • I got $360$ calculating in a different order. – Mark Bennet Jul 22 '13 at 15:18
  • I think it is better to lay down the vowels first, since they have the weirdest constraint. – Thomas Andrews Jul 22 '13 at 15:24
  • Just found http://www.happyforlove.com/questions/c_449511/combination-and-permuation – lab bhattacharjee Jul 22 '13 at 15:24
  • @ThomasAndrews I had trouble figuring out how to place the consonants among the vowels such that there is a consonant between each pair of vowels. How do you calculate that? – angryavian Jul 22 '13 at 15:28
  • 1
    Given an ordered triple $a<b<c$ of ${1,2,3,4,5}$ we can take the positions ${a,b+1,c+2}$ for the vowels. So there are $\binom{5}{3}$ position selections for the vowels, and $\binom 3 1$ ways to put them in those positions. – Thomas Andrews Jul 22 '13 at 15:32
  • (And 360 is the answer I get, too. The answer has to be a multiple of $36=4\cdot3\cdot 3$, so $800$ can't be the right answer unless we are missing some additional information.) – Thomas Andrews Jul 22 '13 at 15:35
  • Yes, the answer isn't 800; it is 900. – OGC Jul 22 '13 at 15:44
  • @labbhattacharjee the site happyforlove is a scraper site which takes MSE's content. The admins have been informed and are dealing with it. – Alex Becker Jul 22 '13 at 17:46
  • How did you find the total number of arrangements blf? – OGC Jul 22 '13 at 20:22
  • @user36829 There are $7!$ ways to arrange $7$ different letters. However, since letter $S$ appears twice, we need to divide by $2!$ because we double counted (e.g. $ES_1 S_2 A$ and $ES_2 S_1A$ should be counted once, not twice). We divide by $2!$ again because letter $A$ appears twice as well. – angryavian Jul 22 '13 at 20:27
  • @ThomasAndrews That's neat, I've never seen that ${a, b+1, c+2}$ trick before. Is there a name for it? Does it appear often in other problems? +1 – angryavian Jul 22 '13 at 20:28
  • 1
    I've certainly seen it in many problems were there must be a gap between elements in a subset. Never seen it with a name. – Thomas Andrews Jul 22 '13 at 20:30
  • @blf I think I understand what's going on now. Thanks blf! Now if I try to solve another similar problem with the word OTTAWA, I get: 6!/2! - 3!/2!5C33!/2! = 270. Is this approach correct? – OGC Jul 22 '13 at 20:50
  • I think it should be: 6!/2!2! - 3!/2!4C33!/2! – OGC Jul 22 '13 at 21:59
  • @user36829 You're welcome! That seems right. – angryavian Jul 22 '13 at 22:09
2

In GAP, we can find the permutations via the code:

IsVowel:=function(l)
  return l="A" or l="E" or l="I" or l="O" or l="U";
end;;

L:=["V","A","N","E","S","S","A"];;

S:=Filtered(PermutationsList(L),p->ForAll([1..Size(p)-1],i->not (IsVowel(p[i]) and IsVowel(p[i+1]))));;

Size(S);

This returns 360, as expected. And we can list them all too:

1 ANASESV
2 ANASEVS
3 ANASSEV
4 ANASSVE
5 ANASVES
6 ANASVSE
7 ANAVESS
8 ANAVSES
9 ANAVSSE
10 ANESASV
11 ANESAVS
12 ANESSAV
13 ANESSVA
14 ANESVAS
15 ANESVSA
16 ANEVASS
17 ANEVSAS
18 ANEVSSA
19 ANSASEV
20 ANSASVE
21 ANSAVES
22 ANSAVSE
23 ANSESAV
24 ANSESVA
25 ANSEVAS
26 ANSEVSA
27 ANSSAVE
28 ANSSEVA
29 ANSVASE
30 ANSVESA
31 ANVASES
32 ANVASSE
33 ANVESAS
34 ANVESSA
35 ANVSASE
36 ANVSESA
37 ASANESV
38 ASANEVS
39 ASANSEV
40 ASANSVE
41 ASANVES
42 ASANVSE
43 ASASENV
44 ASASEVN
45 ASASNEV
46 ASASNVE
47 ASASVEN
48 ASASVNE
49 ASAVENS
50 ASAVESN
51 ASAVNES
52 ASAVNSE
53 ASAVSEN
54 ASAVSNE
55 ASENASV
56 ASENAVS
57 ASENSAV
58 ASENSVA
59 ASENVAS
60 ASENVSA
61 ASESANV
62 ASESAVN
63 ASESNAV
64 ASESNVA
65 ASESVAN
66 ASESVNA
67 ASEVANS
68 ASEVASN
69 ASEVNAS
70 ASEVNSA
71 ASEVSAN
72 ASEVSNA
73 ASNASEV
74 ASNASVE
75 ASNAVES
76 ASNAVSE
77 ASNESAV
78 ASNESVA
79 ASNEVAS
80 ASNEVSA
81 ASNSAVE
82 ASNSEVA
83 ASNVASE
84 ASNVESA
85 ASSANEV
86 ASSANVE
87 ASSAVEN
88 ASSAVNE
89 ASSENAV
90 ASSENVA
91 ASSEVAN
92 ASSEVNA
93 ASSNAVE
94 ASSNEVA
95 ASSVANE
96 ASSVENA
97 ASVANES
98 ASVANSE
99 ASVASEN
100 ASVASNE
101 ASVENAS
102 ASVENSA
103 ASVESAN
104 ASVESNA
105 ASVNASE
106 ASVNESA
107 ASVSANE
108 ASVSENA
109 AVANESS
110 AVANSES
111 AVANSSE
112 AVASENS
113 AVASESN
114 AVASNES
115 AVASNSE
116 AVASSEN
117 AVASSNE
118 AVENASS
119 AVENSAS
120 AVENSSA
121 AVESANS
122 AVESASN
123 AVESNAS
124 AVESNSA
125 AVESSAN
126 AVESSNA
127 AVNASES
128 AVNASSE
129 AVNESAS
130 AVNESSA
131 AVNSASE
132 AVNSESA
133 AVSANES
134 AVSANSE
135 AVSASEN
136 AVSASNE
137 AVSENAS
138 AVSENSA
139 AVSESAN
140 AVSESNA
141 AVSNASE
142 AVSNESA
143 AVSSANE
144 AVSSENA
145 ENASASV
146 ENASAVS
147 ENASSAV
148 ENASSVA
149 ENASVAS
150 ENASVSA
151 ENAVASS
152 ENAVSAS
153 ENAVSSA
154 ENSASAV
155 ENSASVA
156 ENSAVAS
157 ENSAVSA
158 ENSSAVA
159 ENSVASA
160 ENVASAS
161 ENVASSA
162 ENVSASA
163 ESANASV
164 ESANAVS
165 ESANSAV
166 ESANSVA
167 ESANVAS
168 ESANVSA
169 ESASANV
170 ESASAVN
171 ESASNAV
172 ESASNVA
173 ESASVAN
174 ESASVNA
175 ESAVANS
176 ESAVASN
177 ESAVNAS
178 ESAVNSA
179 ESAVSAN
180 ESAVSNA
181 ESNASAV
182 ESNASVA
183 ESNAVAS
184 ESNAVSA
185 ESNSAVA
186 ESNVASA
187 ESSANAV
188 ESSANVA
189 ESSAVAN
190 ESSAVNA
191 ESSNAVA
192 ESSVANA
193 ESVANAS
194 ESVANSA
195 ESVASAN
196 ESVASNA
197 ESVNASA
198 ESVSANA
199 EVANASS
200 EVANSAS
201 EVANSSA
202 EVASANS
203 EVASASN
204 EVASNAS
205 EVASNSA
206 EVASSAN
207 EVASSNA
208 EVNASAS
209 EVNASSA
210 EVNSASA
211 EVSANAS
212 EVSANSA
213 EVSASAN
214 EVSASNA
215 EVSNASA
216 EVSSANA
217 NASASEV
218 NASASVE
219 NASAVES
220 NASAVSE
221 NASESAV
222 NASESVA
223 NASEVAS
224 NASEVSA
225 NASSAVE
226 NASSEVA
227 NASVASE
228 NASVESA
229 NAVASES
230 NAVASSE
231 NAVESAS
232 NAVESSA
233 NAVSASE
234 NAVSESA
235 NESASAV
236 NESASVA
237 NESAVAS
238 NESAVSA
239 NESSAVA
240 NESVASA
241 NEVASAS
242 NEVASSA
243 NEVSASA
244 NSASAVE
245 NSASEVA
246 NSAVASE
247 NSAVESA
248 NSESAVA
249 NSEVASA
250 NVASASE
251 NVASESA
252 NVESASA
253 SANASEV
254 SANASVE
255 SANAVES
256 SANAVSE
257 SANESAV
258 SANESVA
259 SANEVAS
260 SANEVSA
261 SANSAVE
262 SANSEVA
263 SANVASE
264 SANVESA
265 SASANEV
266 SASANVE
267 SASAVEN
268 SASAVNE
269 SASENAV
270 SASENVA
271 SASEVAN
272 SASEVNA
273 SASNAVE
274 SASNEVA
275 SASVANE
276 SASVENA
277 SAVANES
278 SAVANSE
279 SAVASEN
280 SAVASNE
281 SAVENAS
282 SAVENSA
283 SAVESAN
284 SAVESNA
285 SAVNASE
286 SAVNESA
287 SAVSANE
288 SAVSENA
289 SENASAV
290 SENASVA
291 SENAVAS
292 SENAVSA
293 SENSAVA
294 SENVASA
295 SESANAV
296 SESANVA
297 SESAVAN
298 SESAVNA
299 SESNAVA
300 SESVANA
301 SEVANAS
302 SEVANSA
303 SEVASAN
304 SEVASNA
305 SEVNASA
306 SEVSANA
307 SNASAVE
308 SNASEVA
309 SNAVASE
310 SNAVESA
311 SNESAVA
312 SNEVASA
313 SSANAVE
314 SSANEVA
315 SSAVANE
316 SSAVENA
317 SSENAVA
318 SSEVANA
319 SVANASE
320 SVANESA
321 SVASANE
322 SVASENA
323 SVENASA
324 SVESANA
325 VANASES
326 VANASSE
327 VANESAS
328 VANESSA
329 VANSASE
330 VANSESA
331 VASANES
332 VASANSE
333 VASASEN
334 VASASNE
335 VASENAS
336 VASENSA
337 VASESAN
338 VASESNA
339 VASNASE
340 VASNESA
341 VASSANE
342 VASSENA
343 VENASAS
344 VENASSA
345 VENSASA
346 VESANAS
347 VESANSA
348 VESASAN
349 VESASNA
350 VESNASA
351 VESSANA
352 VNASASE
353 VNASESA
354 VNESASA
355 VSANASE
356 VSANESA
357 VSASANE
358 VSASENA
359 VSENASA
360 VSESANA

The number 900 probably comes from the number of permutations of VANESSA in which at least two vowels are consecutive, i.e., the number of "bad" permutations. This can be computed:

T:=Filtered(PermutationsList(L),p->not ForAll([1..Size(p)-1],i->not (IsVowel(p[i]) and IsVowel(p[i+1]))));;

Size(T);

This returns 900. (Or mathematically, the total number is given by the multinomial coefficient $7!/(2!^2)=1260$, and so the number of "bad" permutations is $1260-360=900$.)

Douglas S. Stones
  • 21,079
  • Can anyone offer me a more simpler explanation to this problem so that I can use the methods to solve other problems similar to this one? – OGC Jul 22 '13 at 20:29
  • Thanks for finding the error in OP's statement of the question, and for the nice introduction to GAP! :) – angryavian Jul 22 '13 at 22:18