Artigos

7.4: Problemas Gerais de Combinatória - Matemática


Como costuma acontecer, praticar um tipo de problema por vez é útil para dominar as técnicas necessárias para resolver esse tipo de problema. Nesta seção, os tipos de problemas das três seções anteriores são combinados.

EXERCÍCIOS 4.4
SET I
1) Quantas sequências de seis letras minúsculas do alfabeto inglês contêm
( quad ) a) a letra (a? )
( quad ) b) as letras (a ) e (b ) em posições consecutivas com (a ) precedendo (b ), com todas as letras distintas?
( quad ) c) as letras (a ) e (b ), onde (a ) está em algum lugar à esquerda de (b ) na string, com todas as letras distintas?
2) Sete mulheres e nove homens fazem parte do corpo docente do departamento de matemática de uma escola.
( quad ) a) Quantas maneiras existem para selecionar um comitê de cinco membros do departamento se pelo menos uma mulher deve estar no comitê?
( quad ) b) Quantas maneiras existem para selecionar uma comissão de cinco membros do departamento se pelo menos uma mulher e pelo menos um homem devem estar na comissão?
3) Suponha que um departamento contenha 10 homens e 15 mulheres. Quantas maneiras existem para formar um comitê com 6 membros se ele deve ter o mesmo número de homens e mulheres?
4) O alfabeto inglês contém 21 consoantes e 5 vogais. Quantas sequências de 6 letras minúsculas do alfabeto inglês contêm:
( quad ) a) exatamente uma vogal?
( quad ) b) exatamente 2 vogais?
( quad ) c) pelo menos 1 vogal?
( quad ) d) pelo menos 2 vogais?
5) Quantas maneiras existem para selecionar 12 países nas Nações Unidas para servir em um conselho se 3 são selecionados de um bloco de 45,4 são selecionados de um bloco de (57, ) e os outros são selecionados de restantes 69 países?
6) Suponha que um departamento contenha 10 homens e 15 mulheres. Quantas maneiras existem para formar um comitê com 6 membros se ele deve ter mais mulheres do que homens?
7) Quantas placas de veículos compostas por três letras seguidas de três dígitos não contêm nenhuma letra ou dois dígitos?
8) No torneio de tênis feminino de Wimbledon, duas finalistas, A e B, estão competindo pelo título, que será concedido ao primeiro jogador a vencer dois sets. De quantas maneiras diferentes a partida pode ser concluída?
9) No torneio de tênis masculino em Wimbledon, dois finalistas, (A ) e (B ), estão competindo pelo título, que será concedido ao primeiro jogador a vencer três sets. De quantas maneiras diferentes a partida pode ser concluída?
10) De quantas maneiras diferentes um painel de 12 jurados e 2 jurados suplentes pode ser escolhido de um grupo de 30 jurados em potencial?

CONJUNTO II
11) Uma turma tem 20 alunos, sendo 12 do sexo feminino e 8 do masculino. De quantas maneiras um comitê de cinco alunos pode ser escolhido na classe se:
( quad ) a) Nenhuma restrição é colocada na escolha dos alunos
( quad ) b) Nenhum homem está incluído no comitê
( quad ) c) O comitê deve ter três membros mulheres e 2 membros homens
12) Um comitê de dança da escola deve ser escolhido de um grupo de alunos consistindo de seis calouros, oito alunos do segundo ano, doze do terceiro ano e dez do último ano. Se o comitê consistir em dois calouros, três alunos do segundo ano, quatro do terceiro ano e cinco do último ano, de quantas maneiras isso pode ser feito?
13) Uma companhia de teatro é composta por 22 atores - 10 homens e 12 mulheres. Na próxima peça, o diretor precisa escalar um protagonista, protagonista, protagonista, protagonista, protagonista feminina e oito figurantes (três homens e cinco mulheres). De quantas maneiras essa peça pode ser lançada?
14) Um treinador de hóquei tem 20 jogadores, dos quais doze jogam no ataque, seis na defesa e dois são goleiros. De quantas maneiras o técnico pode escolher uma escalação composta por três atacantes, dois jogadores de defesa e um goleiro?
15) De quantas maneiras dez alunos podem ser dispostos em uma fila para uma foto de classe se John e Jane quiserem ficar um ao lado do outro e Ed e Sally também quiserem ficar um ao lado do outro?
16) De quantas maneiras os alunos do problema anterior podem ser arranjados se Ed e Sally querem ficar um ao lado do outro, mas John e Jane se recusam a ficar um ao lado do outro?
17) De quantas maneiras quatro homens e quatro mulheres podem se sentar em uma fileira de oito assentos se:
( quad ) a) O primeiro assento é ocupado por um homem
( quad ) b) O primeiro e o último lugares são ocupados por mulheres

CONJUNTO III
18) O número do seguro social de uma pessoa é uma sequência de nove dígitos que não são necessariamente distintos. Quantos números de previdência social são possíveis?
19) Um nome de variável na linguagem de programação BASIC é uma letra do alfabeto ou uma letra seguida por um dígito. Quantos nomes de variáveis ​​distintos existem na linguagem BASIC?
20) a) Quantos números pares existem entre 0 e 100?
b) Quantos números pares com dígitos distintos existem entre 0 e
(100 ?)
21) Existem seis caracteres - três letras do alfabeto inglês seguidas por três dígitos - que aparecem no painel traseiro de uma determinada marca de impressora como um número de identificação. Encontre o número de números de identificação possíveis se
( quad ) a) caracteres podem ser repetidos
( quad ) b) dígitos não podem se repetir
( quad ) c) as letras não podem se repetir
( quad ) d) caracteres não podem se repetir
22) Uma sequência de caracteres é chamada de palíndromo se for a mesma para a frente e para trás. Por exemplo ( mathrm {K} 98 mathrm {EE} 89 mathrm {K} ) é um palíndromo de oito caracteres e ( mathrm {K} 98 mathrm {E} 89 mathrm {K} ) é um palíndromo de sete caracteres. UM HOMEM, UM PLANO, UM CANAL, O PANAMÁ também é um palíndromo, assim como FOI UM RATO QUE VI, TACO CAT, TANGY GNAT, E NUNCA EXTRA OU MESMO. Encontre o número de palíndromos de nove caracteres que podem ser formados usando as letras do alfabeto de forma que nenhuma letra apareça mais do que duas vezes em cada um.
23) Encontre o número de maneiras de formar uma sequência de quatro letras usando as letras (A ),
B, (C, D ) e (E ) se:
( quad ) a) repetições são permitidas
( quad ) b) repetições não são permitidas
( quad ) c) a sequência contém a letra (A ) mas as repetições não são permitidas
( quad ) d) a sequência contém a letra (A ) e repetições são permitidas
24) Há 10 membros A, B, C, D, E, F, G, H, I e J em um comitê de arrecadação de fundos. A primeira tarefa do comitê é escolher um presidente, um secretário e um tesoureiro deste grupo. Nenhum indivíduo pode ocupar mais de um cargo. De quantas maneiras essas três posições podem ser preenchidas se:
( quad ) a) ninguém tem qualquer objeção para ocupar qualquer um desses cargos
( quad ) b) Precisa ser o presidente
( quad ) c) ( quad ) B não quer ser o presidente
( quad ) d) ( quad ) A não está disposto a servir como presidente ou secretário
( quad ) e) I ou J deve ser o tesoureiro
( quad ) f) ( quad ) E ou (F ) ou (G ) deve deter um dos três cargos
25) Encontre o número de maneiras de escolher cada um dos seguintes de um baralho de cartas padrão.
( quad ) a) um rei e uma rainha
( quad ) b) um rei ou uma rainha
( quad ) c) um rei e um cartão vermelho
( quad ) d) um rei ou um cartão vermelho
26) Existem três pontes ligando duas cidades A e B. Entre as cidades B e
C existem quatro pontes. Um vendedor precisa viajar de A para C via B. Encontre:
( quad ) a) o número de escolhas possíveis de pontes de A a (C )
( quad ) b) o número de escolhas para uma viagem de ida e volta de A para C e de volta para A
( quad ) c) o número de opções para uma viagem de ida e volta se nenhuma ponte puder ser cruzada duas vezes
27) Uma sequência de dígitos em que cada dígito é 0 ou 1 é chamada de número binário. Números binários de oito dígitos são freqüentemente chamados de "bytes".
( quad ) a) Quantos bytes são possíveis?
( quad ) b) Quantos bytes começam com 10 e terminam com (01? )
( quad ) c) Quantos bytes começam com 10, mas não terminam com (01? )
( quad ) d) Quantos bytes começam com 10 ou terminam com (01? )
28) Um grupo de 12 deve sentar-se em uma fileira de cadeiras. De quantas maneiras isso pode ser feito se:
( quad ) a) duas pessoas, (A ) e (B ) devem estar sentadas uma ao lado da outra?
( quad ) b) duas pessoas (A ) e (B ) não devem estar sentadas uma ao lado da outra?
29) Uma variável no idioma FORTRAN é uma sequência que possui no máximo seis caracteres, sendo o primeiro caractere uma letra do alfabeto e os caracteres restantes (se houver) sendo letras ou dígitos. Quantos nomes de variáveis ​​distintos são possíveis?
30) Quatro peruas, cinco sedans e seis vans devem ser estacionados em uma fila de
15 espaços. Encontre o maior número de maneiras de estacionar os veículos se:
( quad ) a) as peruas ficam estacionadas no início, depois os sedans, depois as vans
( quad ) b) veículos do mesmo tipo devem ser estacionados juntos


