6

Part of VMEO I 2004

Problems(1)

no of binary sequences of length n that are not equivalent.

Source: 2004 VMEO I p6 Vietnamese Mathematics e - Olympiad https://artofproblemsolving.com/community/c2461015_vmeo__vietnam_mathematical

Consider all binary sequences of length

n

. In a sequence that allows the interchange of positions of an arbitrary set of

k

adjacent numbers, (

k < n

), two sequences are said to be equivalent if they can be transformed from one sequence to another by a finite number of transitions as above. Find the number of sequences that are not equivalent.

combinatoricsSequences