4
$\begingroup$

Possible Duplicate:
Proving an equality involving compositions of an integer

A sequence of natural numbers $\langle a_1,\ldots,a_k \rangle$ is an ordered partition of $n$ if $\sum_{i=1}^k a_i=n$. Prove that for $n\ge 4$, the number of occurrences of $3$ in all ordered partitions of $n$ is $n \cdot 2^{n-5}$.

I don't know how to approach. Usually I meet problems on partitions where generating functions are useful, but here I think only combinatorial interpretation can help.

  • 0
    There are two good answers at the duplicate that I just cited.2012-09-08

0 Answers 0