A cancellation property for permutationsNumber of Permutations with k-inversions and with a single clamped...



A cancellation property for permutations


Number of Permutations with k-inversions and with a single clamped value“flavored” equivalence classes of permutationspattern-avoiding permutations vs multi-core partitionsCommon name for totally non-intersecting permutationsSum over permutations is 1Solutions of $x^d=1$ in the symmetric grouptrace and involution permutations: Part Itrace and involution permutations: Part IICounting block-equivalent permutationsOdd permutations $tauin S_n$ with $sum_{k=1}^nktau(k)$ an odd square













1












$begingroup$


Let $mathfrak{G}_n$ be the group of $n$-permutations. Denote the number of inversions of $sigmainmathfrak{G}_n$ by $ell(sigma)$.




QUESTION. Assume $n>2$. Does this cancellation property hold true?
$$sum_{sigmainmathfrak{G}_n}(-1)^{ell(sigma)}sum_{i=1}^ni(i-sigma(i)).$$







nt.number-theory co.combinatorics finite-groups permutations combinatorial-identities







share|cite|improve this question









$endgroup$








  • 3




    $begingroup$
    Is there a missing "=0"?
    $endgroup$
    – Gjergji Zaimi
    35 mins ago










  • $begingroup$
    Why $mathfrak{G}_n$?
    $endgroup$
    – darij grinberg
    24 mins ago










  • $begingroup$
    $sum_i i(i-sigma(i))$ is also known as the inversion sum of a permutation, see findstat.org/StatisticsDatabase/St000055
    $endgroup$
    – FindStat
    19 mins ago


















1












$begingroup$


Let $mathfrak{G}_n$ be the group of $n$-permutations. Denote the number of inversions of $sigmainmathfrak{G}_n$ by $ell(sigma)$.




QUESTION. Assume $n>2$. Does this cancellation property hold true?
$$sum_{sigmainmathfrak{G}_n}(-1)^{ell(sigma)}sum_{i=1}^ni(i-sigma(i)).$$







nt.number-theory co.combinatorics finite-groups permutations combinatorial-identities







share|cite|improve this question









$endgroup$








  • 3




    $begingroup$
    Is there a missing "=0"?
    $endgroup$
    – Gjergji Zaimi
    35 mins ago










  • $begingroup$
    Why $mathfrak{G}_n$?
    $endgroup$
    – darij grinberg
    24 mins ago










  • $begingroup$
    $sum_i i(i-sigma(i))$ is also known as the inversion sum of a permutation, see findstat.org/StatisticsDatabase/St000055
    $endgroup$
    – FindStat
    19 mins ago
















1












1








1





$begingroup$


Let $mathfrak{G}_n$ be the group of $n$-permutations. Denote the number of inversions of $sigmainmathfrak{G}_n$ by $ell(sigma)$.




QUESTION. Assume $n>2$. Does this cancellation property hold true?
$$sum_{sigmainmathfrak{G}_n}(-1)^{ell(sigma)}sum_{i=1}^ni(i-sigma(i)).$$







nt.number-theory co.combinatorics finite-groups permutations combinatorial-identities







share|cite|improve this question









$endgroup$




Let $mathfrak{G}_n$ be the group of $n$-permutations. Denote the number of inversions of $sigmainmathfrak{G}_n$ by $ell(sigma)$.




QUESTION. Assume $n>2$. Does this cancellation property hold true?
$$sum_{sigmainmathfrak{G}_n}(-1)^{ell(sigma)}sum_{i=1}^ni(i-sigma(i)).$$







nt.number-theory co.combinatorics finite-groups permutations combinatorial-identities




nt.number-theory co.combinatorics finite-groups permutations combinatorial-identities






share|cite|improve this question













share|cite|improve this question











share|cite|improve this question




share|cite|improve this question










asked 44 mins ago









T. AmdeberhanT. Amdeberhan

17.5k229129




17.5k229129








  • 3




    $begingroup$
    Is there a missing "=0"?
    $endgroup$
    – Gjergji Zaimi
    35 mins ago










  • $begingroup$
    Why $mathfrak{G}_n$?
    $endgroup$
    – darij grinberg
    24 mins ago










  • $begingroup$
    $sum_i i(i-sigma(i))$ is also known as the inversion sum of a permutation, see findstat.org/StatisticsDatabase/St000055
    $endgroup$
    – FindStat
    19 mins ago
















  • 3




    $begingroup$
    Is there a missing "=0"?
    $endgroup$
    – Gjergji Zaimi
    35 mins ago










  • $begingroup$
    Why $mathfrak{G}_n$?
    $endgroup$
    – darij grinberg
    24 mins ago










  • $begingroup$
    $sum_i i(i-sigma(i))$ is also known as the inversion sum of a permutation, see findstat.org/StatisticsDatabase/St000055
    $endgroup$
    – FindStat
    19 mins ago










3




3




$begingroup$
Is there a missing "=0"?
$endgroup$
– Gjergji Zaimi
35 mins ago




$begingroup$
Is there a missing "=0"?
$endgroup$
– Gjergji Zaimi
35 mins ago












$begingroup$
Why $mathfrak{G}_n$?
$endgroup$
– darij grinberg
24 mins ago




$begingroup$
Why $mathfrak{G}_n$?
$endgroup$
– darij grinberg
24 mins ago












$begingroup$
$sum_i i(i-sigma(i))$ is also known as the inversion sum of a permutation, see findstat.org/StatisticsDatabase/St000055
$endgroup$
– FindStat
19 mins ago






$begingroup$
$sum_i i(i-sigma(i))$ is also known as the inversion sum of a permutation, see findstat.org/StatisticsDatabase/St000055
$endgroup$
– FindStat
19 mins ago












1 Answer
1






active

oldest

votes


















6












$begingroup$

Let $n$ be some integer greater than 2. Since the number of even and odd permutations in $S_n$ is the same we have $sum_{sigmain S_{n}}(-1)^{ell(sigma)}=0$ therefore the contribution of $sum_{sigmain S_{n}}(-1)^{ell(sigma)}left(sum_{i=1}^n i^2right)$ is zero. It remains to show that
$$sum_{sigmain S_{n}}(-1)^{ell(sigma)}sum_{i=1}^n isigma(i)=0.$$
Notice that if we write $P(x)=detleft(x^{ij}right)_{i,j=1}^n$ then this sum is simply $P'(1)$. However the order of vanishing of $P$ at $1$ is $binom{n}{2}$ (notice that the matrix is pretty much a Vandermonde matrix) and this is greater than $1$ since $n>2$, therefore $P'(1)=0$.






share|cite|improve this answer









$endgroup$









  • 2




    $begingroup$
    Alternatively, $sum_{sigmain S_{n}}(-1)^{ell(sigma)}sum_{i=1}^n isigma(i) = sum_{i=1}^n i sum_{sigmain S_{n}}(-1)^{ell(sigma)} sigma(i)$. But it is easy to check that the inner sum is $0$ for each $i$ (because for any given $i$ and $j$, there are as many even as there are odd permutations among those $sigma in S_n$ that send $i$ to $j$).
    $endgroup$
    – darij grinberg
    25 mins ago











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: "504"
};
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%2fmathoverflow.net%2fquestions%2f323764%2fa-cancellation-property-for-permutations%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









6












$begingroup$

Let $n$ be some integer greater than 2. Since the number of even and odd permutations in $S_n$ is the same we have $sum_{sigmain S_{n}}(-1)^{ell(sigma)}=0$ therefore the contribution of $sum_{sigmain S_{n}}(-1)^{ell(sigma)}left(sum_{i=1}^n i^2right)$ is zero. It remains to show that
$$sum_{sigmain S_{n}}(-1)^{ell(sigma)}sum_{i=1}^n isigma(i)=0.$$
Notice that if we write $P(x)=detleft(x^{ij}right)_{i,j=1}^n$ then this sum is simply $P'(1)$. However the order of vanishing of $P$ at $1$ is $binom{n}{2}$ (notice that the matrix is pretty much a Vandermonde matrix) and this is greater than $1$ since $n>2$, therefore $P'(1)=0$.






share|cite|improve this answer









$endgroup$









  • 2




    $begingroup$
    Alternatively, $sum_{sigmain S_{n}}(-1)^{ell(sigma)}sum_{i=1}^n isigma(i) = sum_{i=1}^n i sum_{sigmain S_{n}}(-1)^{ell(sigma)} sigma(i)$. But it is easy to check that the inner sum is $0$ for each $i$ (because for any given $i$ and $j$, there are as many even as there are odd permutations among those $sigma in S_n$ that send $i$ to $j$).
    $endgroup$
    – darij grinberg
    25 mins ago
















6












$begingroup$

