Non combinatorial proof of formula for $n^n$?












12












$begingroup$


I came across the below identity:
$$
n^n=sum_{k=1}^nfrac{n!}{(n-k)!}cdot kcdot n^{n-k-1}
$$
A combinatorial proof of this fact is as follows. Consider the collection of lists of length $n$, where each entry is an integer between 1 and $n$ inclusive. Clearly there are $n^n$ such lists. Let the freshness of a list be the largest $k$ for which the first $k$ entries of the list are distinct. You can then show that the number of lists whose freshness is $k$ is given by $frac{n!}{(n-k)!}cdot kcdot n^{n-k-1}$, so summing over $k$ gives all $n^n$ possible lists.



My question: can anyone think of a proof of this which isn't combinatorial? One that only uses algebraic manipulations, induction, or generating functions?






combinatorics







share|cite|improve this question











$endgroup$








  • 2




    $begingroup$
    Mathematica is able to do it.
    $endgroup$
    – Stephen Montgomery-Smith
    Jul 15 '15 at 3:21
















12












$begingroup$


I came across the below identity:
$$
n^n=sum_{k=1}^nfrac{n!}{(n-k)!}cdot kcdot n^{n-k-1}
$$
A combinatorial proof of this fact is as follows. Consider the collection of lists of length $n$, where each entry is an integer between 1 and $n$ inclusive. Clearly there are $n^n$ such lists. Let the freshness of a list be the largest $k$ for which the first $k$ entries of the list are distinct. You can then show that the number of lists whose freshness is $k$ is given by $frac{n!}{(n-k)!}cdot kcdot n^{n-k-1}$, so summing over $k$ gives all $n^n$ possible lists.



My question: can anyone think of a proof of this which isn't combinatorial? One that only uses algebraic manipulations, induction, or generating functions?






combinatorics







share|cite|improve this question











$endgroup$








  • 2




    $begingroup$
    Mathematica is able to do it.
    $endgroup$
    – Stephen Montgomery-Smith
    Jul 15 '15 at 3:21














12












12








12


5



$begingroup$


I came across the below identity:
$$
n^n=sum_{k=1}^nfrac{n!}{(n-k)!}cdot kcdot n^{n-k-1}
$$
A combinatorial proof of this fact is as follows. Consider the collection of lists of length $n$, where each entry is an integer between 1 and $n$ inclusive. Clearly there are $n^n$ such lists. Let the freshness of a list be the largest $k$ for which the first $k$ entries of the list are distinct. You can then show that the number of lists whose freshness is $k$ is given by $frac{n!}{(n-k)!}cdot kcdot n^{n-k-1}$, so summing over $k$ gives all $n^n$ possible lists.



My question: can anyone think of a proof of this which isn't combinatorial? One that only uses algebraic manipulations, induction, or generating functions?






combinatorics







share|cite|improve this question











$endgroup$




I came across the below identity:
$$
n^n=sum_{k=1}^nfrac{n!}{(n-k)!}cdot kcdot n^{n-k-1}
$$
A combinatorial proof of this fact is as follows. Consider the collection of lists of length $n$, where each entry is an integer between 1 and $n$ inclusive. Clearly there are $n^n$ such lists. Let the freshness of a list be the largest $k$ for which the first $k$ entries of the list are distinct. You can then show that the number of lists whose freshness is $k$ is given by $frac{n!}{(n-k)!}cdot kcdot n^{n-k-1}$, so summing over $k$ gives all $n^n$ possible lists.



My question: can anyone think of a proof of this which isn't combinatorial? One that only uses algebraic manipulations, induction, or generating functions?






combinatorics




combinatorics






share|cite|improve this question















share|cite|improve this question













share|cite|improve this question




share|cite|improve this question








edited Jul 15 '15 at 4:47









Stephen Montgomery-Smith

17.8k12247




17.8k12247










asked Jul 15 '15 at 1:51









Mike EarnestMike Earnest

27.5k22152




27.5k22152








  • 2




    $begingroup$
    Mathematica is able to do it.
    $endgroup$
    – Stephen Montgomery-Smith
    Jul 15 '15 at 3:21














  • 2




    $begingroup$
    Mathematica is able to do it.
    $endgroup$
    – Stephen Montgomery-Smith
    Jul 15 '15 at 3:21








