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!
$\begingroup$
$\endgroup$
3
-
$\begingroup$ 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? $\endgroup$ – mmtauqir Oct 28 '12 at 5:32
-
$\begingroup$ @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. $\endgroup$ – Marc van Leeuwen Oct 28 '12 at 6:24
-
$\begingroup$ Indeed, it looks like my initial interpretation was wrong. (I edited my answer and deleted my comment to match.) $\endgroup$ – Douglas S. Stones Oct 28 '12 at 7:04
Add a comment
|
$\begingroup$
$\endgroup$
2
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.
answered Oct 28 '12 at 5:36
-
-
$\begingroup$ Added a cross-check to the answer. But, GAP will print out the 9840 cases. $\endgroup$ – Douglas S. Stones Oct 28 '12 at 8:37
$\begingroup$
$\endgroup$
1
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)
-
$\begingroup$ 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 $\endgroup$ – Diptarag Oct 28 '12 at 8:18