Let $n$ be some integer greater than 2. Since the number of even and odd permutations in $S_n$ is the same we have $sum_{sigmain S_{n}}(-1)^{ell(sigma)}=0$ therefore the contribution of $sum_{sigmain S_{n}}(-1)^{ell(sigma)}left(sum_{i=1}^n i^2right)$ is zero. It remains to show that
$$sum_{sigmain S_{n}}(-1)^{ell(sigma)}sum_{i=1}^n isigma(i)=0.$$
Notice that if we write $P(x)=detleft(x^{ij}right)_{i,j=1}^n$ then this sum is simply $P'(1)$. However the order of vanishing of $P$ at $1$ is $binom{n}{2}$ (notice that the matrix is pretty much a Vandermonde matrix) and this is greater than $1$ since $n>2$, therefore $P'(1)=0$.






share|cite|improve this answer









$endgroup$









  • 2




    $begingroup$
    Alternatively, $sum_{sigmain S_{n}}(-1)^{ell(sigma)}sum_{i=1}^n isigma(i) = sum_{i=1}^n i sum_{sigmain S_{n}}(-1)^{ell(sigma)} sigma(i)$. But it is easy to check that the inner sum is $0$ for each $i$ (because for any given $i$ and $j$, there are as many even as there are odd permutations among those $sigma in S_n$ that send $i$ to $j$).
    $endgroup$
    – darij grinberg
    25 mins ago














6












6








6





$begingroup$

Let $n$ be some integer greater than 2. Since the number of even and odd permutations in $S_n$ is the same we have $sum_{sigmain S_{n}}(-1)^{ell(sigma)}=0$ therefore the contribution of $sum_{sigmain S_{n}}(-1)^{ell(sigma)}left(sum_{i=1}^n i^2right)$ is zero. It remains to show that
$$sum_{sigmain S_{n}}(-1)^{ell(sigma)}sum_{i=1}^n isigma(i)=0.$$
Notice that if we write $P(x)=detleft(x^{ij}right)_{i,j=1}^n$ then this sum is simply $P'(1)$. However the order of vanishing of $P$ at $1$ is $binom{n}{2}$ (notice that the matrix is pretty much a Vandermonde matrix) and this is greater than $1$ since $n>2$, therefore $P'(1)=0$.






share|cite|improve this answer









$endgroup$



Let $n$ be some integer greater than 2. Since the number of even and odd permutations in $S_n$ is the same we have $sum_{sigmain S_{n}}(-1)^{ell(sigma)}=0$ therefore the contribution of $sum_{sigmain S_{n}}(-1)^{ell(sigma)}left(sum_{i=1}^n i^2right)$ is zero. It remains to show that
$$sum_{sigmain S_{n}}(-1)^{ell(sigma)}sum_{i=1}^n isigma(i)=0.$$
Notice that if we write $P(x)=detleft(x^{ij}right)_{i,j=1}^n$ then this sum is simply $P'(1)$. However the order of vanishing of $P$ at $1$ is $binom{n}{2}$ (notice that the matrix is pretty much a Vandermonde matrix) and this is greater than $1$ since $n>2$, therefore $P'(1)=0$.







share|cite|improve this answer












share|cite|improve this answer



share|cite|improve this answer










answered 28 mins ago









Gjergji ZaimiGjergji Zaimi

63.3k4165313




63.3k4165313








  • 2




    $begingroup$
    Alternatively, $sum_{sigmain S_{n}}(-1)^{ell(sigma)}sum_{i=1}^n isigma(i) = sum_{i=1}^n i sum_{sigmain S_{n}}(-1)^{ell(sigma)} sigma(i)$. But it is easy to check that the inner sum is $0$ for each $i$ (because for any given $i$ and $j$, there are as many even as there are odd permutations among those $sigma in S_n$ that send $i$ to $j$).
    $endgroup$
    – darij grinberg
    25 mins ago














  • 2




    $begingroup$
    Alternatively, $sum_{sigmain S_{n}}(-1)^{ell(sigma)}sum_{i=1}^n isigma(i) = sum_{i=1}^n i sum_{sigmain S_{n}}(-1)^{ell(sigma)} sigma(i)$. But it is easy to check that the inner sum is $0$ for each $i$ (because for any given $i$ and $j$, there are as many even as there are odd permutations among those $sigma in S_n$ that send $i$ to $j$).
    $endgroup$
    – darij grinberg
    25 mins ago








2




2




