lotus

previous page: 102 combinatorics/subsets.p
  
page up: Puzzles FAQ
  
next page: 104 competition/contests/games.magazine.p

103 combinatorics/transitions.p




Description

This article is from the Puzzles FAQ, by Chris Cole chris@questrel.questrel.com and Matthew Daly mwdaly@pobox.com with numerous contributions by others.

103 combinatorics/transitions.p


How many n-bit binary strings (0/1) have exactly k transitions
(an adjacent pair of dissimilar bits, i.e., a 01 or a 10)?

combinatorics/transitions.s

A transition can occur at an adjacent pair (i,i+1) where 1<=i<i+1<=n.
Since there are k transitions, there are C(n-1,k) total number of ways
that transitions can occur. But the string may start with a 1 or a 0
(after which its transitions uniquely determine the string). So there
are a total of 2C(n-1,k) such strings.

 

Continue to:













TOP
previous page: 102 combinatorics/subsets.p
  
page up: Puzzles FAQ
  
next page: 104 competition/contests/games.magazine.p