1. Sejam I_{m}=\{1,2, \ldots, m\} e I_{n}=\{1,2, \ldots, n\}, com m \leqslant n. Quantas são as funções f: I_{m} \rightarrow I_{n} estritamente crescentes?

Passo 1

O enunciado pede: “Quantas são as funções f: I_{m}\to I_{n} estritamente crescentes?”, onde foram dadas as informações:
  • I_{m}=\{1,2,\ldots,m\}.
  • I_{n}=\{1,2,\ldots,n\}.
  • Está explícito que m\leqslant n.
    A pergunta é contar o número de funções f que satisfazem a propriedade “estritamente crescente”.

Passo 2

Entendendo exatamente o que significa “estritamente crescente” no contexto das funções f: I_{m}\to I_{n}.
  • Dizemos que f é estritamente crescente se, para quaisquer i,j\in I_{m} com i<j, vale f(i)<f(j).
  • Como I_{m} tem os elementos 1,2,\ldots,m em ordem natural, essa condição equivale a exigir
f(1)<f(2)<\cdots<f(m).
Ou seja, os valores da função sobre 1,2,\ldots,m formam uma sequência estritamente crescente de elementos de I_{n}.

Passo 3

Observação chave (ideia central da contagem): a informação essencial de uma função estritamente crescente f é exatamente o conjunto dos valores imagem
\{f(1),f(2),\dots,f(m)\}.
Esse conjunto tem as seguintes propriedades:
  • Tem exatamente m elementos (porque f(1),\dots,f(m) são todos distintos, por serem estritamente crescentes).
  • Cada elemento pertence a I_{n}.
  • Uma vez escolhido esse conjunto de m elementos, há uma única maneira de atribuí-los a f(1),\dots,f(m) respeitando a ordem estrita: ordenar os elementos do conjunto em ordem crescente e tomar f(1) como o menor, f(2) como o segundo menor, e assim por diante.
Portanto existe uma correspondência biunívoca (bijeção) entre:
  • funções estritamente crescentes f: I_{m}\to I_{n}, e
  • subconjuntos de I_{n} com exatamente m elementos.
Explicando por etapas a bijeção:
  • Injecão: duas funções distintas teriam imagens diferentes como tuplas ordenadas, portanto seus conjuntos imagem diferem.
  • Sobjectão: dado qualquer subconjunto S\subseteq I_{n} com |S|=m, ordenando os elementos de S em ordem crescente obtemos uma sequência s_1<s_2<\cdots<s_m; definir f(i)=s_i produz uma função estritamente crescente com imagem S.
    Logo é bijetiva.

Passo 4

Agora a contagem reduz-se a contar quantos subconjuntos de I_{n} têm exatamente m elementos. Esse número é o coeficiente binomial
\binom{n}{m},
lido “ n escolhe m”, que conta o número de maneiras de escolher m elementos de um conjunto com n elementos sem considerar ordem.
Para fixar ideia, a fórmula fechada é
\binom{n}{m}=\frac{n!}{m!(n-m)!},
onde n! (lê‑se “ n fatorial”) é definido por
n!=1\cdot 2\cdot 3\cdots n,
e por convenção 0!=1. Essa fórmula vem do raciocínio: o número de listas ordenadas de m elementos distintos escolhidos de n é
n(n-1)\cdots(n-m+1)=\frac{n!}{(n-m)!},
mas cada conjunto escolhido corresponde a m! listas ordenadas (as m! permutações), por isso dividimos por m!.

Passo 5

Exemplo concreto para ficar mais tranquilo: escolha m=2 e n=4.
  • Quais são as funções estritamente crescentes f:\{1,2\}\to\{1,2,3,4\}? São dadas pelas imagens (f(1),f(2)) com f(1)<f(2). As opções são (1,2),(1,3),(1,4),(2,3),(2,4),(3,4) — exatamente 6 possibilidades.
  • E \binom{4}{2}=\dfrac{4!}{2!\,2!}=\dfrac{24}{2\cdot 2}=6. Confere com o exemplo.
Dica para prova: ao ver “funções estritamente crescentes” entre conjuntos de inteiros consecutivos, pense imediatamente em “escolher um subconjunto e ordenar” — isso salva tempo.

Resposta

\displaystyle \binom{n}{m}=\frac{n!}{m!(n-m)!}

Exercícios relacionados