Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Number of functions from one set to another

  1. Oct 21, 2008 #1
    1. The problem statement, all variables and given/known data
    How many functions are there from {1,...,n} to {0,1}? and prove.

    3. The attempt at a solution
    For any k in {1,...,n} we can map k to either 0 or 1. So for any k there are two possible images. Since there are n kinds of k (from 1 to n) then there are 2^n possible functions

    I'm not sure how to formally prove this, or what kind of proof to use at least.
  2. jcsd
  3. Oct 21, 2008 #2


    User Avatar
    Science Advisor
    Homework Helper

    I would call that a proof. How formal do you want to be?
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook