What is wrong with my summation formula?

DerekZ10 · Mar 7, 2014

Im trying to find a general formula I can store in my calculator that can find the number of onto (surjective) functions exists for a relation of when M is mapped to N.

I can't seem to find a nice formula for it, but based on the below material I will show you what I have developed.

From: Discrete Mathemeatics and Its Applications 7th Edition Rosen pg. 561

Theorem 1 from a discrete mathematics text: for positive integers m ≥ n, the number of onto functions from an m-element set to an n-element set is n^m − C(n,1)(n−1)^m + C(n,2)(n−2)^m − ··· + (−1)^(n−1)C(n,n−1)·1^m.

From: Discrete Mathemeatics and Its Applications 7th Edition Rosen pg. 512

Textbook problem 29: Show that S(m, n) satisfies S(m, n) = n^m - sum from k=1 to n-1 of C(n, k) S(m, k) for m >= n and n > 1, with S(m, 1) = 1.

Random Chegg Problem from Google Search I'm using to verify with:

Screenshot of a worked solution counting onto functions from a 7-element set to a 5-element set, ending with the result 16800 in a box.

Here is what I've formed, written out:

Handwritten formula: n^m + sum from k=1 to n-1 of ( C(n,k) (m-k)^m (-1)^k ), with the binomial coefficient written as n over k.

In the TI nSpire CX CAS, it's written like this:

Calculator Scratchpad screen showing n^m plus a summation from k = 1 to n-1 of nCr(n,k)·(m-k)^m·(-1)^k, with result -693210 and previous entry A(4) = 5.

And as you can see, the chegg problem I'm trying to verify it with doesn't match!
But I think it should! If I manually iterate the function like so:

Screenshot of a TI-Nspire Scratchpad showing the definition A(t) := nCr(n,t)·(n-t)^m·(-1)^t, marked Done, followed by values A(1) = -81920, A(2) = 21870, A(3) = -1280, A(4) = 5.

The values are correct and what Chegg is showing. What have I done wrong in my equation?

gopher_p · Mar 7, 2014

Did you check that your summation formula matches the version that doesn't use sigma notation? i.e are all your ##m##s and ##n##s where they're supposed to be?

DerekZ10 · Mar 7, 2014

Wow, good call! I don't know how I constantly was missing that the (m-k) portion that should have been (n-k). And I even had it right in the non iterative equation.

What is wrong with my summation formula?

Discussion

Similar threads