Motivation. In my younger son's class, everyone has to give a (small) Christmas present to one other student. Let $n\in\mathbb{N}$ be the number of students in the class. If you pick a permutation $\...

Consider a uniform random permutation of $\{1,\dots, n\}$, and let $D_n$ be its number of descents (indices $i$ such that $\sigma(i)>\sigma(i+1)$). There is a nice result by Tanny where they show ...

Let $M$ be an $n \times m$ matrix, with $1, \dots, m$ in the first row, $m+1, \dots, 2m$ in the second row, etc.$$M = \left[\begin{array}{c}1 & 2 & \dots & m \\m+1 & m+2 & \...

To generate a Celtic knot:Begin with an $n\times n$ grid of squares.Within each square, randomly pair up the edges and draw a line between them.Tie off the edges of the grid with the neighboring ...

I would like to count the number of permutations with the following restriction:I have $N$ objects distributed over $d$ boxes. The boxes are labelled by $a=1,..,d$ and I know the number $n_a$ of ...

Suppose we have an $N$ by $M$ table. Suppose that $x=(a,b)$ and $y=(c,d)$ are two locations in the table, specified by their row and column indexes. We say that (x,y) is horizontally adjacent if $c=...

Suppose that a random sample $X_1, X_2, \ldots$ is drawn from a continuous spectrum of colors, or species, following a Chinese Restaurant Process distribution with parameter $|\alpha|$ (or ...

Edit:Sorry, for the inconvenience: I have edited the question, since there was a misconception in my thinking.Let $P_1(n) := 1$ if $n=1$ and $\max_{q\mid n, \text{ } q\text{ prime}} q$ otherwise, ...

Assuming I have a fixed dimension $p$ subspace of $\mathbb{R}^d$ orthogonal to $1^d$ and $VV^\top$ with $V \in \mathbb{R}^{d \times p}$ is the orthogonal projection to the subspace.What bound can I ...

In sorting networks, a comparator of positions $i < j$ is an operator which takes a permutation, checks if $p_i > p_j$, and if it is the case, swaps $p_i$ and $p_j$.Using this, we can define ...

Thanks to David Pechersky excellent answer we know thatexpectation of $ | σ({1,2,…,k}) ∩ \{1,2,…,k \} | \rightarrow k^2/N$ for σ uniformly random permutation over $N$.What about the same ...

Let us fix $N$. Note that function $f$ defined below will satisfy $f(0)=0, f(N) = N$ and it is monotonically increasing (not strictly).The code for the function seems to me more clear way to ...

What are some popular settings, when we look at the elements of a randomly generated permutation one by one, and we use certain stopping rule which, as a result gives us a prefix of the observed ...

A random $N$-permutation is the one drawn uniformly from all possible permutations on $N$ points.We know that the expected number of cycles of length $\ell$ in a random $N$-permutation, $\mathbb{E}C_\...

Given positive integers $k$ and $n$, we define the probability distribution $p_{n,k}$ on $S_n$ as:$$p_{n,k}(\sigma):=\frac{\#\{(\tau_1,\dots,\tau_s)\mid \sigma=\tau_1\dots\tau_s, \text{ each }\tau_i\...