MathB.in - Share Mathematics with LaTeX and Markdown

> Suppose u have 6 digit number generator, and it won't permit more than 2 of the same number within the 6 digit sequence. How do u figure out how many sequences are permitted?

*Warning: The text below is long, unclear in places, and overly complicated. It may also contain false statements.*

One way to answer the above question is to calculate the number of 6-digit sequences with:

1. No digits repeated (e.g., 046792). There are 151200 of these (see below).
2. One digit repeated once (e.g., 046794). There are 453600 of these (see below).
3. Two digits each repeated once (e.g., 646794). There are 226800 of these (see below).
4. Three digits each repeated once (e.g., 646774). There are 10800 of these (see below).

Any other 6-digit sequence would have more than 2 occurrences of the same digit, so the total number of 6-digit sequences in which each digit is repeated at most once is the sum of the sequences in the above four categories, i.e. $$151200+453600+226800+10800=842400$$

Below I give a way to calculate the number of sequences in each of the above four categories. Some of the explanations assume familiarity with the [multinomial coefficient](http://mathworld.wolfram.com/MultinomialCoefficient.html) or [BOOKKEEPER rule](https://dspace.mit.edu/bitstream/handle/1721.1/104427/6-042j-spring-2005/contents/lecture-notes/l15_counting3.pdf).

As an illustration of the BOOKKEEPER rule, say you were to form the word "BOOKKEEPER" out of Scrabble tiles. You would need 1 B, 2 Os, 2 Ks, 3 Es, 1 P, and 1 R. The BOOKKEEPER rule states that the number of different ways to arrange those tiles in a sequence is $$(1,2,2,3,1,1)! = (1+2+2+3+1+1)!/(1!2!2!3!1!1!) = 151200$$

## 1. Calculating the number of 6-digit sequences with no digits repeated (e.g. 046792)

The first digit can be any of the 10 digits. No repetitions are allowed in this category, so that leaves 9 possibilities for the second digit. After choosing two unique digits for the first two digits, 8 possibilities remain for the third digit, and so on, down to 5 possibilities for the sixth digit. Therefore, the number of 6-digit sequences with no digits repeated is $$10*9*8*7*6*5  = 151200$$

## 2. Calculating the number of 6-digit sequences with one digit repeated once (e.g. 046794).

Consider a *template* for a 6-digit sequence with one digit repeated once. The template will show the positions of the digits that are distinct and the positions of the digits that repeat, but not the actual digits themselves. One representation for such a template is a 6-letter sequence with four Xs and two As (e.g., XXXXAA, XAXXAX, AXXXAX) in which each X represents a non-repeated digit and the two As represent the repeated digit. In this representation, the template for 046794 would be XAXXXA. By the BOOKKEEPER rule, the number of these templates is $$(4,2)! = \frac{(4+2)!}{4!2!} = 15$$

Let the repeated digit be any of the 10 digits. No other repetitions are allowed in this category, so there are 9 possibilities for the first non-repeated digit, 8 possibilities for the second, and so on, down to 6 possibilities for the fourth non-repeated digit. This means that the number of ways to fill in each of the 15 templates is $$10*9*8*7*6 = 30240$$

The number of 6-digit sequences with one digit repeated is equal to the number of templates for this multiplied by the number of ways to fill in each template, i.e., $$15 * 30240 = 453600$$

## 3. Calculating the number of 6-digit sequences with two digits each repeated once (e.g. 646794)

A template for a 6-digit sequence with two digits repeated can be a 6-letter sequence with two Xs, two As, and two Bs (e.g., XXAABB, BXBAAX) in which each X represents a non-repeated digit, each A represents an occurrence of one of the repeated digits, and each B represents an occurrence of the other repeated digits. By the BOOKKEEPER rule, the number of these templates is $$(2,2,2)! = \frac{(2+2+2)!}{2!2!2!} = 90$$

However, in this scheme, there are two different templates could yield 646794: ABAXXB and BABXXA. This is because swapping the As and Bs yields an equivalent template, which implies that half of the templates are essentially duplicates. To account for this, I'll divide the number of templates by 2. This leaves 45 templates.

For each of the 45 templates, there are 10 ways to choose the first repeated digit, 9 ways to choose the other (different) repeated digit, and 8*7 ways to choose the remaining two non-repeated digits, for a total of $10*9*8*7 = 5040$ ways to fill in each of the 45 templates. The number of 6-digit sequences with two digits repeated is therefore $$45 * 5040 = 226800$$

## 4. Calculating the number of 6-digit sequences with three digits each repeated once (e.g. 646774)

The template for a 6-digit sequence with 3 digits repeated can be represented by a 6-letter sequence with two As, two Bs, and two Cs, in which each different letter represents a different digit (e.g., AABBCC, BACBAC, CCBAAB). By the BOOKKEEPER rule, there are $(2,2,2)! = (2+2+2)!/(2!2!2!) = 90$ of these templates. However, swapping any two pairs of identical letters (e.g. swapping both As for both Bs) yields an equivalent template (in the sense that each could result in the same 6-digit sequence). For example, the following 6 templates are equivalent: AABBCC, AACCBB, BBAACC, BBCCAA, CCAABB, and CCBBAA.

For any of the templates in this scheme, there are 3 ways to choose the first letter, 2 ways to choose the next letter, and 1 way to choose the final letter, which yields a total of $3*2*1=6$ equivalent ways to rearrange the letters in each template. To account for this, I'll divide the 90 templates by 6, leaving 15 templates.

Since the three repeated digits must be different, there are 10 possibilities for the first repeated digit, 9 for the second repeated digit, and 8 for the third repeated digit. There are therefore $10*9*8 = 720$ ways to fill in each of the 15 templates. The number of 6-digit sequences with 3 digits each repeated once is therefore $$15*720 = 10800$$

Thu, 01 Aug 2019 03:52 GMT