Seminário de Combinatória MIT-Harvard-MSR

A taxa de convergência de um passeio aleatório no gráfico de Cayley do grupo alternado A_n em relação a uma classe de conjugação C com suporte sup (C) le (1- delta) n é Theta () .

Esta é uma generalização de longo alcance de um resultado famoso de Diaconis e Shahshahani. Em particular, ele resolve um problema aberto da Diaconis.

O resultado é obtido por novos limites superiores em caracteres dos grupos simétricos e estimativas da probabilidade de um quadro padrão aleatório para satisfazer certas condições.

As estimativas de caracteres implicam em propriedades de expansão de certos gráficos de Cayley dos grupos simétricos e resulta na decomposição da representação de conjugação desses grupos.

Sexta-feira, 7 de outubro, 16h15 MIT, sala 2-338

Algoritmos de hipergrafo on-line, satisfação única de cláusulas de chifre e programação lógica

Um hipergrafo H, onde um vértice de cada hiperragia e é designado por cabeça e os vértices restantes de e formam a cauda, ​​modela um conjunto de cláusulas de Horn (puras). Apresentamos um algoritmo linear on-line para encontrar ciclos em tal hipergrafo quando as arestas são adicionadas on-line, que empregamos para obter um algoritmo (tempo linear) ótimo para determinar se um conjunto de cláusulas de Horn (gerais) é exclusivamente satisfatório. Também apresentamos um algoritmo on-line eficiente para manter a distância de um vértice r em particular a todos os outros vértices do hipergrafo quando as hiperbias são deletadas on-line. Discutimos várias aplicações naturais do último algoritmo, incluindo uma aplicação para semântica bem fundamentada em programação lógica.

Quarta-feira, 2 de novembro, 16h15 MIT, sala 2-338

Números de rosto de complexos cujo anel Stanley-Reisner possui profundidade limitada

Será dada uma caracterização do número possível de faces de complexos simpliciais cujo anel de Stanley-Reisner possui profundidade k ou maior. Para k = 0 (sem condição), isso dá o teorema de Kruskal-Katona e para profundidade máxima (o caso de Cohen-Macaulay) é especializado no teorema de Stanley. Os casos intermediários incluem uma caracterização de vetores f de complexos conectados. Em uma versão mais geral, o teorema geral também envolve os números de Betti do complexo.

Nenhum conhecimento prévio da área será assumido - os resultados antigos serão revisados.

Quarta-feira, 9 de novembro, 16h15 MIT, sala 2-338

Uma visão geral dos polinômios de Schubert

Os polinômios de Schubert são uma família fascinante de polinômios relacionados à geometria de variedades de sinalizadores. Apresentamos uma teoria unificada de polinômios de Schubert para os grupos clássicos no contexto de combinatória e geometria algébrica.

Historicamente, os polinômios de Schubert (para o tipo A) foram definidos por Lascoux e Schutzenberger para simplificar cálculos de multiplicidades de interseção de variedades de Schubert e para fornecer representantes explícitos das classes de Schubert definidas por Bernstein, Gelfand e Gelfand. Recentemente, os polinômios de Schubert foram estudados por combinatorialistas algébricos por causa de suas conexões com a teoria das funções simétricas, teoria da representação e palavras reduzidas.

Nesta palestra, apresentaremos alguns dos antecedentes da geometria algébrica em variedades de sinalizadores e seus anéis de cohomologia. A partir da geometria existe uma construção natural que define os polinômios de Schubert. Uma vez que temos uma definição geral desses polinômios, podemos dar fórmulas para polinômios de Schubert para cada um dos sistemas de raiz do tipo A, B, C e D. Essas fórmulas são definidas em termos de funções Q de Schur, a correspondência de Haiman de B_n e D_n palavras reduzidas e funções simétricas de Stanley. Concluímos com algumas conjecturas para expandir produtos de polinômios de Schubert em casos especiais, esses casos especiais correspondem a análogos das regras de Pieri para funções de Schur.

Discrete Math Dinner, 9 de novembro, 18h, Cambridge Brewing Company

O custo para estudantes de graduação e pós-graduação será mantido em $ $ 7 (bebidas incluídas). O custo para o restante de nós deve ser inferior a $ $ 20 por pessoa.

Quarta-feira, 16 de novembro, 16h15 MIT, sala 2-338

A função simétrica do ciclo do caminho de um dígrafo

R. Stanley generalizou o polinômio cromático de um gráfico para uma função simétrica. Independentemente, F. Chung e R. Graham definiram um polinômio dígrafo chamado polinômio de cobertura, que tem conexões estreitas com polinômios cromáticos e também polinômios de torre. Neste artigo, imitamos a construção de Stanley para definir uma generalização de função simétrica do polinômio de cobertura. Obtemos generalizações e análogos de vários resultados de Stanley, Chung e Graham e outros. Além disso, provamos um teorema de reciprocidade combinatória que inesperadamente une uma série de resultados espalhados na literatura que anteriormente pareciam não relacionados, e definimos uma nova base de função simétrica que parece ser uma contraparte natural da base polinomial $_$.

Quarta-feira, 30 de novembro, 16h15 MIT, sala 2-338

Um análogo da transformada de Fourier para funções simétricas

Motivados por questões de física matemática (notadamente, o trabalho de Kontsevich), Kapranov e eu estudamos o seguinte problema. Dados os módulos S_n a (n), associe a um grafo G o espaço vetorial a (G) dado pela tensoragem de uma cópia de a (n) para cada vértice de G de valência n, e então tomando co-variantes sob o grupo de automorfismo de G. Agora some a (G) sobre todos os gráficos com a característica de Euler dada. Derivamos uma fórmula para a dimensão deste espaço vetorial, usando a teoria das funções simétricas. Esta fórmula pode ser aplicada para calcular certas combinações das características de Euler de espaços de módulos de superfícies de Riemann.

Sexta-feira, 2 de dezembro, 16h15 MIT, sala 2-338

Constantes de estrutura para polinômios de Schubert

Os polinômios de Schubert se originaram do estudo de variedades de bandeiras em geometria algébrica. Recentemente, muitas de suas propriedades foram elucidadas usando combinatória e álgebra. Um problema aberto básico é fornecer uma regra para a multiplicação de dois polinômios de Schubert, ou seja, uma regra do tipo 'Littlewood-Richardson' para suas constantes de estrutura.

Nesta palestra, estabeleceremos uma fórmula análoga à regra de Pieri para polinômios de Schubert. Isso já havia sido conjecturado por Bergeron e Billey. Embora nossos métodos venham da geometria algébrica, a prova que apresentamos envolve apenas álgebra linear elementar (embora complicada!).

Quarta-feira, 7 de dezembro, 16h15 MIT, sala 2-338

Jay Goldman (Minnesota e M.I.T.)

Nós, emaranhados e gráficos assinados

Os gráficos assinados de emaranhados ou de links de túnel são redes assinadas de dois terminais. O último contém as redes elétricas passivas de dois terminais. A condutância entre os dois terminais de tal rede assinada é definida, generalizando a noção elétrica clássica. A condutância é um invariante topológico do emaranhado ou link de túnel correspondente. Métodos de série, paralelo e triângulo em estrela generalizados a partir do contexto elétrico geram a primeira interpretação natural dos movimentos gráficos de Reidemeister. A condutância é sensível à detecção de imagens de espelho e vinculação. A fração contínua de Conway de um emaranhado racional é uma condutância e isso leva a uma prova elementar da classificação de Conway dos emaranhados racionais. A condutância está relacionada às avaliações dos polinômios de Jones e Conway.

Sexta-feira, 9 de dezembro, 16h15 MIT, sala 2-338

Sobre as regras de Littlewood-Richardson e Murnaghan-Nakayama

A Regra de Murnaghan-Nakayama é uma regra combinatória explícita para calcular um valor de um caráter irredutível do grupo simétrico S_n em uma determinada classe de conjugação. A regra de Littlewood-Richardson semelhante descreve os coeficientes de uma expansão de uma representação enviesada de S_n em irredutíveis.

Usamos funções de Schur não comutativas para generalizar essas regras para uma grande classe de representações de S_n, incluindo aquelas relacionadas a polinômios de Schubert / Grothendieck estáveis. Versões alternativas das regras clássicas L-R e M-N também serão fornecidas.

A maioria dos novos resultados é conjunta com Curtis Greene.

Quarta-feira, 14 de dezembro, 16h15 MIT, sala 2-338

Em um tabuleiro de xadrez de 2m por 2n, o número máximo de reis não-atacantes que podem ser colocados é mn. A questão aqui é determinar f (m, n), que é o número dessas colocações. Esta questão foi levantada por D. E. Knuth no caso m = n.

Usando o método da matriz de transferência, primeiro expressamos a função geradora de f (m, n) como a soma das entradas de x (Ix Lambda) ^ <-1>, onde a matriz de transferência Lambda é (m + 1) 2 ^ m por (m + 1) 2 ^ m $. Em seguida, introduzimos uma ordem parcial nas configurações de modo que a matriz de transferência Lambda se torne triangular em blocos superiores, e discutimos os espectros dos blocos diagonais. O resultado é que para cada m fixo, temos

f (m, n) = (c_mn + d_m) (m + 1) ^ n + O ( theta_m ^ n) (conforme n vai para o infinito),

onde | theta_m | & lt m + 1. Finalmente, discutimos também alguns trabalhos relacionados ao problema por outros pesquisadores e algumas questões em aberto.

Sexta-feira, 16 de dezembro, 16h15 MIT, sala 2-338

William Jockusch (Michigan)

Algumas misteriosas fatorações de matrizes

Apresentarei algumas fatorações de matrizes misteriosas que surgem no estudo das álgebras centralizadoras de Brauer e que gostaria de entender melhor. Espero que alguém na plateia tenha visto algo parecido antes ou tenha algumas ideias sobre o que está acontecendo.


Reiterando o que foi dito anteriormente em um comentário:

Sua resposta está quase correta, mas você cometeu o erro de escolher as posições duas vezes em vez de apenas uma. Ao escolher as quatro posições a serem ocupadas por letras e, em seguida, escolher novamente quais três posições deveriam ser ocupadas por dígitos e tendo escolhido essas posições entre as sete originais, você terá corrido o risco de escolher a mesma posição várias vezes designando-a para ser usado simultaneamente por carta e dígito.

Em vez disso, as posições dos dígitos deveriam ter sido selecionadas das demais não utilizado posições dando um total de $ binom <3> <3> = 1 $ maneira pela qual esta etapa poderia ser realizada, sendo apenas $ 1 $ a forma como ela pode ser deixada de fora do produto final. Isso deixa a resposta final como sendo:

