I_{m}=\{1,2, \ldots, m\} e I_{n}=\{1,2, \ldots, n\}. Quantas são as funções f: I_{m} \rightarrow I_{n} nāo decrescentes?

Passo 1

O enunciado define os conjuntos \r \;I_{m}=\{1,2,\dots,m\} e \;I_{n}=\{1,2,\dots,n\} \r
e pede o número de funções f\colon I_{m}\to I_{n} não decrescentes. Isso equivale a contar sequências \r \bigl(f(1),f(2),\dots,f(m)\bigr) com \r \;1\le f(1)\le f(2)\le\cdots\le f(m)\le n. Vamos usar o método de estrelas e barras para resolver.

Passo 2

Cada função não decrescente corresponde exatamente a uma sequência \r \bigl(f(1),\dots,f(m)\bigr) satisfazendo \r
1\le f(1)\le f(2)\le\cdots\le f(m)\le n. \r
Para contar essas sequências, basta agrupar quantas vezes cada valor de 1 a n aparece.

Passo 3

Defina x_i como o número de índices j tais que f(j)=i. Então cada x_i é inteiro não negativo e vale \r
x_1 + x_2 + \cdots + x_n = m. \r
Contar as sequências é o mesmo que contar as soluções não negativas dessa equação.

Passo 4

Pelo teorema de estrelas e barras, o número de soluções inteiras não negativas de \r
x_1 + x_2 + \cdots + x_n = m \r
é dado por \r
\binom{n + m - 1}{m}.

Resposta

\displaystyle \binom{n + m - 1}{m}

Exercícios relacionados