4
$\begingroup$

We say the $\mathbb{N}$-valued, non-increasing, eventually zero sequence $\lambda=(\lambda_1\geq\lambda_2\geq\cdots)$ is a partition of $N$ if $|\lambda|:=\sum_{k\geq 1}\lambda_k=N$, and denote $m_k(\lambda):=\#\{k\text{ in }\lambda\}$. So for a partition of $N$, $N=|\lambda|=\sum_{k=1}^N km_k(\lambda)$. Since a partition of $N$ can also be viewed as an outcome of a permutation cycle structure of $N$ points, we have $$\sum_{|\lambda|=N}\prod_{k\geq 1}\frac{1}{k^{m_k(\lambda)}m_k(\lambda)!}=1$$ from the random permutation theory.

I want to bound the following sum from below by an absolute constant (so independent of $N$), but I didn't find a simple way as it is from above. The sum is: $$\sum_{|\lambda|=N}\prod_{k\geq 1}\frac{2^{m_k(\lambda)}}{k^{m_k(\lambda)}m_k(\lambda)!(m_k(\lambda)+1)!}.$$ Easy to see it is upper bounded by the above formula and thus at most constant order, but how do we show a matching order lower bound to argue that it is indeed of constant order?

Improve this question
$\endgroup$
4
  • $\begingroup$ @SamHopkins It arises as a special case in a probability study, and the whole issue is treated in a totally different manner (involving advanced probability ideas like GMC methods). I am wondering whether something can be said using elementary methods in this very special case. $\endgroup$ Commented Feb 29, 2024 at 1:03
  • 1
    $\begingroup$ I wrote some simple Sage code to test this. For instance for $N=50$, your sum evaluates to $0.8039724931...$. Seems plausible that it is converges as $N\to \infty$ to some positive constant. $\endgroup$ Commented Feb 29, 2024 at 1:27
  • 2
    $\begingroup$ I don't know why the answer by @Lucia has been deleted but it can be used to show that the generating function $\sum_{N=0}^\infty\text{(your sum)}(N)z^N$ is$$\prod_{k=1}^\infty\frac{I_1\left(2\sqrt\frac{2z^k}k\right)}{\sqrt\frac{2z^k}k}$$where $I_1$ is the first modified Bessel function $\endgroup$ Commented Mar 2, 2024 at 6:09
  • 1
    $\begingroup$ (or if you prefer$$\prod_{k=1}^\infty\left(I_0\left(2\sqrt\frac{2z^k}k\right)-I_2\left(2\sqrt\frac{2z^k}k\right)\right)$$ $\endgroup$ Commented Mar 2, 2024 at 6:24

2 Answers 2

Reset to default
5
$\begingroup$

The sum you want is the coefficient of $z^N$ in the generating function $$ F(z) = \prod_{k=1}^{\infty} \Big( \sum_{m=0}^{\infty} \frac{2^m}{(m+1)!} \frac{z^{km}}{k^m m!}\Big). $$ The function $F(z)$ converges absolutely in $|z|<1$, and we can understand it better by writing $$ g(z) = e^{-z} \sum_{m=0}^{\infty} \frac{2^m}{(m+1)!} \frac{z^m}{m!}, $$ so that
$$ F(z) = \prod_{k=1}^{\infty} e^{z^k/k} g(z^k/k)= \frac{1}{1-z} G(z), $$ say, where $$ G(z) = \prod_{k=1}^{\infty} g(z^k/k), $$ and we used that $\sum_{k=1}^{\infty} z^{k}/k = -\log (1-z)$.

Observe that $g(z)$ is a power series $1+ 0\times z+ a_2 z^2 +\ldots$ where the coefficients $a_j$ for $j\ge 2$ may easily be bounded in size by the corresponding coefficient of $e^z \sum_{m=0}^{\infty} z^m/m! = e^{2z}$. Thus $|a_j| \le 2^j/j!$ for all $j\ge 2$. Thus if we write $$ G(z) = \sum_{n=0}^{\infty} b(n) z^n, $$ then the coefficients $b(n)$ are bounded in absolute value by the corresponding coefficients of $$ H(z) = \prod_{k=1}^{\infty} h(z^k/k), $$ with $h(z) = 1+ \sum_{j=2}^{\infty} 2^jz^j/j!$. Since $h(z)=1+O(|z|^2)$ for $|z|\le 1$, the product defining $H$ converges at $z=1$. Therefore the sum $\sum_{n=0}^{\infty} b(n)$ converges absolutely, and thus to its limiting value $G(1)$.

The coefficient of $z^N$ in $F(z)$ equals $b(0)+b(1)+\ldots +b(N)$, which therefore tends to $G(1)$ which equals $$ \prod_{k=1}^{\infty} e^{-1/k} \Big(1 +\frac 1k + \frac{1}{3k^2} + \frac{1}{18k^3} +\ldots \Big). $$

There is an amusing related problem, which I didn't know offhand before. It is well known that the proportion of square-free integers up to $N$ is $1/\zeta(2) = 6/\pi^2$. What is the proportion of "square-free" permutations? by which I mean the permutations where no cycle length appears more than once. This is a variant of your problem. The answer by the same argument is very pretty:
$$ \prod_{k=1}^{\infty} e^{-1/k} \Big(1 + \frac 1k\Big) = e^{-\gamma}. $$

Improve this answer
$\endgroup$
7
$\begingroup$

I have no idea why Lucia removed her nice answer, but here goes a short elementary argument.

We want to bound from below the expectation of $f(\pi)$, where $\pi$ is a random permutation and $f(\pi)=\prod_k 2^{m_k}/(m_k+1)!$, where $m_k=m_k(\pi)$ is a number of $k$-cycles in $\pi$. Note that $f(\pi)=1$ whenever all $m_k$ are 0 or 1 ($\pi$ is "squarefree" in Lucia's terms). So, it suffices to bound from above by a constant less than 1 the probability that $m_k>1$ for at least one value of $k$.

For given $k$, the probability that $\pi$ has at least two cycles of length $k$ does not exceed $$\frac1{n!}\cdot\frac12\cdot \frac{n!}{k!k!(n-2k)!}\cdot (k-1)!\cdot (k-1)!\cdot (n-2k)!=\frac1{2k^2},$$ here we choose two disjoint subsets of size $k$ to form cycles on them (there are $\frac12 \cdot \frac{n!}{k!k!(n-2k)!}$ choices of two sets, and $(k-1)!$ ways to make a cycle on each of them), and some permutation on remaining $n-2k$ elements.

It remains to note that $\frac12\sum_{k=1}^\infty\frac1{k^2}<1$.

Improve this answer
$\endgroup$
1
  • $\begingroup$ There was an oversight in what I wrote before; which is now fixed. The convergence is not as rapid as I thought initially. $\endgroup$ Commented Mar 2, 2024 at 21:40

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.