Combinatória

por **Giiovanna** Seg Abr 08 2013, 11:42

O conjunto A possui p elementos e o conjunto B possui n elementos.Determine o número de funções f:A->B sobrejetoras para:

b) p = n+1
c) p = n+
R:
b) [n(n+1)!]/2
c) [(n+2)!n(3n+1)]/24

por **parofi** Qua Abr 10 2013, 14:51

Olá:
b)p=n+1. Sejam a1,a2,...,an+1 os n+1 objetos de A e b1,b2,...,bn os n elementos de B.
Para a função ser sobrejetora, cada um dos bi tem de ser imagem de algum dos ai. Assim, para o objeto cuja imagem vai ser b1 temos n+1 hipóteses; para o objeto cuja imagem vai ser b2 temos n hipóteses (não pode ser o mesmo objeto, porque senão não seria uma função); e assim sucessivamente, para o objeto cuja imagem vai ser bn teremos 2 hipóteses.
Temos para já (n+1)*(n)*(n-1)*...*2=(n+1)! possibilidades.
Mas, em qualquer desses casos, falta ainda utilizar um objeto (pois ainda só utilizamos n elementos de A). Para esse objeto temos n correspondências possíveis ( qualquer um dos n elementos de B).
Assim, temos (n+1)!*n possibilidades. No entanto,em cada um desses casos aparece repetida 2 vezes a mesma correspondência: por exemplo, a correspondência (a1,b1),(a2,b2),...,(an,bn),(an+1,b1) é a mesma que (an+1,b1),(a2,b2),...,(an,bn),(a1,b1). Daí termos de dividir por 2.
c) Não se vê o enunciado completo: p=n+?
Um abraço.

por **Giiovanna** Qua Abr 10 2013, 15:47

n+2 parofi, desculpe.

Obrigada pela explicação do b, aliás Smile

por radium226 Qua Jul 10 2019, 18:33

Na c): Temos n+2 elementos no domínio(A) e n no contradomínio(B). Esses 2 "novos" elementos em A podem ter imagens iguais ou diferentes. Separemos em casos:
Caso 1.Imagens iguais: Temos n elementos em A associados 1 a 1 aos n elementos de B. Ao adicionar 2 elementos novos com imagens iguais, terão que necessariamente ter imagens iguais a algum dos n elementos (princípio da casa dos pombos, se quiser ser formal). Há \binom{n+2}{3} formas de escolher esses 3 elementos que terão imagens iguais. Há n possibilidades para a imagem desses 3 elementos. Para o grupo dos n-1 restantes, há (n-1)! imagens possíveis. Multiplicando:
\binom{n+2}{3}n(n-1)!=\frac{n(n+2)!}{6}.
Caso 2.Imagens diferentes: Agora existem dois pares de elementos associados a suas duas respectivas imagens. Temos \binom{n+2}{2} modos para escolha do primeiro par, e para o segundo \binom{n}{2}. O primeiro par possui n possibilidades, o segundo n-1 e o grupo dos n-2 elementos tem (n-2)!.Ainda temos que perceber, antes de multiplicar, que (x_i,x_j) estarem no primeiro ou no segundo par não faz diferença, o que significa que contamos em 2! vezes, portanto, devemos dividir por 2! para corrigir. Multiplicando:
\frac{\binom{n+2}{2}\binom{n}{2}}{2!}n(n-1)(n-2)!=\frac{(n+2)!n(n-1)}{8}

Soma: \frac{n(3n+1)(n+2)!}{24}

por **Emanuel Dias** Ter Jun 30 2020, 06:36

parofi escreveu:Olá:
b)p=n+1. Sejam a1,a2,...,an+1 os n+1 objetos de A e b1,b2,...,bn os n elementos de B.
Para a função ser sobrejetora, cada um dos bi tem de ser imagem de algum dos ai. Assim, para o objeto cuja imagem vai ser b1 temos n+1 hipóteses; para o objeto cuja imagem vai ser b2 temos n hipóteses (não pode ser o mesmo objeto, porque senão não seria uma função); e assim sucessivamente, para o objeto cuja imagem vai ser bn teremos 2 hipóteses.
Temos para já (n+1)*(n)*(n-1)*...*2=(n+1)! possibilidades.
Mas, em qualquer desses casos, falta ainda utilizar um objeto (pois ainda só utilizamos n elementos de A). Para esse objeto temos n correspondências possíveis ( qualquer um dos n elementos de B).
Assim, temos (n+1)!*n possibilidades. No entanto,em cada um desses casos aparece repetida 2 vezes a mesma correspondência: por exemplo, a correspondência (a1,b1),(a2,b2),...,(an,bn),(an+1,b1) é a mesma que (an+1,b1),(a2,b2),...,(an,bn),(a1,b1). Daí termos de dividir por 2.
c) Não se vê o enunciado completo: p=n+?
Um abraço.

Não consigo enxergar a necessidade dessa divisão por 2.

por **Mateus Meireles** Dom Jul 05 2020, 12:01

Olá, Emanuel

Se não estou enganado, essa divisão foi feita pois acontece de contarmos repetidas vezes a mesma função. Por exemplo, quando escolhemos b₁ como imagem de a₁ e, ao final, b₁ como imagem de a₂; e também, em outro caso, b₁ como imagem de a₂ e, ao final, b₁ como imagem de a₁, e etc, temos a mesma função, mas sendo contadas como distinta.

Uma maneira mais fácil de enxergar é fazendo [latex]\binom{n+1}{2}[/latex] (escolha dos elementos de A que terão a mesma imagem) vezes [latex]n[/latex] (escolha da imagem em B) vezes [latex](n-1)![/latex] (relação bijetiva entre os n-1 elementos restantes).

Daí a resposta fica [latex]\binom{n+1}{2} \times n \times (n-1)! = \frac{n(n+1)!}{2}.[/latex]

Abs.

por **Emanuel Dias** Dom Jul 05 2020, 14:12

Mateus Meireles escreveu:Olá, Emanuel

Se não estou enganado, essa divisão foi feita pois acontece de contarmos repetidas vezes a mesma função. Por exemplo, quando escolhemos b₁ como imagem de a₁ e, ao final, b₁ como imagem de a₂; e também, em outro caso, b₁ como imagem de a₂ e, ao final, b₁ como imagem de a₁, e etc, temos a mesma função, mas sendo contadas como distinta.

Uma maneira mais fácil de enxergar é fazendo [latex]\binom{n+1}{2}[/latex] (escolha dos elementos de A que terão a mesma imagem) vezes [latex]n[/latex] (escolha da imagem em B) vezes [latex](n-1)![/latex] (relação bijetiva entre os n-1 elementos restantes).

Daí a resposta fica [latex]\binom{n+1}{2} \times n \times (n-1)! = \frac{n(n+1)!}{2}.[/latex]

Abs.