Combinatorics and Graph Theory · Problem 1.3.10

Fundamentals — David Guichard

Mathematics — Combinatorics · counting-compositions

Problem

Find the number of ways to write

n

as an ordered sum of ones and twos,

n \geq 0

. For example, when

n = 4

, there are five ways:

1+1+1+1

2+1+1

1+2+1

1+1+2

, and

2+2