Compare isso com um problema um pouco maior, onde você tem $ 26 $ letras para escolher, $ 10 $ dígitos e $ 15 $ símbolos especiais (por exemplo,! @ # $% ^ E assim por diante.) E queremos fazer uma senha de dez caracteres consistindo em $ 6 $ letras, $ 3 $ dígitos e $ 1 $ símbolo especial com repetição permitida.

Primeiro, escolhemos as posições usadas pelas letras e, em seguida, dessas posições restantes escolha as posições usadas pelos dígitos, deixando a posição final restante ser ocupada pelo símbolo e, em seguida, escolha quais letras, dígitos e símbolos eles eram para uma contagem total de:


Conteúdo

Dado um certo número n de pessoas, é possível atribuí-los a conjuntos de modo que cada pessoa esteja em pelo menos um conjunto, cada par de pessoas esteja em exatamente um conjunto juntos, cada dois conjuntos tenham exatamente uma pessoa em comum e nenhum conjunto contenha todos, todos mas uma pessoa, ou exatamente uma pessoa? A resposta depende de n.

Isso só tem solução se n tem a forma q 2 + q + 1. É menos simples provar que existe uma solução se q é uma potência primária. É conjecturado que estes são os soluções. Foi ainda demonstrado que se existe uma solução para q congruente com 1 ou 2 mod 4, então q é a soma de dois números quadrados. Este último resultado, o teorema de Bruck-Ryser, é provado por uma combinação de métodos construtivos baseados em campos finitos e uma aplicação de formas quadráticas.

Quando tal estrutura existe, ela é chamada de plano projetivo finito, mostrando assim como a geometria finita e a combinatória se cruzam. Quando q = 2, o plano projetivo é denominado plano de Fano.

Os designs combinatórios datam da antiguidade, sendo o quadrado Lo Shu um dos primeiros quadrados mágicos. Uma das primeiras aplicações datáveis ​​de design combinatório é encontrada na Índia no livro Brhat Samhita de Varahamihira, escrita por volta de 587 DC, com o objetivo de fazer perfumes a partir de 4 substâncias selecionadas a partir de 16 substâncias diferentes usando um quadrado mágico. [2]

Os projetos combinatórios se desenvolveram junto com o crescimento geral da combinatória a partir do século 18, por exemplo, com os quadrados latinos no século 18 e os sistemas de Steiner no século 19. Os projetos também foram populares na matemática recreativa, como o problema das colegiais de Kirkman (1850), e em problemas práticos, como a programação de torneios round-robin (solução publicada na década de 1880). No século 20, os projetos foram aplicados ao projeto de experimentos, principalmente quadrados latinos, geometria finita e esquemas de associação, gerando o campo da estatística algébrica.

O núcleo clássico do assunto de projetos combinatórios é construído em torno de projetos de blocos incompletos balanceados (BIBDs), matrizes de Hadamard e projetos de Hadamard, BIBDs simétricos, quadrados latinos, BIBDs resolvíveis, conjuntos de diferenças e projetos de pares equilibrados (PBDs). [3] Outros projetos combinatórios estão relacionados ou foram desenvolvidos a partir do estudo desses projetos fundamentais.

  • UMA projeto de bloco incompleto balanceado ou BIBD (geralmente chamado de design de bloco) é uma coleção B do b subconjuntos (chamados blocos) de um conjunto finito X do v elementos, de modo que qualquer elemento de X está contido no mesmo número r de blocos, cada bloco tem o mesmo número k de elementos, e cada par de elementos distintos aparecem juntos no mesmo número λ de blocos. BIBDs também são conhecidos como 2 designs e são frequentemente denotados como 2- (v,k, λ) designs. Por exemplo, quando λ = 1 e b = v, temos um plano projetivo: X é o conjunto de pontos do plano e os blocos são as linhas.
  • UMA projeto de bloco incompleto simétrico balanceado ou SBIBD é um BIBD no qual v = b (o número de pontos é igual ao número de blocos). Eles são a subclasse mais importante e bem estudada de BIBDs. Planos de projeção, biplanos e designs Hadamard 2 são todos SBIBDs. Eles são de particular interesse, uma vez que são os exemplos extremos da desigualdade de Fisher (bv).
  • UMA BIBD resolvível é um BIBD cujos blocos podem ser particionados em conjuntos (chamados aulas paralelas), cada um dos quais forma uma partição do conjunto de pontos do BIBD. O conjunto de classes paralelas é chamado de resolução do design. Uma solução para o famoso problema das 15 colegiais é a resolução de um BIBD com v = 15, k = 3 e λ = 1. [4]
  • UMA Retângulo latino é um r × nmatriz que possui os números 1, 2, 3,. n como suas entradas (ou qualquer outro conjunto de n símbolos distintos) com nenhum número ocorrendo mais de uma vez em qualquer linha ou coluna onde rn. Um n × n O retângulo latino é chamado de quadrado latino. Se r & lt n, então é possível anexar nr filas para um r × n Retângulo latino para formar um quadrado latino, usando o teorema do casamento de Hall. [5]
  • UMA (v, k, λ) diferença definida é um subconjuntoD de um grupoG de modo que a ordem de G é v, o tamanho de D é k, e cada elemento de não identidade de G pode ser expresso como um produto d1d2 -1 de elementos de D exatamente em formas λ (quando G é escrito com uma operação multiplicativa). [6]
  • Um Matriz de Hadamard de ordem m é um m × m matriz H cujas entradas são ± 1, de modo que HH ⊤ = meum, Onde H ⊤ é a transposição de H e eum é o m × m matriz de identidade. Uma matriz Hadamard pode ser colocada em formulário padronizado (isto é, convertido em uma matriz Hadamard equivalente) em que as entradas da primeira linha e da primeira coluna são todas +1. Se o pedido m & gt 2 então m deve ser um múltiplo de 4.
  • UMA design equilibrado em pares (ou PBD) é um conjunto X junto com uma família de subconjuntos de X (que não precisa ter o mesmo tamanho e pode conter repetições) de modo que cada par de elementos distintos de X está contido em subconjuntos exatamente λ (um inteiro positivo). O conjunto X pode ser um dos subconjuntos, e se todos os subconjuntos forem cópias de X, o PBD é chamado trivial. O tamanho de X é v e o número de subconjuntos na família (contados com multiplicidade) é b.

O Manual de projetos combinatórios (Colbourn & amp Dinitz 2007) tem, entre outros, 65 capítulos, cada um dedicado a um projeto combinatório diferente dos dados acima. Uma lista parcial é fornecida abaixo:


Requisito de redação principal em matemática (Math 300):

Se você é um graduado em matemática e gostaria de completar seus principais requisitos de redação por meio de um trabalho de redação nesta classe, por favor, me avise na primeira semana de aula e nós discutiremos o assunto. Esta tarefa de redação não contará para sua nota nesta aula, mas servirá apenas como seu Requisito Principal de Redação. Se você decidir fazer isso, você deve escrever seu trabalho sobre um tópico da Combinatória aprovado por mim, e você deve manter um cronograma de entrega de rascunhos que é definido no início do semestre para obter os créditos.


Análise Combinatória

O ramo da matemática dedicado à solução de problemas de escolha e organização dos elementos de certos conjuntos (geralmente finitos) de acordo com regras prescritas. Cada uma dessas regras define um método de construção de alguma configuração de elementos de um determinado conjunto, chamada de configuração combinatória. Portanto, pode-se dizer que o objetivo da análise combinatória é o estudo das configurações combinatórias. Este estudo inclui questões sobre a existência de configurações combinatórias, algoritmos e sua construção, otimização de tais algoritmos, bem como a resolução de problemas de enumeração, em particular a determinação do número de configurações de uma dada classe. Os exemplos mais simples de configurações combinatórias são permutações, combinações e arranjos.

Um conjunto $ X $ de $ n $ elementos é chamado de $ n $ - conjunto e $ m $ - subconjunto dele, $ m leq n $, é chamado de combinação de tamanho $ m $. O número de combinações de tamanho $ m $ de $ n $ elementos distintos é igual a

$ (1 + t) ^ = sum _ ^ left ( begin n m end right) t ^ , left ( begin n 0 fim right) = 1, $

geralmente é chamada de fórmula binomial de Newton. Os números $ C (n, m) $ são chamados de coeficientes binomiais. Um subconjunto $ m $ ordenado é chamado de arranjo de tamanho $ m $. O número de arranjos de tamanho $ m $ de $ n $ elementos distintos é igual a

$ A (n, m) = n (n - 1) pontos (n - m + 1). $

Para $ m = n $, um arranjo é uma permutação dos elementos de $ X $, sendo o número de tais permutações $ P (n) = n! $.

O surgimento das noções fundamentais e do desenvolvimento da análise combinatória foi paralelo ao desenvolvimento de outros ramos da matemática, como álgebra, teoria dos números, teoria da probabilidade, todos intimamente ligados à análise combinatória. A fórmula que expressa o número de combinações em termos de coeficientes binomiais e a fórmula binomial de Newton para inteiros positivos $ n $ já era conhecida dos matemáticos do Antigo Oriente. Quadrados mágicos (cf. Quadrados mágicos) de ordem três foram estudados para fins místicos. O nascimento da análise combinatória como um ramo da matemática está associado ao trabalho de B. Pascal e P. (de) Fermat sobre a teoria dos jogos de azar. Esses trabalhos, que formaram os fundamentos da teoria da probabilidade, continham ao mesmo tempo os princípios para determinar o número de combinações de elementos de um conjunto finito e, assim, estabeleceram a conexão tradicional entre a análise combinatória e a teoria da probabilidade.

Uma grande contribuição para o desenvolvimento sistemático de métodos combinatórios foi fornecida por G. Leibniz em sua dissertação Ars Combinatoria (a Arte da Combinatória) na qual, aparentemente, o termo "combinatória" apareceu pela primeira vez. De grande importância para o estabelecimento da análise combinatória foi o artigo Ars Conjectandi (a Arte da Conjectura) de J. Bernoulli, que foi dedicado às noções básicas da teoria da probabilidade, e uma série de noções combinatórias foram necessariamente apresentadas e aplicações ao cálculo de probabilidades foram dados. Pode-se dizer que com o surgimento das obras de Leibniz e Bernoulli, os métodos combinatórios passaram a ser um ramo independente da matemática.

Uma contribuição importante para o desenvolvimento de métodos combinatórios foi fornecida por L. Euler. Em seus artigos sobre a partição e decomposição de inteiros positivos em somas, ele estabeleceu o início de um dos métodos básicos de cálculo de configurações combinatórias, a saber, o método de geração de funções.

Os anos 1950 estão associados a uma expansão do interesse na análise combinatória em conexão com o rápido desenvolvimento da cibernética e da matemática discreta e a ampla aplicação de técnicas de computador. Neste período, um interesse por problemas combinatórios clássicos foi ativado.

Dois fatores mostraram-se influentes na formação da direção das investigações subsequentes. Por um lado, a escolha dos objetos de investigação, por outro, a formação dos objetivos da investigação, dependendo, em última análise, da complexidade dos objetos em estudo. Se a configuração combinatória sob investigação tem um caráter complexo, o objetivo da investigação é elucidar as condições de sua existência e desenvolver algoritmos para sua construção.

Um grande ramo bem desenvolvido da análise combinatória é a teoria de projetos de blocos (cf. Projeto de blocos, e também [2], [3], [10]) os principais problemas deste ramo estão relacionados a questões de classificação, condições de existência e métodos de construção de certas classes de projetos de bloco. Um caso especial de projetos de blocos são os chamados projetos de blocos incompletos balanceados ou configurações $ (b, v, r, k, lambda) $, que são definidas como coleções de $ b $ $ k $ - subconjuntos de alguns $ v $ - conjunto, denominado blocos, com a condição de que cada elemento apareça em blocos $ r $ e cada par de elementos em blocos $ lambda $. Quando $ b = v $ e, portanto, quando $ r = k $, uma configuração $ (b, v, r, k, lambda) $ é chamada de configuração $ (v, k, lambda) $, ou um projeto de bloco incompleto simétrico balanceado. Mesmo para configurações $ (v, k, lambda) $, a questão das condições necessárias e suficientes para sua existência permanece sem solução (1988). Para a existência de configurações $ (v, k, lambda) $ - é necessário que quando $ v $ for par, $ k - lambda $ seja um quadrado perfeito, enquanto quando $ v $ for ímpar, a equação

$ z ^ <2> = (k - lambda) x ^ <2> + (- 1) ^ <(v - 1) / 2> lambda y ^ <2> $

deve ter uma solução integral em $ x, y, z $, não totalmente zero.

Quando $ v = n ^ <2> + n + 1 $, $ k = n + 1 $, $ lambda = 1 $ a $ (v, k, lambda) $ - a configuração representa um plano projetivo de ordem $ n $ e é um caso particular de geometria finita contendo um número finito de pontos e linhas sob condições de incidência prescritas. Correspondendo a cada plano projetivo de ordem $ n $, há um conjunto completo único de $ n - 1 $ quadrados latinos ortogonais em pares de ordem $ n $ (cf. quadrado latino). Para que exista um plano projetivo de ordem $ n $, é necessário que para $ n equiv 1, 2 $ ($ mathop < rm mod> 4 $) existam inteiros $ a, b $ tais que

An affirmative solution to the question of the existence of projective planes of order $ n $ has been obtained only for $ n = p ^ alpha $, where $ p $ is a prime number and $ alpha $ is a positive integer. Even for $ n = 10 $ this question remains open (1988). Related to this circle of questions is a result in connection with the falsification of the Euler conjecture on the non-existence of pairs of orthogonal Latin squares of order $ n = 4k + 2 $, $ k = 1, 2 , . . . $( see Classical combinatorial problems).

Another direction in combinatorial analysis relates to selection theorems. At the foundation of a whole series of results along these lines is the P. Hall theorem on the existence of a system of distinct representatives (a transversal) of a family of subsets $ ( X _ <1>dots X _ ) $ of a set $ X $, that is, a system of elements $ ( x _ <1>dots x _ ) $ such that $ x _ in X _ $ and $ x _ eq x _ $ when $ i eq j $. A transversal exists if and only if for any $ i _ <1>dots i _ $ such that $ 1 leq i _ <1>< dots < i _ leq n $, $ 1 leq k leq n $, the following inequality holds:

$ | X _ > cup dots cup X _ > | geq k, $

where $ | Y | $ is the number of elements in $ Y $. A corollary of Hall's theorem is the theorem on the existence of Latin squares, stating that any Latin rectangle of order $ k imes n $, $ 1 leq k leq n - 1 $, can be extended to a Latin square of order $ n $. Another corollary of Hall's theorem: Any non-negative matrix $ A = | a _ | _ ^ $ such that

can be represented in the form

$ A = alpha _ <1>Pi _ <1>+ dots + alpha _ Pi _ , $

where $ Pi _ <1>dots Pi _ $ are permutation matrices of order $ n $ and $ s leq ( n - 1) ^ <2>+ 1 $. Hall's theorem also implies that the minimum number of rows and columns of a non-negative matrix containing all positive elements is equal to the maximum number of elements that pairwise are not in the same row or in the same column. The extremal property of partially ordered sets, which is analogous to this theorem, is established by the theorem stating that the minimum number of non-intersecting chains is the same as the size of the maximal subset consisting of pairwise-incomparable elements. The following theorem also bears an extremal character: If for an $ n $- set $ X $ one collects all the $ C ( n, r) $ combinations of $ r $ elements and partitions them into $ k $ non-intersecting classes, then, given an integer $ m $, there exists an $ n _ <0>= n _ <0>( m, r, k) $ such that for $ n geq n _ <0>$ there is a subset of $ m $ elements $ Y subset X $ for which all the $ C ( m, r) $ combinations belong to the same class.

The travelling-salesman problem is an extremal problem too it consists in composing the shortest route visiting $ n $ towns and returning to the starting point, where the distances between the towns are known. This problem has applications in the study of transportation networks. Combinatorial problems of an extremal character are considered in the theory of flows in networks and in graph theory.

A significant portion of combinatorial analysis consists of enumeration problems. For their solution one either indicates a method of sorting out combinatorial configurations of a given class, or one determines the number of them, or one does both. Typical results of enumeration problems are: The number of permutations of order $ n $ with $ k $ cycles is equal to $ | S ( n, k) | $, where $ S ( n, k) $ is the Stirling number of the first kind, defined by the equation

$ x ( x - 1) dots ( x - n + 1) = sum _ ^ < n >S ( n, k) x ^ $

the number of partitions of a set of $ n $ elements into $ k $ subsets is equal to the Stirling number of the second kind

$ sigma ( n, k) = < frac<1> > sum _ ^ < k >(- 1) ^ left ( egin k j end ight ) ( k - j) ^ $

and, the number of arrangements of $ m $ distinct objects in $ n $ distinct cells with no cell empty is equal to $ n! sigma ( m, n) $.

A useful device for the solution of enumeration problems is the permanent of a matrix. The permanent of a matrix $ A = | a _ | $( $ i = 1 dots n $ $ j = 1 dots m $, $ n leq m $) the elements of which belong to some ring, is defined by the formula

$ mathop < m per>A = sum _ <( j _ <1>dots j _ ) > a _ <1j _ <1>> dots a _ > , $

where the summation is carried out over all possible arrangements of size $ n $ from $ m $ distinct elements. The number of transversals of some family of subsets of a finite set is equal to the permanent of the corresponding incidence matrix.

A whole class of problems on the determination of the number of permutations with restricted positions reduces to the calculation of permanents. For convenience, these problems are sometimes formulated as problems on the arrangement of mutually non-attacking pieces on an $ n imes n $ chessboard. Connected with the determination of the permanents of certain classes of matrices are variants of the problem of dimers, which arises in the study of the phenomenon of adsorption and consists in the determination of the number of ways of combining the atoms of di-atomic molecules on some surface. Its solution can also be obtained in terms of Pfaffians (cf. Pfaffian), which are certain functions of matrices close to determinants. The problem of the number of Latin rectangles (squares) is also connected with the development of effective methods for calculating permanents of certain $ ( 0, 1) $- matrices.

For the calculation of permanents one applies the formula:

$ mathop < m per>A = sum _ ^ < m >(- 1) ^ left ( egin k m - n end ight ) S _ , $

$ S _ = sum _ <1 leq j _ <1>< dots < j _ leq m > prod _ ^ < n >left ( sum _ ^ < m >a _ - sum _ ^ < k >a _ > ight ) . $

There are a large number of inequalities giving an estimate of the size of the permanent in certain classes of matrices. The determination of the extremal values of the permanent in specific classes of non-negative matrices is of interest. For a $ ( 0, 1) $- matrix $ A $ with given values $ r _ <1>dots r _ $ of the number of ones in the rows one has the estimate

cf. [12]. The famous van der Waerden conjecture, that the minimum permanent of a doubly-stochastic matrix of order $ n $ is equal to $ n!/n ^ $ was proved, independently, by D.I. Falikman (1979) and G.P. Egorichev (1980), cf. [13].

An important role in the solution of enumeration problems is played by the method of generating functions (cf. Generating function). A generating function

$ f ( t) = sum _ ^ infty a _ t ^ $

sets up a correspondence between the sequence $ ( a _ <0>, a _ <1>, . . . ) $ and the elements of some ring, and is regarded as a formal power series. According to this definition, generating functions are effectively used for the solution of enumeration problems in parallel with methods of recurrence relations and finite-difference equations. In obtaining asymptotic formulas for the generating functions, analytic functions of a real or complex variable are usually employed. In the latter case, the Cauchy integral is applied in finding expressions for the coefficients.

There are results in the direction of a possible unification of enumeration methods these are connected with the study of so-called incidence algebras and the use of the Möbius function on a partially ordered set (see for example, [10]). In the solution of enumeration problems, an essential role is played by the formalization of the concept of indistinguishability of objects. The use of the notion of equivalence of objects with respect to a certain group of permutations in combination with the application of the method of generating functions forms the basis of the so-called Pólya theory of enumeration (see [10]), the essence of which is as follows. Consider the set $ Y ^ $ of configurations

$ f: X ightarrow Y, | X | = m, | Y | = n. $

On the set $ X $, a group $ A $ of permutations acts, thus defining an equivalence relation $ sim $ under which $ f sim f _ <1>$, $ f, f _ <1>in Y ^ $, if there exists an $ alpha in A $ such that $ f ( alpha ( x)) = f _ <1>( x) $ for all $ x in X $. To each $ y in Y $ corresponds a characteristic $ [ y] = ( s _ <1>dots s _ ) $, where $ s _ $, $ i = 1 dots k $, are elements of an Abelian group. The characteristic of the configuration $ f $ is given by the formula

If $ a ( s _ <1>dots s _ ) $ is the number of elements $ y in Y $ with a given value of the characteristic and $ b _ ( s _ <1>dots s _ ) $ is the number of inequivalent configurations $ f in Y ^ $,

$ F ( y _ <1>dots y _ ) = sum _ <( s _ <1>dots s _ ) > a ( s _ <1>dots s _ ) y _ <1>^ > dots y _ ^ > , $

$ Phi _ ( y _ <1>dots y _ ) = sum _ <( s _ <1>dots s _ ) > b ( s _ <1>dots s _ ) y _ <1>^ > dots y _ ^ > , $

then Pólya's fundamental theorem states that

$ = Z ( F ( y _ <1>dots y _ ), F ( y _ <1>^ <2>dots y _ ^ <2>) dots F ( y _ <1>^ dots y _ ^ )), $

where $ Z $ is the cyclic index of the group $ A $, defined by the equation

$ = sum _ + 2j _ <2>+ dots + mj _ = n > C ( j _ <1>dots j _ A) t _ <1>^ > dots t _ ^ > , $

and $ C ( j _ <1>dots j _ A) $ is the number of elements of the cyclic class $ < 1 ^ > dots m ^ > > $( cf. Symmetric group) of $ A $. This theorem is based on Burnside's lemma: The number of equivalence classes $ N ( A) $ defined on the set $ X $ by the permutation group $ A $ is given by the formula

where $ j _ <1>( alpha ) $ is the number of unit cycles of $ alpha in A $. Pólya's theory has applications in the solution of enumeration problems in graph theory and in the enumeration of carbon chemical compounds. There is a generalization of Pólya's theory to the case when the equivalence of two configurations is defined by two groups $ G $ and $ H $ acting on $ X $ and $ Y $, respectively (see [4] and [10]). In this form it is applied, for example, in the determination of the number of non-isomorphic abstract automata.

If $ X = < 1 dots m >$, $ Y = < a _ <1>dots a _ > $ and $ sigma : X ightarrow Y $, where $ a _ $ is used as an image $ alpha _ $ times, then the expression

$ [ sigma ] = [ a _ <1>^ > dots a _ ^ > ] , alpha _ <1>+ dots + alpha _ = m, $

is called the first specification of $ sigma $. If the numbers $ alpha _ <1>dots alpha _ $ contain $ eta _ <0>$ zeros, $ eta _ <1>$ ones, etc., then the expression

$ eta _ <1>+ 2 eta _ <2>+ dots + m eta _ = m, $

is called the second specification. Under some specification of the groups $ G $ and $ H $ defining the equivalence of configurations $ sigma : X ightarrow Y $, it is possible to give a method of constructing generating functions for the enumeration of the inequivalent configurations. This method, called the general combinatorial scheme, can be subdivided into four particular cases, according as the groups $ G $ and $ H $ take values in the identity group $ E $ or the symmetric groups $ S _ $ of corresponding orders. These particular cases are the models for the majority of the known combinatorial schemes (see [9], [10]).

1) The commutative non-symmetric case: $ G = S _ $, $ H = E $. This models combination schemes of distributing identical objects into different cells, etc. The generating function for the enumeration of inequivalent configurations $ sigma $ such that

$ alpha _ in Lambda _ subseteq mathbf N _ <0>= < 0, 1 , . . . >, Lambda = ( Lambda _ <1>dots Lambda _ ), $

$ Phi ( t x _ <1>dots x _ Lambda ) = prod _ ^ < n > sum _ in Lambda _ > ( tx _ ) ^ > . $

2) The non-commutative non-symmetric case: $ G = E $, $ H = E $. This models allocation schemes of distributing distinct objects into different cells, etc. The generating function for the enumeration of inequivalent configurations $ sigma $ such that

$ [ sigma ] = [ a _ <1>^ > dots a _ ^ > ] , alpha _ in Lambda _ , Lambda = ( Lambda _ <1>dots Lambda _ ), $

$ widetilde Phi ( t x _ <1>dots x _ Lambda ) = prod _ ^ < n > sum _ in Lambda _ > frac > > ! > x _ ^ > . $

3) The commutative symmetric case: $ G = S _ $, $ H = S _ $. This models schemes of distributing identical objects into identical cells, the enumeration of the partitions of natural numbers, etc. The enumeration of configurations $ sigma $ such that

$ [[ sigma ]] = [ [ 0 ^ <eta _ <0>> dots m ^ <eta _ > ] ] , eta _ in Lambda _ , Lambda = ( Lambda _ <1>, Lambda _ <2>, . . . ), $

