I want to know how to calculate number of non decreasing functions from one set to another set.  Let $A=\{1,2,3,\ldots,10\}$ and $B=\{1,2,3,\ldots,25\}$  Please tell me an easy method to calculate the number of non decreasing functions from set $A$ to $B$.  I can understand permutations and combinations, but I need an explanation which sticks to a basic level.
121102
Let $I_j={\{1,2,\ldots,j}\}$ for $j \in \mathbb{N}$. For $m,n \in \mathbb{N}$, how many non-decreasing functions $f:I_m \to I_n$ exist?
51157
Find all functions $f$ such that $f:\mathbb{N}\rightarrow\  \mathbb{N}$ and $f(f(n))+f(n+1)=n+2$   Let us plug in $n=1$  $f(f(1))+f(2)=3$  Since the function is from $\mathbb{N}$ to $\mathbb{N}$, $f(2)$ can only take the values $1,2$. Now we divide the problem into cases.  Case-1: $f(f(1))=2,f(2)=1$  We can assume that $f(1)=c$ for the time being. Then plugging in $n=3$ and using $f(2)=1$ gives $$f(3)=4-c$$ and again since the range of the function is positive integers,then $4-c$ has to be positive and hence $c$ belongs to  {$1,2,3$}. Now, $$f(1)=c$$$$\implies f(f(1))=f(c)$$$$\implies 2=f(c)$$ by the assumption that $f(f(1))=2$ . Now,since $c$ can only take the values $1,2,3$,we start treating cases. If $c=1$,$$f(c)=2$$$$\implies f(1)=2$$ but we know from the deinition of $c$ that $f(1)=c=1$,a contradiction.If $c=2$,then $2=f(c)=f(2)$ but $f(2)=1$ by assumption. Finally,if $c=3$ $$2=f(c)=f(3)$$ but $$f(3)=4-c=4-3=1$$ which is once again a contradiction. Therefore there are no such functions in this case.  Case-2: $f(f(1))=1,f(2)=2$  Again assuming $f(1)=c$ and using $f(n)\le n$ along with plugging $n=c-1$ will give us that $f(1)=1$ and then it is easy to prove that such a function exists by recursion. I can only give a "sort of recursive" way to define the function. Here it goes $$f:\mathbb{N}\rightarrow \mathbb{N}$$$$f(1)=1$$$$f(n)=n+1-f(f(n-1))$$  But this case is harder to deal with.Some help will be appreciated.
73580
Let $S = \{1,2,3,4\}$. Let $F$ be the sets of all functions from $S$ to $S$.  Now I think this statement is true:  $\forall f \in F , \exists g\in F$ so that $(g \circ f)(1) =2$  I suppose $f \in F$, and I need to show that $\exists g\in F$ so that $(g \circ f)(1) = 2$  Do I just make an example  of $g$ so that $(g \circ f)(1) = 2$ ?  Like $f(1) = y$  and then  $g (y)=2 ?
119103
Omg this is driving me crazy seriously, it's a subproblem for a bigger problem, and i'm stuck on it.  Anyways i need the number of ways to pick $x[1]$ ammount of objects type $1$, $x[2]$ ammount of objects type $2$, $x[3]$ ammounts of objects type $3$ etc etc such that $$x[1] + x[2] + \ldots x[n] = k\;.$$ Order of the objects of course doesn't matter.  I know there is a simple formula for this something like $\binom{k + n}n$ or something like that i just can't find it anywhere on google.
8362
I am provided with a multi-set, let's say S with elements as [num1, num2, num3] and these elements are integers (both negative as well as non negative). As this is a multi-set, elements in the multi-set can be present multiple times. I need to choose an element from this multi-set and multiply it with -1. I need to perform this operation m times. I want to find out how many multi-sets are there which can be made from this multi-set. This is home work, so really sorry but I am not able to proceed. I need some help in this. Please give me some hints. I am providing one example.  S = [2, 3, 2] and m=2 then there are 4 possible multisets   [2, 3, 2] [-2, -3, 2] [-2, 3, -2] [2, -3, -2].   Any help would be appreciated.
122810
can someone please explain to me how to count the number of topological sorts  for poset(A|) where A = {2,3,4,8,9,16,27,81} ? Quick example would be nice. Please help...I have an exam in several hours. Thanks !
35739
I just wonder if my following solution is true. Let $X,Y$ be sets, let $f:X\to Y$ be a function, let $\{Y_i\}_{i\in I}$ be a family of subsets of $Y$. (Note: I use equalities instead of mutual containment) $$\begin{align}f^{-1}\left[\bigcup_{i\in I} Y_i\right]  &amp;= \{x \in X: \mbox{there exists an}\quad i \in I\mbox{ such that } y \in Y_i,f(x)=y\}  \\&amp;=\bigcup_{i \in  I} f^{-1}\left[Y_i\right] \end{align}$$ I initially do not know how to get from the left to right, but when I put both sets in set notation, they turn out to be the same, hence the one line proof. Something go ultimately wrong?
59684
I have encountered this question in a coding competition and want the formula for $f(n)$. Is there any way to do this?
29049
Suppose that both f(n) and g(n) are non-negative functions. If $f(n)=O(g(n))$, is  $2^{f(n)}=O(2^{(g(n)})$ true too? If not, give counter examples.  I am unsure of how to proceed. What I have in mind at the moment is that since f(n) and g(n) are non-negative functions, making them functions exponents to 2 (as the base) would not change their characteristics. I would appreciate help in understanding this problem and proving it.
64845
In how many ways can we choose $r$ numbers from $\{1,2,3,...,n\}$,   In a way where we have no consecutive numbers in the set? (like $1,2$)
23980
I'm reading .     The graph of $f: A \rightarrow B$ is the subset of $A × B$ consisting   of all ordered pairs $(a, b)$ with $f (a) = b$. If $A$ happens to be   $B^n$ for some $n ∈ N$, then we say that $f$ is a function on $B$ and   $n$ is the arity of $f$.   I don't understand the notation for the exponent of a set, I'm aware of what  is, it's the number of arguments or operands the function takes. I'm just not so sure if I can assume that a set with an exponent such as in $B^n$ means that a function has two operands.  I know the question may be too naive and perhapes the answer is the one I suggested and it's right in front of my face, I'm just searching for a confirmation or the negation of it. Thanks.
63864
If a set has $n$ elements, how many transitive relations are there on it?  For example if set $A$ has $2$ elements then how many transitive relations. I know the total number of relations is $16$ but how to find only the transitive relations? Is there a formula for finding this or is it a counting problem?  Also how to find this for any number of elements $n$?
41538
What is the number of ways to select ten distinct letters from the alphabet $\{a, b, c, \ldots, z\}$, if no two consecutive letters can be selected?   There are a couple of formulas that I could use, but I am not sure how to use them.     The number of combinations of a given length that use elements from a given set, allowing repetition and with no missing elements in other words, each element of the given set occurs at least once in each combination: $\binom{k-1}{n-1}$ where where $n$ is the number of elements in the given set and $k$ is the length of the combination.   OR     The number of combinations of a given length that use elements from a given set, allowing repetition: $\binom{n+k-1}{n-1}=\binom{n+k-1}{k}$ where $n$ is number of elements in the given set and $k$ is the length of the combination.   Please help me understand what I should do and how to go about solving this question?
111161
Am I on the right track? I am not sure about my reasoning... Number of surjective functions from $A$ to $B$ $$A = \{1,2,3,4\} ; B = \{a,b,c\}$$ We must count the surjective functions, meaning the functions for which for all $b \in B$, $\exists~a \in A$ such that $f(a) = b$, $f$ being one of those functions. In order for a function $f:A\rightarrow B$ to be a surjective function, all 3 elements of $B$ must be mapped. We need to count how many ways we can map those 3 elements. We will subtract the number of functions from $A$ to $B$ which only maps 1 or 2 elements of $B$ to the number of functions from $A$ to $B$ (computed in 4.c : 81). Only 1 element of $B$ is mapped The first $a \in A$ has three choices of $b \in B$. The others will then only have one. Total functions from $A$ to $B$ mapping to only one element of $B$ : 3. Exactly 2 elements of $B$ are mapped Similarly, there are $2^4$ functions from $A$ to $B$ mapping to 2 or less $b \in B$. However, these functions include the ones that map to only 1 element of $B$. So there are $2^4-3 = 13$ functions respecting the property we are looking for. In the end, there are $(3^4) - 13 - 3 = 65$ surjective functions from $A$ to $B$.
4694
I am trying to figure out how many permutations exist in a set where none of the numbers equal their own position in the set; for example, $3,1,5,2,4$ is an acceptable permutation where $3,1,2,4,5$ is not because 5 is in position 5.  I know that the number of total permutations is $n!$. Is there a formula for how many are acceptable given the case that no position holds its own number?
105141
How many subsets does the set $\{1, 2, \dots , n\}$ have that contain no two   consecutive integers if 1 and n also count as consecutive?   It looks that the number of such subsets obeys the (Fibonacci-style) formula $$ F(n) = F(n-1)+F(n-2) $$ with $F(0)=1$ and $F(1)=2$, but I wasn't able to prove this conjecture.
108230
We have $r$ objects and $n$ boxes. I have to count all the combinations possible if the objects and boxes could be both different. If that happens I can count the number of variations from $n$ to $r$ (number of functions between objects and boxes). I mean, $n^r$.  But if I have to count all the combinations possible if anyone of the boxes is empty ($r\ge n$). Now I have to count the surjective functions.  For example if I have $r$ objects and 1 box. The number of surjective functions is 1. Then, if I have $r$ objects and 2 boxes, the number of surjective functions is $2^r-2$. And finally if I have $r$ objects and 3 boxes, I will count $3^r-2\cdot[3\cdot2^r-3]$. How do I get the formula for $r$ objects and $n$ boxes?