Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

How many $10$-digit numbers have two digits $1$, two digits $2$, three digits $3$, three digits $4$ so that between the two digits $1$ it has at least other two digits and between two digits $2$ it has at least other two digits (not necessarily distinct)? Thanks!

share|improve this question
    
Do you know how this can be done and just don't want to go through the procedure or are you wondering how this can be done? –  mtahmed Oct 28 '12 at 5:32
    
@DouglasS.Stones: I don't see your problem. Whether "of" is present or not, one wants the positions of the two digits 1 to be at distance at least $3$ of each other, and likewise for the positions of the digits 2. I do not think the interpretation "two distinct other digits" is plausible in either formulation. –  Marc van Leeuwen Oct 28 '12 at 6:24
    
Indeed, it looks like my initial interpretation was wrong. (I edited my answer and deleted my comment to match.) –  Douglas S. Stones Oct 28 '12 at 7:04

2 Answers 2

up vote 0 down vote accepted

I computed the number in GAP, which gave 9840.

We should expect it to be divisible by $2 {6 \choose 3}=40$ since the number of ways of placing the 3's and 4's, once the 1's and 2's have been placed, is ${6 \choose 3}$, and we can still swap the 1's and 2's (and indeed it is).

Here's the code:

Check:=function(T,x)
  local i,S;
  i:=1;
  while(T[i]<>x) do i:=i+1; od;
  i:=i+1;
  if(T[i]=x) then return false; fi;
  S:=[];
  while(T[i]<>x) do S:=Concatenation(S,[T[i]]); i:=i+1; od;
  return Size(S)>1;
end;;

A:=Arrangements([1,1,2,2,3,3,3,4,4,4],10);;
count:=0;
for T in A do
  if(Check(T,1) and Check(T,2)) then
    count:=count+1;
    Print(T,"\n");
  fi;
od;

The first few examples are:

[ 1, 2, 3, 1, 2, 3, 3, 4, 4, 4 ]
[ 1, 2, 3, 1, 2, 3, 4, 3, 4, 4 ]
[ 1, 2, 3, 1, 2, 3, 4, 4, 3, 4 ]
[ 1, 2, 3, 1, 2, 3, 4, 4, 4, 3 ]

Some intermediate examples:

[ 1, 3, 3, 1, 2, 3, 4, 2, 4, 4 ]
[ 1, 3, 3, 1, 2, 3, 4, 4, 2, 4 ]
[ 1, 3, 3, 1, 2, 3, 4, 4, 4, 2 ]
[ 1, 3, 3, 1, 2, 4, 3, 2, 4, 4 ]

And the last few are:

[ 4, 4, 4, 3, 2, 3, 1, 2, 3, 1 ]
[ 4, 4, 4, 3, 2, 3, 1, 3, 2, 1 ]
[ 4, 4, 4, 3, 3, 1, 2, 3, 1, 2 ]
[ 4, 4, 4, 3, 3, 2, 1, 3, 2, 1 ]

As a cross-check, here's the 246 ways the 1's and 2's can be placed, ignoring the 3's and 4's, such that the first number is 1.

