Search Results

Put $a=|v_1|$, $b=|v_2|$, $c=|v_1v_2|$. Then we have $$ \sum_{i=0}^a\sum_{j=0}^b\sum_{k=0}^c\binom{a-c}{i-k}\binom{b-c}{j-k}= \sum_{k=0}^c\left(\sum_{i=0}^a\binom{a-c}{i-k}\right)\left(\sum_{j=0}^b\bi …

Pyber showed that the number of groups of order $n$ is $\leq n^{\frac{2}{27}\nu(n)^3+C\nu(n)^{3/2}}$, where $\nu$ is the highest power of a prime dividing $n$ and $C$ is an absolute constant. On the o …

Looking at the exponential series, we have $\frac{r^k}{k!}\leq e^r$. Hence we have $$ \frac{r^{m-k-r}}{(m-2k-r)!r!k!} = \frac{1}{r!}\frac{r^k}{k!}\frac{r^{m-2k-r}}{(m-2k-r)!} \leq\frac{e^{2r}}{r!}=\ma …

Let $p\neq 3$ be a prime. Then \begin{eqnarray*} \nu_p\left(\frac{(3x)!}{x!^3}\right) & = & \sum_k \left[\frac{3x}{p^k}\right]-3\left[\frac{x}{p^k}\right]\\ & = & \sum_k 3\left\{\frac{x}{p^k}\right\} …

The number of totient divisors of $n$ is $d(n-1)-d((n-1, \varphi(n))$. As $n$ gets large, then almost all $n$ have the property that $\varphi(n)$ is divisble by all small primes. The average number of …

D. Bressoud, Factorization and Primality testing. Easy to read, but does not contain the algorithm to count the points on an elliptic curve.

Converging sieves: Let $q_i$ be a sequence of integers with $\sum\frac{1}{q_i}<\infty$, and pick for each $i$ an integer $a_i$ within a finite set $\mathcal{A}$. Then the set of integers $n$ such that …

I assume that $m$ is squarefree, for otherwise the minimum would be equal to 2 no matter what $k$ is. Let $p_1, \ldots, p_k$ be the set of all prime numbers of the form $2^a3^b+1$, where $a, b<t$. Th …

It depends a lot what you exactly you mean by "constructive". You can replace randomization by a greedy algorithm, or by a deterministic strategy similar to the one developed by Beck for combinatorial …

In higher dimension things become more complicated. For a finite abelian group $G$ define $\mathfrak{s}(G)$ to be the least integer $N$, such that every sequence $x_1, \ldots, x_N$ of elements of $G$ …

The probability that a fixed entry of $v$ is 1 equals $2^{-n^{s+t}}$. Hence the expected Hamming weight of $v$ is $2^{n-n^{s+t}}$. If $s+t\geq 1$, this implies that with high probability the Hamming w …

The number $N(i,j)$ of paths from $i$ to $j$ is given by the matrix $B=E+A+A^2+\dots$. The number of paths from $i$ to $j$ passing through $k$ is $N(i,k)N(k,j)$, which is the number of times you have …

Consider the set of $n\times n$-matrices with entries in $\{0,1\}$ which have at most $r$ distinct rows. The number of such matrices is $2^{rn}r^n$. As long as $n$ and $n-r$ tend to infinity, we have …

The number of necklaces of size $p$ is $\frac{a^p}{p}+\mathcal{O}(a^{p/2})$, hence $$ \prod_{p=1}^nN(p,a)=\frac{a^{n(n+1)/2}}{n!}\prod_{p=1}^n\left(1+\mathcal{O}(a^{-p/2})\right) = \left(c+\mathcal{O} …

In a quite large range of the parameters we can approximate the fraction by a Taylor series to obtain $$ f(x) = \frac{1}{x!}\frac{1}{\frac{-\log c}{\binom{x+n-1}{n-1}} + \mathcal{O}\left(\frac{\log^2 …