is based on the use of generating functions of the form:

$ Psi ( t x _ <1>, . . . Lambda ) = prod _ ^ infty sum _ <eta _ in Lambda _ > ( x _ t ^ ) ^ <eta _ > . $

4) The non-commutative symmetric case: $ G = E $, $ H = S _ $. This models schemes of partitioning finite sets into blocks, distributing distinct objects into identical cells, etc. The enumeration of configurations $ sigma $ such that

$ [[ sigma ]] = [ [ 0 ^ <eta _ <0>> dots m ^ <eta _ > ] ] , eta _ in Lambda _ , Lambda = ( Lambda _ <1>, Lambda _ <2>, . . . ), $

is based on the use of generating functions of the form:

$ widetilde Psi ( t x _ <1>, . . . Lambda ) = prod _ ^ infty sum _ <eta _ in Lambda _ > left ( frac t ^ > ight ) ^ <eta _ > < frac<1> <eta _ ! > > . $

An important place in combinatorial analysis is taken up by asymptotic methods. They are applied both for the simplification of complex finite expressions for large values of the parameters entering into them, as well as for obtaining approximate formulas in roundabout ways when the exact formulas are unknown. It is sometimes convenient to formulate a combinatorial problem of an enumerative character as a problem of finding the characteristics of the distribution of some random process. Such an interpretation makes it possible to apply the well-developed apparatus of probability theory for finding asymptotics or limit theorems. Classical schemes of random allocations of objects in cells are open to a detailed investigation from these points of view so also are random partitions of sets, the cyclic structure of random permutations, as well as various classes of random graphs, including graphs of mappings (see [8], [9], [11]).

The probabilistic approach is applied in the study of the combinatorial properties of symmetric groups and semi-groups. The limiting distribution of the order of a random element of the symmetric group $ S _ $ as $ n ightarrow infty $ has been investigated, as also have the asymptotics of the probability of the generation of random elements of them. For certain classes of random non-negative matrices, the distributions have been studied of the number of zero rows in a matrix and in permanents, and estimates have been given of the probability of the primitiveness of such matrices. For the proof of the existence of combinatorial configurations without constructing them, one sometimes employs a certain specific probabilistic device. The essence of this device consists in the proof of the existence of the configuration (without constructing it) by means of an estimate of the probability of some event (see [7]).

Referências

[1] J. Riordan, "An introduction to combinational analysis" , Wiley (1958)
[2] H.J. Ryser, "Combinatorial mathematics" , Carus Math. Monogr. , 14 , Math. Assoc. Amer. (1963)
[3] M. Hall, "Combinatorial theory" , Blaisdell (1967)
[4] E.F. Beckenbach (ed.) , Applied combinatorial mathematics , Wiley (1964)
[5] F. Harary, "Graph theory" , Addison-Wesley (1969) pp. Chapt. 9
[6] F Harary, E. Palmer, "Graphical enumeration" , Acad. Press (1973)
[7] P. Erdös, J. Spencer, "Probabilistic methods in combinatorics" , Acad. Press (1974)
[8] V.F. Kolchin, V.P. Chistyakov, "Combinatorial problems of probability theory" Itogi Nauk. i Tekhn. Teor. Veroyatnost. Mat. Stat. Teoret. Kibernet. , 11 (1974) pp. 5–45 (In Russian)
[9] V.N. Sachkov, , Questions of cybernetics. Proc. Seminar on Combinatorial Mathematics , Moscow (1973) pp. 146–164 (In Russian)
[10] V.N. Sachkov, "Combinatorial methods in discrete mathematics" , Moscow (1977) (In Russian)
[11] V.N. Sachkov, "Probabilistic methods in combinatorial analysis" , Moscow (1978) (In Russian)
[12] H. Minc, "Permanents" , Addison-Wesley (1978)
[13] G.P. [G.P. Egorichev] Egorychev, "The solution of van der Waerden's problem for permanents" Adv. in Math. , 42 : 3 (1981) pp. 299–305

Comments

The marriage problem is the following. Let there be a set $ < g _ <1>dots g _ > $ of $ n $ girls and a set $ < b _ <1>dots b _ > $ of $ m $ boys. Each girl $ g _ $ likes a subset $ B _ subset < b _ <1>dots b _ > $ of boys. When is it possible that each girl marries a boy she likes? The solution is of course given by the P. Hall theorem on distinct representatives, and this theorem is also known as the marriage theorem or the P. Hall marriage theorem. The abbreviation SDR is often used for systems of distinct representatives. Let $ G $ be the bipartite graph (cf. Graph, bipartite) consisting of the vertices $ < g _ <1>dots g _ , b _ <1>dots b _ > $ and with an edge joining $ g _ $ and $ b _ $ if and only if girl $ i $ likes boy $ j $( and no other edges). Then a solution of the marriage problem provides a matching, and in this context the marriage theorem is also known as the P. Hall matching theorem.


As is the case with all of mathematics, the only way to learn it well is to do as many problems as possible. So, homework problems will be a very important part of the course, and there will be homework assigned every week (other than the week of the midterm). Completion of all homework problems is required, and your grade on a homework assignment will be based on completeness, as well as on the details of the solutions of the problems graded. In particular, I will not necessarily grade every homework problem assigned, but part of your score for an assignment will be for the completion of all problems. Individual homework assignment should be completed by the student alone, although I am always open for questions, either in office hours or by email.

For each homework problem assigned, a complete solution with each step explained should be written up clearly and neatly. Be sure to completely explain your steps and reasoning for calculations as well as for proofs. This is especially important in enumerative problems, as there can be many ways to arrive at the same answer, and what I am interested in is your thought process.

Homework is due at the beginning of class on the due date of the assignment. Late homework will be marked off 20% for every day late. Homework turned in after class on the due date is considered one day late, and the next weekday after that 2 days late, and so on. Everything is easier, of course, if you turn in the homework on time!

Assignment Problemas Due Date
1 5.1 #18, 24, 5.2 #46, 67, 5.3 #14, 19, 5.4 #14, 32 Mon, Jan 30
2 5.5 #14(d,e,f,g), 21, 26, 32, 8.1 #20, 27, 8.2 #10, 25 Mon, Feb 6
3 8.2: Finish the proof of Theorem 2, by proving the formula for Nm * , and #37,
1.1 #16, 18, 22, 1.2 #6, 11, 14
Mon, Feb 13
4 1.3 #9, 14, 15, 1.4 #8, 9, 12, 14, 20 Mon, Feb 20
5 2.1 #8, 12(a,c), 13, 14, 2.2 #4(b,h), 6, 16 Mon, Feb 27
6 2.3 #1(d,f), 2.4 #1, 2, 8(a,b), 11(a,b,c) Wed, Mar 14
7 6.1 #14, 22, 6.2 #18, 31, 6.3 #2, 15, 18, 20 Fri, Apr 6
8 6.3 #21, 6.4 #2, 12, 20, 6.5 #1(c,d,e), #2(c,d,e) Mon, Apr 16
9 7.3 #3(b,c,d), 5, 7, 7.4 #6, 9(b,c,d), 7.5 #1(b,c), #2(for #1b,c) Mon, Apr 23


