# Tagged Questions

**18**

votes

**2**answers

1k views

### The behavior of a certain greedy algorithm for ErdÅ‘s Discrepancy Problem

Let $N$ be a positive integer.
We want to find a completely multiplicative functions f(n) with values $\pm 1$ for $n \le N$ such that the discrepancy
$$D=\max_{n \le N} |\{\sum_{i=1}^nf(i)\}|$$
is ...

**26**

votes

**6**answers

6k views

### How many surjections are there from a set of size n?

It is well-known that the number of surjections from a set of size n to a set of size m is quite a bit harder to calculate than the number of functions or the number of injections. (Of course, for ...

**18**

votes

**3**answers

842 views

### The probability for a sequence to have small partial sums

The question
Let $a_1,a_2,\dots,a_n$ be a sequence whose entries are +1 or -1. Let t be a parameter. My question is to give an estimate for the number of such sequences so that
$|a_1+a_2+\dots ...

**4**

votes

**2**answers

271 views

### Finding the codomain of a monoid homomorphism

We have a monoid M, and a function $f: M \rightarrow \{0, 1\}$. We're promised that this function factors through a (surjective) homomorphism to a finite abelian group (considered as a commutative ...