4
$\begingroup$

I going to apply to a maths major the coming year and in order to do that, I need to pass the entry test (just so you know my level ain't high).

The question is from a long list of exercises they gave me to get ready for the test:

$Let$ $[n]={1,2,3,....,n}$

How many functions are there from [9] to [7] if every image in the codomain has 3 arguments in the domain? (I translated it from hebrew, I hope I'm correct)

so I thought taking the set $[9]$ and divide it into 3 triplets:

for example:$${(1,2,3),(4,5,6),(7,8,9)}$$ so all possible combinations are $${9 \choose 3}$$

and then I'll try to calculate all possible permutations with $[7]$ which is:

$${9 \choose 3}*\frac{7!}{(7-3)!}$$

I think I made a mistake about how I counted the combinations but I don't have any solutions to check myself (silly I know), is it correct?

$\endgroup$
2
$\begingroup$

Your answer is incorrect.

Strategy: A function is determined by choosing which elements in the domain map to which elements in the codomain. We choose three elements in the codomain to be in the range, then choose which three elements of the domain map to each image in the range.

  1. Choose three of the seven elements in the codomain to be in the range.
  2. Choose which three of the nine elements in the domain map to the smallest of the three images in the range.
  3. Choose which three of the six remaining elements in the domain map to the next smallest image in the range.
  4. Assign all three of the remaining elements to map to the largest image in the range.

$$\binom{7}{3}\binom{9}{3}\binom{6}{3}\binom{3}{3}$$

$\endgroup$
4
  • $\begingroup$ Unfortunately, I didn't really get why should I choose 3 of 9 elements in the domain to map to the smallest of three images in the range. How does that help to get all possible permutations? $\endgroup$
    – user565804
    Jun 6 '18 at 13:10
  • $\begingroup$ You have to decide which elements in the domain map to which elements in the range. $\endgroup$ Jun 6 '18 at 13:17
  • $\begingroup$ ok, I understand what happens in your strategy but it's hard for me to see how it correlates to the combinatorics, maybe I'll understand better if you'll explain it in a more formal way? $\endgroup$
    – user565804
    Jun 6 '18 at 13:33
  • $\begingroup$ Now I noticed your spoiler, should help, I'll dig into it now. $\endgroup$
    – user565804
    Jun 7 '18 at 5:49
0
$\begingroup$

There is no need of ordering. A quite formal approach would be by the mean of combinatorial species. The general species associated to this sort of problem is :

$$ E(E(X).Y).E(Y) $$

reading such a formula requires similar skills to writing a strategy. The advantage is that we solve all this kind of problems at a time.

coming back, we have to consider objects like {1,2,3}-A, {4,5,6}-B, {7,8,9}-C and {D,E,F,G}

Overall we get a new formula :

$$ 3(3(X).Y).4(Y) $$

where for eg 3(chickens) stands for three chickens.

Passing to e.g.f. one has

$$ \frac {1} {3!} (\frac {x^3}{3!} y)^3. \frac {y^4} {4!} $$

after calculus we got the sollution that is the coefficient of the e.g.f : $$ 58880 .\frac {x^9}{9!}. \frac {y^7}{7!} $$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy