Fórum de Matemática
DÚVIDAS? Nós respondemos!

Bom dia,

Este é meu primeiro post, acredito que eu esteja na seção correta. Minha dúvida é a seguinte:

Dado que eu tenho um conjunto de números inteiros N = {1, 2, 3, ..., n}, eu sei que existem 2ⁿ-1 subconjuntos possíveis, dado pelas combinações entre cada um dos seus elementos. Eu gostaria então de saber a quantos desses subconjuntos, cada um dos meus elementos pertence, como exemplo, a quantos destes subconjuntos meu número 2 pertenceria? Preciso saber disso para terminar de implementar computacionalmente, pois meu conjunto N tem 100 elementos, o que me leva a 1.267.650.600.228.230.000.000.000.000.000 de subconjuntos...

Espero que tenha conseguido ser totalmente claro.

A função que eu gero os subconjuntos (S) e seus complementos (S_) em C++ é:



Muito obrigado,

Allexandre.

Bom dia,

Pode pensar do seguinte modo, os conjuntos a que certo elemento pertence são formados pela união do conjunto formado apenas por esse elemento com qualquer subconjunto formado pelos restantes. O número de subconjuntos formados com os restantes (n-1) inteiros pode ser obtido com a mesma fórmula que referiu. Assim, tomando o seu exemplo com o número 2, começamos por determinar o número de subconjuntos de {1,3,4, ..., n}, que será de \(2^{n-1}\) (incluindo o conjunto vazio). Este é exactamente o número de subconjuntos que inclui o inteiro 2. No caso de n=100 terá 2^99= 633.825.300.114.114.700.748.351.602.688 conjuntos nessas coindições.

Obrigado Sobolev,

Acabei percebendo isso, mas revisando meu problema, acabei descobrindo que ele tem uma grande maneira de ser simplificado. \(\forall i \in N = \{1,...,100\}, \exists N_i \subseteq N.\). Cada um destes subconjuntos \(N_i, \forall i \in N\), chamado de vizinhança de i, contém o inteiro i (referente a um ponto no plano cartesiano) e os índices dos 9 outros pontos mais próximos a ele. Assim, eu só me interesso pelos subconjuntos de \(N_i, \forall i \in N\) que também contém i. Meu real problema agora reside em como gerar somente os subconjuntos de \(N_i, \forall i \in N\) que contenham i.

Vocês tem alguma ideia de como fazer isso?

Muito obrigado,

Allexandre.

Um ponto que esqueci de falar, que a cardinalidade de \(N_i, \forall i \in N\) é de 10 elementos, assim, a cardinalidade dos seus subconjuntos é menor ou igual a 10.

A escolha dos conjuntos \(N_i\) não parece a mais evidente, já que esses conjuntos não são simétricos relativamente ao inteiro i. É preciso pois especificar um pouco melhor como é obtida. Por exemplo, considera que

\(N_{10} = \{6,7,8,9,10,11,12,13,14,15\}\)

ou

\(N_{10} = \{5,6,7,8,9,10,11,12,13,14\}\)?