Number of sequences that maintain a property

Question

In how many ways can i create a sequence of $m$ elements from the set $1,2,...,n$ such that the longest strictly increasing subsequence of it is exactly $n$?

For example if $n=3$ and $m=4$ then the answer is $9$.

Answer 1

We assume $n$ is fixed.

Given $i\geq 0$ and $j>0$ we let $R(i,j)$ be the number of sequences of length $i$ of alphabet $\{1,2\dots n\}$ such that sequence $1,2,3\dots j$ is a subsequence but $1,2\dots j+1$ is not. ($R(m,0)$ is the number of sequences without $1$).

You want $R(m,n)$.

We clearly have $R(1,0)=n-1$, $R(1,1)=1$ and $R(1,x)=0$ if $x>1$

We also have $R(i,0)=(n-1)^i$.

Finally, if $i,j>1$ and $j<n$ we have $R(i,j)=R(i-1,j-1)+(n-1)\times R(i-1,j)$

and if $i,j>1$ and $j=n$ we have $R(i,j)=R(i-1,j-1)+n\times R(i-1,x)$

The following algorithm prints R(m,n) (the residue after dividing by $10^9+7$ to avoid overflows)

#include <bits/stdc++.h>
using namespace std;
typedef long long lli;

const lli MOD=1000000007;
const int MAX=10010;
lli R[MAX][MAX]; // this stores the answer.

lli pow(lli base, lli exp){
    lli res=1;
    while(exp){
        if(exp%2) res=(res*base)%MOD;
        base=(base*base)%MOD;
        exp/=2;
    }
    return(res);
}

int main(){
    int m,n;
    scanf("%d %d",&m,&n);
    R[1][1]=1;
    for(int i=1;i<=n;i++){
        R[i][0]=pow(n-1,i);
    }
    for(int i=2;i<=m;i++){
        for(int j=1;j<=n;j++){
            if(j==n) R[i][j]=(R[i-1][j-1]+n*R[i-1][j])%MOD;
            else R[i][j]= (R[i-1][j-1]+(n-1)*R[i-1][j])%MOD;
        }
    }
    printf("%lld\n",R[m][n]);
}