# Number of surjections

## Task

Given 2 positive integers n and k, where n > k, output the number of surjections from a set of n distinguishable elements to a set of k distinguishable elements.

## Definition

A function f: S → T is called a surjection if for every t∈T there is s∈S such that f(s) = t.

## Example

When n=3 and k=2, the output is 6, since there are 6 surjections from {1,2,3} to {1,2}:

1. 1↦1, 2↦1, 3↦2
2. 1↦1, 2↦2, 3↦1
3. 1↦1, 2↦2, 3↦2
4. 1↦2, 2↦1, 3↦1
5. 1↦2, 2↦1, 3↦2
6. 1↦2, 2↦2, 3↦1

## Testcases

n k output
5 3 150
8 4 40824
9 8 1451520


## Scoring

This is . Shortest answer in bytes wins.

Standard loopholes apply.

• A definition of surjection would be nice. Apr 20 '18 at 16:02
• Is it intentional that n cannot equal k? Apr 20 '18 at 16:08
• @Dennis I like to exclude every possible edge case from my challenges Apr 20 '18 at 16:15
• That seems like an important edge case to include. My guess is that most answers that work for n>k will also work for n==k but it might allow for some sneaky golfing somewhere Apr 20 '18 at 16:22
• @ whoever voted to close what is your reason? Apr 20 '18 at 18:49

# Jelly, 5 4 bytes

ṗṬML


This is an O(kn) brute force solution.

Try it online!

### How it works

ṗṬML  Main link. Left argument: k. Right argument: n.

ṗ     Cartesian power; yield the list of all n-tuples over {1, ..., k}.
Each tuple represents a (not necessarily surjective) function from
{1, ..., n} to {1, ..., k}.
Ṭ    Apply the "untruth" atom to each tuple.
Ṭ maps a list of indices to an array with 1's at those indices, and exactly
as many zeroes as needed to build the array.
Examples:
[1, 2, 3, 3, 3] -> [1, 1, 1]
[1, 3, 5]       -> [1, 0, 1, 0, 1]
[2, 6, 2, 4, 4] -> [0, 1, 0, 1, 0, 1]
M   Yield all indices of maximal elements, i.e., all indices of [1] * k.
L  Take the length.


# Haskell, 48 bytes

s(_,1)=1
s(1,_)=0
s(m,n)=n*(s(m-1,n-1)+s(m-1,n))


Try it online!

### Why is the surjection count s(m,n)=n*s(m-1,n-1)+n*s(m-1,n)?

in order to harvest n images, i can either

• squeeze a singleton [m] creation into any of the n boundaries surrounding n-1 groups
• or add my new m into any of n already existing groups of [1..m-1]

# Haskell, 38 bytes

m#n|n<2=1|m<2=0|o<-m-1=n*(o#(n-1)+o#n)


Try it online!

• 38 bytes by using an infix operator: Try it online! Apr 21 '18 at 21:42

# Lean, 66 bytes

def s:_->nat->nat|(m+1)(n+1):=(n+1)*(s m n+s m(n+1))|0 0:=1|_ _:=0


Try it online!

Try it online!

## Explanation

Let us ungolf the function:

def s : nat->nat->nat
| (m+1) (n+1) := (n+1)*(s m n + s m (n+1))
| 0     0     := 1
| _     _     := 0


The function is defined by pattern matching and recursion, both of which have built-in support.

