Mixing
Summation of Stirling numbers of second kind
$begingroup$
Evaluate:
begin{equation}
n^{n-ell} cdot sumlimits_{k=1}^ell dbinom{n}{k} k! begin{Bmatrix} ell \ k end{Bmatrix}
end{equation}
I used my primitive math skills along with the some formulas given in "Close Encounters with the Stirling Numbers of the Second Kind" by KHRISTO N. BOYADZHIEV to simplify the above equation to $n^n$. Am I correct?
combinatorics binomial-coefficients stirling-numbers
asked Jan 18 at 15:12
SinghSingh
454
$endgroup$
add a comment |
$begingroup$
Evaluate:
begin{equation}
n^{n-ell} cdot sumlimits_{k=1}^ell dbinom{n}{k} k! begin{Bmatrix} ell \ k end{Bmatrix}
end{equation}
I used my primitive math skills along with the some formulas given in "Close Encounters with the Stirling Numbers of the Second Kind" by KHRISTO N. BOYADZHIEV to simplify the above equation to $n^n$. Am I correct?
combinatorics binomial-coefficients stirling-numbers
asked Jan 18 at 15:12
SinghSingh
454
$endgroup$
1
$begingroup$
Hi and welcome to MSE. Showing your work will help us to correct the mistakes, if there are any.
$endgroup$
– Thomas Shelby
Jan 18 at 15:37
1
$begingroup$
See the answers here math.stackexchange.com/questions/3076215/… ... Send me a message if you need more help.
$endgroup$
– Donald Splutterwit
Jan 18 at 20:16
$begingroup$
@DonaldSplutterwit Perfect, many thanks!! Can you please give me some reference to read more about the relation that you mentioned in your answer, namely $k! begin{Bmatrix} n\ k end{Bmatrix} = n! [x^n]:(e^x -1)^k$?
$endgroup$
– Singh
Jan 18 at 20:28
1
$begingroup$
$5^{th}$ formula here en.wikipedia.org/wiki/… and also look at mathworld.wolfram.com/StirlingNumberoftheSecondKind.html ... the first two that come up when you google @Stirling numbers of the second knid.
$endgroup$
– Donald Splutterwit
Jan 18 at 20:33
$begingroup$
@DonaldSplutterwit From your answer, I wondered what squaring of the Stirling number in the given expression leads to? I asked that question 3 days back and have been working on it myself since then; but to no avail. Link to my question: math.stackexchange.com/q/3081960.
$endgroup$
– Singh
Jan 25 at 4:24
add a comment |
$begingroup$
Evaluate:
begin{equation}
n^{n-ell} cdot sumlimits_{k=1}^ell dbinom{n}{k} k! begin{Bmatrix} ell \ k end{Bmatrix}
end{equation}
I used my primitive math skills along with the some formulas given in "Close Encounters with the Stirling Numbers of the Second Kind" by KHRISTO N. BOYADZHIEV to simplify the above equation to $n^n$. Am I correct?
combinatorics binomial-coefficients stirling-numbers
asked Jan 18 at 15:12
SinghSingh
454
$endgroup$
Evaluate:
begin{equation}
n^{n-ell} cdot sumlimits_{k=1}^ell dbinom{n}{k} k! begin{Bmatrix} ell \ k end{Bmatrix}
end{equation}
I used my primitive math skills along with the some formulas given in "Close Encounters with the Stirling Numbers of the Second Kind" by KHRISTO N. BOYADZHIEV to simplify the above equation to $n^n$. Am I correct?
combinatorics binomial-coefficients stirling-numbers
combinatorics binomial-coefficients stirling-numbers
asked Jan 18 at 15:12
SinghSingh
454
asked Jan 18 at 15:12
SinghSingh
454
edited Jan 18 at 15:19
Singh
asked Jan 18 at 15:12
SinghSingh
454
asked Jan 18 at 15:12
SinghSingh
454
asked Jan 18 at 15:12
SinghSingh
454
454
1
$begingroup$
Hi and welcome to MSE. Showing your work will help us to correct the mistakes, if there are any.
$endgroup$
– Thomas Shelby
Jan 18 at 15:37
1
$begingroup$
See the answers here math.stackexchange.com/questions/3076215/… ... Send me a message if you need more help.
$endgroup$
– Donald Splutterwit
Jan 18 at 20:16
$begingroup$
@DonaldSplutterwit Perfect, many thanks!! Can you please give me some reference to read more about the relation that you mentioned in your answer, namely $k! begin{Bmatrix} n\ k end{Bmatrix} = n! [x^n]:(e^x -1)^k$?
$endgroup$
– Singh
Jan 18 at 20:28
1
$begingroup$
$5^{th}$ formula here en.wikipedia.org/wiki/… and also look at mathworld.wolfram.com/StirlingNumberoftheSecondKind.html ... the first two that come up when you google @Stirling numbers of the second knid.
$endgroup$
– Donald Splutterwit
Jan 18 at 20:33
$begingroup$
@DonaldSplutterwit From your answer, I wondered what squaring of the Stirling number in the given expression leads to? I asked that question 3 days back and have been working on it myself since then; but to no avail. Link to my question: math.stackexchange.com/q/3081960.
$endgroup$
– Singh
Jan 25 at 4:24
add a comment |
1
$begingroup$
Hi and welcome to MSE. Showing your work will help us to correct the mistakes, if there are any.
$endgroup$
– Thomas Shelby
Jan 18 at 15:37
1
$begingroup$
See the answers here math.stackexchange.com/questions/3076215/… ... Send me a message if you need more help.
$endgroup$
– Donald Splutterwit
Jan 18 at 20:16
$begingroup$
@DonaldSplutterwit Perfect, many thanks!! Can you please give me some reference to read more about the relation that you mentioned in your answer, namely $k! begin{Bmatrix} n\ k end{Bmatrix} = n! [x^n]:(e^x -1)^k$?
$endgroup$
– Singh
Jan 18 at 20:28
1
$begingroup$
$5^{th}$ formula here en.wikipedia.org/wiki/… and also look at mathworld.wolfram.com/StirlingNumberoftheSecondKind.html ... the first two that come up when you google @Stirling numbers of the second knid.
$endgroup$
– Donald Splutterwit
Jan 18 at 20:33
$begingroup$
@DonaldSplutterwit From your answer, I wondered what squaring of the Stirling number in the given expression leads to? I asked that question 3 days back and have been working on it myself since then; but to no avail. Link to my question: math.stackexchange.com/q/3081960.
$endgroup$
– Singh
Jan 25 at 4:24
1
1
$begingroup$
Hi and welcome to MSE. Showing your work will help us to correct the mistakes, if there are any.
$endgroup$
– Thomas Shelby
Jan 18 at 15:37
$begingroup$
Hi and welcome to MSE. Showing your work will help us to correct the mistakes, if there are any.
$endgroup$
– Thomas Shelby
Jan 18 at 15:37
1
1
$begingroup$
See the answers here math.stackexchange.com/questions/3076215/… ... Send me a message if you need more help.
$endgroup$
– Donald Splutterwit
Jan 18 at 20:16
$begingroup$
See the answers here math.stackexchange.com/questions/3076215/… ... Send me a message if you need more help.
$endgroup$
– Donald Splutterwit
Jan 18 at 20:16
$begingroup$
@DonaldSplutterwit Perfect, many thanks!! Can you please give me some reference to read more about the relation that you mentioned in your answer, namely $k! begin{Bmatrix} n\ k end{Bmatrix} = n! [x^n]:(e^x -1)^k$?
$endgroup$
– Singh
Jan 18 at 20:28
$begingroup$
@DonaldSplutterwit Perfect, many thanks!! Can you please give me some reference to read more about the relation that you mentioned in your answer, namely $k! begin{Bmatrix} n\ k end{Bmatrix} = n! [x^n]:(e^x -1)^k$?
$endgroup$
– Singh
Jan 18 at 20:28
1
1
$begingroup$
$5^{th}$ formula here en.wikipedia.org/wiki/… and also look at mathworld.wolfram.com/StirlingNumberoftheSecondKind.html ... the first two that come up when you google @Stirling numbers of the second knid.
$endgroup$
– Donald Splutterwit
Jan 18 at 20:33
$begingroup$
$5^{th}$ formula here en.wikipedia.org/wiki/… and also look at mathworld.wolfram.com/StirlingNumberoftheSecondKind.html ... the first two that come up when you google @Stirling numbers of the second knid.
$endgroup$
– Donald Splutterwit
Jan 18 at 20:33
$begingroup$
@DonaldSplutterwit From your answer, I wondered what squaring of the Stirling number in the given expression leads to? I asked that question 3 days back and have been working on it myself since then; but to no avail. Link to my question: math.stackexchange.com/q/3081960.
$endgroup$
– Singh
Jan 25 at 4:24
$begingroup$
@DonaldSplutterwit From your answer, I wondered what squaring of the Stirling number in the given expression leads to? I asked that question 3 days back and have been working on it myself since then; but to no avail. Link to my question: math.stackexchange.com/q/3081960.
$endgroup$
– Singh
Jan 25 at 4:24
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
If you're familiar with combinatorics, this being equal to $n^n$ means it counts functions $f:[n]to[n]$ ($[n]$ denoting the set ${1,2,ldots,n}$, since each of the $n$ elements in the domain have $n$ choices of image in the codomain.
I'll give you the idea of a proof and let you fill in the details. The given expression counts functions from $[n]$ to $[n]$ with some fixed subset $S$ of size $ell$ of $[n]$. The term $n^{n-ell}$ counts functions from $[n]-S$ to $[n]$, since each of the $n-ell$ elements in the domain have $n$ choices o image in the codomain. The remaining sum $sum_{k=1}^ell binom{n}{k}k! begin{Bmatrix} ell \ k end{Bmatrix}$ determines the image of $S$, where each $k$ corresponds to a possible size of $f(S)$. In other words, for each $k$, $binom{n}{k}k! begin{Bmatrix} ell \ k end{Bmatrix}$ counts the number of functions $f:Sto [n]$ where $|f(S)|=k$.
The only other major fact you need is that $k! begin{Bmatrix} ell \ k end{Bmatrix}$ counts surjections $f:[ell]to[k]$. The Stirling number of the second kind counts partitions of $[ell]$ into $k$ parts. There are $k!$ ways to associate each block with an element of $[k]$, creating a surjection from $[ell]$ onto $[k]$.
answered Jan 18 at 20:39
Kevin LongKevin Long
3,57121431
$endgroup$
add a comment |
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
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3078367%2fsummation-of-stirling-numbers-of-second-kind%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
If you're familiar with combinatorics, this being equal to $n^n$ means it counts functions $f:[n]to[n]$ ($[n]$ denoting the set ${1,2,ldots,n}$, since each of the $n$ elements in the domain have $n$ choices of image in the codomain.
I'll give you the idea of a proof and let you fill in the details. The given expression counts functions from $[n]$ to $[n]$ with some fixed subset $S$ of size $ell$ of $[n]$. The term $n^{n-ell}$ counts functions from $[n]-S$ to $[n]$, since each of the $n-ell$ elements in the domain have $n$ choices o image in the codomain. The remaining sum $sum_{k=1}^ell binom{n}{k}k! begin{Bmatrix} ell \ k end{Bmatrix}$ determines the image of $S$, where each $k$ corresponds to a possible size of $f(S)$. In other words, for each $k$, $binom{n}{k}k! begin{Bmatrix} ell \ k end{Bmatrix}$ counts the number of functions $f:Sto [n]$ where $|f(S)|=k$.
The only other major fact you need is that $k! begin{Bmatrix} ell \ k end{Bmatrix}$ counts surjections $f:[ell]to[k]$. The Stirling number of the second kind counts partitions of $[ell]$ into $k$ parts. There are $k!$ ways to associate each block with an element of $[k]$, creating a surjection from $[ell]$ onto $[k]$.
answered Jan 18 at 20:39
Kevin LongKevin Long
3,57121431
$endgroup$
add a comment |
$begingroup$
If you're familiar with combinatorics, this being equal to $n^n$ means it counts functions $f:[n]to[n]$ ($[n]$ denoting the set ${1,2,ldots,n}$, since each of the $n$ elements in the domain have $n$ choices of image in the codomain.
I'll give you the idea of a proof and let you fill in the details. The given expression counts functions from $[n]$ to $[n]$ with some fixed subset $S$ of size $ell$ of $[n]$. The term $n^{n-ell}$ counts functions from $[n]-S$ to $[n]$, since each of the $n-ell$ elements in the domain have $n$ choices o image in the codomain. The remaining sum $sum_{k=1}^ell binom{n}{k}k! begin{Bmatrix} ell \ k end{Bmatrix}$ determines the image of $S$, where each $k$ corresponds to a possible size of $f(S)$. In other words, for each $k$, $binom{n}{k}k! begin{Bmatrix} ell \ k end{Bmatrix}$ counts the number of functions $f:Sto [n]$ where $|f(S)|=k$.
The only other major fact you need is that $k! begin{Bmatrix} ell \ k end{Bmatrix}$ counts surjections $f:[ell]to[k]$. The Stirling number of the second kind counts partitions of $[ell]$ into $k$ parts. There are $k!$ ways to associate each block with an element of $[k]$, creating a surjection from $[ell]$ onto $[k]$.
answered Jan 18 at 20:39
Kevin LongKevin Long
3,57121431
$endgroup$
add a comment |
$begingroup$
If you're familiar with combinatorics, this being equal to $n^n$ means it counts functions $f:[n]to[n]$ ($[n]$ denoting the set ${1,2,ldots,n}$, since each of the $n$ elements in the domain have $n$ choices of image in the codomain.
I'll give you the idea of a proof and let you fill in the details. The given expression counts functions from $[n]$ to $[n]$ with some fixed subset $S$ of size $ell$ of $[n]$. The term $n^{n-ell}$ counts functions from $[n]-S$ to $[n]$, since each of the $n-ell$ elements in the domain have $n$ choices o image in the codomain. The remaining sum $sum_{k=1}^ell binom{n}{k}k! begin{Bmatrix} ell \ k end{Bmatrix}$ determines the image of $S$, where each $k$ corresponds to a possible size of $f(S)$. In other words, for each $k$, $binom{n}{k}k! begin{Bmatrix} ell \ k end{Bmatrix}$ counts the number of functions $f:Sto [n]$ where $|f(S)|=k$.
The only other major fact you need is that $k! begin{Bmatrix} ell \ k end{Bmatrix}$ counts surjections $f:[ell]to[k]$. The Stirling number of the second kind counts partitions of $[ell]$ into $k$ parts. There are $k!$ ways to associate each block with an element of $[k]$, creating a surjection from $[ell]$ onto $[k]$.
answered Jan 18 at 20:39
Kevin LongKevin Long
3,57121431
$endgroup$
If you're familiar with combinatorics, this being equal to $n^n$ means it counts functions $f:[n]to[n]$ ($[n]$ denoting the set ${1,2,ldots,n}$, since each of the $n$ elements in the domain have $n$ choices of image in the codomain.
I'll give you the idea of a proof and let you fill in the details. The given expression counts functions from $[n]$ to $[n]$ with some fixed subset $S$ of size $ell$ of $[n]$. The term $n^{n-ell}$ counts functions from $[n]-S$ to $[n]$, since each of the $n-ell$ elements in the domain have $n$ choices o image in the codomain. The remaining sum $sum_{k=1}^ell binom{n}{k}k! begin{Bmatrix} ell \ k end{Bmatrix}$ determines the image of $S$, where each $k$ corresponds to a possible size of $f(S)$. In other words, for each $k$, $binom{n}{k}k! begin{Bmatrix} ell \ k end{Bmatrix}$ counts the number of functions $f:Sto [n]$ where $|f(S)|=k$.
The only other major fact you need is that $k! begin{Bmatrix} ell \ k end{Bmatrix}$ counts surjections $f:[ell]to[k]$. The Stirling number of the second kind counts partitions of $[ell]$ into $k$ parts. There are $k!$ ways to associate each block with an element of $[k]$, creating a surjection from $[ell]$ onto $[k]$.
answered Jan 18 at 20:39
Kevin LongKevin Long
3,57121431
answered Jan 18 at 20:39
Kevin LongKevin Long
3,57121431
answered Jan 18 at 20:39
Kevin LongKevin Long
3,57121431
answered Jan 18 at 20:39
Kevin LongKevin Long
3,57121431
3,57121431
add a comment |
add a comment |
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.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3078367%2fsummation-of-stirling-numbers-of-second-kind%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
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
1
$begingroup$
Hi and welcome to MSE. Showing your work will help us to correct the mistakes, if there are any.
$endgroup$
– Thomas Shelby
Jan 18 at 15:37
1
$begingroup$
See the answers here math.stackexchange.com/questions/3076215/… ... Send me a message if you need more help.
$endgroup$
– Donald Splutterwit
Jan 18 at 20:16
$begingroup$
@DonaldSplutterwit Perfect, many thanks!! Can you please give me some reference to read more about the relation that you mentioned in your answer, namely $k! begin{Bmatrix} n\ k end{Bmatrix} = n! [x^n]:(e^x -1)^k$?
$endgroup$
– Singh
Jan 18 at 20:28
1
$begingroup$
$5^{th}$ formula here en.wikipedia.org/wiki/… and also look at mathworld.wolfram.com/StirlingNumberoftheSecondKind.html ... the first two that come up when you google @Stirling numbers of the second knid.
$endgroup$
– Donald Splutterwit
Jan 18 at 20:33
$begingroup$
@DonaldSplutterwit From your answer, I wondered what squaring of the Stirling number in the given expression leads to? I asked that question 3 days back and have been working on it myself since then; but to no avail. Link to my question: math.stackexchange.com/q/3081960.
$endgroup$
– Singh
Jan 25 at 4:24