I have the following function $$ f(s,p) = \binom{s}{\left\lceil \frac{p-1}{p}s \right\rceil} (p-1)^{\left\lceil \frac{p-1}{p}s \right\rceil}$$

which describes the number of $p$-ary words of length $s$ and Hamming weight $r= \left\lceil \frac{p-1}{p}s \right\rceil$ (number of non-zero positions). I use the Hamming weight $r= \left\lceil \frac{p-1}{p}s \right\rceil$ since it maximizes the number of the words of length $s$. Here, $s\geq1$ and $p\geq2$.

Now I am interested in a valid lower bound for that number $f(s,p)$.

I would be happy, of someone could help me by finding a lower bound.

Thank You!


1 Answer 1


By Striling formula, for each $n$ there exists a number $0<\theta_n<1$ such that $n!=\sqrt{2\pi n}\left(\frac ne\right)^n e^{\frac{\theta_n}{12n}}$. So for $s>r$ we have

$$\ln f(s,p)= s\ln s -r\ln r- (s-r)\ln (s-r)+ r\ln (p-1)+ \frac 12\left(\ln s-\ln r-\ln (s-r)-\ln 2\pi\right)+\frac{1}{12}\left(\frac{\Theta_s}{s}-\frac{\Theta_r}{r}+\frac{\Theta_{s-r}}{s-r}\right)>$$ $$\left(s+\frac 12\right)\ln s -\left(r+\frac 12\right)\ln r- \left(s-r+\frac 12\right)\ln (s-r)+ r\ln (p-1)-\frac{\ln 2\pi}2-\frac{1}{12(s-r)}.$$

In particular, if $r=\frac {p-1}{p}s$ then we have

$$\ln f(s,p)>\frac12\left((2s+2)\ln p-\ln s- \ln (p-1)- \ln 2\pi-\frac{p}{6s}\right).$$

Update. If $f(s,p)$ non-decreases with respect to $s$ and we allowed to lost terms of order $O(p)$ then we may assume that $s$ is divisible by $p$ and so the second lower bound is applicable. It shows that it suffices to have

$$ (2s+2)\ln p-\ln s- \ln (p-1)- \ln 2\pi-\frac{p}{6s}\ge 2\ln X.$$

Since $\ln (p-1)\le \ln p$, $s\ge p$, and $\ln s \le s-1$, it suffices to have

$$ s \ge \frac{2\ln X-\ln p +\ln 2\pi-\frac{5}{6}}{2\ln p-1}.$$

I expect that the smallest required $s$ is not essentially smaller than that.

  • $\begingroup$ If $s$ is a multiple of $p$, I can neglect the ceil-operator and the Stirling lower bound is valid. If $s$ is not a multiple of $p$, we roundup to the next integer. In this case, if I use Stirling lower bound with $r=\frac{p-1}{p}s$, I can't be sure that the lower bound is valid for $f(s,p)$,or? My goal is, to find s, s.t. $f(s,p) >= X$ ($X$ is a some positive integer) is fulfilled. I mean, if the resulting $s$ is not an integer, than in the end I would round it up to the next integer. Also, I need an s (it can be real) which is always larger than the optimal integer s. $\endgroup$
    – N. Younger
    Oct 28, 2017 at 8:37
  • $\begingroup$ @N.Younger The first lower bound is valid for any $1\le r<s$. $\endgroup$ Oct 28, 2017 at 10:07
  • $\begingroup$ @N.Younger As I understood, given positive integers $p$ and $X$ your are looking for a smallest positive interger $s$ with $f(s,p)\ge X$, right? $\endgroup$ Oct 28, 2017 at 10:11
  • $\begingroup$ To your first comment: I think, $1 \leq r<s$ is another realistic condition, we can make. So this lower bound is also valid for integers $r$? Can you explain me this lower bound, or could give me somer reference? To your second comment: Exactly, that's what I am looking for!!! We can further say: $p\geq2$. But it don't need to be the "best" (smallest) $s$, but we must be sure that the $s$ satisfies the inequality. $\endgroup$
    – N. Younger
    Oct 30, 2017 at 13:30
  • $\begingroup$ @N.Younger Everywhere in my answer $r$ is integer. All my bounds are obtained by direct application of the well-known Striling formula approximating factorial and equality ${s\choose r}=\frac {s!}{r!(s-r)!}$. Aslo see the update. $\endgroup$ Oct 31, 2017 at 1:35

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .