I have 6 digits (e.g: 1,2,3,4,5,6), then I use these digits to form a sequence of six digit pairs. Each digit in the given set can be used twice, and only two different digits can be formed into a pair. How to determine the number of sequences that can be generated?
Example:
The digits provided: 1,2,3,4,5,6
This is a valid sequence:
#1 | #2 | #3 | #4 | #5 | #6
--------------------------- 1 | 3 | 5 | 1 | 3 | 5 2 | 4 | 6 | 2 | 4 | 6
This sequence won't be counted since it's the same sequence as the one above
#1 | #2 | #3 | #4 | #5 | #6
--------------------------- 1 | 4 | 6 | 2 | 4 | 5 2 | 3 | 5 | 1 | 3 | 6
But this one will:
#1 | #2 | #3 | #4 | #5 | #6
--------------------------- 1 | 1 | 3 | 3 | 5 | 5 2 | 2 | 4 | 4 | 6 | 6
This is an invalid sequence (two '1' in the same pair)
#1 | #2 | #3 | #4 | #5 | #6
--------------------------- 1 | 3 | 5 | 3 | 2 | 5 1 | 4 | 6 | 2 | 4 | 6
This one is invalid, too. Each digit must appear twice, not more or less.
#1 | #2 | #3 | #4 | #5 | #6
--------------------------- 1 | 3 | 5 | 2 | 3 | 5 2 | 4 | 6 | 1 | 1 | 1To sum up:
- We have a set of 6 distinct digits.
- Two different digits form a pair, without ordering.
- Each digit must be used twice (i.e: there will always be 2 pair containing the same digits).
- Six pairs will be placed into a sequence, with ordering.
2 Answers
$\begingroup$(This question was bumped to the Main Page by "Community".)
We first have to obtain an overview over the admissible pairings $P$ of the multiset $\{1^2,2^2,\ldots, 6^2\}$. To each such $P$ we associate a graph on the vertex set $[6]$ as follows: For each pair $\{x,y\}\in P$ draw an edge $\{x,y\}$. The resulting graph $\Gamma$ may have double edges, but all vertices have degree $2$. It follows that $\Gamma$ is a union of disjoint cycles, whereby the following length spectra are possible: $$({\rm i}):\ (6),\qquad ({\rm ii}):\ (4,2),\qquad ({\rm iii}):\ (3,3),\qquad ({\rm iv}):\ (2,2,2)\ .$$ In case (i) we can connect the six vertices to a $6$-cycle in ${5\cdot4\cdot3\cdot 2\over2}=60$ ways. (Note that $\Gamma$ is nondirected, hence the $2$ in the denominator). Since case (i) always leads to $6$ different pairs we obtain $6!\cdot 60=43\,200$ sequences of the described kind.
In case (ii) we can choose the $2$-cycle in ${6\choose2}=15$ ways, and then we can connect the remaining four vertices to a nondirected $4$-cycle in ${3\cdot2\over2}=3$ ways. Since the $2$-cycle encodes two equal pairs we can arrange the chosen pairs in ${6!\over2}=360$ ways to a sequence, so that we obtain $15\cdot3\cdot 360=16\,200$ sequences in this case.
In case (iii) we can split the $6$ vertices into two triples in ${5\choose2}=10$ ways, because vertex $v_1$ can be associated with any two of the five other vertices. Since case (iii) always leads to $6$ different pairs we obtain $6!\cdot 10=7200$ sequences of the described kind.
In case (iv) we can pair off the six vertices in $5\cdot3=15$ ways, and we always obtain three double-pairs. It follows that there are ${6!\over 2^3}\cdot 15=1350$ sequences in this case.
The total number of sequences in question therefore is ${\bf 67\,950}$.
$\endgroup$ $\begingroup$Let a1, a2, ... ak k <= 6 all the different numbers used to form the pairs. They can not be taken more than twice so they fill at most 2k boxes. Now it has to fill 12 boxes so k>= 6 and then k = 6. That figures all appear exactly twice in the set.
And form 6 pairs satisfying the imposed rules, is to fill the following 12 cases,
o o o o o o
o o o o o o
reserving two locations from 12 to 1 and 2 locations from 10 to 2,… so that the same numbers are not the same in pairs.
Counting
Without taking into account that the pairs must not contain identical numbers, it has total:
total = C (12,2) * C (10,2) * C (8.2) * C (6.2) * C (4.2) * C (2,2) possibilities.
(In the first pair of boxes chosen there is 1, the second 2, etc.)
To get the number sought, we use the principle of inclusion-exclusion:
Let Pi all distributions such as the pair i has identical numbers.
Must determine
total-|P1 union P2 union … union P6|= total - sum|Pi| + sum_{i<j}|Pi inter Pj|- sum_{i<j<k}|Pi inter Pj inter Pk|+…
|Pi|=6*C(10,2)*C(8,2)*C(6,2)*C(4,2) 6 is the choice of the number of the "pair" Pi
|Pi inter Pj| = C(6,2)*6*5**C(8,2)*C(6,2)*C(4,2)
...
For programming, you can use a 12-array of integers, initialized to 0.
oooooo oooooo
The first 6 items from 0 to 5 representing the first element of each pair, and 6-11 the second element of each pair.
Then, we do vary (i1, j1) couple as 0 <= i1 < j1 < 12 and i1 + 6 <>j1 to place number 1,...
then we vary (i2, j2) such as 0 <= i2 < j2 < 10 and i2 + 6 <>j2 to place number 2, in the holes not occupied by 1,...
until (i6,j6)
$\endgroup$
