Mixing
Cycles in permutations of a given size
$begingroup$
How would I find the number of permutations of $[n]$ in which all cycles have length $1$ or $2$?
I know how to do this if I have, say, $8$ numbers from ${{1,2,3,...,8}}$ and I want them to be broken into Count$(4, 3, 1)$. But not when I don't know how many cycles of $2$ and $1$ I want.
Note:
I'm looking for a way to derive a formula or something. I need to use it to prove by induction, I'm assuming, $r(n + 1) = r(n) + n · r(n − 1)$.
combinatorics permutations
asked Jan 28 '13 at 3:30
MITjanitorMITjanitor
1,9631543
$endgroup$
add a comment |
$begingroup$
How would I find the number of permutations of $[n]$ in which all cycles have length $1$ or $2$?
I know how to do this if I have, say, $8$ numbers from ${{1,2,3,...,8}}$ and I want them to be broken into Count$(4, 3, 1)$. But not when I don't know how many cycles of $2$ and $1$ I want.
Note:
I'm looking for a way to derive a formula or something. I need to use it to prove by induction, I'm assuming, $r(n + 1) = r(n) + n · r(n − 1)$.
combinatorics permutations
asked Jan 28 '13 at 3:30
MITjanitorMITjanitor
1,9631543
$endgroup$
$begingroup$
Is $[n] = {1, 2, cdots, n}$?
$endgroup$
– user123454321
Jan 28 '13 at 3:36
1
$begingroup$
This is OEIS A000085. It is easy to derive the recurrence $a_n = (n-1)a_{n-2} + a_{n-1}$.
$endgroup$
– Erick Wong
Jan 28 '13 at 3:39
$begingroup$
@GilYoungCheong: yes!
$endgroup$
– MITjanitor
Jan 28 '13 at 3:44
add a comment |
$begingroup$
How would I find the number of permutations of $[n]$ in which all cycles have length $1$ or $2$?
I know how to do this if I have, say, $8$ numbers from ${{1,2,3,...,8}}$ and I want them to be broken into Count$(4, 3, 1)$. But not when I don't know how many cycles of $2$ and $1$ I want.
Note:
I'm looking for a way to derive a formula or something. I need to use it to prove by induction, I'm assuming, $r(n + 1) = r(n) + n · r(n − 1)$.
combinatorics permutations
asked Jan 28 '13 at 3:30
MITjanitorMITjanitor
1,9631543
$endgroup$
How would I find the number of permutations of $[n]$ in which all cycles have length $1$ or $2$?
I know how to do this if I have, say, $8$ numbers from ${{1,2,3,...,8}}$ and I want them to be broken into Count$(4, 3, 1)$. But not when I don't know how many cycles of $2$ and $1$ I want.
Note:
I'm looking for a way to derive a formula or something. I need to use it to prove by induction, I'm assuming, $r(n + 1) = r(n) + n · r(n − 1)$.
combinatorics permutations
combinatorics permutations
asked Jan 28 '13 at 3:30
MITjanitorMITjanitor
1,9631543
asked Jan 28 '13 at 3:30
MITjanitorMITjanitor
1,9631543
edited Jan 28 '13 at 3:49
MITjanitor
asked Jan 28 '13 at 3:30
MITjanitorMITjanitor
1,9631543
asked Jan 28 '13 at 3:30
MITjanitorMITjanitor
1,9631543
asked Jan 28 '13 at 3:30
MITjanitorMITjanitor
1,9631543
1,9631543
$begingroup$
Is $[n] = {1, 2, cdots, n}$?
$endgroup$
– user123454321
Jan 28 '13 at 3:36
1
$begingroup$
This is OEIS A000085. It is easy to derive the recurrence $a_n = (n-1)a_{n-2} + a_{n-1}$.
$endgroup$
– Erick Wong
Jan 28 '13 at 3:39
$begingroup$
@GilYoungCheong: yes!
$endgroup$
– MITjanitor
Jan 28 '13 at 3:44
add a comment |
$begingroup$
Is $[n] = {1, 2, cdots, n}$?
$endgroup$
– user123454321
Jan 28 '13 at 3:36
1
$begingroup$
This is OEIS A000085. It is easy to derive the recurrence $a_n = (n-1)a_{n-2} + a_{n-1}$.
$endgroup$
– Erick Wong
Jan 28 '13 at 3:39
$begingroup$
@GilYoungCheong: yes!
$endgroup$
– MITjanitor
Jan 28 '13 at 3:44
$begingroup$
Is $[n] = {1, 2, cdots, n}$?
$endgroup$
– user123454321
Jan 28 '13 at 3:36
$begingroup$
Is $[n] = {1, 2, cdots, n}$?
$endgroup$
– user123454321
Jan 28 '13 at 3:36
1
1
$begingroup$
This is OEIS A000085. It is easy to derive the recurrence $a_n = (n-1)a_{n-2} + a_{n-1}$.
$endgroup$
– Erick Wong
Jan 28 '13 at 3:39
$begingroup$
This is OEIS A000085. It is easy to derive the recurrence $a_n = (n-1)a_{n-2} + a_{n-1}$.
$endgroup$
– Erick Wong
Jan 28 '13 at 3:39
$begingroup$
@GilYoungCheong: yes!
$endgroup$
– MITjanitor
Jan 28 '13 at 3:44
$begingroup$
@GilYoungCheong: yes!
$endgroup$
– MITjanitor
Jan 28 '13 at 3:44
add a comment |
2 Answers
2
active
oldest
votes
$begingroup$
These permutations are involutions, meaning $sigma in S_n$ with $sigma^2=1$.
Online Encyclopedia of Integer Sequences A000085. This was one of the first sequences in that library.
1, 1, 2, 4, 10, 26, 76, 232, 764, 2620, 9496
- a(n) is also the number of matchings in the complete graph K(n).
- a(n) is the number of partitions of a set of n distinguishable elements into sets of size 1 and 2.
- a(n) = number of nonnegative lattice paths of upsteps U = (1,1) and downsteps D = (1,-1) that start at the origin and end on the vertical line x = n in which each downstep (if any) is marked with an integer between 1 and the height of its initial vertex above the x-axis. For example, with the required integer immediately preceding each downstep, a(3) = 4 counts UUU, UU1D, UU2D, U1DU.
- a(n) = a(n-1) + (n-1)*a(n-2)
answered Jan 28 '13 at 3:41
cactus314cactus314
15.5k42269
$endgroup$
$begingroup$
Involutions are not cycles, are they? Let me know if I am not right about this!
$endgroup$
– user123454321
Jan 28 '13 at 3:43
$begingroup$
Oops. I misunderstood the question!
$endgroup$
– user123454321
Jan 28 '13 at 3:44
add a comment |
$begingroup$
I will show why indeed $a_n = (n-1)a_{n-2}+a_{n-1}$ is the right reccurence relation. Clearly $a_1 = 1$. Let $S_n$ be a set of all permutations $pi$ of length $n$. The number of permutations of length $n$ with cycles only of lengths $1$ and $2$ we will denote $a_n$.
Next, all permutations from $S_{n+1}$ can be constructed by following procedure from $piin S_n$, where
$$pi = begin{pmatrix}
1 & 2 & 3 & cdots & n \
pi(1) & pi(2) & pi(3) & cdots & pi(n)
end{pmatrix}.$$
By adding 1-cycle $pi(n+1)=n+1$ one gets $pi^*in S_{n+1}$
$$pi^* = begin{pmatrix}
1 & 2 & 3 & cdots & n & n+1 \
pi(1) & pi(2) & pi(3) & cdots & pi(n) & n+1
end{pmatrix}$$
and then by $n$ inversions to get another $S_{n+1}$ permutations of the form
$$pi^*_i = begin{pmatrix}
1 & 2 & 3 & cdots & i & cdots & n & n+1 \
pi(1) & pi(2) & n+1 & cdots & n & cdots & pi(n) & pi(i)
end{pmatrix}$$
In total $n!+nn!=(n+1)!$ distinct permutations. Now, it is clear that all permutations $pi^*$ constructed by just adding $pi(n+1)=n+1$ satisfy the original statement. The number of them is $a_n$. Next, since the inversion will increase the cycle length which has been swapped with by one (see this answer of mine), only those permutations $pi^*_i$ with swap 1-cycle by 1-cycle are allowed. To know the number of these, we first define $Pi_n$ a set of allowed permutations of length $n$, i.e. those with only 1-cycles and 2-cycles (there are $a_n$ of elements of this set), $j(pi)$ as a number of 1-cycles in a given permutation. With this one can easily obtain the desired reccurence (will be added later in this proof)
GENERATING FUNCTION
Consider the sum
$$S_n(x,y) = sum_{piinPi_n}x^{j(pi)}y^{n-j(pi)}$$
This may look strange and meaningless, but you will see it is indeed fruitful. The reason is that
$$S_n(1,1)=a_n.$$
Trivially, we have $S_1(x,y)=x$. Let us express $S_{n+1}(x,y)$, since we can decompose it as permutations $piinPi_n$ with added $pi(n+1)=n+1$ (i.e. $pi^*$, clearly $j(pi^*)=j(pi)+1$) and one with inversions such that they invert $pi(n+1)=n+1$ with only 1-cycles (there are exactly $j(pi)$ disting inversion to make an allowed permutation, similarly $j(pi^*_i)=j(pi)$), therefore
$$S_{n+1}(x,y) = sum_{piinPi_{n+1}}x^{j(pi)}y^{n+1-j(pi)}= sum_{piinPi_n}x^{j(pi^*)}y^{n+1-j(pi^*)} + sum_{piinPi_n}j(pi)x^{j(pi^*_i)}y^{n+1-j(pi^*_i)}=
sum_{piinPi_n}x^{j(pi)+1}y^{n-j(pi)} + sum_{piinPi_n}j(pi)x^{j(pi)}y^{n+1-j(pi)}= left(x+yfrac{partial}{partial x}right)S_n(x,y)
$$
By $S_1(x,y)=x$ we can therefore in the spirit of the previous relation define $S_0(x,y)=1$. We define a generation function
$$G(x,y,t)=sum_{n=0}^infty t^n S_n(x,y),$$
therefore
$$frac{1}{t}(G(x,y,t)-1) = left(x+yfrac{partial}{partial x}right)G(x,y,t)
$$
According to wolphram alpha and by imposing $G(0,y,t)=1$ we get
$$G(x,y,t) = expleft(frac{2x-tx^2}{2t y}right) + frac{1}{t}sqrt{frac{pi y}{2}}expleft(-frac{(tx-1)^2}{2t^2 y}right)left[operatorname{erfi}left(frac{1-tx}{tsqrt{2y}}right)-operatorname{erfi}left(frac{1}{tsqrt{2y}}right)right]$$
Since $G(1,1,t) = sum_{n=1}^infty a_n t^n$ with $a_0=1$ we get
$$sum_{n=0}^infty a_n t^n = expleft(frac{2-t}{2t}right) + frac{1}{t}sqrt{frac{pi}{2}}expleft(-frac{(t-1)^2}{2t^2 }right)left[operatorname{erfi}left(frac{1-t}{tsqrt{2}}right)-operatorname{erfi}left(frac{1}{tsqrt{2}}right)right]$$
answered Jan 30 at 22:42
MachinatoMachinato
1,1681021
$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%2f288597%2fcycles-in-permutations-of-a-given-size%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$
These permutations are involutions, meaning $sigma in S_n$ with $sigma^2=1$.
Online Encyclopedia of Integer Sequences A000085. This was one of the first sequences in that library.
1, 1, 2, 4, 10, 26, 76, 232, 764, 2620, 9496
- a(n) is also the number of matchings in the complete graph K(n).
- a(n) is the number of partitions of a set of n distinguishable elements into sets of size 1 and 2.
- a(n) = number of nonnegative lattice paths of upsteps U = (1,1) and downsteps D = (1,-1) that start at the origin and end on the vertical line x = n in which each downstep (if any) is marked with an integer between 1 and the height of its initial vertex above the x-axis. For example, with the required integer immediately preceding each downstep, a(3) = 4 counts UUU, UU1D, UU2D, U1DU.
- a(n) = a(n-1) + (n-1)*a(n-2)
answered Jan 28 '13 at 3:41
cactus314cactus314
15.5k42269
$endgroup$
$begingroup$
Involutions are not cycles, are they? Let me know if I am not right about this!
$endgroup$
– user123454321
Jan 28 '13 at 3:43
$begingroup$
Oops. I misunderstood the question!
$endgroup$
– user123454321
Jan 28 '13 at 3:44
add a comment |
$begingroup$
These permutations are involutions, meaning $sigma in S_n$ with $sigma^2=1$.
Online Encyclopedia of Integer Sequences A000085. This was one of the first sequences in that library.
1, 1, 2, 4, 10, 26, 76, 232, 764, 2620, 9496
- a(n) is also the number of matchings in the complete graph K(n).
- a(n) is the number of partitions of a set of n distinguishable elements into sets of size 1 and 2.
- a(n) = number of nonnegative lattice paths of upsteps U = (1,1) and downsteps D = (1,-1) that start at the origin and end on the vertical line x = n in which each downstep (if any) is marked with an integer between 1 and the height of its initial vertex above the x-axis. For example, with the required integer immediately preceding each downstep, a(3) = 4 counts UUU, UU1D, UU2D, U1DU.
- a(n) = a(n-1) + (n-1)*a(n-2)
answered Jan 28 '13 at 3:41
cactus314cactus314
15.5k42269
$endgroup$
$begingroup$
Involutions are not cycles, are they? Let me know if I am not right about this!
$endgroup$
– user123454321
Jan 28 '13 at 3:43
$begingroup$
Oops. I misunderstood the question!
$endgroup$
– user123454321
Jan 28 '13 at 3:44
add a comment |
$begingroup$
These permutations are involutions, meaning $sigma in S_n$ with $sigma^2=1$.
Online Encyclopedia of Integer Sequences A000085. This was one of the first sequences in that library.
1, 1, 2, 4, 10, 26, 76, 232, 764, 2620, 9496
- a(n) is also the number of matchings in the complete graph K(n).
- a(n) is the number of partitions of a set of n distinguishable elements into sets of size 1 and 2.
- a(n) = number of nonnegative lattice paths of upsteps U = (1,1) and downsteps D = (1,-1) that start at the origin and end on the vertical line x = n in which each downstep (if any) is marked with an integer between 1 and the height of its initial vertex above the x-axis. For example, with the required integer immediately preceding each downstep, a(3) = 4 counts UUU, UU1D, UU2D, U1DU.
- a(n) = a(n-1) + (n-1)*a(n-2)
answered Jan 28 '13 at 3:41
cactus314cactus314
15.5k42269
$endgroup$
These permutations are involutions, meaning $sigma in S_n$ with $sigma^2=1$.
Online Encyclopedia of Integer Sequences A000085. This was one of the first sequences in that library.
1, 1, 2, 4, 10, 26, 76, 232, 764, 2620, 9496
- a(n) is also the number of matchings in the complete graph K(n).
- a(n) is the number of partitions of a set of n distinguishable elements into sets of size 1 and 2.
- a(n) = number of nonnegative lattice paths of upsteps U = (1,1) and downsteps D = (1,-1) that start at the origin and end on the vertical line x = n in which each downstep (if any) is marked with an integer between 1 and the height of its initial vertex above the x-axis. For example, with the required integer immediately preceding each downstep, a(3) = 4 counts UUU, UU1D, UU2D, U1DU.
- a(n) = a(n-1) + (n-1)*a(n-2)
answered Jan 28 '13 at 3:41
cactus314cactus314
15.5k42269
answered Jan 28 '13 at 3:41
cactus314cactus314
15.5k42269
answered Jan 28 '13 at 3:41
cactus314cactus314
15.5k42269
answered Jan 28 '13 at 3:41
cactus314cactus314
15.5k42269
15.5k42269
$begingroup$
Involutions are not cycles, are they? Let me know if I am not right about this!
$endgroup$
– user123454321
Jan 28 '13 at 3:43
$begingroup$
Oops. I misunderstood the question!
$endgroup$
– user123454321
Jan 28 '13 at 3:44
add a comment |
$begingroup$
Involutions are not cycles, are they? Let me know if I am not right about this!
$endgroup$
– user123454321
Jan 28 '13 at 3:43
$begingroup$
Oops. I misunderstood the question!
$endgroup$
– user123454321
Jan 28 '13 at 3:44
$begingroup$
Involutions are not cycles, are they? Let me know if I am not right about this!
$endgroup$
– user123454321
Jan 28 '13 at 3:43
$begingroup$
Involutions are not cycles, are they? Let me know if I am not right about this!
$endgroup$
– user123454321
Jan 28 '13 at 3:43
$begingroup$
Oops. I misunderstood the question!
$endgroup$
– user123454321
Jan 28 '13 at 3:44
$begingroup$
Oops. I misunderstood the question!
$endgroup$
– user123454321
Jan 28 '13 at 3:44
add a comment |
$begingroup$
I will show why indeed $a_n = (n-1)a_{n-2}+a_{n-1}$ is the right reccurence relation. Clearly $a_1 = 1$. Let $S_n$ be a set of all permutations $pi$ of length $n$. The number of permutations of length $n$ with cycles only of lengths $1$ and $2$ we will denote $a_n$.
Next, all permutations from $S_{n+1}$ can be constructed by following procedure from $piin S_n$, where
$$pi = begin{pmatrix}
1 & 2 & 3 & cdots & n \
pi(1) & pi(2) & pi(3) & cdots & pi(n)
end{pmatrix}.$$
By adding 1-cycle $pi(n+1)=n+1$ one gets $pi^*in S_{n+1}$
$$pi^* = begin{pmatrix}
1 & 2 & 3 & cdots & n & n+1 \
pi(1) & pi(2) & pi(3) & cdots & pi(n) & n+1
end{pmatrix}$$
and then by $n$ inversions to get another $S_{n+1}$ permutations of the form
$$pi^*_i = begin{pmatrix}
1 & 2 & 3 & cdots & i & cdots & n & n+1 \
pi(1) & pi(2) & n+1 & cdots & n & cdots & pi(n) & pi(i)
end{pmatrix}$$
In total $n!+nn!=(n+1)!$ distinct permutations. Now, it is clear that all permutations $pi^*$ constructed by just adding $pi(n+1)=n+1$ satisfy the original statement. The number of them is $a_n$. Next, since the inversion will increase the cycle length which has been swapped with by one (see this answer of mine), only those permutations $pi^*_i$ with swap 1-cycle by 1-cycle are allowed. To know the number of these, we first define $Pi_n$ a set of allowed permutations of length $n$, i.e. those with only 1-cycles and 2-cycles (there are $a_n$ of elements of this set), $j(pi)$ as a number of 1-cycles in a given permutation. With this one can easily obtain the desired reccurence (will be added later in this proof)
GENERATING FUNCTION
Consider the sum
$$S_n(x,y) = sum_{piinPi_n}x^{j(pi)}y^{n-j(pi)}$$
This may look strange and meaningless, but you will see it is indeed fruitful. The reason is that
$$S_n(1,1)=a_n.$$
Trivially, we have $S_1(x,y)=x$. Let us express $S_{n+1}(x,y)$, since we can decompose it as permutations $piinPi_n$ with added $pi(n+1)=n+1$ (i.e. $pi^*$, clearly $j(pi^*)=j(pi)+1$) and one with inversions such that they invert $pi(n+1)=n+1$ with only 1-cycles (there are exactly $j(pi)$ disting inversion to make an allowed permutation, similarly $j(pi^*_i)=j(pi)$), therefore
$$S_{n+1}(x,y) = sum_{piinPi_{n+1}}x^{j(pi)}y^{n+1-j(pi)}= sum_{piinPi_n}x^{j(pi^*)}y^{n+1-j(pi^*)} + sum_{piinPi_n}j(pi)x^{j(pi^*_i)}y^{n+1-j(pi^*_i)}=
sum_{piinPi_n}x^{j(pi)+1}y^{n-j(pi)} + sum_{piinPi_n}j(pi)x^{j(pi)}y^{n+1-j(pi)}= left(x+yfrac{partial}{partial x}right)S_n(x,y)
$$
By $S_1(x,y)=x$ we can therefore in the spirit of the previous relation define $S_0(x,y)=1$. We define a generation function
$$G(x,y,t)=sum_{n=0}^infty t^n S_n(x,y),$$
therefore
$$frac{1}{t}(G(x,y,t)-1) = left(x+yfrac{partial}{partial x}right)G(x,y,t)
$$
According to wolphram alpha and by imposing $G(0,y,t)=1$ we get
$$G(x,y,t) = expleft(frac{2x-tx^2}{2t y}right) + frac{1}{t}sqrt{frac{pi y}{2}}expleft(-frac{(tx-1)^2}{2t^2 y}right)left[operatorname{erfi}left(frac{1-tx}{tsqrt{2y}}right)-operatorname{erfi}left(frac{1}{tsqrt{2y}}right)right]$$
Since $G(1,1,t) = sum_{n=1}^infty a_n t^n$ with $a_0=1$ we get
$$sum_{n=0}^infty a_n t^n = expleft(frac{2-t}{2t}right) + frac{1}{t}sqrt{frac{pi}{2}}expleft(-frac{(t-1)^2}{2t^2 }right)left[operatorname{erfi}left(frac{1-t}{tsqrt{2}}right)-operatorname{erfi}left(frac{1}{tsqrt{2}}right)right]$$
answered Jan 30 at 22:42
MachinatoMachinato
1,1681021
$endgroup$
add a comment |
$begingroup$
I will show why indeed $a_n = (n-1)a_{n-2}+a_{n-1}$ is the right reccurence relation. Clearly $a_1 = 1$. Let $S_n$ be a set of all permutations $pi$ of length $n$. The number of permutations of length $n$ with cycles only of lengths $1$ and $2$ we will denote $a_n$.
Next, all permutations from $S_{n+1}$ can be constructed by following procedure from $piin S_n$, where
$$pi = begin{pmatrix}
1 & 2 & 3 & cdots & n \
pi(1) & pi(2) & pi(3) & cdots & pi(n)
end{pmatrix}.$$
By adding 1-cycle $pi(n+1)=n+1$ one gets $pi^*in S_{n+1}$
$$pi^* = begin{pmatrix}
1 & 2 & 3 & cdots & n & n+1 \
pi(1) & pi(2) & pi(3) & cdots & pi(n) & n+1
end{pmatrix}$$
and then by $n$ inversions to get another $S_{n+1}$ permutations of the form
$$pi^*_i = begin{pmatrix}
1 & 2 & 3 & cdots & i & cdots & n & n+1 \
pi(1) & pi(2) & n+1 & cdots & n & cdots & pi(n) & pi(i)
end{pmatrix}$$
In total $n!+nn!=(n+1)!$ distinct permutations. Now, it is clear that all permutations $pi^*$ constructed by just adding $pi(n+1)=n+1$ satisfy the original statement. The number of them is $a_n$. Next, since the inversion will increase the cycle length which has been swapped with by one (see this answer of mine), only those permutations $pi^*_i$ with swap 1-cycle by 1-cycle are allowed. To know the number of these, we first define $Pi_n$ a set of allowed permutations of length $n$, i.e. those with only 1-cycles and 2-cycles (there are $a_n$ of elements of this set), $j(pi)$ as a number of 1-cycles in a given permutation. With this one can easily obtain the desired reccurence (will be added later in this proof)
GENERATING FUNCTION
Consider the sum
$$S_n(x,y) = sum_{piinPi_n}x^{j(pi)}y^{n-j(pi)}$$
This may look strange and meaningless, but you will see it is indeed fruitful. The reason is that
$$S_n(1,1)=a_n.$$
Trivially, we have $S_1(x,y)=x$. Let us express $S_{n+1}(x,y)$, since we can decompose it as permutations $piinPi_n$ with added $pi(n+1)=n+1$ (i.e. $pi^*$, clearly $j(pi^*)=j(pi)+1$) and one with inversions such that they invert $pi(n+1)=n+1$ with only 1-cycles (there are exactly $j(pi)$ disting inversion to make an allowed permutation, similarly $j(pi^*_i)=j(pi)$), therefore
$$S_{n+1}(x,y) = sum_{piinPi_{n+1}}x^{j(pi)}y^{n+1-j(pi)}= sum_{piinPi_n}x^{j(pi^*)}y^{n+1-j(pi^*)} + sum_{piinPi_n}j(pi)x^{j(pi^*_i)}y^{n+1-j(pi^*_i)}=
sum_{piinPi_n}x^{j(pi)+1}y^{n-j(pi)} + sum_{piinPi_n}j(pi)x^{j(pi)}y^{n+1-j(pi)}= left(x+yfrac{partial}{partial x}right)S_n(x,y)
$$
By $S_1(x,y)=x$ we can therefore in the spirit of the previous relation define $S_0(x,y)=1$. We define a generation function
$$G(x,y,t)=sum_{n=0}^infty t^n S_n(x,y),$$
therefore
$$frac{1}{t}(G(x,y,t)-1) = left(x+yfrac{partial}{partial x}right)G(x,y,t)
$$
According to wolphram alpha and by imposing $G(0,y,t)=1$ we get
$$G(x,y,t) = expleft(frac{2x-tx^2}{2t y}right) + frac{1}{t}sqrt{frac{pi y}{2}}expleft(-frac{(tx-1)^2}{2t^2 y}right)left[operatorname{erfi}left(frac{1-tx}{tsqrt{2y}}right)-operatorname{erfi}left(frac{1}{tsqrt{2y}}right)right]$$
Since $G(1,1,t) = sum_{n=1}^infty a_n t^n$ with $a_0=1$ we get
$$sum_{n=0}^infty a_n t^n = expleft(frac{2-t}{2t}right) + frac{1}{t}sqrt{frac{pi}{2}}expleft(-frac{(t-1)^2}{2t^2 }right)left[operatorname{erfi}left(frac{1-t}{tsqrt{2}}right)-operatorname{erfi}left(frac{1}{tsqrt{2}}right)right]$$
answered Jan 30 at 22:42
MachinatoMachinato
1,1681021
$endgroup$
add a comment |
$begingroup$
I will show why indeed $a_n = (n-1)a_{n-2}+a_{n-1}$ is the right reccurence relation. Clearly $a_1 = 1$. Let $S_n$ be a set of all permutations $pi$ of length $n$. The number of permutations of length $n$ with cycles only of lengths $1$ and $2$ we will denote $a_n$.
Next, all permutations from $S_{n+1}$ can be constructed by following procedure from $piin S_n$, where
$$pi = begin{pmatrix}
1 & 2 & 3 & cdots & n \
pi(1) & pi(2) & pi(3) & cdots & pi(n)
end{pmatrix}.$$
By adding 1-cycle $pi(n+1)=n+1$ one gets $pi^*in S_{n+1}$
$$pi^* = begin{pmatrix}
1 & 2 & 3 & cdots & n & n+1 \
pi(1) & pi(2) & pi(3) & cdots & pi(n) & n+1
end{pmatrix}$$
and then by $n$ inversions to get another $S_{n+1}$ permutations of the form
$$pi^*_i = begin{pmatrix}
1 & 2 & 3 & cdots & i & cdots & n & n+1 \
pi(1) & pi(2) & n+1 & cdots & n & cdots & pi(n) & pi(i)
end{pmatrix}$$
In total $n!+nn!=(n+1)!$ distinct permutations. Now, it is clear that all permutations $pi^*$ constructed by just adding $pi(n+1)=n+1$ satisfy the original statement. The number of them is $a_n$. Next, since the inversion will increase the cycle length which has been swapped with by one (see this answer of mine), only those permutations $pi^*_i$ with swap 1-cycle by 1-cycle are allowed. To know the number of these, we first define $Pi_n$ a set of allowed permutations of length $n$, i.e. those with only 1-cycles and 2-cycles (there are $a_n$ of elements of this set), $j(pi)$ as a number of 1-cycles in a given permutation. With this one can easily obtain the desired reccurence (will be added later in this proof)
GENERATING FUNCTION
Consider the sum
$$S_n(x,y) = sum_{piinPi_n}x^{j(pi)}y^{n-j(pi)}$$
This may look strange and meaningless, but you will see it is indeed fruitful. The reason is that
$$S_n(1,1)=a_n.$$
Trivially, we have $S_1(x,y)=x$. Let us express $S_{n+1}(x,y)$, since we can decompose it as permutations $piinPi_n$ with added $pi(n+1)=n+1$ (i.e. $pi^*$, clearly $j(pi^*)=j(pi)+1$) and one with inversions such that they invert $pi(n+1)=n+1$ with only 1-cycles (there are exactly $j(pi)$ disting inversion to make an allowed permutation, similarly $j(pi^*_i)=j(pi)$), therefore
$$S_{n+1}(x,y) = sum_{piinPi_{n+1}}x^{j(pi)}y^{n+1-j(pi)}= sum_{piinPi_n}x^{j(pi^*)}y^{n+1-j(pi^*)} + sum_{piinPi_n}j(pi)x^{j(pi^*_i)}y^{n+1-j(pi^*_i)}=
sum_{piinPi_n}x^{j(pi)+1}y^{n-j(pi)} + sum_{piinPi_n}j(pi)x^{j(pi)}y^{n+1-j(pi)}= left(x+yfrac{partial}{partial x}right)S_n(x,y)
$$
By $S_1(x,y)=x$ we can therefore in the spirit of the previous relation define $S_0(x,y)=1$. We define a generation function
$$G(x,y,t)=sum_{n=0}^infty t^n S_n(x,y),$$
therefore
$$frac{1}{t}(G(x,y,t)-1) = left(x+yfrac{partial}{partial x}right)G(x,y,t)
$$
According to wolphram alpha and by imposing $G(0,y,t)=1$ we get
$$G(x,y,t) = expleft(frac{2x-tx^2}{2t y}right) + frac{1}{t}sqrt{frac{pi y}{2}}expleft(-frac{(tx-1)^2}{2t^2 y}right)left[operatorname{erfi}left(frac{1-tx}{tsqrt{2y}}right)-operatorname{erfi}left(frac{1}{tsqrt{2y}}right)right]$$
Since $G(1,1,t) = sum_{n=1}^infty a_n t^n$ with $a_0=1$ we get
$$sum_{n=0}^infty a_n t^n = expleft(frac{2-t}{2t}right) + frac{1}{t}sqrt{frac{pi}{2}}expleft(-frac{(t-1)^2}{2t^2 }right)left[operatorname{erfi}left(frac{1-t}{tsqrt{2}}right)-operatorname{erfi}left(frac{1}{tsqrt{2}}right)right]$$
answered Jan 30 at 22:42
MachinatoMachinato
1,1681021
$endgroup$
I will show why indeed $a_n = (n-1)a_{n-2}+a_{n-1}$ is the right reccurence relation. Clearly $a_1 = 1$. Let $S_n$ be a set of all permutations $pi$ of length $n$. The number of permutations of length $n$ with cycles only of lengths $1$ and $2$ we will denote $a_n$.
Next, all permutations from $S_{n+1}$ can be constructed by following procedure from $piin S_n$, where
$$pi = begin{pmatrix}
1 & 2 & 3 & cdots & n \
pi(1) & pi(2) & pi(3) & cdots & pi(n)
end{pmatrix}.$$
By adding 1-cycle $pi(n+1)=n+1$ one gets $pi^*in S_{n+1}$
$$pi^* = begin{pmatrix}
1 & 2 & 3 & cdots & n & n+1 \
pi(1) & pi(2) & pi(3) & cdots & pi(n) & n+1
end{pmatrix}$$
and then by $n$ inversions to get another $S_{n+1}$ permutations of the form
$$pi^*_i = begin{pmatrix}
1 & 2 & 3 & cdots & i & cdots & n & n+1 \
pi(1) & pi(2) & n+1 & cdots & n & cdots & pi(n) & pi(i)
end{pmatrix}$$
In total $n!+nn!=(n+1)!$ distinct permutations. Now, it is clear that all permutations $pi^*$ constructed by just adding $pi(n+1)=n+1$ satisfy the original statement. The number of them is $a_n$. Next, since the inversion will increase the cycle length which has been swapped with by one (see this answer of mine), only those permutations $pi^*_i$ with swap 1-cycle by 1-cycle are allowed. To know the number of these, we first define $Pi_n$ a set of allowed permutations of length $n$, i.e. those with only 1-cycles and 2-cycles (there are $a_n$ of elements of this set), $j(pi)$ as a number of 1-cycles in a given permutation. With this one can easily obtain the desired reccurence (will be added later in this proof)
GENERATING FUNCTION
Consider the sum
$$S_n(x,y) = sum_{piinPi_n}x^{j(pi)}y^{n-j(pi)}$$
This may look strange and meaningless, but you will see it is indeed fruitful. The reason is that
$$S_n(1,1)=a_n.$$
Trivially, we have $S_1(x,y)=x$. Let us express $S_{n+1}(x,y)$, since we can decompose it as permutations $piinPi_n$ with added $pi(n+1)=n+1$ (i.e. $pi^*$, clearly $j(pi^*)=j(pi)+1$) and one with inversions such that they invert $pi(n+1)=n+1$ with only 1-cycles (there are exactly $j(pi)$ disting inversion to make an allowed permutation, similarly $j(pi^*_i)=j(pi)$), therefore
$$S_{n+1}(x,y) = sum_{piinPi_{n+1}}x^{j(pi)}y^{n+1-j(pi)}= sum_{piinPi_n}x^{j(pi^*)}y^{n+1-j(pi^*)} + sum_{piinPi_n}j(pi)x^{j(pi^*_i)}y^{n+1-j(pi^*_i)}=
sum_{piinPi_n}x^{j(pi)+1}y^{n-j(pi)} + sum_{piinPi_n}j(pi)x^{j(pi)}y^{n+1-j(pi)}= left(x+yfrac{partial}{partial x}right)S_n(x,y)
$$
By $S_1(x,y)=x$ we can therefore in the spirit of the previous relation define $S_0(x,y)=1$. We define a generation function
$$G(x,y,t)=sum_{n=0}^infty t^n S_n(x,y),$$
therefore
$$frac{1}{t}(G(x,y,t)-1) = left(x+yfrac{partial}{partial x}right)G(x,y,t)
$$
According to wolphram alpha and by imposing $G(0,y,t)=1$ we get
$$G(x,y,t) = expleft(frac{2x-tx^2}{2t y}right) + frac{1}{t}sqrt{frac{pi y}{2}}expleft(-frac{(tx-1)^2}{2t^2 y}right)left[operatorname{erfi}left(frac{1-tx}{tsqrt{2y}}right)-operatorname{erfi}left(frac{1}{tsqrt{2y}}right)right]$$
Since $G(1,1,t) = sum_{n=1}^infty a_n t^n$ with $a_0=1$ we get
$$sum_{n=0}^infty a_n t^n = expleft(frac{2-t}{2t}right) + frac{1}{t}sqrt{frac{pi}{2}}expleft(-frac{(t-1)^2}{2t^2 }right)left[operatorname{erfi}left(frac{1-t}{tsqrt{2}}right)-operatorname{erfi}left(frac{1}{tsqrt{2}}right)right]$$
answered Jan 30 at 22:42
MachinatoMachinato
1,1681021
answered Jan 30 at 22:42
MachinatoMachinato
1,1681021
answered Jan 30 at 22:42
MachinatoMachinato
1,1681021
answered Jan 30 at 22:42
MachinatoMachinato
1,1681021
1,1681021
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%2f288597%2fcycles-in-permutations-of-a-given-size%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
$begingroup$
Is $[n] = {1, 2, cdots, n}$?
$endgroup$
– user123454321
Jan 28 '13 at 3:36
1
$begingroup$
This is OEIS A000085. It is easy to derive the recurrence $a_n = (n-1)a_{n-2} + a_{n-1}$.
$endgroup$
– Erick Wong
Jan 28 '13 at 3:39
$begingroup$
@GilYoungCheong: yes!
$endgroup$
– MITjanitor
Jan 28 '13 at 3:44