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.

$\endgroup$
5
  • $\begingroup$ I edited your question to hopefully clarify the meaning. Please check to make sure that I correctly interpreted what you were asking. $\endgroup$ – Michael Joyce Sep 8 '12 at 21:04
  • $\begingroup$ Thank you very much for editing. It is exactly what I was trying to ask. $\endgroup$ – ray Sep 8 '12 at 21:05
  • $\begingroup$ If I understand correctly, you're not including zero in the natural numbers. Am I right? $\endgroup$ – Rod Carvalho Sep 8 '12 at 21:23
  • $\begingroup$ that's right, only positive integers $\endgroup$ – ray Sep 8 '12 at 21:27
  • $\begingroup$ There are two good answers at the duplicate that I just cited. $\endgroup$ – Brian M. Scott Sep 8 '12 at 21:56