permutation formula $P(n, k) = P(n-1, k) + k P(n-1, k-1)$
$begingroup$
Can any one explain me the intuition behind this formula ? (with permutation example)
P(n, k) = P(n-1, k) + k* P(n-1, k-1)
combinatorics discrete-mathematics permutations
$endgroup$
add a comment |
$begingroup$
Can any one explain me the intuition behind this formula ? (with permutation example)
P(n, k) = P(n-1, k) + k* P(n-1, k-1)
combinatorics discrete-mathematics permutations
$endgroup$
1
$begingroup$
Isn't this Stirling's numbers of the second kind recurrence formula?
$endgroup$
– Zacky
Jan 3 at 11:08
$begingroup$
For this Stirling number, S(n, k) = S(n − 1, k − 1) + k · S(n − 1, k).
$endgroup$
– Wuestenfux
Jan 3 at 11:25
$begingroup$
Ah, close enough :D Thanks!
$endgroup$
– Zacky
Jan 3 at 11:33
add a comment |
$begingroup$
Can any one explain me the intuition behind this formula ? (with permutation example)
P(n, k) = P(n-1, k) + k* P(n-1, k-1)
combinatorics discrete-mathematics permutations
$endgroup$
Can any one explain me the intuition behind this formula ? (with permutation example)
P(n, k) = P(n-1, k) + k* P(n-1, k-1)
combinatorics discrete-mathematics permutations
combinatorics discrete-mathematics permutations
edited Jan 3 at 11:17
Scientifica
6,80941335
6,80941335
asked Jan 3 at 11:04
akashkingakashking
53
53
1
$begingroup$
Isn't this Stirling's numbers of the second kind recurrence formula?
$endgroup$
– Zacky
Jan 3 at 11:08
$begingroup$
For this Stirling number, S(n, k) = S(n − 1, k − 1) + k · S(n − 1, k).
$endgroup$
– Wuestenfux
Jan 3 at 11:25
$begingroup$
Ah, close enough :D Thanks!
$endgroup$
– Zacky
Jan 3 at 11:33
add a comment |
1
$begingroup$
Isn't this Stirling's numbers of the second kind recurrence formula?
$endgroup$
– Zacky
Jan 3 at 11:08
$begingroup$
For this Stirling number, S(n, k) = S(n − 1, k − 1) + k · S(n − 1, k).
$endgroup$
– Wuestenfux
Jan 3 at 11:25
$begingroup$
Ah, close enough :D Thanks!
$endgroup$
– Zacky
Jan 3 at 11:33
1
1
$begingroup$
Isn't this Stirling's numbers of the second kind recurrence formula?
$endgroup$
– Zacky
Jan 3 at 11:08
$begingroup$
Isn't this Stirling's numbers of the second kind recurrence formula?
$endgroup$
– Zacky
Jan 3 at 11:08
$begingroup$
For this Stirling number, S(n, k) = S(n − 1, k − 1) + k · S(n − 1, k).
$endgroup$
– Wuestenfux
Jan 3 at 11:25
$begingroup$
For this Stirling number, S(n, k) = S(n − 1, k − 1) + k · S(n − 1, k).
$endgroup$
– Wuestenfux
Jan 3 at 11:25
$begingroup$
Ah, close enough :D Thanks!
$endgroup$
– Zacky
Jan 3 at 11:33
$begingroup$
Ah, close enough :D Thanks!
$endgroup$
– Zacky
Jan 3 at 11:33
add a comment |
2 Answers
2
active
oldest
votes
$begingroup$
Here is an example which should give you some insight into how I believe you should think about the formula.
Let's say $P(n, k)$ counts the number of teams of $k$ people you can make from a roster of $n$ people, where each person on a team has an assigned role. For instance, to make a bobsleigh team you have to pick four people, and you have to decide who sits in front, and so on.
If you only have four people available (Alice, Bob, Charlie and David), then there are $24$ different bobsleigh teams you can make from that. Thus $P(4, 4) = 24$.
Now, what happens if we get a fifth person, Eve? In other words, what is $P(5, 4)$? Well, one possibility is that Eve isn't chosen to sit in the bobsleigh. In that case there are $P(5-1, 4)$ different teams we can make, namely all the teams we already know of which do not include Eve.
Or Eve can be chosen as part of the team. In that case, she can hold any of $4$ positions, and no matter which of those four positions she chooses, the remaining three teammates can be picked and placed in $P(5-1, 4-1)$ ways (there are $5-1$ people left to choose from, and $4-1$ roles left to fill on the team).
In total, the number of different 4-person bobsleigh teams we can make from our five people is
$$
P(5, 4) = P(5-1, 4) + 4cdot P(5-1, 4-1)\
= 24 + 4cdot 24 = 120
$$
$endgroup$
add a comment |
$begingroup$
Okay, define a word $x=x_1ldots x_k$ of length $k$ over the alphabet $[n]={1,ldots,n}$ to be a $k$-permutation of $n$ if $x$ contains no symbol more than once. The word $x$ can be viewed as an injective mapping $[k]rightarrow[n]:imapsto x_i$. Indeed, the $k$-permutations of $n$ correspond one-to-one with the injective mappings $[k]rightarrow[n]$.
Let $P(n,k)$ denote the number of all $k$-permutations of $n$. We have $P(n,1)=n$ and $P(n,n)=n!$ (bijections). For each $1<k<n$, the above formula holds.
This can be proved by a socalled ''Pascal argument''. Let $A$ be the set of $k$-permutations of $n$ which contain $n$, and let $B$ be the set of remaining $k$-permutations of $n$. Then $P(n,k)= |A|+|B|$.
In view of $A$, each $k-1$-permutation of $n-1$, $y=y_1ldots y_{k-1}$, can be extended to a $k$-permutation of $n$, $y^{(i)}$, such that the symbol $n$ is inserted into position $i$. The assignment $(i,y)mapsto y^{(i)}$ provides a bijection between $[k]times mbox{(set of $k-1$-permutations of $n-1$)}$ and the set $A$. Thus $|A| = kcdot P(k-1,n-1)$.
In view of $B$, the elements of $B$ are exactly the $k$-permutations of $n-1$ and so $|B|=P(n-1,k)$.
As an example, the 2-permutations of 3,
$12, 21, 13, 31, 23, 32$, are decomposed into $A={13,31,23,32}$ and $B={12,21}$.
$endgroup$
add a comment |
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%2f3060456%2fpermutation-formula-pn-k-pn-1-k-k-pn-1-k-1%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
$begingroup$
Here is an example which should give you some insight into how I believe you should think about the formula.
Let's say $P(n, k)$ counts the number of teams of $k$ people you can make from a roster of $n$ people, where each person on a team has an assigned role. For instance, to make a bobsleigh team you have to pick four people, and you have to decide who sits in front, and so on.
If you only have four people available (Alice, Bob, Charlie and David), then there are $24$ different bobsleigh teams you can make from that. Thus $P(4, 4) = 24$.
Now, what happens if we get a fifth person, Eve? In other words, what is $P(5, 4)$? Well, one possibility is that Eve isn't chosen to sit in the bobsleigh. In that case there are $P(5-1, 4)$ different teams we can make, namely all the teams we already know of which do not include Eve.
Or Eve can be chosen as part of the team. In that case, she can hold any of $4$ positions, and no matter which of those four positions she chooses, the remaining three teammates can be picked and placed in $P(5-1, 4-1)$ ways (there are $5-1$ people left to choose from, and $4-1$ roles left to fill on the team).
In total, the number of different 4-person bobsleigh teams we can make from our five people is
$$
P(5, 4) = P(5-1, 4) + 4cdot P(5-1, 4-1)\
= 24 + 4cdot 24 = 120
$$
$endgroup$
add a comment |
$begingroup$
Here is an example which should give you some insight into how I believe you should think about the formula.
Let's say $P(n, k)$ counts the number of teams of $k$ people you can make from a roster of $n$ people, where each person on a team has an assigned role. For instance, to make a bobsleigh team you have to pick four people, and you have to decide who sits in front, and so on.
If you only have four people available (Alice, Bob, Charlie and David), then there are $24$ different bobsleigh teams you can make from that. Thus $P(4, 4) = 24$.
Now, what happens if we get a fifth person, Eve? In other words, what is $P(5, 4)$? Well, one possibility is that Eve isn't chosen to sit in the bobsleigh. In that case there are $P(5-1, 4)$ different teams we can make, namely all the teams we already know of which do not include Eve.
Or Eve can be chosen as part of the team. In that case, she can hold any of $4$ positions, and no matter which of those four positions she chooses, the remaining three teammates can be picked and placed in $P(5-1, 4-1)$ ways (there are $5-1$ people left to choose from, and $4-1$ roles left to fill on the team).
In total, the number of different 4-person bobsleigh teams we can make from our five people is
$$
P(5, 4) = P(5-1, 4) + 4cdot P(5-1, 4-1)\
= 24 + 4cdot 24 = 120
$$
$endgroup$
add a comment |
$begingroup$
Here is an example which should give you some insight into how I believe you should think about the formula.
Let's say $P(n, k)$ counts the number of teams of $k$ people you can make from a roster of $n$ people, where each person on a team has an assigned role. For instance, to make a bobsleigh team you have to pick four people, and you have to decide who sits in front, and so on.
If you only have four people available (Alice, Bob, Charlie and David), then there are $24$ different bobsleigh teams you can make from that. Thus $P(4, 4) = 24$.
Now, what happens if we get a fifth person, Eve? In other words, what is $P(5, 4)$? Well, one possibility is that Eve isn't chosen to sit in the bobsleigh. In that case there are $P(5-1, 4)$ different teams we can make, namely all the teams we already know of which do not include Eve.
Or Eve can be chosen as part of the team. In that case, she can hold any of $4$ positions, and no matter which of those four positions she chooses, the remaining three teammates can be picked and placed in $P(5-1, 4-1)$ ways (there are $5-1$ people left to choose from, and $4-1$ roles left to fill on the team).
In total, the number of different 4-person bobsleigh teams we can make from our five people is
$$
P(5, 4) = P(5-1, 4) + 4cdot P(5-1, 4-1)\
= 24 + 4cdot 24 = 120
$$
$endgroup$
Here is an example which should give you some insight into how I believe you should think about the formula.
Let's say $P(n, k)$ counts the number of teams of $k$ people you can make from a roster of $n$ people, where each person on a team has an assigned role. For instance, to make a bobsleigh team you have to pick four people, and you have to decide who sits in front, and so on.
If you only have four people available (Alice, Bob, Charlie and David), then there are $24$ different bobsleigh teams you can make from that. Thus $P(4, 4) = 24$.
Now, what happens if we get a fifth person, Eve? In other words, what is $P(5, 4)$? Well, one possibility is that Eve isn't chosen to sit in the bobsleigh. In that case there are $P(5-1, 4)$ different teams we can make, namely all the teams we already know of which do not include Eve.
Or Eve can be chosen as part of the team. In that case, she can hold any of $4$ positions, and no matter which of those four positions she chooses, the remaining three teammates can be picked and placed in $P(5-1, 4-1)$ ways (there are $5-1$ people left to choose from, and $4-1$ roles left to fill on the team).
In total, the number of different 4-person bobsleigh teams we can make from our five people is
$$
P(5, 4) = P(5-1, 4) + 4cdot P(5-1, 4-1)\
= 24 + 4cdot 24 = 120
$$
answered Jan 3 at 11:24
ArthurArthur
121k7122208
121k7122208
add a comment |
add a comment |
$begingroup$
Okay, define a word $x=x_1ldots x_k$ of length $k$ over the alphabet $[n]={1,ldots,n}$ to be a $k$-permutation of $n$ if $x$ contains no symbol more than once. The word $x$ can be viewed as an injective mapping $[k]rightarrow[n]:imapsto x_i$. Indeed, the $k$-permutations of $n$ correspond one-to-one with the injective mappings $[k]rightarrow[n]$.
Let $P(n,k)$ denote the number of all $k$-permutations of $n$. We have $P(n,1)=n$ and $P(n,n)=n!$ (bijections). For each $1<k<n$, the above formula holds.
This can be proved by a socalled ''Pascal argument''. Let $A$ be the set of $k$-permutations of $n$ which contain $n$, and let $B$ be the set of remaining $k$-permutations of $n$. Then $P(n,k)= |A|+|B|$.
In view of $A$, each $k-1$-permutation of $n-1$, $y=y_1ldots y_{k-1}$, can be extended to a $k$-permutation of $n$, $y^{(i)}$, such that the symbol $n$ is inserted into position $i$. The assignment $(i,y)mapsto y^{(i)}$ provides a bijection between $[k]times mbox{(set of $k-1$-permutations of $n-1$)}$ and the set $A$. Thus $|A| = kcdot P(k-1,n-1)$.
In view of $B$, the elements of $B$ are exactly the $k$-permutations of $n-1$ and so $|B|=P(n-1,k)$.
As an example, the 2-permutations of 3,
$12, 21, 13, 31, 23, 32$, are decomposed into $A={13,31,23,32}$ and $B={12,21}$.
$endgroup$
add a comment |
$begingroup$
Okay, define a word $x=x_1ldots x_k$ of length $k$ over the alphabet $[n]={1,ldots,n}$ to be a $k$-permutation of $n$ if $x$ contains no symbol more than once. The word $x$ can be viewed as an injective mapping $[k]rightarrow[n]:imapsto x_i$. Indeed, the $k$-permutations of $n$ correspond one-to-one with the injective mappings $[k]rightarrow[n]$.
Let $P(n,k)$ denote the number of all $k$-permutations of $n$. We have $P(n,1)=n$ and $P(n,n)=n!$ (bijections). For each $1<k<n$, the above formula holds.
This can be proved by a socalled ''Pascal argument''. Let $A$ be the set of $k$-permutations of $n$ which contain $n$, and let $B$ be the set of remaining $k$-permutations of $n$. Then $P(n,k)= |A|+|B|$.
In view of $A$, each $k-1$-permutation of $n-1$, $y=y_1ldots y_{k-1}$, can be extended to a $k$-permutation of $n$, $y^{(i)}$, such that the symbol $n$ is inserted into position $i$. The assignment $(i,y)mapsto y^{(i)}$ provides a bijection between $[k]times mbox{(set of $k-1$-permutations of $n-1$)}$ and the set $A$. Thus $|A| = kcdot P(k-1,n-1)$.
In view of $B$, the elements of $B$ are exactly the $k$-permutations of $n-1$ and so $|B|=P(n-1,k)$.
As an example, the 2-permutations of 3,
$12, 21, 13, 31, 23, 32$, are decomposed into $A={13,31,23,32}$ and $B={12,21}$.
$endgroup$
add a comment |
$begingroup$
Okay, define a word $x=x_1ldots x_k$ of length $k$ over the alphabet $[n]={1,ldots,n}$ to be a $k$-permutation of $n$ if $x$ contains no symbol more than once. The word $x$ can be viewed as an injective mapping $[k]rightarrow[n]:imapsto x_i$. Indeed, the $k$-permutations of $n$ correspond one-to-one with the injective mappings $[k]rightarrow[n]$.
Let $P(n,k)$ denote the number of all $k$-permutations of $n$. We have $P(n,1)=n$ and $P(n,n)=n!$ (bijections). For each $1<k<n$, the above formula holds.
This can be proved by a socalled ''Pascal argument''. Let $A$ be the set of $k$-permutations of $n$ which contain $n$, and let $B$ be the set of remaining $k$-permutations of $n$. Then $P(n,k)= |A|+|B|$.
In view of $A$, each $k-1$-permutation of $n-1$, $y=y_1ldots y_{k-1}$, can be extended to a $k$-permutation of $n$, $y^{(i)}$, such that the symbol $n$ is inserted into position $i$. The assignment $(i,y)mapsto y^{(i)}$ provides a bijection between $[k]times mbox{(set of $k-1$-permutations of $n-1$)}$ and the set $A$. Thus $|A| = kcdot P(k-1,n-1)$.
In view of $B$, the elements of $B$ are exactly the $k$-permutations of $n-1$ and so $|B|=P(n-1,k)$.
As an example, the 2-permutations of 3,
$12, 21, 13, 31, 23, 32$, are decomposed into $A={13,31,23,32}$ and $B={12,21}$.
$endgroup$
Okay, define a word $x=x_1ldots x_k$ of length $k$ over the alphabet $[n]={1,ldots,n}$ to be a $k$-permutation of $n$ if $x$ contains no symbol more than once. The word $x$ can be viewed as an injective mapping $[k]rightarrow[n]:imapsto x_i$. Indeed, the $k$-permutations of $n$ correspond one-to-one with the injective mappings $[k]rightarrow[n]$.
Let $P(n,k)$ denote the number of all $k$-permutations of $n$. We have $P(n,1)=n$ and $P(n,n)=n!$ (bijections). For each $1<k<n$, the above formula holds.
This can be proved by a socalled ''Pascal argument''. Let $A$ be the set of $k$-permutations of $n$ which contain $n$, and let $B$ be the set of remaining $k$-permutations of $n$. Then $P(n,k)= |A|+|B|$.
In view of $A$, each $k-1$-permutation of $n-1$, $y=y_1ldots y_{k-1}$, can be extended to a $k$-permutation of $n$, $y^{(i)}$, such that the symbol $n$ is inserted into position $i$. The assignment $(i,y)mapsto y^{(i)}$ provides a bijection between $[k]times mbox{(set of $k-1$-permutations of $n-1$)}$ and the set $A$. Thus $|A| = kcdot P(k-1,n-1)$.
In view of $B$, the elements of $B$ are exactly the $k$-permutations of $n-1$ and so $|B|=P(n-1,k)$.
As an example, the 2-permutations of 3,
$12, 21, 13, 31, 23, 32$, are decomposed into $A={13,31,23,32}$ and $B={12,21}$.
edited Jan 3 at 11:45
answered Jan 3 at 11:24
WuestenfuxWuestenfux
5,3331513
5,3331513
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%2f3060456%2fpermutation-formula-pn-k-pn-1-k-k-pn-1-k-1%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$
Isn't this Stirling's numbers of the second kind recurrence formula?
$endgroup$
– Zacky
Jan 3 at 11:08
$begingroup$
For this Stirling number, S(n, k) = S(n − 1, k − 1) + k · S(n − 1, k).
$endgroup$
– Wuestenfux
Jan 3 at 11:25
$begingroup$
Ah, close enough :D Thanks!
$endgroup$
– Zacky
Jan 3 at 11:33