2




2




$begingroup$
Mathematica is able to do it.
$endgroup$
– Stephen Montgomery-Smith
Jul 15 '15 at 3:21




$begingroup$
Mathematica is able to do it.
$endgroup$
– Stephen Montgomery-Smith
Jul 15 '15 at 3:21










2 Answers
2






active

oldest

votes


















11












$begingroup$

Note: This is just a kind of streamlining of existing answers. The addendum of @MarkoRiedels answer already provides the calculation and it's using as essential step @StephenMontgomery-Smith's hint regarding telescoping.



In fact we don't need any generating functions, since we can show the validity of OPs identity by a few simple transformations.




begin{align*}
color{blue}{sum_{k=1}^{n}}&color{blue}{frac{n!}{(n-k)!}kn^{n-k-1}}\
&=n!sum_{k=1}^{n}frac{n-(n-k)}{(n-k)!}n^{n-k-1}tag{1}\
&=n!left(sum_{k=1}^{n}frac{n^{n-k}}{(n-k)!}-sum_{k=1}^{n-1}frac{n^{n-k-1}}{(n-k-1)!}right)tag{2}\
&=n!left(sum_{k=1}^{n}frac{n^{n-k}}{(n-k)!}-sum_{k=2}^{n}frac{n^{n-k}}{(n-k)!}right)tag{3}\
&=n!frac{n^{n-1}}{(n-1)!}\
&color{blue}{=n^n}
end{align*}




Comment:




  • In (1) we use $k=n-(n-k)$


  • In (2) observe, that the upper limit of the second sum is $n-1$ since $(n-k)=0$ in case $k=n$


  • In (3) we shift the index of the second sum by $1$ to prepare the telescoping.







share|cite|improve this answer











$endgroup$













  • $begingroup$
    (+1). Thank you for the kind remark. I was quite off base applying residue calculus to this problem.
    $endgroup$
    – Marko Riedel
    Jul 16 '15 at 17:58










  • $begingroup$
    @MarkoRiedel: You're welcome!
    $endgroup$
    – Markus Scheuer
    Jul 16 '15 at 19:04



















7












$begingroup$

Let
$$ f(n,k) = cases{ frac{n!}{(n-k)!} n^{n-k} & $k le n$ cr 0 & $k>n$}.$$
Then see that
$$ f(n,k) - f(n,k+1) = frac{n!}{(n-k)!} k n^{n-k-1} .$$
Now use a telescoping sum.



(Motivation - $f(n,k)$ is the number of sequences whose freshness is at least $k$.)






share|cite|improve this answer











$endgroup$













  • $begingroup$
    Very nice! I wonder if this was what Mathematica's method was
    $endgroup$
    – Mike Earnest
    Jul 15 '15 at 4:10












Your Answer





StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");

StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "69"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);

StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});

function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});


}
});














draft saved

draft discarded


















StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f1361500%2fnon-combinatorial-proof-of-formula-for-nn%23new-answer', 'question_page');
}
);

Post as a guest















Required, but never shown

























2 Answers
2






active

oldest

votes








2 Answers
2






active

oldest

votes









active

oldest

votes






active

oldest

votes









11












$begingroup$

Note: This is just a kind of streamlining of existing answers. The addendum of @MarkoRiedels answer already provides the calculation and it's using as essential step @StephenMontgomery-Smith's hint regarding telescoping.



In fact we don't need any generating functions, since we can show the validity of OPs identity by a few simple transformations.




begin{align*}
color{blue}{sum_{k=1}^{n}}&color{blue}{frac{n!}{(n-k)!}kn^{n-k-1}}\
&=n!sum_{k=1}^{n}frac{n-(n-k)}{(n-k)!}n^{n-k-1}tag{1}\
&=n!left(sum_{k=1}^{n}frac{n^{n-k}}{(n-k)!}-sum_{k=1}^{n-1}frac{n^{n-k-1}}{(n-k-1)!}right)tag{2}\
&=n!left(sum_{k=1}^{n}frac{n^{n-k}}{(n-k)!}-sum_{k=2}^{n}frac{n^{n-k}}{(n-k)!}right)tag{3}\
&=n!frac{n^{n-1}}{(n-1)!}\
&color{blue}{=n^n}
end{align*}