Conteúdo

Knapsack problems appear in real-world decision-making processes in a wide variety of fields, such as finding the least wasteful way to cut raw materials, [3] selection of investments and portfolios, [4] selection of assets for asset-backed securitization, [5] and generating keys for the Merkle–Hellman [6] and other knapsack cryptosystems.

One early application of knapsack algorithms was in the construction and scoring of tests in which the test-takers have a choice as to which questions they answer. For small examples, it is a fairly simple process to provide the test-takers with such a choice. For example, if an exam contains 12 questions each worth 10 points, the test-taker need only answer 10 questions to achieve a maximum possible score of 100 points. However, on tests with a heterogeneous distribution of point values, it is more difficult to provide choices. Feuerman and Weiss proposed a system in which students are given a heterogeneous test with a total of 125 possible points. The students are asked to answer all of the questions to the best of their abilities. Of the possible subsets of problems whose total point values add up to 100, a knapsack algorithm would determine which subset gives each student the highest possible score. [7]

A 1999 study of the Stony Brook University Algorithm Repository showed that, out of 75 algorithmic problems, the knapsack problem was the 19th most popular and the third most needed after suffix trees and the bin packing problem. [8]

O bounded knapsack problem (BKP) removes the restriction that there is only one of each item, but restricts the number x i > of copies of each kind of item to a maximum non-negative integer value c :

O unbounded knapsack problem (UKP) places no upper bound on the number of copies of each kind of item and can be formulated as above except for that the only restriction on x i > is that it is a non-negative integer.

One example of the unbounded knapsack problem is given using the figure shown at the beginning of this article and the text "if any number of each box is available" in the caption of that figure.

The knapsack problem is interesting from the perspective of computer science for many reasons:

  • The decision problem form of the knapsack problem (Can a value of at least V be achieved without exceeding the weight C?) is NP-complete, thus there is no known algorithm both correct and fast (polynomial-time) in all cases.
  • While the decision problem is NP-complete, the optimization problem is not, its resolution is at least as difficult as the decision problem, and there is no known polynomial algorithm which can tell, given a solution, whether it is optimal (which would mean that there is no solution with a larger V, thus solving the NP-complete decision problem).
  • There is a pseudo-polynomial time algorithm using dynamic programming.
  • There is a fully polynomial-time approximation scheme, which uses the pseudo-polynomial time algorithm as a subroutine, described below.
  • Many cases that arise in practice, and "random instances" from some distributions, can nonetheless be solved exactly.

There is a link between the "decision" and "optimization" problems in that if there exists a polynomial algorithm that solves the "decision" problem, then one can find the maximum value for the optimization problem in polynomial time by applying this algorithm iteratively while increasing the value of k. On the other hand, if an algorithm finds the optimal value of the optimization problem in polynomial time, then the decision problem can be solved in polynomial time by comparing the value of the solution output by this algorithm with the value of k. Thus, both versions of the problem are of similar difficulty.

One theme in research literature is to identify what the "hard" instances of the knapsack problem look like, [9] [10] or viewed another way, to identify what properties of instances in practice might make them more amenable than their worst-case NP-complete behaviour suggests. [11] The goal in finding these "hard" instances is for their use in public key cryptography systems, such as the Merkle-Hellman knapsack cryptosystem.

Furthermore, notable is the fact that the hardness of the knapsack problem depends on the form of the input. If the weights and profits are given as integers, it is weakly NP-complete, while it is strongly NP-complete if the weights and profits are given as rational numbers. [12] However, in the case of rational weights and profits it still admits a fully polynomial-time approximation scheme.

Several algorithms are available to solve knapsack problems, based on the dynamic programming approach, [13] the branch and bound approach [14] or hybridizations of both approaches. [11] [15] [16] [17]

Dynamic programming in-advance algorithm Edit

O unbounded knapsack problem (UKP) places no restriction on the number of copies of each kind of item. Besides, here we assume that x i > 0 >0>


História

Certain types of combinatorial problems have attracted the attention of mathematicians since early times. Magic squares, for example, which are square arrays of numbers with the property that the rows, columns, and diagonals add up to the same number, occur in the I Ching, a Chinese book dating back to the 12th century bc . The binomial coefficients, or integer coefficients in the expansion of (uma + b) n , were known to the 12th-century Indian mathematician Bhāskara, who in his Līlāvatī (“The Graceful”), dedicated to a beautiful woman, gave the rules for calculating them together with illustrative examples. “Pascal’s triangle,” a triangular array of binomial coefficients, had been taught by the 13th-century Persian philosopher Naṣīr ad-Dīn aḷ-Ṭūsī.

In the West, combinatorics may be considered to begin in the 17th century with Blaise Pascal and Pierre de Fermat, both of France, who discovered many classical combinatorial results in connection with the development of the theory of probability. The term combinatorial was first used in the modern mathematical sense by the German philosopher and mathematician Gottfried Wilhelm Leibniz in his Dissertatio de Arte Combinatoria (“Dissertation Concerning the Combinational Arts”). He foresaw the applications of this new discipline to the whole range of the sciences. The Swiss mathematician Leonhard Euler was finally responsible for the development of a school of authentic combinatorial mathematics beginning in the 18th century. He became the father of graph theory when he settled the Königsberg bridge problem, and his famous conjecture on Latin squares was not resolved until 1959.

In England, Arthur Cayley, near the end of the 19th century, made important contributions to enumerative graph theory, and James Joseph Sylvester discovered many combinatorial results. The British mathematician George Boole at about the same time used combinatorial methods in connection with the development of symbolic logic, and the combinatorial ideas and methods of Henri Poincaré, which developed in the early part of the 20th century in connection with the problem of n bodies, have led to the discipline of topology, which occupies the centre of the stage of mathematics. Many combinatorial problems were posed during the 19th century as purely recreational problems and are identified by such names as “the problem of eight queens” and “the Kirkman school girl problem.” On the other hand, the study of triple systems begun by Thomas P. Kirkman in 1847 and pursued by Jakob Steiner, a Swiss-born German mathematician, in the 1850s was the beginning of the theory of design. Among the earliest books devoted exclusively to combinatorics are the German mathematician Eugen Netto’s Lehrbuch der Combinatorik (1901 “Textbook of Combinatorics”) and the British mathematician Percy Alexander MacMahon’s Combinatory Analysis (1915–16), which provide a view of combinatorial theory as it existed before 1920.


Conteúdo

Basic combinatorial concepts and enumerative results appeared throughout the ancient world. In the 6th century BCE, ancient Indian physician Sushruta asserts in Sushruta Samhita that 63 combinations can be made out of 6 different tastes, taken one at a time, two at a time, etc., thus computing all 2 6 − 1 possibilities. Greek historian Plutarch discusses an argument between Chrysippus (3rd century BCE) and Hipparchus (2nd century BCE) of a rather delicate enumerative problem, which was later shown to be related to Schröder–Hipparchus numbers. [7] [8] [9] Earlier, in the Ostomachion, Archimedes (3rd century BCE) may have considered the number of configurations of a tiling puzzle, [10] while combinatorial interests possibly were present in lost works by Apollonius. [11] [12]

In the Middle Ages, combinatorics continued to be studied, largely outside of the European civilization. The Indian mathematician Mahāvīra (c. 850) provided formulae for the number of permutations and combinations, [13] [14] and these formulas may have been familiar to Indian mathematicians as early as the 6th century CE. [15] The philosopher and astronomer Rabbi Abraham ibn Ezra (c. 1140) established the symmetry of binomial coefficients, while a closed formula was obtained later by the talmudist and mathematician Levi ben Gerson (better known as Gersonides), in 1321. [16] The arithmetical triangle—a graphical diagram showing relationships among the binomial coefficients—was presented by mathematicians in treatises dating as far back as the 10th century, and would eventually become known as Pascal's triangle. Later, in Medieval England, campanology provided examples of what is now known as Hamiltonian cycles in certain Cayley graphs on permutations. [17] [18]

During the Renaissance, together with the rest of mathematics and the sciences, combinatorics enjoyed a rebirth. Works of Pascal, Newton, Jacob Bernoulli and Euler became foundational in the emerging field. In modern times, the works of J.J. Sylvester (late 19th century) and Percy MacMahon (early 20th century) helped lay the foundation for enumerative and algebraic combinatorics. Graph theory also enjoyed an explosion of interest at the same time, especially in connection with the four color problem.

