Easy If You Know It's Property !

Probability Level 5

Let $\displaystyle f( a) ={ 101 }^{ a }-101{ (100) }^{ a }+\frac { 101\times 100 }{ 2 } { (99) }^{ a }-\frac { 101\times 100\times 99 }{ 6 } { (98) }^{ a } \dots .$

If $\displaystyle A=\left\{ a : a \in \mathbb{N} | f(a) = 0 \right\},$
find $\displaystyle \sum _{ a\in A } a$

Original

The answer is 5050.

3 solutions

Mvs Saketh
Feb 22, 2015

A beautiful problem, however pretty simple as well,

imagine a set having 'a' elements , and another set having 101 elements,

suppose you wish to find the number of onto functions,,

Then how do you go about? there is no simple closed form expression for it, so we use the inclusion exclusion principle,

no. of onto functions = total no. of functions - the ones in which atleast one element of the second set is unmapped

= $\displaystyle{101^{ a }\quad -\quad 101\quad (100)^{ a }}$

But is that right? no because in the process of subtracting, what i have done is fix any one element of the second set, and map the rest randomnly ,,

so consider any two elements a and b of second set,

Suppose i fix a and decide to unmap it and rest i map, and then i do the same with b,

But wait in this process the number of mappings where both a and b are unmapped have been counted twice, this occurs for all pairs so i add back

$\displaystyle{+\quad 101C2\quad (99)^{ a }}$

, But is that all , again using similar reasoning i deduce that i have double added all mappings where atleast 3 are unmapped, and so on till i get a sum

$\displaystyle{\sum _{ r=0 }^{ 101 }{ (-1)^{ r } } (101Cr)(101-r)^{ a }}$

which is nothing but f(a),

Now when is it 0 , obviiously when the number of onto maps is 0 or impossible, which occurs when the number of elements in Domain is less than that in range, hence a varies from 0 to 100,

sum is simple AP

100*101/2 = 5050

This can also be solved using concept and formula of stirling numbers of second kind and multiplying 101 !, but then that formulas proof comes from here, so we will just end up in circles

Your Approach Is Different and Interesting ! I need Some Time To Understand It More Precisely . But I create this By using concept that degree 'a' of polynomial is less then 101 (in this quest) then expression will alway's be zero . We can Prove It By using Calculus. And We can Check for simple cases like a=0 , a=1 etc.

$\displaystyle{f\left( a \right) =\sum _{ r=0 }^{ 101 }{ { (-1) }^{ r }(\begin{matrix} 101 \\ r \end{matrix}) } { (101-r) }^{ a }\\ f(a)=0\quad \Rightarrow \quad If\quad 0<a<101\quad \\ \sum _{ a\in A }^{ }{ a } =1+2+3+................100=5050\\ }$

Deepanshu Gupta - 6 years, 3 months ago

woah, i thought for sure that you had the same approach, and hence you even gave the tag of combinatorics , basically i used the fact that the formula is the exact formula for number of onto functions , and no. of onto functions is 0 when domain has lesser elements than range, because then atleast one y will definitely not have a preimage, please upload your solution as well :) (when u have time)

Mvs Saketh - 6 years, 3 months ago

Wow Man ! Hat's Off . That's Coooool approach , " Awesome " . I want to upvote this many times . :)

And Yes I will Post If I got Some Time. But really I'am afraid To post it , because It's Proof is nasty . :) I hope Some-one Post It ! If not then I will...... :)

Deepanshu Gupta - 6 years, 3 months ago

@Deepanshu Gupta – thanks :) shall wait for solution

Mvs Saketh - 6 years, 3 months ago

I tried very hard to find closed form of this expression but failed, finally pressed on see solution button, didn't thought of the onto functions approach( I have formed the same expression while solving for the number of onto functions) but didn't thought of using that in this question.

Nice approach +1

Ronak Agarwal - 6 years, 3 months ago

That was ingenious! Since I used calculus here, I can see the relationship between what you did and what Deepanshu actually intended people to do.

Hats-Off!

Raghav Vaidyanathan - 6 years, 3 months ago

Really very nice solution! It would never have struck me!

Arpan Banerjee - 6 years, 3 months ago

You could have obtained that formula for onto functions by using the Principle of Inclusion-Exclusion (however, what you have done is principally the same).

Anant Kumar - 6 years, 3 months ago

wow cool solution , Never thought to use onto function formula here , Although It is tag with Combinatorics .. But still I used Calculus here ! Nice approach !

Nishu sharma - 6 years, 1 month ago

Rayyan Shahid
Mar 18, 2018

Well it isn't really a different solution, I mean more or less equivalent to @Mvs Saketh solution. Just another way of interpreting the onto functions is to realise it is the number of ways of distributing a distinct balls among $101$ distinct boxes such that no box remains empty. We will get the same expression using PIE and its easy to see that we must have at least $101$ balls (i.e $a$ ) for no box to remain empty. Hence the expression takes the value $0$ for $a \in { 1,2,3....100}$ . So the sum is $5050$

Uddeshya Upadhyay
Feb 25, 2015

It's simply the total number of onto functions from set U containing a elements to set The containing 101 elements.. To be zero... Set U must contain less than 101 elements

Easy If You Know It's Property !

Original

The answer is 5050.

3 solutions

0 pending reports