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
    I edited your question to hopefully clarify the meaning. Please check to make sure that I correctly interpreted what you were asking.2012-09-08
  • 0
    Thank you very much for editing. It is exactly what I was trying to ask.2012-09-08
  • 0
    If I understand correctly, you're not including zero in the natural numbers. Am I right?2012-09-08
  • 0
    that's right, only positive integers2012-09-08
  • 0
    There are two good answers at the duplicate that I just cited.2012-09-08

0 Answers 0