Sejam e conjuntos de números naturais com e . Quantas são as funções não-decrescentes?

Passo 1

Vamos resumir o problema: temos dois conjuntos de números naturais, com elementos e com elementos. Queremos descobrir quantas funções são não-decrescentes. Aqui, estamos trabalhando com Combinatória, especificamente com combinações com repetição. Para resolver isso, vamos precisar entender como contar as maneiras de atribuir valores de para de forma que respeitem a ordem não-decrescente.

Passo 2

Primeiro, vamos entender o que significa uma função ser não-decrescente. Isso quer dizer que se temos dois elementos e em onde , então . Como e são conjuntos de números naturais, podemos pensar nos elementos de e como sendo ordenados.

Passo 3

Agora, imagine que queremos atribuir valores de para cada elemento de de maneira que respeite essa ordem. Para facilitar, podemos considerar que estamos escolhendo uma sequência de números de que seja não-decrescente. Por exemplo, se e , uma possível sequência seria .

Passo 4

Para contar essas sequências, usamos o conceito de combinações com repetição. Nesse caso, estamos escolhendo elementos de , permitindo que se repitam, e sem nos importar com a ordem (já que a sequência será não-decrescente).

Passo 5

A fórmula para calcular o número de combinações com repetição é dada por:
Aqui, representa o número de maneiras de escolher elementos de um conjunto de elementos com repetição permitida.

Resposta

O número de funções não-decrescentes é dado por:

Exercícios relacionados

Sejam e conjuntos de números naturais com e . Quantas são as funções injetoras?
Um dado é lançado sucessivamente até que o primeiro 6 ocorra. Qual a probabilidade de ter jogar esse dado menos que 5 vezes (4 vezes ou menos)?
Quantos números de 5 algarismos podem ser formados usando apenas os algarismos 1, 1, 1, 1, 3 ?
Permutam-se de todas as formas possíveis os algarismos 1, 2, 4, 6, 7 e escrevem-se os números formados em ordem crescente. Determine: que número ocupa o lugar.