$begingroup$
Alternatively, $sum_{sigmain S_{n}}(-1)^{ell(sigma)}sum_{i=1}^n isigma(i) = sum_{i=1}^n i sum_{sigmain S_{n}}(-1)^{ell(sigma)} sigma(i)$. But it is easy to check that the inner sum is $0$ for each $i$ (because for any given $i$ and $j$, there are as many even as there are odd permutations among those $sigma in S_n$ that send $i$ to $j$).
$endgroup$
– darij grinberg
25 mins ago




$begingroup$
Alternatively, $sum_{sigmain S_{n}}(-1)^{ell(sigma)}sum_{i=1}^n isigma(i) = sum_{i=1}^n i sum_{sigmain S_{n}}(-1)^{ell(sigma)} sigma(i)$. But it is easy to check that the inner sum is $0$ for each $i$ (because for any given $i$ and $j$, there are as many even as there are odd permutations among those $sigma in S_n$ that send $i$ to $j$).
$endgroup$
– darij grinberg
25 mins ago


















draft saved

draft discarded




















































Thanks for contributing an answer to MathOverflow!


  • 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%2fmathoverflow.net%2fquestions%2f323764%2fa-cancellation-property-for-permutations%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

Szabolcs (Ungheria) Altri progetti | Menu di navigazione48°10′14.56″N 21°29′33.14″E /...

Image
Comuni della provincia di Szabolcs-Szatmár-Bereg Ungheria2001provincia di Szabolcs-Szatmár-Bereg Szabolcs comune Localizzazione Stato   Ungheria Regione Grande Pianura Settentrionale Provincia Szabolcs-Szatmár-Bereg Territorio Coordinate 48°10′14.56″N 21°29′33.14″E  /  48.17071°N 21.49254°E 48.17071; 21.49254  ( Szabolcs ) Coordinate: 48°10′14.56″N 21°29′33.14″E  /  48.17071°N 21.49254°E 48.17071; 21.49254  ( Szabolcs ) Superficie 5,88 km² Abitanti 425 (2001) Densità 72,28 ab./km² Altre informazioni Cod. postale 4467 Prefisso 42 Fuso orario UTC+1 Codice KSH 19169 Cartografia Szabolcs Sito istituzionale Modifica dati su Wikidata  · Manuale Szabolcs è un comune dell'Ungheria di 425 abitanti (dati 2001). È situato nella provincia di Szabolcs-Szatmár-Bereg. Altri progetti | Altri progetti Wikimedia Commons Wikimedia Commons contiene immagini o altri file su Szabolcs .mw-parser-output
Read more

Discografia di Klaus Schulze Indice Album in studio | Album dal vivo | Singoli | Antologie | Colonne...

Image
Discografie di artisti tedeschi Voce principale: Klaus Schulze . Discografia di Klaus Schulze Klaus Schulze e Lisa Gerrard durante un concerto Album in studio 56 ↙ Album dal vivo 15 ↙ Raccolte 37 ↙ Singoli 4 ↙ Album video 1 ↙ Colonne sonore 4 ↙ Indice 1 Album in studio 1.1 Solisti 1.1.1 Come Richard Wahnfried 1.2 Collaborazioni 1.2.1 Con Rainer Bloss 1.2.2 Con Rainer Bloss ed Ernst Fuchs 1.2.3 Con Lisa Gerrard 1.2.4 Con Andreas Grosser 1.2.5 Con Pete Namlook 1.2.6 Con Pete Namlook e Bill Laswell 1.2.7 Con Michael Shrieve 1.2.8 Con Solar Moon 1.2.9 Con artisti vari 2 Album dal vivo 3 Singoli 4 Antologie 5 Colonne sonore 6 Videografia 7 Collegamenti musica Album in studio | Solisti | 1972 – Irrlicht 1973 – Cyborg 1974 – Blackdance 1975 – Timewind 1975 – Picture Music 1976 – Moondawn 1977 – Mirage 1978 – "X" 1979 – Dune
Read more

How to make inet_server_addr() return localhost in spite of ::1/128RETURN NEXT in Postgres FunctionConnect to...

Image
Potential client has a problematic employee I can't work with Can the "Friends" spell be used without making the target hostile? Does it take energy to move something in a circle? Why are carbons of Inositol chiral centers? Count repetitions of an array Which RAF squadrons and aircraft types took part in the bombing of Berlin on the 25th of August 1940? Memory usage: #define vs. static const for uint8_t Broad Strokes - missing letter riddle Why does 0.-5 evaluate to -5? Why is 'diphthong' pronounced the way it is? Why did Luke use his left hand to shoot?
Read more