The objective of this course is to learn the basic elements of mathematics and how to use the mathematical language as well as the techniques for proving and solving problems. This course goes deeply into combinatorial aspects started in the first year course Matemáticas Básicas and is a basis for the second year course Cálculo de Probabilidades. Some of the concepts introduced, such as recurrences and graphs, are used later in the third and fourth year courses Métodos Numéricos II and Programación Matemática.

COMPETENCES

M06CM01 - To be familiarized with the main types of mathematical proof and with the techniques of solving problems (observation-conjecture-proof).

M06CM06 - To know how to solve combinatorial problems using basic techniques, generating functions and recurrence relations.

M06CM07 - To be familiarized with combinatorial identities and the main families of numbers with combinatorial meaning.

M06CM08 - To know the concepts, techniques and basic results of the graph theory and to be familiarized with some of its multiple applications.



LEARNING RESULTS

To know how to solve combinatorial problems with a certain degree of complexity.

To be familiarized with families of numbers that are present in many areas of Mathematics.

To use skillfully combinatorial expressions and identities, inequalities, recurrence relations and generating functions.

To be familiarized with graphs, their main properties, and some of their multiple applications.

1. BASIC COMBINATORICS: Basic resources in the combinatorial reasoning. The principle of inclusion and exclusion. The pigeonhole principle.

2. COMBINATORIAL IDENTITIES: Binomial and multinomial coefficients. Binomial and multinomial formulae. Related identities.

3. GENERATING FUNCTIONS AND RECURRENCE RELATIONS: Generating function of a sequence of numbers. Applications to combinatorial problems. Recurrence relations and combinatorial problems. Recurrence relations and generating functions. Obtaining the general term.

4. MAIN FAMILIES OF NUMBERS: Numbers of Fibonacci. Numbers of Catalan. Numbers of Bell. Numbers of Stirling. Partitions of natural numbers.

5. GRAPHS: Basic concepts. Paths. Trees. Planar graphs. Coloring.

In the M classes the theoretical contents will be developed.

In the S classes the students will work and present problems ans tasks.

In the GA classes exercises will be solved.

• Continuous Assessment System
• Final Assessment System
• Tools and qualification percentages:
  • See GUIDELINES (%): 100

GUIDELINES

Final exam (70%), partial test (15%), and preparing and presenting tasks (15%).

The minimum grade required to pass is 5 points (over 10) provided that at least 4 points (over 10) are gotten in the final exam (compulsory).



WITHDRAWAL OF CONTINUOUS ASSESSMENT SYSTEM

The student must give written notice of widthdrawal of countinuous assessment system in a period of 9 weeks since the begining of the course. In this case, the final grade will be the grade of the exam (100%) and at least 5 points (over 10) are required to pass.



DECLINING TO SIT

A student who does not take the final exam will obtain <>.

GUIDELINES

In the case of continuous assessment:

The grade obtained in the exercises and tasks will be kept, when advantageous to the student. Grades will never be kept from one year to another. The minimum grade required to pass is 5 points (over 10) provided that at least 4 points (over 10) are gotten in the final exam (compulsory).



In the case of end-of-course assessment:

The final grade will be the grade of the exam (100%) and at least 5 points (over 10) are required to pass.



DECLINING TO SIT

A student who does not take the final exam will obtain <>.

The recommended materials will be available at the virtual platform.

Basic bibliography

D.I.A. COHEN, Basic Techniques of Combinatorial Theory, Wiley, New York,1978.

J.M. HARRIS, J.L. HIRST, M.J. MOSSINGHOFF, Combinatorics and Graph Theory, Springer, New York, 2008.

N. HARTSFIELD, G. RINGEL, Pearls in Graph Theory, Dover, New York, 1994.

R.L. GRAHAM, D.E. KNUTH, O. PATASHNIK, Concrete Mathematics, Addison-Wesley, Reading, Mass., 1994.

In-depth bibliography

V.K. BALAKRISHNAN, Combinatorics, Schaum’s Outline Series, McGraw-Hill, 1995.
R.C. BOSE, B. MANVEL. Introduction to Combinatorial Theory, Wiley, New York, 1984.
F. GARCIA MERAYO, Matemática Discreta, Paraninfo, Madrid, 2001.
J. HEBER NIETO SAID, Teoría Combinatoria.La Universidad del Zulia, 1996. http://www.jhnieto.org/tc.pdf
D.A. MARCUS, Combinatorics: A Problem Oriented Approach, The Mathematical Association of America, 1998.
R. J. TRUDEAU, Introduction to Graph Theory, Dover Pulications, Inc, Nueva York, 1993.
N. Ya. VILENKIN, Combinatorics, Academic Press, New York, 1971.
H.S. WILF, Generatingfuntionology, Academic Press, Boston, 1990. http://www.math.upenn.edu/~wilf/gfology2.pdf

Journals

The Electronic Journal of Combinatorics http://www.combinatorics.org/
The Fibonaccy Quarterly http://www.fq.math.ca/

Web addresses

Combinatorics http://mathworld.wolfram.com/topics/Combinatorics.html
Pascal triangle http://en.wikipedia.org/wiki/Pascal%27s_triangle
Pigeon principle http://www.cut-the-knot.org/do_you_know/pigeon.shtml
Fibonacci numbers http://www.maths.surrey.ac.uk/hosted-sites/R.Knott/Fibonacci/
Catalan numbers http://mathforum.org/advanced/robertd/catalan.html
Stirling Number of the First Kind http://mathworld.wolfram.com/StirlingNumberoftheFirstKind.html
Stirling Number of the Second Kind http://mathworld.wolfram.com/StirlingNumberoftheSecondKind.html
The Encyclopedia of Integer Sequences http://oeis.org/
Graphs http://en.wikipedia.org/wiki/Graph_theory