0
$\begingroup$

Give a combinatorial proof of the following identity: Let $n$ be a positive integer. $n^3 = n(n - 1)(n - 2) + 3n(n - 1) + n$.

How would I go about proving this identity combinatorially? Thank you.

$\endgroup$

closed as off-topic by Morgan Rodgers, José Carlos Santos, Archer, Cesareo, Parcly Taxel Mar 10 at 3:39

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "This question is missing context or other details: Please provide additional context, which ideally explains why the question is relevant to you and our community. Some forms of context include: background and motivation, relevant definitions, source, possible strategies, your current progress, why the question is interesting or important, etc." – Morgan Rodgers, José Carlos Santos, Archer, Cesareo, Parcly Taxel
If this question can be reworded to fit the rules in the help center, please edit the question.

7
$\begingroup$

$n^3$ is the number of possible triplets of numbers from $1$ to $n$. $n(n-1)(n-2)$ is the number of triplets where no $2$ numbers are the same. Then, $n(n-1)$ is the number of triplets with $(a, a, b)$ ($a\not =b$), so $3n(n-1)$ is the number of triplets with exactly two equal elements. $n$ is the number of triplets with all elements the same.

$\endgroup$
  • $\begingroup$ I would assume that the second sentence needs some editing. $\endgroup$ – user Mar 6 at 20:36
  • $\begingroup$ Thank you, this helps tremendously. But how did you determine that $3n(n-1)$ is the set of all lists with exactly two equal elements? $\endgroup$ – M Lee Mar 6 at 20:46
  • $\begingroup$ Because, either first equals the second, or second equals the third or third equals the first. $\endgroup$ – enedil Mar 6 at 20:47
  • $\begingroup$ "that 3n(n−1) is the set of all lists with exactly two equal elements?" Because there are $n(n-1)$ ways you can pick which two elements, and there are $3$ ways you can arrange the two like elements and the one unlike element. $\endgroup$ – fleablood Mar 6 at 22:00
4
$\begingroup$

Consider an $n\times n\times n$ cube. We partition it into five pieces:

First, there is a large $n\times (n-1)\times (n-2)$ block. This leaves an L-shaped piece, of height $n$, with one arm width $1$ and the other arm of width $2$. We partition the arms into three slabs, each of size $n\times 1\times (n-1)$. This leaves the corner of the L, which is a single $n\times 1\times 1$ long piece.

MS Paint masterpiece below:
enter image description here

$\endgroup$
  • $\begingroup$ How is it combinatorial? $\endgroup$ – enedil Mar 6 at 20:11
  • 2
    $\begingroup$ We are double-counting the same object. If you like, take the cube as a collection of $n^3$ small cubes, and we are counting the number of those small cubes. $\endgroup$ – vadim123 Mar 6 at 20:11
  • $\begingroup$ Ok, fair enough $\endgroup$ – enedil Mar 6 at 20:12

Not the answer you're looking for? Browse other questions tagged or ask your own question.