每日一题[563]计数的映射方法

集合$A=\{1,2,\cdots ,n\}$，则定义在$A$上的不减函数$f:A\to A$(即$\forall x,y\in A,x\leqslant y,$有$f(x)\leqslant f(y)$)的个数为_______．

分析与解　考虑$(n+1) \times n$的网格，每一个符合题意的不减函数都与其中的路径 $$(1,f(1))\to (2,f(2))\to \cdots \to (n,f(n))$$ 一一对应，将路径补充为 $$(1,1)\to (1,f(1))\to (2,f(2))\to \cdots \to (n,f(n)) \to (n+1,n)$$ 且将该路径看作沿网格中的线段从$(1,1)$运动到$(n+1,n)$，每次只能往右或者往上运动．因此只需要在总共的$2n-1$次运动中确定向右运动的那$n$次的位置即可，答案为${\rm C}_{2n-1}^{n}$．

注　本文是卡特兰数的一个应用，也可以将这个问题转化成$n$个相同的小球放入编号为$1,2,\cdots,n$的$n$个盒子的问题，编号为$k$的盒子中球的数目就是函数值$k$对应的原象个数，而函数不减，所以原象个数确定后，原象也唯一确定．比如：编号为$(1,2,\cdots,n)$的盒子中小球数目分别为$(2,1,0,0,\cdots,0,n-3)$，则有两个自变量对应的函数值为$1$，必为$1,2$；有$1$个自变量对应的函数值为$2$，必为$3$，其它自变量对应的函数值均为$n$，即$f$为 $$f(1)=f(2)=1,f(3)=2,f(4)=f(5)=\cdots=f(n)=n.$$ 由隔板法与对应法知，不同的放法总数为$\mathrm{C}_{2n-1}^{n-1}$．

进一步学习见卡特兰数——计数的映射方法的伟大胜利（方法技巧栏目）．