IME / ITA ⇒ IME 2002/2003 Tópico resolvido

[RonaldoJr]

Sejam [tex3]A[/tex3] e [tex3]B[/tex3] dois subconjuntos de [tex3]\operatorname{N}[/tex3].Por definição, uma função [tex3]f:A\rightarrow B[/tex3] é crescente se [tex3]a_{1} > a_{2} \rightarrow f(a_{1}) \geq f(a_{2})[/tex3], para quaisquer [tex3]a_{1}[/tex3] e [tex3]a_{2} \in A[/tex3]
Para [tex3]A = \{ 1,2,3\}[/tex3] e [tex3]B = \{1,2,...,n\}[/tex3] quantas funções de [tex3]A[/tex3] para [tex3]B[/tex3] são crescentes, onde [tex3]n[/tex3] é um número inteiro maior que zero?

[poti]

Estão faltando dados.

[RonaldoJr]

Que nada leq... É pq eu só coloquei a letra "b"... ?

[poti]

Possivelmente. Posta a questão inteira pra eu dar uma olhada.

[RonaldoJr]

Então tentei fazer o seguinte...
Analisando as valores de [tex3](a;f(a))[/tex3], temos os possiveis:



[tex3](1;1),(1;2),(1;3),(1;4)....(1;n)[/tex3] [tex3]E_{1}[/tex3]
[tex3](2;1),(2;2),(2;3),(2;4)....(2;n)[/tex3] [tex3]E_{2}[/tex3]
[tex3](3;1),(3;2),(3;3),(3;4)....(3;n)[/tex3] [tex3]E_{3}[/tex3]

Pelo fato da função ser crescente, analisando caso a caso E_{1} op:
(1;1)
Para [tex3]E_{2} = (2;1)[/tex3]
Temos [tex3]n-0[/tex3] possiveis valores de [tex3]E_{3}[/tex3]

Para [tex3]E_{2} = (2;2)[/tex3]
Temos [tex3]n-1[/tex3] possiveis valores de [tex3]E_{3}[/tex3]
...
(1;1)
Para [tex3]E_{2} = (2;n)[/tex3]
Temos [tex3]n-(n-1)[/tex3] possiveis valores de [tex3]E_{3}[/tex3]
Total de funções[tex3]E_{1}[/tex3] =(1;1) [tex3]\rightarrow \sum_{k=0}^{n-1}

(n-k)[/tex3]

(1;2)
Para [tex3]E_{2} = (2;2)[/tex3]
Temos n-1 possiveis valores de [tex3]E_{3}[/tex3]

Para [tex3]E_{2} = (2;3)[/tex3]
Temos [tex3]n-2[/tex3] possiveis valores de [tex3]E_{3}[/tex3]
...
Para [tex3]E_{2} = (2;n)[/tex3]
Temos n-(n-1) possiveis valores de [tex3]E_{3}[/tex3]

Total de funções para[tex3]E_{1}[/tex3]=(1;2) [tex3]\rightarrow

\sum_{k=1}^{n-1} (n-k)[/tex3]

Seguindo o raciocionio até:

(1;n)
Total de funções [tex3]\rightarrow \sum_{k=n-1}^{n-1} (n-k)[/tex3]


Logo, o número de funções injetivas de é:

[tex3]\sum_{i=0}^{n-1} \sum_{k=i}^{n-1} (n-k) = \frac{1}{6} n(n^2+3n+2)[/tex3]

Tá o [tex3]\sum_{i=0}^{n-1} \sum_{k=i}^{n-1} (n-k)[/tex3] eu tirei do WOLFRAM...
Ou seja minha dúvida mesmo seria como resolver o somatório...

[tex3]\sum_{i=0}^{n-1} \sum_{k=i}^{n-1} (n-k)[/tex3] = ????

De qualquer forma a questão é boa.. Tá valendo

[poti]

Eu saquei seu raciocínio, mas você tá complicando as coisas. Pensa assim:

Pras possibilidades, você tem uma PA de razão [tex3]q = n - x + 1[/tex3]. Vamos botar na fórmula da soma:

[tex3]S_{n} = \frac{(n - x + 1)(a_{n} + a_{1})}{2} = \frac{(n - x + 1)(n - x + 1 + 1)}{2} = \frac{(n - x + 1)(n - x + 2)}{2}[/tex3]

Você agora tem que fazer o somatório disso varrendo [tex3]x=1 \to n[/tex3], pois conforme você aumenta [tex3]x[/tex3] você diminui as possibilidades. Ele quer exatamente essa soma.

[tex3]\sum_{x=1}^n \frac{(n - x + 1)(n - x + 2)}{2}[/tex3]

[tex3]\sum_{x=1}^n \frac{n^2 - nx + 2n - nx + x^2 - 2x + n - x + 2}{2}[/tex3]

[tex3]\sum_{x=1}^n \frac{n^2 - nx + 2n - nx + x^2 - 2x + n - x + 2}{2}[/tex3]

[tex3]\sum_{x=1}^n \frac{n^2 - 2nx + 3n - 3x + x^2 + 2}{2}[/tex3]

Usando a propriedade dos somatórios, desmembramos em:

[tex3]\sum_{x=1}^n \frac{n^2 - 2nx + 3n}{2} + \sum_{x=1}^n \frac{- 3x + x^2 + 2}{2}[/tex3]

[tex3]\sum_{x=1}^n \frac{n^2 - 2nx + 3n}{2} + \sum_{x=1}^n \frac{- 3x + 2}{2} + \sum_{x=1}^n \frac{x^2}{2}[/tex3]

[tex3]\frac{1}{2} \sum_{x=1}^n (n^2 - 2nx + 3n) + \frac{1}{2} \sum_{x=1}^n (- 3x + 2) + \frac{1}{2} \sum_{x=1}^n x^2[/tex3]
[tex3]\ \ \ \ \ \ \ \ \ \ \ \ \ \ (I) \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (II) \ \ \ \ \ \ \ \ \ \ \ (III)[/tex3]

Para (I): Separo a parcela com [tex3]x[/tex3] para o cálculo e a outra continua igual.
Para (II): Separo todas as constantes e chego na soma de uma PA de razão 1.
Para (III): Fórmula manjada da soma dos quadrados.

[tex3]n^2 + \frac{n - 3n^2}{4} + \frac{n(n+1)(2n+1)}{12}[/tex3]

[tex3]\frac{12n^2}{12} + \frac{3n - 9n^2}{12} + \frac{n(n+1)(2n+1)}{12}[/tex3]

Realizando as contas, chegamos em:

[tex3]\boxed{\frac{n(n+1)(n+2)}{6}}[/tex3]

Obs: No fim eu compliquei mais, hahaha. Vê o gabarito aí, eu estou sem o PDF com as provas do IME.

[RonaldoJr]

uaahu a soma é tranquilinha nem tinha notado que a primeira é uma PA... rsrs
[tex3]\sum_{i=0}^{n-1} \sum_{k=i}^{n-1} (n-k) = \sum_{i=0}^{n-1} \sum_{k=1}^{n-i} (k)[/tex3]
= [tex3]\sum_{i=0}^{n-1} \frac {(1+n-i)(n-i)}{2} = \frac{(n^2+n)}{2} \sum_{i=0}^{n-1} 1 - \frac{(2n+1)}{2} \sum_{i=0}^{n-1} i + \frac{1}{2} \sum_{i=0}^{n-1} i^2 = \frac{1}{6} n(n^2+3n+2)[/tex3]
Vlw poti!
Abraço