The tag has no wiki summary.

learn more… | top users | synonyms

3
votes
1answer
100 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
175 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
553 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
153 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
190 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
469 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 ...