We define s(m+1, n+1) = (n+1) * (s(m, n) + s(m, n+1) and s(0, 0) = 1, which leaves open s(m+1, 0) and s(0, n+1), both of which are defined to be 0 by the last case.

Lean uses lamdba calculus syntax, so s m n is s(m, n).

Now, the proof of correctness: I stated it in two ways:

def correctness : ∀ m n, fin (s m n) ≃ { f : fin m → fin n // function.surjective f } :=
λ m, nat.rec_on m (λ n, nat.cases_on n s_zero_zero (λ n, s_zero_succ n)) $λ m ih n, nat.cases_on n (s_succ_zero m)$ λ n,
calc fin (s (nat.succ m) (nat.succ n))
≃ (fin (n + 1) × (fin (s m n + s m (n + 1)))) :
(fin_prod _ _).symm
... ≃ (fin (n + 1) × (fin (s m n) ⊕ fin (s m (n + 1)))) :
equiv.prod_congr (equiv.refl _) (fin_sum _ _).symm
... ≃ (fin (n + 1) × ({f : fin m → fin n // function.surjective f} ⊕
{f : fin m → fin (n + 1) // function.surjective f})) :
equiv.prod_congr (equiv.refl _) (equiv.sum_congr (ih n) (ih (n + 1)))
... ≃ {f // function.surjective f} : s_aux m n

def correctness_2 (m n : nat) : s m n = fintype.card { f : fin m → fin n // function.surjective f } :=
by rw fintype.of_equiv_card (correctness m n); simp


The first one is what is really going on: a bijection between [0 ... s(m, n)-1] and the surjections from [0 ... m-1] onto [0 ... n-1].

The second one is how it is usually stated, that s(m, n) is the cardinality of the surjections from [0 ... m-1] onto [0 ... n-1].

Lean uses type theory as its foundation (instead of set theory). In type theory, every object has a type that is inherent to it. nat is the type of natural numbers, and the statement that 0 is a natural number is expressed as 0 : nat. We say that 0 is of type nat, and that nat has 0 as an inhabitant.

Propositions (statements / assertions) are also types: their inhabitant is a proof of the proposition.

• def: We are going to introduce a definition (because a bijection is really a function, not just a proposition).

• correctness: the name of the definition

• ∀ m n: for every m and n (Lean automatically infers that their type is nat, because of what follows).

• fin (s m n) is the type of natural numbers that is smaller than s m n. To make an inhabitant, one provides a natural number and a proof that it is smaller than s m n.

• A ≃ B: bijection between the type A and the type B. Saying bijection is misleading, as one actually has to provide the inverse function.

• { f : fin m → fin n // function.surjective f } the type of surjections from fin m to fin n. This syntax builds a subtype from the type fin m → fin n, i.e. the type of functions from fin m to fin n. The syntax is { var : base type // proposition about var }.

• λ m : ∀ var, proposition / type involving var is really a function that takes var as an input, so λ m introduces the input. ∀ m n, is short-hand for ∀ m, ∀ n,

• nat.rec_on m: do recursion on m. To define something for m, define the thing for 0 and then given the thing for k, build the thing for k+1. One would notice that this is similar to induction, and indeed this is a result of the Church-Howard correspondence. The syntax is nat.rec_on var (thing when var is 0) (for all k, given "thing when k is k", build thing when var is "k+1").

Heh, this is getting long and I'm only on the third line of correctness...

# J, 19 bytes

-/@(^~*]!0{])],i.@-


Try it online!

## Explanation

-/@(^~*]!0{])],i.@-  Input: n (LHS), k (RHS)
-  Negate k
i.@   Range [k-1, k-2, ..., 0]
]       Get RHS
,      Join, forms [k, k-1, ..., 0]
(        )        Dyad between n (LHS), [k, k-1, ..., 0] (RHS)
]           Get RHS
0{            Select value at index 0
]               Get RHS
!              Binomial coefficient
^~                 Raise each in RHS to power of n
*                Multiply
-/@                  Reduce from right to left using subtraction (forms alternating sum)

• -/@(^~*]!0{])]-i. May 22 '18 at 21:06

# Husk, 7 bytes

#¦ḣ¹π²


Try it online!

### Explanation

#¦ḣ¹π²  Inputs: n (²), implicit k (¹)
π²  Cartesian power of [1..k] to n
#        Count if:
ḣ¹      Range [1..k]
¦        Is a subset


# R, 49 bytes

function(n,k,j=0:k)((-1)^(k-j)*j^n)%*%choose(k,j)


Try it online!

Implements one of the formulas by Mario Catalani:

T(n, k) = Sum_{j=0..k} (-1)^(k-j)*j^n*binomial(k, j)


or alternately:

T(n, k) = Sum_{j=0..k} (-1)^j*binomial(k, j)*(k-j)^n


which yields the same byte count in R.

# Python 2, 56 53 50 bytes

f=lambda n,k:n/k and(1/k or f(n-1,k-1)+f(n-1,k))*k


Try it online!

-3 bytes thanks to H.PWiz.

-3 bytes thanks to Dennis.

• If n<k not all k can be mapped onto thus there are no surjections. n/k and takes care of this.
• Taking f(0,0)=1 gives us the only nonzero base case we need. 1/k or achieves this.

# Ruby, 46 bytes

f=->n,k{k>n ?0:k+n<1?1:k*(f[n-=1,k]+f[n,k-1])}


Try it online!

Standard recursive approach...

# Brain-Flak, 142 bytes

({}<({}()){({}[(())]<<>{({}({})<>)<>}{}>)}{}>)<>{<>(({}<>)<{({}[()]<([])({([{}]()({}))([{}]({}))}{}[{}])>)}{}({}<>)>)<>}<>{}{}{({}<>[{}])<>}<>


Try it online!

This uses the standard inclusion-exclusion formula.

I can't write up a full explanation at this time, but here's a high-level explanation:

# Compute k-th row of Pascal's triangle
({}<({}()){({}[(())]<<>{({}({})<>)<>}{}>)}{}>)<>

# Multiply each element by n^j (and reverse to other stack)
{<>(({}<>)<{({}[()]<([])({([{}]()({}))([{}]({}))}{}[{}])>)}{}({}<>)>)<>}

# Compute alternating sum
<>{}{}{({}<>[{}])<>}<>


# Pari/GP, 38 bytes

(n,k)->Pol(exp(x+O(x^n))-1)^k*n!\x^n%x


Try it online!

Using the formula by Vladimir Kruchinin on OEIS:

E.g.f.: (exp(x)-1)^k = sum T(n,k)x^n/n!


# JavaScript (Node.js), 43 bytes

T=(n,k)=>n<k?0:k+n<1||k*(T(--n,k)+T(n,k-1))


Try it online!

# 05AB1E, 10 bytes

sLsãʒêgQ}g


Try it online!

Explanation

sLsã       # Cartesian product of range(k) repeated n times
ʒ   }  # Filter by ...
êgQ   # Connected uniquified length == k  (every item in range(k) appears at least once)
g # Count
`