Striking Distribution
Probability
Level
pending
Given n, how many ways can we write n as a sum of one or more positive integers a1 ≤ a2 ≤ ... ≤ ak with ak - a1 = 0 or 1.
n
(n+1)/2
(n-1)/2
n^2
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
1 solution
Well I managed to get this but not quite sure about it
There is one way for each 1 ≤ k ≤ n . Induction on n . Obvious for n = 1 . Write the solution with a > 0 N s and b ≥ 0 (N+1) s as ( a , b , N ) . Define a map f from the solutions for n to the solutions for n + 1 by f ( a , b , N ) = ( a − 1 , b + 1 , N ) for a > 1 or ( b + 1 , 0 , N + 1 ) for a = 1 . Define a map g from the solutions for n + 1 excluding ( n , 0 , 1 ) to the solutions for n by g ( a , b , N ) = ( a + 1 , b − 1 , N ) for b ≥ 1 and ( 1 , a − 1 , N − 1 ) for b = 1 . Evidently f and g are inverses, so each is a bijection. Hence there is one more solution for n + 1 than for n .