Olá Pedro e demaiscolegas desta lista ... OBM-L,
Se eu entendesse a sua notação, opinaria. Acredito que seja Latex, mas eu não
tenho aqui o plugin que permite a visualização.
PROBLEMA 1
Vou supor que "r" e "s" são inteiros não-negativos e que r + s =< n. Seja A
o conjunto original com n elementos
1) r+s = n e r # s
Neste caso é óbvio que a resposta será Binom(n,r) = Binom(n,n-r) = Binom(n,s)
pois ao escolher um conjunto, digamos, de r elementos, o que "sobra" no
conjunto A terá n-r=s elementos e será o outro conjunto da partição.
Se r = s, divida o resultado anterior por 2
2) r+s < n e r # s
Neste caso, seja t = n - (r+s). Podemos formar um conjunto de t elementos de
Binom(n,t) maneiras. Fixada uma destas maneira, recaímos no caso anterior :
poderemosformar Binom(n-(r+s),r) partições. Pelo principio multiplicativo segue
que a resposta sera : Binom(n,t)*Binom(n-t ,r).
Se r=s, divida o resultado anterior por 2
Note que a resposta 2) engloba a 1), pois se r+s=n então t=n-(r+s)=0 e
Binom(n,t)=Binom(n,0)=1
PROBLEMA 2
Vamos escolher um dentre os n elementos e chama-lo de INTERSECÇÃO. Retirando a
INTERSECÇÃO, sobram n-1 elementos. Sejam r' = r-1 e s' = s-1. É facil ver
que n-1, r' e s' recai no problema anterior, ja resolvido. Então a resposta
aqui é : N*( resposta anterior com a devida adaptação )
Um problema de combinatória que eu acho interessante pode ser enunciado assim :
Seja A um matriz quadrada de ordem N tal que A(i,j) = j + (i -1)*N, onde j e i
variam em K={1,2,...,N } e j representa a coluna e i representa a linha.Quantas
matrizes quadradas B de ordem N podem ser formadas tais que :
1) B não tem elementos repetidos2) Todo elemento de B pertence a {1,2,3,...,
N^2}3) B(i,j) é diferente de A(i,j) para todo par (i,j) pertencente a K^2 (
K^2 é o produto cartesiano de K por si mesmo )
Um abraço a todosPSR,51005111338
Date: Thu, 19 May 2011 18:29:53 +0430
Subject: [obm-l] Número de partições de um conjunto
From: pedromatematic...@gmail.com
To: obm-l@mat.puc-rio.br
No primeiro problema cheguei a algo do tipo 1/2\cdot [ C_{n}^{1} \cdot
(2^{n-1}-1) + C_{n}^{2} \cdot (2^{n-2}-1) + C_{n}^{3} \cdot (2^{n-3}-1)
+...+C_{n}^{n-1} ]
queria saber se alguém sabe opinaar se estou no caminho correto.
Abraços.
1. Seja X um conjunto com "n" elementos. Calcule o número de escolhas possíveis
de dois subconjuntos disjuntos de "r" e "s" elementos, respectivamente. [E se r
= s?]
2. O mesmo exercício anterior mas em que os dois subconjuntos possam
intersectar-se
num único elemento.
--
Pedro Jerônimo S. de O.
Júnior
Professor
de Matemática
Geo João Pessoa
– PB
