Sejam A e B conjuntos de números naturais com |A| = p e |B| = n. Quantas são as funções f: A -> B não-decrescentes?

Passo 1

Vamos resumir o problema: temos dois conjuntos de números naturais, A com p elementos e B com n elementos. Queremos descobrir quantas funções f: A -> B 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 B para A 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 x e y em A onde x <= y, então . Como A e B são conjuntos de números naturais, podemos pensar nos elementos de A e B como sendo ordenados.

Passo 3

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

Passo 4

Para contar essas sequências, usamos o conceito de combinações com repetição. Nesse caso, estamos escolhendo p elementos de B, 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 p elementos de um conjunto de n elementos com repetição permitida.

Resposta

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

Exercícios relacionados