Counting total Number of Functions

  • Thread starter Thread starter 22990atinesh
  • Start date Start date
  • Tags Tags
    Counting Functions
Click For Summary

Homework Help Overview

The discussion revolves around counting the total number of functions from set A={1,2,3,...,n} to set B={1,2,3,...,m}, specifically focusing on strictly increasing and non-decreasing functions. The participants are exploring the implications of the function's properties, such as injectivity, in relation to these conditions.

Discussion Character

  • Conceptual clarification, Assumption checking, Mathematical reasoning

Approaches and Questions Raised

  • Participants are examining the counting methods for strictly increasing functions and questioning whether injectivity is a necessary condition. There is a discussion about the correctness of the original poster's approach and the implications of their formulas.

Discussion Status

There is an ongoing exploration of the counting methods, with some participants suggesting a more conceptual approach. The original poster has revised their calculations based on feedback, indicating a dynamic discussion with attempts to verify the formulas through examples.

Contextual Notes

Participants are encouraged to verify their formulas by testing with small values of n and m, although there is a caution that examples may not always validate the logic used in the reasoning.

22990atinesh
Messages
143
Reaction score
1

Homework Statement



Consider Sets A={1,2,3,...,n} and B={1,2,3,...,m} where 1<=n<=m. F:A->B

1) Total no. of strictly increasing function i.e if x<y then f(x)<f(y)
2) Total no. of non decreasing function i.e if x<y then f(x)<=f(y)

How can we count total number of functions here

2. The attempt at a solution

1st element in set A has [(m-1)-n+1] choices
2nd ... [(m-2)-n+1] choices
3rd ... [(m-3)-n+1] choices

and so on

So for 1) I'm getting (m-1)(m-2)(m-3)...(m-2n+1)
Is it the correct approach
 
Physics news on Phys.org
Do you agree in problem 1 that F must be injective? I think you do, so think how this interplays with the strictly increasing condition.

What I'm trying to get at is, there is a more conceptual way to count those functions.
 
verty said:
Do you agree in problem 1 that F must be injective? I think you do, so think how this interplays with the strictly increasing condition.

What I'm trying to get at is, there is a more conceptual way to count those functions.

Sorry for 1) It should be (m-1)(m-2)(m-3)...(m-n) and If the function is injective then ans for 1) should be (m-n)(m-n-1)(m-m-2)...(m-2n+1).
 
Last edited:
22990atinesh said:
Sorry for 1) It should be (m-1)(m-2)(m-3)...(m-n) and If the function is injective then ans for 1) should be (m-n)(m-n-1)(m-m-2)...(m-2n+1).

Why not try to verify your formulas by making n and m very small?
 
verty said:
Why not try to verify your formulas by making n and m very small?

Examples doesn't always works. If Logic is correct then example will definitely work. :smile:
 

Similar threads

Replies
2
Views
1K
  • · Replies 3 ·
Replies
3
Views
2K
  • · Replies 4 ·
Replies
4
Views
2K
  • · Replies 6 ·
Replies
6
Views
2K
  • · Replies 3 ·
Replies
3
Views
2K
Replies
1
Views
2K
Replies
3
Views
2K
Replies
3
Views
2K
  • · Replies 8 ·
Replies
8
Views
2K
Replies
8
Views
2K