Comment:




  • In (1) we use $k=n-(n-k)$


  • In (2) observe, that the upper limit of the second sum is $n-1$ since $(n-k)=0$ in case $k=n$


  • In (3) we shift the index of the second sum by $1$ to prepare the telescoping.







share|cite|improve this answer











$endgroup$













  • $begingroup$
    (+1). Thank you for the kind remark. I was quite off base applying residue calculus to this problem.
    $endgroup$
    – Marko Riedel
    Jul 16 '15 at 17:58










  • $begingroup$
    @MarkoRiedel: You're welcome!
    $endgroup$
    – Markus Scheuer
    Jul 16 '15 at 19:04
















11












$begingroup$

Note: This is just a kind of streamlining of existing answers. The addendum of @MarkoRiedels answer already provides the calculation and it's using as essential step @StephenMontgomery-Smith's hint regarding telescoping.



In fact we don't need any generating functions, since we can show the validity of OPs identity by a few simple transformations.




begin{align*}
color{blue}{sum_{k=1}^{n}}&color{blue}{frac{n!}{(n-k)!}kn^{n-k-1}}\
&=n!sum_{k=1}^{n}frac{n-(n-k)}{(n-k)!}n^{n-k-1}tag{1}\
&=n!left(sum_{k=1}^{n}frac{n^{n-k}}{(n-k)!}-sum_{k=1}^{n-1}frac{n^{n-k-1}}{(n-k-1)!}right)tag{2}\
&=n!left(sum_{k=1}^{n}frac{n^{n-k}}{(n-k)!}-sum_{k=2}^{n}frac{n^{n-k}}{(n-k)!}right)tag{3}\
&=n!frac{n^{n-1}}{(n-1)!}\
&color{blue}{=n^n}
end{align*}




Comment:




  • In (1) we use $k=n-(n-k)$


  • In (2) observe, that the upper limit of the second sum is $n-1$ since $(n-k)=0$ in case $k=n$


  • In (3) we shift the index of the second sum by $1$ to prepare the telescoping.







share|cite|improve this answer











$endgroup$













  • $begingroup$
    (+1). Thank you for the kind remark. I was quite off base applying residue calculus to this problem.
    $endgroup$
    – Marko Riedel
    Jul 16 '15 at 17:58










  • $begingroup$
    @MarkoRiedel: You're welcome!
    $endgroup$
    – Markus Scheuer
    Jul 16 '15 at 19:04














11












11








11





$begingroup$

Note: This is just a kind of streamlining of existing answers. The addendum of @MarkoRiedels answer already provides the calculation and it's using as essential step @StephenMontgomery-Smith's hint regarding telescoping.



In fact we don't need any generating functions, since we can show the validity of OPs identity by a few simple transformations.




begin{align*}
color{blue}{sum_{k=1}^{n}}&color{blue}{frac{n!}{(n-k)!}kn^{n-k-1}}\
&=n!sum_{k=1}^{n}frac{n-(n-k)}{(n-k)!}n^{n-k-1}tag{1}\
&=n!left(sum_{k=1}^{n}frac{n^{n-k}}{(n-k)!}-sum_{k=1}^{n-1}frac{n^{n-k-1}}{(n-k-1)!}right)tag{2}\
&=n!left(sum_{k=1}^{n}frac{n^{n-k}}{(n-k)!}-sum_{k=2}^{n}frac{n^{n-k}}{(n-k)!}right)tag{3}\
&=n!frac{n^{n-1}}{(n-1)!}\
&color{blue}{=n^n}
end{align*}




Comment:




  • In (1) we use $k=n-(n-k)$


  • In (2) observe, that the upper limit of the second sum is $n-1$ since $(n-k)=0$ in case $k=n$


  • In (3) we shift the index of the second sum by $1$ to prepare the telescoping.







share|cite|improve this answer











$endgroup$



Note: This is just a kind of streamlining of existing answers. The addendum of @MarkoRiedels answer already provides the calculation and it's using as essential step @StephenMontgomery-Smith's hint regarding telescoping.



