Skip to main content
6 of 20
edited title
tony
  • 405
  • 2
  • 8

Estimate sum of $\binom{L}{\sum_{i=1}^l a_i}(\sum_{i=1}^l a_i)!\frac{n!}{(p_1!)^{a_1}\cdots(p_l!)^{a_l}a_1!\cdots a_l!}$ over restricted partitions

Let $L$ be a constant, $n$ be positive integer, $p_1^{a_1}\cdots p_l^{a_l}$ be a partition of integer $n$, i.e. $a_1p_1+\cdots+a_lp_l=n$

Define

$$f(L, a_1,\cdots,a_l,p_1,\cdots,p_l,n):=\binom{L}{\sum_{i=1}^l a_i}(\sum_{i=1}^l a_i)!\frac{n!}{(p_1!)^{a_1}\cdots(p_l!)^{a_l}a_1!\cdots a_l!}$$

My question is, how to compute or find the upper bound of

\begin{equation} S:=\sum_{\substack{n^1\neq p_1^{a_1} \cdots p_l^{a_l}\vdash n, \\ \sum_{i=1}^la_i\leq L},\\ \sum_{i=1}^l \binom{p_i}{2}a_i=N(n)}f(L, a_1,\cdots,a_l,p_1,\cdots,p_l,n) \end{equation} where $N(n)\in\{0,1,2,\cdots,\lfloor \frac{\mu_n-n}{2} \rfloor\}$, and $\mu=n^2-2\sqrt{2} n^{3/2}-2cn^{1+\epsilon}+n$ where $C,0<\epsilon<\frac{1}{2}$ are constants.

If for general $n$, it is hard to analyze this formula, it is also nice to consider asymptotic analysis.

What I tried: I tried to compute the summation for small $N(n)$ to see what happens.

(1) When $N=0$, since $\sum_{i=1}^l \binom{p_i}{2}a_i=N(n)=0$, we have $p_1^{a_1}\cdots p_l^{a_l}=1^n$. Thus $$S=\frac{L!}{(L-n)!n!}$$

(2) When $N=1$, since $\sum_{i=1}^l \binom{p_i}{2}a_i=N(n)=1$, we have $p_1^{a_1}\cdots p_l^{a_l}=1^{n-2}2^1$, thus $$S=\frac{L!n(n-1)}{(L-n+1)!}$$

(3) When $N=2$, since $\sum_{i=1}^l \binom{p_i}{2}a_i=N(n)=2$, we have $p_1^{a_1}\cdots p_l^{a_l}=1^{n-4}2^2$, thus $$S=\frac{L!n(n-1)(n-2)(n-3)}{(L-n+2)!8}$$

(4) When $N=3$, there are two partitions satisfying $\sum_{i=1}^l \binom{p_i}{2}a_i=N(n)=3,$ namely $p_1^{a_1}\cdots p_l^{a_l}=1^{n-4}3^1$ or $2^31^{n-6}$. Thus $$S=\frac{L!}{(L-n+3)!}\big(\frac{n(n-1)(n-2)(n-3)}{6}+\frac{n(n-1)(n-2)(n-3)(n-4)(n-5)}{48}\big)$$

But when $N$ is larger, even a function of $n$, it is not possible to find all partitions that $p_1^{a_1}\cdots p_l^{a_l}=N$, thus this becomes quickly infeasible..

I would appreciate for any comment/idea/help!

tony
  • 405
  • 2
  • 8