Having problem with a surjection problem.

Question

Hello, I am a fairly decent programmer, but I suck at math. I need help understanding this problem so i can write a program to solve it. I dont really understand the formula.

https://cs.harding.edu/easel/cgi-bin/view?id=4896

Answer 1

Well, summarily you are just asked to read a file, to apply a function to compute number of surjection whose definition is given on the second page, then to write result to the output file.

You don't even have to understand what is a surjection, just to translate the mathematical formula to compute the number of surjections. It's easier than it could look at first sight.

First you just have to perform some tests on parameters to find in which case you are because you are given 4 different formulas depending on the case. The only complex formula is the last one with the big sigma. Hint: look at the big sigma like a loop where you add the results of each loop. And if the number of surjection appears in this formula... well, if you are a decent programmer you know recursivity.

Good luck.

To give you the feeling, below is the direct translation to python of the formula for Combinations(n, i) given at the end. As you can see it's a no brainer, you just read the definition and type the equivalent function.

def c(n,i):
    if i == 0 or n == 0 or i == n:
        return 1
    return c(n-1, i-1) + c(n-1, i)

(Note: as i is always between 0 and n, no need to check it's true)

Answer 2

You need to implement the formula given on the second page of the assignment. This is a typical piecewise function. Are you having problems understanding the notation or the concept?

A piecewise function is implemented by selecting the piece based on the input, m and n in this case, and then executing the formula associated with the piece. Here's a very basic start:

int calculate_summation(int m, int n);

int calculate_surjection(int m, int n) {
  if (n == 1) {
    return 1;
  }
  if (m < n) {
    return 0;
  }
  if (m == n) {
    // calculate m! and return it
  }
  int summation = calculate_summation(m, n);
  return int(std::pow(double(n), double(m))) - summation;
}

int n_choose_i(int n, int i) {
  // implement the "n things taken i times" piecewise function
}

int calculate_summation(int m, int n) {
  // implement the rest of your homework here using n_choose_i function
}

int main() {
  std:ifstream in_stream("surjections.in");
  std::ofstream out_stream("surjections.out");
  int m, n;
  while (in_stream >> m >> n)
    out_stream << "S(" << m << "," << n << ") = "
               << calculate_surjection(m,n) << std::endl;
  out_stream.close();
  return 0;
}

Answer 3

Sounds like you don't understand the notation.

the function describes a case analysis with for branches. a case like:

{ f(x)   if g(x)

just means

if(g(x) )
    return f(x)

The sigma bit (the sidways M) means add up all of the stuff on the right, with every possible combination of the stuff on the right with i between something and something else. Basically

sum = 0;
for ( i = 1; i <= n-1; i++)
    sum += etcetera...;