Re: [obm-l] Combinatoria - Sequencias Cheias

[kleinad@xxxxxxxxxx]

>Seja n um natural dado.
>
>Dizemos que uma sequencia de n naturais (nao necessariamente distintos) e
>CHEIA se ela satisfaz essas propriedades:
>
>para cada k>1, se k aparece entao k-1 tambem aparece;
>a primeira apari�ao de k-1 ocorre antes da ultima apari�ao de k, para k>1.
>
>Calcule quantas cheias existem, em fun�ao de n.

S�o 2^(n-1) cheias.

De fato, repare que o 1 dever� ser o �ltimo elemento de toda seq��ncia.
Ainda, n�meros seguidos na seq��ncia ou s�o iguais ou ent�o o primeiro �
sucessor do segundo, logo o maior n�mero em cada seq��ncia s� poder� ser
mesmo o n. Ilustro o caso n=4:

1, 1, 1, 1
2, 1, 1, 1
2, 2, 1, 1
2, 2, 2, 1
3, 2, 1, 1
3, 2, 2, 1
3, 3, 2, 1
4, 3, 2, 1

S�o 2^3 cheias, e vale a afirma��o. Suponha que valha para n = x --> S_x = 2^
(x-1). Repare que quando n = x+1, as cheias podem ser constru�das a partir
das cheias anteriores colocando-se � sua frente, como termo inicial, um
termo igual ou sucessor do antigo termo. Quero dizer: se 1,1 � uma seq��ncia
de n=2, ent�o 1, 1, 1 e 2, 1, 1 ser�o seq��ncias quando n = 3. Repare que
este m�todo esgotar� todas as seq��ncias poss�veis sem repeti��es, e, para
cada uma das seq��ncias de n = x, produziremos duas seq��ncias em n = x + 1,
logo se S_x = 2^(x-1) ent�o S_(x+1) = 2*S_x = 2^x, e acabamos.

[]s,
Daniel

=========================================================================
Instru��es para entrar na lista, sair da lista e usar a lista em
http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html
=========================================================================