number of permutations with k inversions modulo 3
Clash Royale CLAN TAG#URR8PPP
up vote
2
down vote
favorite
Let 0 ≤ k ≤ 2. Show that for n ≥ 3, the number of permutations
w ∈ Sn whose number of inversions is congruent to k
modulo 3 is independent of k. For instance, when n = 3 there are
two permutations with 0 or 3 inversions, two with one inversion,
and two with two inversions.
This is a problem from EC1 additional problems.
I tried to use recursive relations:
$i(n,k)$: number of permutations in $S_n$ with exactly $k$ inversions.
$$i(n+1,k)=i(n,k)+i(n,k−1)+i(n,k−2)+⋯+i(n,k−n).$$
But it seems to be too complicated.
Any hint would be appreciated!
combinatorics
edited Sep 11 at 4:56
Leucippus
19.5k102869
asked Sep 11 at 4:53
math_novice
117
add a comment |
up vote
2
down vote
favorite
Let 0 ≤ k ≤ 2. Show that for n ≥ 3, the number of permutations
w ∈ Sn whose number of inversions is congruent to k
modulo 3 is independent of k. For instance, when n = 3 there are
two permutations with 0 or 3 inversions, two with one inversion,
and two with two inversions.
This is a problem from EC1 additional problems.
I tried to use recursive relations:
$i(n,k)$: number of permutations in $S_n$ with exactly $k$ inversions.
$$i(n+1,k)=i(n,k)+i(n,k−1)+i(n,k−2)+⋯+i(n,k−n).$$
But it seems to be too complicated.
Any hint would be appreciated!
combinatorics
edited Sep 11 at 4:56
Leucippus
19.5k102869
asked Sep 11 at 4:53
math_novice
117
Please see math.meta.stackexchange.com/questions/5020
– Lord Shark the Unknown
Sep 11 at 4:55
add a comment |
up vote
2
down vote
favorite
up vote
2
down vote
favorite
Let 0 ≤ k ≤ 2. Show that for n ≥ 3, the number of permutations
w ∈ Sn whose number of inversions is congruent to k
modulo 3 is independent of k. For instance, when n = 3 there are
two permutations with 0 or 3 inversions, two with one inversion,
and two with two inversions.
This is a problem from EC1 additional problems.
I tried to use recursive relations:
$i(n,k)$: number of permutations in $S_n$ with exactly $k$ inversions.
$$i(n+1,k)=i(n,k)+i(n,k−1)+i(n,k−2)+⋯+i(n,k−n).$$
But it seems to be too complicated.
Any hint would be appreciated!
combinatorics
edited Sep 11 at 4:56
Leucippus
19.5k102869
asked Sep 11 at 4:53
math_novice
117
Let 0 ≤ k ≤ 2. Show that for n ≥ 3, the number of permutations
w ∈ Sn whose number of inversions is congruent to k
modulo 3 is independent of k. For instance, when n = 3 there are
two permutations with 0 or 3 inversions, two with one inversion,
and two with two inversions.
This is a problem from EC1 additional problems.
I tried to use recursive relations:
$i(n,k)$: number of permutations in $S_n$ with exactly $k$ inversions.
$$i(n+1,k)=i(n,k)+i(n,k−1)+i(n,k−2)+⋯+i(n,k−n).$$
But it seems to be too complicated.
Any hint would be appreciated!
combinatorics
combinatorics
edited Sep 11 at 4:56
Leucippus
19.5k102869
asked Sep 11 at 4:53
math_novice
117
edited Sep 11 at 4:56
Leucippus
19.5k102869
asked Sep 11 at 4:53
math_novice
117
edited Sep 11 at 4:56
Leucippus
19.5k102869
edited Sep 11 at 4:56
Leucippus
19.5k102869
edited Sep 11 at 4:56
Leucippus
19.5k102869
19.5k102869
asked Sep 11 at 4:53
math_novice
117
asked Sep 11 at 4:53
math_novice
117
asked Sep 11 at 4:53
math_novice
117
117
Please see math.meta.stackexchange.com/questions/5020
– Lord Shark the Unknown
Sep 11 at 4:55
add a comment |
Please see math.meta.stackexchange.com/questions/5020
– Lord Shark the Unknown
Sep 11 at 4:55
Please see math.meta.stackexchange.com/questions/5020
– Lord Shark the Unknown
Sep 11 at 4:55
Please see math.meta.stackexchange.com/questions/5020
– Lord Shark the Unknown
Sep 11 at 4:55
add a comment |
1 Answer
1
active
oldest
votes
up vote
2
down vote
accepted
The generating function for the permutations by inversion is
$$sum_sigmain S_nx^textrminv(sigma)=(1+x)(1+x+x^2)cdots
(1+x+x^2+cdots+x^n-1)$$
where $textrminv(sigma)$ is the number of inversions
of the permutation $sigma$.
Let $f(x)=a_0+a_1x+a_2x^2+cdots+a_m x^m$ with the $a_j$ real.
Define $b_0=a_0+a_3+a_6+cdots$, $b_1=a_1+a_4+a_7+cdots$
and $b_2=a_2+a_5+a_8+cdots$. Then $b_0=b_1=b_2$ iff $f(exp(2pi i/3))=0$.
answered Sep 11 at 4:59
Lord Shark the Unknown
95.8k957125
Thank you for you quick and clear answer. It helps a lot!
– math_novice
Sep 11 at 5:02
add a comment |
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
2
down vote
accepted
The generating function for the permutations by inversion is
$$sum_sigmain S_nx^textrminv(sigma)=(1+x)(1+x+x^2)cdots
(1+x+x^2+cdots+x^n-1)$$
where $textrminv(sigma)$ is the number of inversions
of the permutation $sigma$.
Let $f(x)=a_0+a_1x+a_2x^2+cdots+a_m x^m$ with the $a_j$ real.
Define $b_0=a_0+a_3+a_6+cdots$, $b_1=a_1+a_4+a_7+cdots$
and $b_2=a_2+a_5+a_8+cdots$. Then $b_0=b_1=b_2$ iff $f(exp(2pi i/3))=0$.
answered Sep 11 at 4:59
Lord Shark the Unknown
95.8k957125
Thank you for you quick and clear answer. It helps a lot!
– math_novice
Sep 11 at 5:02
add a comment |
up vote
2
down vote
accepted
The generating function for the permutations by inversion is
$$sum_sigmain S_nx^textrminv(sigma)=(1+x)(1+x+x^2)cdots
(1+x+x^2+cdots+x^n-1)$$
where $textrminv(sigma)$ is the number of inversions
of the permutation $sigma$.
Let $f(x)=a_0+a_1x+a_2x^2+cdots+a_m x^m$ with the $a_j$ real.
Define $b_0=a_0+a_3+a_6+cdots$, $b_1=a_1+a_4+a_7+cdots$
and $b_2=a_2+a_5+a_8+cdots$. Then $b_0=b_1=b_2$ iff $f(exp(2pi i/3))=0$.
answered Sep 11 at 4:59
Lord Shark the Unknown
95.8k957125
Thank you for you quick and clear answer. It helps a lot!
– math_novice
Sep 11 at 5:02
add a comment |
up vote
2
down vote
accepted
up vote
2
down vote
accepted
The generating function for the permutations by inversion is
$$sum_sigmain S_nx^textrminv(sigma)=(1+x)(1+x+x^2)cdots
(1+x+x^2+cdots+x^n-1)$$
where $textrminv(sigma)$ is the number of inversions
of the permutation $sigma$.
Let $f(x)=a_0+a_1x+a_2x^2+cdots+a_m x^m$ with the $a_j$ real.
Define $b_0=a_0+a_3+a_6+cdots$, $b_1=a_1+a_4+a_7+cdots$
and $b_2=a_2+a_5+a_8+cdots$. Then $b_0=b_1=b_2$ iff $f(exp(2pi i/3))=0$.
answered Sep 11 at 4:59
Lord Shark the Unknown
95.8k957125
The generating function for the permutations by inversion is
$$sum_sigmain S_nx^textrminv(sigma)=(1+x)(1+x+x^2)cdots
(1+x+x^2+cdots+x^n-1)$$
where $textrminv(sigma)$ is the number of inversions
of the permutation $sigma$.
Let $f(x)=a_0+a_1x+a_2x^2+cdots+a_m x^m$ with the $a_j$ real.
Define $b_0=a_0+a_3+a_6+cdots$, $b_1=a_1+a_4+a_7+cdots$
and $b_2=a_2+a_5+a_8+cdots$. Then $b_0=b_1=b_2$ iff $f(exp(2pi i/3))=0$.
answered Sep 11 at 4:59
Lord Shark the Unknown
95.8k957125
answered Sep 11 at 4:59
Lord Shark the Unknown
95.8k957125
answered Sep 11 at 4:59
Lord Shark the Unknown
95.8k957125
answered Sep 11 at 4:59
Lord Shark the Unknown
95.8k957125
95.8k957125
Thank you for you quick and clear answer. It helps a lot!
– math_novice
Sep 11 at 5:02
add a comment |
Thank you for you quick and clear answer. It helps a lot!
– math_novice
Sep 11 at 5:02
Thank you for you quick and clear answer. It helps a lot!
– math_novice
Sep 11 at 5:02
Thank you for you quick and clear answer. It helps a lot!
– math_novice
Sep 11 at 5:02
add a comment |
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
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2912750%2fnumber-of-permutations-with-k-inversions-modulo-3%23new-answer', 'question_page');
);
Post as a guest
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
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
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
Please see math.meta.stackexchange.com/questions/5020
– Lord Shark the Unknown
Sep 11 at 4:55