The tag has no usage guidance.

learn more… | top users | synonyms

3
votes
1answer
161 views

variance of the number of fixed points for a permutation group

It is reasonably well-known that the variance of the number of fixed points for $S_n$ equals $1.$ Now, what about other transitive permutation groups on $\{1, \dotsc, n\}?$ Presumably much is known. I ...
1
vote
0answers
74 views

permutations sampling by probability matrix [closed]

I am looking for effective and reliable algorithm which is able to generate random samples of permutations by square doubly stochastic probability matrix $P$ (n x n) distribution ($\sum_{i}p_{i,j} = ...
2
votes
0answers
39 views

Smooth bivariate functions identifiable under permutations

Consider a "smooth" $f : [0,1]^2 \to [0,1]$ and let $\pi : [n] \to [n]$ be a permutation of $[n] =\{1,\dots,n\}$. Let us define $$ A^{f,\pi} := \Big( f\Big(\frac{\pi(i)}{n},\frac{\pi(j)}{n}\Big) ...
1
vote
0answers
97 views

Horizontal vs Vertical sides Exit from a Rectangle for simple symmetric Random Walk on $\textbf{Z}^{2}$

Consider simple symmetric random walk, $X_{n} = (X_{n}^{(1)}, X_{n}^{(2)})$ with $X_0= (0,0)$, on the 2 dimensional integer lattice, $\textbf{Z}^{2}$. Let $T_{M}, T_{N}$ be the smallest $n$ such ...
3
votes
1answer
110 views

What is the probability of a given induced ordering of a random permutation?

I ran into the following problem in a calculation involving permutations. Let $[n] = \{1,...,n\}$, and assume that $[n]$ is partitioned into equivalency classes. That is, $[n]$ is the disjoint union ...
5
votes
1answer
187 views

Partial sums of partitions

Suppose I have two random partitions of $N.$ ("random" really means "the cycle type of a random permutation", but if there is an answer with any definition, I am interested). The question is: what is ...
5
votes
1answer
635 views

Number of Permutations with k-inversions and with a single clamped value

This question is cross-posted from math.stackexchange because it might be too technical. Let $S_n$ be the symmetric group. Recall that the number of inversions of a permutation $\sigma\in S_n$ is the ...
1
vote
0answers
156 views

Factorization of permutations.

Let $n,k$ be positive integers such that $3n=2k$ and $N = \lfloor \alpha n\rfloor$ for some constant $0<\alpha<1$. Let $S_{3n}$ denote the permutation group of order $3n$. Consider the following ...
1
vote
0answers
197 views

Random Permutation with fixed cycle length.

Suppose $ S_{n,N} $ be the set of $n$ elements with $N$ many cycles where $N$ is proportional to $n$. $U_{n,N}$ is an element picked randomly from this. It is known that the length of any cycle cannot ...
1
vote
2answers
525 views

What is the expected number of increasing subsequence? [closed]

Given n numbers (each of which is a random integer, uniformly between 1~n), what is the expected number of increasing subsequences?
26
votes
6answers
1k views

Combinatorial Morse functions and random permutations

This question has its origin in combinatorial topology. In the 90s R. Forman proposed a discrete counterpart of Morse theory. In his case, a Morse function on a triangulated space is a function ...