In fact we don't need any generating functions, since we can show the validity of OPs identity by a few simple transformations.




begin{align*}
color{blue}{sum_{k=1}^{n}}&color{blue}{frac{n!}{(n-k)!}kn^{n-k-1}}\
&=n!sum_{k=1}^{n}frac{n-(n-k)}{(n-k)!}n^{n-k-1}tag{1}\
&=n!left(sum_{k=1}^{n}frac{n^{n-k}}{(n-k)!}-sum_{k=1}^{n-1}frac{n^{n-k-1}}{(n-k-1)!}right)tag{2}\
&=n!left(sum_{k=1}^{n}frac{n^{n-k}}{(n-k)!}-sum_{k=2}^{n}frac{n^{n-k}}{(n-k)!}right)tag{3}\
&=n!frac{n^{n-1}}{(n-1)!}\
&color{blue}{=n^n}
end{align*}




Comment:




  • In (1) we use $k=n-(n-k)$


  • In (2) observe, that the upper limit of the second sum is $n-1$ since $(n-k)=0$ in case $k=n$


  • In (3) we shift the index of the second sum by $1$ to prepare the telescoping.








share|cite|improve this answer














share|cite|improve this answer



share|cite|improve this answer








edited Apr 26 '18 at 13:04

























answered Jul 16 '15 at 14:09









Markus ScheuerMarkus Scheuer

64.1k460152




64.1k460152












  • $begingroup$
    (+1). Thank you for the kind remark. I was quite off base applying residue calculus to this problem.
    $endgroup$
    – Marko Riedel
    Jul 16 '15 at 17:58










  • $begingroup$
    @MarkoRiedel: You're welcome!
    $endgroup$
    – Markus Scheuer
    Jul 16 '15 at 19:04


















  • $begingroup$
    (+1). Thank you for the kind remark. I was quite off base applying residue calculus to this problem.
    $endgroup$
    – Marko Riedel
    Jul 16 '15 at 17:58










  • $begingroup$
    @MarkoRiedel: You're welcome!
    $endgroup$
    – Markus Scheuer
    Jul 16 '15 at 19:04
















$begingroup$
(+1). Thank you for the kind remark. I was quite off base applying residue calculus to this problem.
$endgroup$
– Marko Riedel
Jul 16 '15 at 17:58




$begingroup$
(+1). Thank you for the kind remark. I was quite off base applying residue calculus to this problem.
$endgroup$
– Marko Riedel
Jul 16 '15 at 17:58












$begingroup$
@MarkoRiedel: You're welcome!
$endgroup$
– Markus Scheuer
Jul 16 '15 at 19:04




$begingroup$
@MarkoRiedel: You're welcome!
$endgroup$
– Markus Scheuer
Jul 16 '15 at 19:04











7












$begingroup$

Let
$$ f(n,k) = cases{ frac{n!}{(n-k)!} n^{n-k} & $k le n$ cr 0 & $k>n$}.$$
Then see that
$$ f(n,k) - f(n,k+1) = frac{n!}{(n-k)!} k n^{n-k-1} .$$
Now use a telescoping sum.



(Motivation - $f(n,k)$ is the number of sequences whose freshness is at least $k$.)






share|cite|improve this answer











$endgroup$













  • $begingroup$
    Very nice! I wonder if this was what Mathematica's method was
    $endgroup$
    – Mike Earnest
    Jul 15 '15 at 4:10
















7












$begingroup$

Let
$$ f(n,k) = cases{ frac{n!}{(n-k)!} n^{n-k} & $k le n$ cr 0 & $k>n$}.$$
Then see that
$$ f(n,k) - f(n,k+1) = frac{n!}{(n-k)!} k n^{n-k-1} .$$
Now use a telescoping sum.



(Motivation - $f(n,k)$ is the number of sequences whose freshness is at least $k$.)






share|cite|improve this answer











$endgroup$













  • $begingroup$
    Very nice! I wonder if this was what Mathematica's method was
    $endgroup$
    – Mike Earnest
    Jul 15 '15 at 4:10














7












7








7





$begingroup$

Let
$$ f(n,k) = cases{ frac{n!}{(n-k)!} n^{n-k} & $k le n$ cr 0 & $k>n$}.$$
Then see that
$$ f(n,k) - f(n,k+1) = frac{n!}{(n-k)!} k n^{n-k-1} .$$
Now use a telescoping sum.



