Sejam Im=1,2, ldots, m e In=1,2, ldots, n, com m <= n. Quantas são as funções f: Im In estritamente crescentes?

Passo 1

O enunciado nos dá os conjuntos
Im = 1,2,dots,m, In = 1,2,dots,n,
com m<= n, e pede o número de funções fcolon Imto In que sejam estritamente crescentes. O conteúdo aplicado é combinatória de funções monotônicas, e vamos usar a ideia de escolher subconjuntos de tamanho m.

Passo 2

Uma função f é estritamente crescente se, para todo i<i' em Im, tem-se f(i)<f(i'). Logo os valores
f(1)<f(2)<cdots<f(m)
são m elementos distintos de In, tomados em ordem crescente.

Passo 3

Assim, dar uma função estritamente crescente é o mesmo que escolher um subconjunto Ssubseteq In com lvert Srvert=m e, em seguida, atribuir a f(1),dots,f(m) os elementos de S na sua ordem natural. Cada subconjunto de tamanho m gera exatamente uma função crescente.

Passo 4

O número de formas de escolher um subconjunto de tamanho m de um conjunto de n elementos é o coeficiente binomial
binomnm

Resposta

binomnm

Exercícios de Livros Relacionados