16
\$\begingroup\$

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

Reference

Scoring

This is . Shortest answer in bytes wins.

Standard loopholes apply.

\$\endgroup\$
  • 11
    \$\begingroup\$ A definition of surjection would be nice. \$\endgroup\$ – Stewie Griffin Apr 20 '18 at 16:02
  • 3
    \$\begingroup\$ Is it intentional that n cannot equal k? \$\endgroup\$ – Dennis Apr 20 '18 at 16:08
  • 1
    \$\begingroup\$ @Dennis I like to exclude every possible edge case from my challenges \$\endgroup\$ – Leaky Nun Apr 20 '18 at 16:15
  • 3
    \$\begingroup\$ 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 \$\endgroup\$ – dylnan Apr 20 '18 at 16:22
  • \$\begingroup\$ @ whoever voted to close what is your reason? \$\endgroup\$ – dylnan Apr 20 '18 at 18:49

12 Answers 12

5
\$\begingroup\$

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.
\$\endgroup\$
4
\$\begingroup\$

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!

\$\endgroup\$
  • 2
    \$\begingroup\$ 38 bytes by using an infix operator: Try it online! \$\endgroup\$ – Laikoni Apr 21 '18 at 21:42
4
\$\begingroup\$

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!


Proof of correctness

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...

\$\endgroup\$
3
\$\begingroup\$

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)
\$\endgroup\$
  • \$\begingroup\$ -/@(^~*]!0{])]-i. \$\endgroup\$ – FrownyFrog May 22 '18 at 21:06
2
\$\begingroup\$

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.

\$\endgroup\$
2
\$\begingroup\$

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.
\$\endgroup\$
2
\$\begingroup\$

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...

\$\endgroup\$
2
\$\begingroup\$

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
<>{}{}{({}<>[{}])<>}<>
\$\endgroup\$
2
\$\begingroup\$

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!
\$\endgroup\$
2
\$\begingroup\$

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
\$\endgroup\$
1
\$\begingroup\$

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!

\$\endgroup\$
1
\$\begingroup\$

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
\$\endgroup\$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.