1 -----12-12
2 ----1-2-12
3 ----1-21-2
4 ----12--12
5 ----12--21
6 ----12-1-2
7 ----12-12-
8 ---1--2-12
9 ---1--21-2
10 ---1-2--12
11 ---1-2--21
12 ---1-2-1-2
13 ---1-2-12-
14 ---1-21--2
15 ---1-21-2-
16 ---12---12
17 ---12---21
18 ---12--1-2
19 ---12--12-
20 ---12--2-1
21 ---12--21-
22 ---12-1--2
23 ---12-1-2-
24 ---12-12--
25 --1---2-12
26 --1---21-2
27 --1--12--2
28 --1--2--12
29 --1--2--21
30 --1--2-1-2
31 --1--2-12-
32 --1--21--2
33 --1--21-2-
34 --1-2---12
35 --1-2---21
36 --1-2--1-2
37 --1-2--12-
38 --1-2--2-1
39 --1-2--21-
40 --1-2-1--2
41 --1-2-1-2-
42 --1-2-12--
43 --1-21---2
44 --1-21--2-
45 --1-21-2--
46 --12----12
47 --12----21
48 --12---1-2
49 --12---12-
50 --12---2-1
51 --12---21-
52 --12--1--2
53 --12--1-2-
54 --12--12--
55 --12--2--1
56 --12--2-1-
57 --12--21--
58 --12-1---2
59 --12-1--2-
60 --12-1-2--
61 --12-12---
62 -1----2-12
63 -1----21-2
64 -1---12--2
65 -1---2--12
66 -1---2--21
67 -1---2-1-2
68 -1---2-12-
69 -1---21--2
70 -1---21-2-
71 -1--1-2--2
72 -1--12---2
73 -1--12--2-
74 -1--2---12
75 -1--2---21
76 -1--2--1-2
77 -1--2--12-
78 -1--2--2-1
79 -1--2--21-
80 -1--2-1--2
81 -1--2-1-2-
82 -1--2-12--
83 -1--21---2
84 -1--21--2-
85 -1--21-2--
86 -1-2----12
87 -1-2----21
88 -1-2---1-2
89 -1-2---12-
90 -1-2---2-1
91 -1-2---21-
92 -1-2--1--2
93 -1-2--1-2-
94 -1-2--12--
95 -1-2--2--1
96 -1-2--2-1-
97 -1-2--21--
98 -1-2-1---2
99 -1-2-1--2-
100 -1-2-1-2--
101 -1-2-12---
102 -1-21----2
103 -1-21---2-
104 -1-21--2--
105 -1-21-2---
106 -12-----12
107 -12-----21
108 -12----1-2
109 -12----12-
110 -12----2-1
111 -12----21-
112 -12---1--2
113 -12---1-2-
114 -12---12--
115 -12---2--1
116 -12---2-1-
117 -12---21--
118 -12--1---2
119 -12--1--2-
120 -12--1-2--
121 -12--12---
122 -12--2---1
123 -12--2--1-
124 -12--2-1--
125 -12--21---
126 -12-1----2
127 -12-1---2-
128 -12-1--2--
129 -12-1-2---
130 -12-12----
131 1-----2-12
132 1-----21-2
133 1----12--2
134 1----2--12
135 1----2--21
136 1----2-1-2
137 1----2-12-
138 1----21--2
139 1----21-2-
140 1---1-2--2
141 1---12---2
142 1---12--2-
143 1---2---12
144 1---2---21
145 1---2--1-2
146 1---2--12-
147 1---2--2-1
148 1---2--21-
149 1---2-1--2
150 1---2-1-2-
151 1---2-12--
152 1---21---2
153 1---21--2-
154 1---21-2--
155 1--1--2--2
156 1--1-2---2
157 1--1-2--2-
158 1--12----2
159 1--12---2-
160 1--12--2--
161 1--2----12
162 1--2----21
163 1--2---1-2
164 1--2---12-
165 1--2---2-1
166 1--2---21-
167 1--2--1--2
168 1--2--1-2-
169 1--2--12--
170 1--2--2--1
171 1--2--2-1-
172 1--2--21--
173 1--2-1---2
174 1--2-1--2-
175 1--2-1-2--
176 1--2-12---
177 1--21----2
178 1--21---2-
179 1--21--2--
180 1--21-2---
181 1-2-----12
182 1-2-----21
183 1-2----1-2
184 1-2----12-
185 1-2----2-1
186 1-2----21-
187 1-2---1--2
188 1-2---1-2-
189 1-2---12--
190 1-2---2--1
191 1-2---2-1-
192 1-2---21--
193 1-2--1---2
194 1-2--1--2-
195 1-2--1-2--
196 1-2--12---
197 1-2--2---1
198 1-2--2--1-
199 1-2--2-1--
200 1-2--21---
201 1-2-1----2
202 1-2-1---2-
203 1-2-1--2--
204 1-2-1-2---
205 1-2-12----
206 1-21-----2
207 1-21----2-
208 1-21---2--
209 1-21--2---
210 1-21-2----
211 12------12
212 12------21
213 12-----1-2
214 12-----12-
215 12-----2-1
216 12-----21-
217 12----1--2
218 12----1-2-
219 12----12--
220 12----2--1
221 12----2-1-
222 12----21--
223 12---1---2
224 12---1--2-
225 12---1-2--
226 12---12---
227 12---2---1
228 12---2--1-
229 12---2-1--
230 12---21---
231 12--1----2
232 12--1---2-
233 12--1--2--
234 12--1-2---
235 12--12----
236 12--2----1
237 12--2---1-
238 12--2--1--
239 12--2-1---
240 12--21----
241 12-1-----2
242 12-1----2-
243 12-1---2--
244 12-1--2---
245 12-1-2----
246 12-12-----

We would expect $246 \cdot 2{6 \choose 3}=9840$ completions in total.

share|improve this answer
    
My answer is 8440. –  Schwarz Oct 28 '12 at 7:25
    
Added a cross-check to the answer. But, GAP will print out the 9840 cases. –  Douglas S. Stones Oct 28 '12 at 8:37

I am not sure if I get your problem right, but from my understanding I think a very simple solution exists - number of 10 digits numbers with two 1 digit, two 2 digit, three 3 digit and three 4 digit - 10!/(2! 2! 3! 3!) = 25200, this includes all possible numbers, now we consider the cases where between two digit 1 exactly one other digit is present - to determine this we consider first 1 is at first position and second 1 is at position third (eg 1-1-------) now for 8 remaining position two digit 2, three digit 3 and three digit 4 can be arranged - 8!/(2!3!3!) = 560, so for each of the 8 such combination [(1st - 3rd) (3rd - 5th) (2nd - 4th) ..... ] we get 8*560 = 4480 cases, now if we consider the case where two digit 1 are placed consecutive we get 9 cases and for each case 560 distinct arrangements, so total 4480+9*560=9520 distinct cases are there where between two digit 1 less than 1 other digit is present, subtracting the number we get 25200-9520=15680 cases where between two digit 1 two or more other digit (not necessarily distinct) is present, similarly for two digit 2 we also get same number of cases so total number of cases(25200) - [[number of cases where between two digit 1 one or less digit is present (9520)] or [number of cases where between two digit 2 one or less digit is present (9520)]] = 6160 numbers where between the two digits 1 it has at least other two digits and between two digits 2 it has at least other two digits (not necessarily distinct)

share|improve this answer
    
After posting the solution I found one glitch in the answer while subtracting two cases one by one I subtracted the cases twice where both happens in unison, need to add those cases, let me think –  Diptarag Oct 28 '12 at 8:18

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.