Porisma

Worked solution

Separate fixed digit counts from adjacent-repeat complements

A student working on a coding project studies 11-digit quaternary sequences. A quaternary sequence is a sequence formed using the digits 0, 1, 2 or 3. Examples are 12030201131, 01122211100, 12321232123 and 00000000000. Find the number of ways that 11-digit quaternary sequences can be formed with

(i) no restriction, mark

(ii) exactly four 0 s and four 2 s, marks

(iii) at least two consecutive digits that are the same. marks

[2017/PJC/II/9]

CJC · Review problems · Question 2

Answer

(i) 4194304; (ii) 92400; (iii) 3958108.

(i) Four choices per position

Leading zeros are permitted in a sequence. The count is 411=41943044^{11}=4194304.

How did this part go?

(ii) Method 1: classify the remaining three digits

The remaining digits are 1 or 3. If their multiplicities are one of one type and two of the other, there are 2×11!/(4!4!2!)=693002\times11!/(4!4!2!)=69300 strings. If all three have one type, there are 2×11!/(4!4!3!)=231002\times11!/(4!4!3!)=23100. The disjoint total is 69300+23100=9240069300+23100=92400.

How did this part go?

(ii) Method 2: choose the occupied slots

Choose four of the eleven positions for zeros, four of the remaining seven for twos, and fill each of the last three positions independently with 1 or 3. Thus (114)(74) 23=92400\binom{11}4\binom74\,2^3=92400.

How did this part go?

(iii) Exclude strings with no equal neighbours

For the complement, the first position has four choices and each subsequent position has three choices, excluding only its predecessor. Therefore 411−4×310=4194304−236196=39581084^{11}-4\times3^{10}=4194304-236196=3958108.

How did this part go?

Common mistakes

Part (iii) requires at least one adjacent equal pair, not all repeated digits to be consecutive.

Solution notes

All three asks, both methods in(ii), the complement and printed marks retained. The examples explicitly establish that leading zeros are valid.

Read the hint