In the second half of the 20th century, combinatorics enjoyed a rapid growth, which led to establishment of dozens of new journals and conferences in the subject. [19] In part, the growth was spurred by new connections and applications to other fields, ranging from algebra to probability, from functional analysis to number theory, etc. These connections shed the boundaries between combinatorics and parts of mathematics and theoretical computer science, but at the same time led to a partial fragmentation of the field.

Enumerative combinatorics Edit

Enumerative combinatorics is the most classical area of combinatorics and concentrates on counting the number of certain combinatorial objects. Although counting the number of elements in a set is a rather broad mathematical problem, many of the problems that arise in applications have a relatively simple combinatorial description. Fibonacci numbers is the basic example of a problem in enumerative combinatorics. The twelvefold way provides a unified framework for counting permutations, combinations and partitions.

Analytic combinatorics Edit

Analytic combinatorics concerns the enumeration of combinatorial structures using tools from complex analysis and probability theory. In contrast with enumerative combinatorics, which uses explicit combinatorial formulae and generating functions to describe the results, analytic combinatorics aims at obtaining asymptotic formulae.

Partition theory Edit

Partition theory studies various enumeration and asymptotic problems related to integer partitions, and is closely related to q-series, special functions and orthogonal polynomials. Originally a part of number theory and analysis, it is now considered a part of combinatorics or an independent field. It incorporates the bijective approach and various tools in analysis and analytic number theory and has connections with statistical mechanics.

Graph theory Edit

Graphs are fundamental objects in combinatorics. Considerations of graph theory range from enumeration (e.g., the number of graphs on n vertices with k edges) to existing structures (e.g., Hamiltonian cycles) to algebraic representations (e.g., given a graph G and two numbers x e y, does the Tutte polynomial TG(x,y) have a combinatorial interpretation?). Although there are very strong connections between graph theory and combinatorics, they are sometimes thought of as separate subjects. [20] While combinatorial methods apply to many graph theory problems, the two disciplines are generally used to seek solutions to different types of problems.

Design theory Edit

Design theory is a study of combinatorial designs, which are collections of subsets with certain intersection properties. Block designs are combinatorial designs of a special type. This area is one of the oldest parts of combinatorics, such as in Kirkman's schoolgirl problem proposed in 1850. The solution of the problem is a special case of a Steiner system, which systems play an important role in the classification of finite simple groups. The area has further connections to coding theory and geometric combinatorics.

Finite geometry Edit

Finite geometry is the study of geometric systems having only a finite number of points. Structures analogous to those found in continuous geometries (Euclidean plane, real projective space, etc.) but defined combinatorially are the main items studied. This area provides a rich source of examples for design theory. It should not be confused with discrete geometry (combinatorial geometry).

Order theory Edit

Order theory is the study of partially ordered sets, both finite and infinite. Various examples of partial orders appear in algebra, geometry, number theory and throughout combinatorics and graph theory. Notable classes and examples of partial orders include lattices and Boolean algebras.

Matroid theory Edit

Matroid theory abstracts part of geometry. It studies the properties of sets (usually, finite sets) of vectors in a vector space that do not depend on the particular coefficients in a linear dependence relation. Not only the structure but also enumerative properties belong to matroid theory. Matroid theory was introduced by Hassler Whitney and studied as a part of order theory. It is now an independent field of study with a number of connections with other parts of combinatorics.

Extremal combinatorics Edit

Extremal combinatorics studies extremal questions on set systems. The types of questions addressed in this case are about the largest possible graph which satisfies certain properties. For example, the largest triangle-free graph on 2n vertices is a complete bipartite graph Kn,n. Often it is too hard even to find the extremal answer f(n) exactly and one can only give an asymptotic estimate.

Ramsey theory is another part of extremal combinatorics. It states that any sufficiently large configuration will contain some sort of order. It is an advanced generalization of the pigeonhole principle.

Probabilistic combinatorics Edit

In probabilistic combinatorics, the questions are of the following type: what is the probability of a certain property for a random discrete object, such as a random graph? For instance, what is the average number of triangles in a random graph? Probabilistic methods are also used to determine the existence of combinatorial objects with certain prescribed properties (for which explicit examples might be difficult to find), simply by observing that the probability of randomly selecting an object with those properties is greater than 0. This approach (often referred to as a probabilistic method) proved highly effective in applications to extremal combinatorics and graph theory. A closely related area is the study of finite Markov chains, especially on combinatorial objects. Here again probabilistic tools are used to estimate the mixing time.

Often associated with Paul Erdős, who did the pioneering work on the subject, probabilistic combinatorics was traditionally viewed as a set of tools to study problems in other parts of combinatorics. However, with the growth of applications to analyze algorithms in computer science, as well as classical probability, additive number theory, and probabilistic number theory, the area recently grew to become an independent field of combinatorics.

Algebraic combinatorics Edit

Algebraic combinatorics is an area of mathematics that employs methods of abstract algebra, notably group theory and representation theory, in various combinatorial contexts and, conversely, applies combinatorial techniques to problems in algebra. Algebraic combinatorics is continuously expanding its scope, in both topics and techniques, and can be seen as the area of mathematics where the interaction of combinatorial and algebraic methods is particularly strong and significant.

Combinatorics on words Edit

Combinatorics on words deals with formal languages. It arose independently within several branches of mathematics, including number theory, group theory and probability. It has applications to enumerative combinatorics, fractal analysis, theoretical computer science, automata theory, and linguistics. While many applications are new, the classical Chomsky–Schützenberger hierarchy of classes of formal grammars is perhaps the best-known result in the field.

Geometric combinatorics Edit

Geometric combinatorics is related to convex and discrete geometry, in particular polyhedral combinatorics. It asks, for example, how many faces of each dimension a convex polytope can have. Metric properties of polytopes play an important role as well, e.g. the Cauchy theorem on the rigidity of convex polytopes. Special polytopes are also considered, such as permutohedra, associahedra and Birkhoff polytopes. Combinatorial geometry is an old fashioned name for discrete geometry.

Topological combinatorics Edit

Combinatorial analogs of concepts and methods in topology are used to study graph coloring, fair division, partitions, partially ordered sets, decision trees, necklace problems and discrete Morse theory. It should not be confused with combinatorial topology which is an older name for algebraic topology.

Arithmetic combinatorics Edit

Arithmetic combinatorics arose out of the interplay between number theory, combinatorics, ergodic theory, and harmonic analysis. It is about combinatorial estimates associated with arithmetic operations (addition, subtraction, multiplication, and division). Additive number theory (sometimes also called additive combinatorics) refers to the special case when only the operations of addition and subtraction are involved. One important technique in arithmetic combinatorics is the ergodic theory of dynamical systems.

Infinitary combinatorics Edit

Infinitary combinatorics, or combinatorial set theory, is an extension of ideas in combinatorics to infinite sets. It is a part of set theory, an area of mathematical logic, but uses tools and ideas from both set theory and extremal combinatorics.

Gian-Carlo Rota used the name continuous combinatorics [21] to describe geometric probability, since there are many analogies between counting e measure.

Combinatorial optimization Edit

Combinatorial optimization is the study of optimization on discrete and combinatorial objects. It started as a part of combinatorics and graph theory, but is now viewed as a branch of applied mathematics and computer science, related to operations research, algorithm theory and computational complexity theory.

Coding theory Edit

Coding theory started as a part of design theory with early combinatorial constructions of error-correcting codes. The main idea of the subject is to design efficient and reliable methods of data transmission. It is now a large field of study, part of information theory.

Discrete and computational geometry Edit

Discrete geometry (also called combinatorial geometry) also began as a part of combinatorics, with early results on convex polytopes and kissing numbers. With the emergence of applications of discrete geometry to computational geometry, these two fields partially merged and became a separate field of study. Restam muitas conexões com combinatórias geométricas e topológicas, que podem ser vistas como conseqüências da geometria discreta inicial.

Sistemas combinatórios e dinâmicos Editar

Aspectos combinatórios de sistemas dinâmicos é outro campo emergente. Aqui, os sistemas dinâmicos podem ser definidos em objetos combinatórios. Veja, por exemplo, sistema gráfico dinâmico.

Edição combinatória e física

Existem interações crescentes entre a combinatória e a física, particularmente a física estatística. Os exemplos incluem uma solução exata do modelo de Ising e uma conexão entre o modelo de Potts, por um lado, e os polinômios cromáticos e de Tutte, por outro.


Assista o vídeo: APRENDA COM EXERCÍCIOS. ANÁLISE COMBINATÓRIA (Outubro 2021).