(Motivation - $f(n,k)$ is the number of sequences whose freshness is at least $k$.)






share|cite|improve this answer











$endgroup$



Let
$$ f(n,k) = cases{ frac{n!}{(n-k)!} n^{n-k} & $k le n$ cr 0 & $k>n$}.$$
Then see that
$$ f(n,k) - f(n,k+1) = frac{n!}{(n-k)!} k n^{n-k-1} .$$
Now use a telescoping sum.



(Motivation - $f(n,k)$ is the number of sequences whose freshness is at least $k$.)







share|cite|improve this answer














share|cite|improve this answer



share|cite|improve this answer








edited Jul 15 '15 at 4:00









Mike Earnest

27.5k22152




27.5k22152










answered Jul 15 '15 at 3:47









Stephen Montgomery-SmithStephen Montgomery-Smith

17.8k12247




17.8k12247












  • $begingroup$
    Very nice! I wonder if this was what Mathematica's method was
    $endgroup$
    – Mike Earnest
    Jul 15 '15 at 4:10


















  • $begingroup$
    Very nice! I wonder if this was what Mathematica's method was
    $endgroup$
    – Mike Earnest
    Jul 15 '15 at 4:10
















$begingroup$
Very nice! I wonder if this was what Mathematica's method was
$endgroup$
– Mike Earnest
Jul 15 '15 at 4:10




$begingroup$
Very nice! I wonder if this was what Mathematica's method was
$endgroup$
– Mike Earnest
Jul 15 '15 at 4:10


















draft saved

draft discarded




















































Thanks for contributing an answer to Mathematics Stack Exchange!


  • Please be sure to answer the question. Provide details and share your research!

But avoid …



  • Asking for help, clarification, or responding to other answers.

  • Making statements based on opinion; back them up with references or personal experience.


Use MathJax to format equations. MathJax reference.


To learn more, see our tips on writing great answers.




draft saved


draft discarded














StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f1361500%2fnon-combinatorial-proof-of-formula-for-nn%23new-answer', 'question_page');
}
);

Post as a guest















Required, but never shown





















































Required, but never shown














Required, but never shown












Required, but never shown







Required, but never shown

































Required, but never shown














Required, but never shown












Required, but never shown







Required, but never shown







-

Popular posts from this blog

Index of /

This page is only for reference, If you need detailed information, please check here
Read more

Tribalistas

Image
  Nota: Para o álbum homônimo, veja Tribalistas (álbum de 2002). Para o segundo álbum homônimo, veja Tribalistas (álbum de 2017). Para o tipo de organização tribal, veja Tribalismo. Tribalistas Informação geral Origem Salvador e Rio de Janeiro País   Brasil Gênero(s) MPB Pop Samba Período em atividade 2002–2004 2017–atualmente Gravadora(s) EMI Phonomotor Records Universal Music Afiliação(ões) Dadi Pretinho da Serrinha Margareth Menezes Integrantes Arnaldo Antunes Carlinhos Brown Marisa Monte Página oficial www2.uol.com.br/tribalistas/ ...
Read more

Listed building

Image
Listed building (literalmente: prédio listado ) é toda estrutura protegida por lei pelo complexo sistema de tombamento do Reino Unido. Um listed building é qualquer estrutura oficialmente designada como tendo especial interesse arquitetônico, histórico ou cultural. É um estatuto amplamente usado, aplicado a centenas de milhares de estruturas. Estruturas tombadas não podem ser alteradas sem permissão especial, e desfrutam de isenções fiscais e outros benefícios. Cada um dos países do Reino Unido trata tombamento de forma diferente: Índice 1 Inglaterra 2 País de Gales 3 Irlanda do Norte 4 Escócia 5 Referências Inglaterra | O Palácio de Buckingham, Londres. As estruturas tombadas são listadas no Statutory List of Buildings of Special Architectural or Historic Interest , e incluem campos, sinais de trânsito, piers e áreas geográficas. A principal legislação pertinente é o Ancient Monuments and Archaeological Areas Act 1979 , [ 1 ] embora legisla...
Read more