Dtjytyk

What is the population of Romulus in the TNG era?

Rationale to prefer local variables over instance variables?

Is a piano played in the same way as a harmonium?

Would an aboleth's Phantasmal Force lair action be affected by Counterspell, Dispel Magic, and/or Slow?

How does Ehrenfest's theorem apply to the quantum harmonic oscillator?

Doesn't allowing a user mode program to access kernel space memory and execute the IN and OUT instructions defeat the purpose of having CPU modes?

Plausibility of Mushroom Buildings

Which situations would cause a company to ground or recall a aircraft series?

PTIJ: Why does only a Shor Tam ask at the Seder, and not a Shor Mu'ad?

What is the generally accepted pronunciation of “topoi”?

What would be the most expensive material to an intergalactic society?

Are all players supposed to be able to see each others' character sheets?

Having the player face themselves after the mid-game

When Schnorr signatures are part of Bitcoin will it be possible validate each block with only one signature validation?

How do electrons receive energy when a body is heated?

Can't make sense of a paragraph from Lovecraft

Giving a career talk in my old university, how prominently should I tell students my salary?

How to write a chaotic neutral protagonist and prevent my readers from thinking they are evil?

Confusion about Complex Continued Fraction

How to resolve: Reviewer #1 says remove section X vs. Reviewer #2 says expand section X

Can one live in the U.S. and not use a credit card?

When a wind turbine does not produce enough electricity how does the power company compensate for the loss?

How exactly does an Ethernet collision happen in the cable, since nodes use different circuits for Tx and Rx?

What's the 'present simple' form of the word "нашла́" in 3rd person singular female?

permutation composition in *permutation bar* space, can it be expressed?

Permutation of composition factors?Bijection between tensors and permutations (in linear $O(n)$ time)Finite Permutation CompositionEndomorphism monoid $End(B_n)$ is isomorphic to the monoid $S_n^0$Permutation Composition/MultiplicationEquation with a permutation compositioninfinite permutation - auto compositionAntisymmetry of exterior product for alternating multilinear formsThe norm of a tower of ring extensions is the composition of normspermutation inversions, after random composition

2

1

$begingroup$

For a permutation $piin S_n$ we define its bar permutation $barpi$ as:
$$barpi=[barpi(1),...barpi(n)]colon; barpi(i)=#{jle icolon pi(j)gepi(i)}$$
If we define bar space as $B_n=[1]times[2]times ...[n-1]times[n]$, the bar operation is a one-to-one map from $S_n$ to $B_n$ (see problem 3.16 in "Combinatorial Problems and Exercises" by Lovász). $B_n$ has the advantage that it decomposes the permutation to independent components (say if permutation is uniformly chosen at random its components in $B_n$ space are indpendent)

Moroever, for two permutations $pi,sigmain S_n$ permutation composition is defined as:
$$sigmacircpi = [sigma(pi(1)),sigma(pi(2)),...,sigma(pi(n))]$$

Is it possible to express composition in the bar space, i.e., to compute $overline{sigmacircpi}$ as a function of $barsigma$ and $barpi$?

combinatorics permutations

share|cite|improve this question

edited 2 days ago

kvphxga

asked 2 days ago

kvphxgakvphxga

1567

$endgroup$

• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  $begingroup$
  Have a look at Lehmer code en.wikipedia.org/wiki/Lehmer_code#The_code ... How is the Lehmer codes of the composition of permutations related to the Lehmer codes of the original permutations ? ... Great Question !
  $endgroup$
  – Donald Splutterwit
  2 days ago
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  @DonaldSplutterwit thanks! Lehmer's code is clearly tightly related to bar operation here. In fact, if we make the inequalities to strict inequality in definition of $barsigma$, and set $sigma'=[n+1-sigma(n),n+1-sigma(n-1),...,n+1-sigma(1)]$ then $barsigma=L(sigma')$
  $endgroup$
  – kvphxga
  2 days ago
  
  
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  I think you're going to have a tough time for general $pi$. It should however be doable for the case when $pi$ is an adjacent transposition $(i,i+1)$
  $endgroup$
  – Alex R.
  2 days ago
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  @AlexR. how about a combination of Lehmer's code and bar space? Like if we have $L(sigma)$ and $barpi$ or vice versa? My goal is to work with the composition in a decomposed space (that components are independent of each other). Doesn't matter what kind of decomposition though.
  $endgroup$
  – kvphxga
  2 days ago
  

  
  
  
  

add a comment | 

2

1

$begingroup$

For a permutation $piin S_n$ we define its bar permutation $barpi$ as:
$$barpi=[barpi(1),...barpi(n)]colon; barpi(i)=#{jle icolon pi(j)gepi(i)}$$
If we define bar space as $B_n=[1]times[2]times ...[n-1]times[n]$, the bar operation is a one-to-one map from $S_n$ to $B_n$ (see problem 3.16 in "Combinatorial Problems and Exercises" by Lovász). $B_n$ has the advantage that it decomposes the permutation to independent components (say if permutation is uniformly chosen at random its components in $B_n$ space are indpendent)

Moroever, for two permutations $pi,sigmain S_n$ permutation composition is defined as:
$$sigmacircpi = [sigma(pi(1)),sigma(pi(2)),...,sigma(pi(n))]$$

Is it possible to express composition in the bar space, i.e., to compute $overline{sigmacircpi}$ as a function of $barsigma$ and $barpi$?

combinatorics permutations

share|cite|improve this question

edited 2 days ago

kvphxga

asked 2 days ago

kvphxgakvphxga

1567

$endgroup$

• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  $begingroup$
  Have a look at Lehmer code en.wikipedia.org/wiki/Lehmer_code#The_code ... How is the Lehmer codes of the composition of permutations related to the Lehmer codes of the original permutations ? ... Great Question !
  $endgroup$
  – Donald Splutterwit
  2 days ago
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  @DonaldSplutterwit thanks! Lehmer's code is clearly tightly related to bar operation here. In fact, if we make the inequalities to strict inequality in definition of $barsigma$, and set $sigma'=[n+1-sigma(n),n+1-sigma(n-1),...,n+1-sigma(1)]$ then $barsigma=L(sigma')$
  $endgroup$
  – kvphxga
  2 days ago
  
  
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  I think you're going to have a tough time for general $pi$. It should however be doable for the case when $pi$ is an adjacent transposition $(i,i+1)$
  $endgroup$
  – Alex R.
  2 days ago
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  @AlexR. how about a combination of Lehmer's code and bar space? Like if we have $L(sigma)$ and $barpi$ or vice versa? My goal is to work with the composition in a decomposed space (that components are independent of each other). Doesn't matter what kind of decomposition though.
  $endgroup$
  – kvphxga
  2 days ago
  

  
  
  
  

add a comment | 

$begingroup$

For a permutation $piin S_n$ we define its bar permutation $barpi$ as:
$$barpi=[barpi(1),...barpi(n)]colon; barpi(i)=#{jle icolon pi(j)gepi(i)}$$
If we define bar space as $B_n=[1]times[2]times ...[n-1]times[n]$, the bar operation is a one-to-one map from $S_n$ to $B_n$ (see problem 3.16 in "Combinatorial Problems and Exercises" by Lovász). $B_n$ has the advantage that it decomposes the permutation to independent components (say if permutation is uniformly chosen at random its components in $B_n$ space are indpendent)

Moroever, for two permutations $pi,sigmain S_n$ permutation composition is defined as:
$$sigmacircpi = [sigma(pi(1)),sigma(pi(2)),...,sigma(pi(n))]$$

Is it possible to express composition in the bar space, i.e., to compute $overline{sigmacircpi}$ as a function of $barsigma$ and $barpi$?

combinatorics permutations

share|cite|improve this question

edited 2 days ago

kvphxga

asked 2 days ago

kvphxgakvphxga

1567

$endgroup$

share|cite|improve this question

edited 2 days ago

kvphxga

asked 2 days ago

kvphxgakvphxga

1567

share|cite|improve this question

edited 2 days ago

kvphxga

asked 2 days ago

kvphxgakvphxga

1567

asked 2 days ago

kvphxgakvphxga

1567

asked 2 days ago

kvphxgakvphxga

1567