Find the number of ordered $k$-tuples Let $n$ be positive integer. Find the number of ordered $k$-tuples $(a_1,a_2, \ldots, a_k), k\le n$ from $\{1,2,\ldots, n\}$ satisfying at least one of the conditions:

*

*There exist $ s,t\in \{1,2,\ldots, k\} $ such that $ s<t $ and $ a_s> a_t $,

*There exist $ s \in \{1,2,\ldots, k\} $ such that $ a_s -s $ is an odd number.

I am not getting how to start with. Please help me. Thanks in advance.
 A: Here's a (rather long) hint to get you on the right track.
In the world of counting, sometimes things with a "there exists" constraint is a lot harder to control than a "for all" constraint.
For instance, consider the question of:

A. How many ordered $k$-tuples $(a_1,\dots,a_k)$ with $a_i\in\{0,\dots,9\}$ satisfy the property that $a_i=9$ for some $i$? (in other words, there exists $1\leq i\leq k$ such that $a_i=9$)

this can be pretty difficult to count since we have to consider a lot of things such as: where is the $9$? how many $9$'s are there in the tuple?
However, consider the similar problem:

B. How many ordered $k$-tuples $(a_1,\dots,a_k)$ with $a_i\in\{0,\dots,9\}$ satisfy the property that none of the $a_i=9$? (in other words, for all $1\leq i\leq k$, we have $a_i\neq9$)

This one is much easier to count: this just means all $a_i$ sample from $\{0,\dots,7,9\}$ and therefore we have $9^k$ such $k$-tuples. However, notice that this is the opposite to problem A! In particular, since there are $10^k$ ordered $k$-tuples in total, the answer to problem A is $10^k-9^k$.

We can employ a similar strategy to address your problems. Instead of trying to directly count the $k$-tuples in problems (1) and (2), try the opposite problems:

1') How many $k$-tuples $(a_1,\dots,a_k)$ with $a_i\in\{1,\dots,n\}$ satisfy that $a_s\leq a_t$ for all $s\leq t$?
2') How many $k$-tuples as above satisfy that $a_s-s$ is even for all $s$?

Problem (1') is counting the number of monotone sequences of length $k$ with numbers between $1$ and $n$, so you can try to solve this problem recursively: let $M(k,n)$ be the answer to (1') for some fixed $k$ and $n$, then we know

*

*$M(k,1)=1$ because the only solution here is $(1,1,1,\dots)$

*to compute $M(k,n+1)$, split the cases based on what the last number is. For example, if $a_k=n$, then the $(k-1)$-tuple $(a_1,\dots,a_{k-1})$ is monotone where each $a_i\in\{1,\dots,n\}$ (to ensure that $a_i\leq a_k$), so that there are $M(k-1,n)$ such tuples. In general, if $a_k=L$, then there will be $M(k-1,L)$ ways of choosing $a_1,\dots,a_{k-1}$ monotone and fitting in $\{1,2,\dots,L\}$ and therefore we get the recurrence
$$
M(k,n+1) = \sum_{L=1}^{n+1}M(k-1,L)
$$
I'll leave it to you to find a closed form of this (feel free to choose any alternative way of approaching this problem too; this is just a possible approach).

As for problem (2'), note that when $s$ is even, then $a_s-s$ is even iff $a_s$ is even; if $s$ is odd, then $a_s-s$ is even iff $a_s$ is odd. Therefore, you're trying to count the number of $k$-tuples $(a_1,\dots,a_k)$ where $a_{2i}\in\{2,4,6,\dots\}$ and $a_{2i-1}\in\{1,3,5,\dots\}$ are all at most $n$.
Once you have an answer for (1') and (2'), you can conclude with answers for (1) and (2) by noting that there are $n^k$ total $k$-tuples $(a_1,\dots,a_k)$ where $a_i\in\{1,\dots,n\}$ for all $i$.
