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!
How many 10-digit numbers
-
0Indeed, it looks like my initial interpretation was wrong. (I edited my answer and deleted my comment to match.) – 2012-10-28
2 Answers
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.
-
0Added a cross-check to the answer. But, GAP will print out the 9840 cases. – 2012-10-28
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)
-
0After 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 – 2012-10-28