## Combinatorics

This branch of **BookofProofs** is devoted to *combinatorcs*. Combinartorics, sometimes also called *discrete mathematics*, is a branch of mathematics that focusses on the study of *discrete* objects (as opposed to continuous ones). The main purpose is to provide a framework for counting these objects under diffent operations, including exchanges, permutations, choice situations, combinations, and many more.

Combinatorics plays a crucial role in the development of many other mathematical areas, e.g. number theory, probability theory, graph theory, geometry, and the theory of algorithms.

### Theoretical minimum (in a nutshell)

As a framework for counting discrete objects, combinatorics does not require very sophisticated prerequisites to be acquainted with. However, the theoretical concepts of counting in combinatorics can become demanding for the undergraduates. The main difficulty might result not in the mere understanding of the techniques, but in the ability to recognize which technique to count things is applicable in a given situation.

### Concepts you will learn in this part of **BookofProofs**

- Basic
*counting principles*, e.g.- the
*Pigeonhole principle*, - the
*fundamental counting principle*for addition and multiplication, *permutations*and*factorials*, with and without repetitions,*combinations*and*permutations*of indistinguishable objects,

- the
- You will learn problem solving strategies for
*counting problems*. - Learn about some number sequences, including
*Stirling*,*Bernoulli*, and about their applications. - Learn what are
*recurrencies*and why they are important for solving combinatorial problems and programming. - Learn solving strategies to solve recurrences, including
*generating functions*.

| | | | Contributors: *bookofproofs*

## 1.Inclusion and Exclusion

## 2.**Proposition**: The Fundamental Counting Principle

## 3.**Definition**: Permutations

## 4.**Definition**: Combinations

## 5.Stirling Numbers

## 6.**Proposition**: Number of Relations on a Finite Set

## 7.**Definition**: Falling And Rising Factorial Powers

## 8.**Proposition**: Counting the Set's Elements Using Its Partition

## 9.**Proposition**: Number of Strings With a Fixed Length Over an Alphabet with k Letters

## 10.**Proposition**: Number of Subsets of a Finite Set

## 11.**Proposition**: Multinomial Coefficient

© 2018 Powered by BooOfProofs, All rights reserved.