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

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

Armoriale delle famiglie italiane (Car) Indice Armi | Bibliografia | Menu di navigazioneBlasone...

Image
Armoriali delle famiglie italiane Blasone Cesenate Famiglie nobili di SiciliaFamiglie nobili di SiciliaTropea MagazineTropea MagazineNobili napoletani Nobili napoletani[1]Nobili napoletaniNobili napoletaniTropea Magazine Nobili napoletaniNobili napoletani Famiglie nobili di SiciliaBlasonario CremoneseFamiglie nobili di Sicilia Archivio Storico CapitolinoRaccolta stemmi TrippiniFamiglie nobili di SiciliaNobili napoletaniArmas de los cavalleros de Veneçia Tropea Magazine Famiglie nobili di Sicilia Nobili napoletaniFamiglie nobili di SiciliaRaccolta stemmi Topoguz Famiglie nobili di SiciliaBlasone CesenateRaccolta stemmi TrippiniArchivio Storico Capitolino Famiglie nobili di SiciliaFamiglie nobili di SiciliaFamiglie nobili di SiciliaFamiglie nobili di SiciliaFamiglie nobili di Sicilia Famiglie nobili di SiciliaFamiglie nobili di SiciliaBlasone Cesenate Raccolta stemmi TrippiniFamiglie nobili di SiciliaFamiglie nobili di SiciliaFamiglie nobili di Sicilia Blasonario CremoneseBlasonario Cr...
Read more

Lupi Siderali Indice Storia | Organizzazione | La Tredicesima Compagnia | Aspetto | Membri Importanti...

Capitoli degli Space Marine Space MarineImperium della Terrawargame tridimensionaleWarhammer 40.000PrimarcalupiuroImperatoreRune di DissimulazioneAngeli OscuriEresia di HorusStirpe dei MilleOcchio del TerroreCaosTzeentchHorusCodex AstartesSeconda FondazioneFratelli del LupoOcchio del TerroreAlbero della VitareliquieGuardia ImperialeLogan Grimnartruppe d'assaltoImperium dell'UomoveteraniStirpe dei MilleCaosOcchio del TerroreAngeli SanguinariEresia di Horus Lupi Siderali Nome originale Space Wolves Primarca Leman Russ Grido di battaglia Per Russ e per il Padre di Tutti (un feroce ululato) Colori Grigio Altri capitoli I Lupi Siderali sono una delle venti Legioni della Prima Fondazione degli Space Marine che servono l'Imperium della Terra nel wargame tridimensionale Warhammer 40.000. Sono formidabili nel corpo a corpo, i Confratelli desiderano solo la gloria sul campo di battaglia. Indice 1 Storia 1.1 Leman Russ 1.2 La ...
Read more