MathDB
Problems
Contests
Undergraduate contests
VTRMC
2006 VTRMC
Problem 2
Problem 2
Part of
2006 VTRMC
Problems
(1)
counting sequences of letters, Cs in a block
Source: VTRMC 2006 P2
6/5/2021
Let
S
(
n
)
S(n)
S
(
n
)
denote the number of sequences of length
n
n
n
formed by the three letters
A
,
B
,
C
A,B,C
A
,
B
,
C
with the restriction that the
C
C
C
's (if any) all occur in a single block immediately following the first
B
B
B
(if any). For example
A
B
C
C
A
A
ABCCAA
A
BCC
AA
,
A
A
A
B
A
A
AAABAA
AAA
B
AA
, and
A
B
C
C
C
C
ABCCCC
A
BCCCC
are counted in, but
A
C
A
C
C
B
ACACCB
A
C
A
CCB
and
C
A
A
A
A
A
CAAAAA
C
AAAAA
are not. Derive a simple formula for
S
(
n
)
S(n)
S
(
n
)
and use it to calculate
S
(
10
)
S(10)
S
(
10
)
.
combinatorics