Oris teme

  • Splošno


  • Lectures

    October 4, 2021

    We talked about counting sequences and when we can say that we "know" them (do we have an explicit formula? a recursion? an asymptotic formula? a generating function?). Then we talked about basic combinatorial structures (subsets, permutations, compositions, integer partitions, set partitions...) and defined some statistics (number of elements, cycles, inversions, descents, parts...) and sequences (binomial coefficients, Stirling numbers of the first and second kind, Lah numbers, partition numbers...).

    October 11, 2021

    We introduced basic counting rules (sum rule, product rule) and used them to count the number of subsets of a set, the number of (injective) maps from one set to another, and the number of permutations. We talked about the pigeon-hole principle. We introduced binomial coefficients and talked about their properties (symmetry, explicit formula, recursion, binomial theorem) and applications (counting compositions, weak compositions, number of ways to select k balls from n balls, Lah numbers, Dyck paths).

    October 18, 2021

    We talked about multinomial coefficients and the twelvefold way (number of ways to place n balls into k boxes, under various assumptions). We gave recursions for many of our objects (Stirling numbers of the first and second kind, Lah numbers, Eulerian numbers etc.). We proved the principle of inclusion and exclusion and used it to count derangements (permutations without fixed points).

    October 25, 2021

    We used the principle of inclusion and exclusion to count surjections, to find a formula for Euler's totient function, and to prove Euler's pentagonal theorem. We started talking about polynomial identities. We proved identities connecting powers of x and rising and falling factorials (involving Stirling numbers of the first and second kind and Lah numbers). We defined the inversion table of a permutation.

    November 8, 2021

    We proved that the inversion table map is a bijection, and used that to interpret the q-factorial in terms of inversions of permutations. We defined q-binomial coefficients, and proved two recursive formulas and the q-binomial theorem. We defined the q-multinomial coefficient and found the connection with inversions of a multiset. Then we started a new chapter on formal power series and generating functions. We motived and defined the concept of a formal power series, and defined the algebra of formal power series.

    November 15, 2021

    We proved that a formal power series has a multiplicative inverse if and only if its constant term is non-zero. We defined the derivative of a formal power series. We defined the exponential, logarithmic, and binomial series. We defined a metric on the algebra of formal power series and proved completeness. We used the metric to define (in certain cases) the composition of two formal power series.

    November 22, 2021

    We figured out when a formal power series has a compositional inverse. We used generating function to solve homogeneous linear recurrence equations with constant coefficients. We showed some further applications of ordinary generating functions.

    November 29, 2021

    We interpreted 1/(1-F(x)) and F(G(x)) for ordinary generating functions. We interpreted F(x)G(x) and e^F(x) for exponential generating functions. We showed many examples.

    December 6, 2021

    We stated the composition formula, which describes the combinatorial meaning of the composition of two exponential generating functions. We talked about algebraic generating functions and proved that they are d-finite. We found the exponential generating function for Euler numbers.

    December 13, 2021

    We stated some results about Euler and Bernoulli numbers, including some evaluations of the Riemann zeta function and Faulhaber's formula. We found the mixed generating function for Eulerian numbers.  We showed how to use generating functions to compute averages and variances for statistics on finite sets. We gave two variants of Lagrange inversion.

    December 20, 2021

    We studied the asymptotics of coefficients. We showed how to find the asymptotics if the singularity closest to the origin is a pole (meromorphic functions) or an algebraic singularity, and Hayman's theorem for entire functions.

    January 3, 2022

    We defined the incidence algebra for a locally finite poset (a partially ordered set with finite intervals). We found a criterion for invertibility, and defined the Möbius function. We computed it for an interval and the Boolean algebra.

    January 10, 2022

    We proved the Möbius inversion formula. We proved a formula for the Möbius function in a lattice, and used it to compute the Möbius function for the lattice of set partitions and the lattice of subspaces of the n-dimensional space over a finite field. We defined the action of a group on a set.

    January 11, 2022

    We defined orbits, stabilizers and the set of fixed points. We proved Burnside's lemma, and we used it to prove Pólya's theorem. We also defined the cyclic index, and computed it for the cyclic group and the dihedral group.

    • Izpiti

      Kolokviji:
      • 1. kolokvij: četrtek, 2. 12. 2021, ob 17.30 v VFP
      • 2. kolokvij: četrtek, 13. 1. 2022, ob 17.30 v VFP
      Midterms:
      • 1st: Thursday, 2. 12. 2021, at 17.30 in VFP
      • 2nd: Thursday, 13. 1. 2022, at 17.30 in VFP

      Izpiti:
      • 1. pisni izpit: torek, 25. 1. 2022, ob 10.00 v 2.05
      • 2. pisni izpit: četrtek, 17. 3. 2022, ob 16.00 v MFP
      • 3. pisni izpit: ??
      Exams:
      • 1st written exam: Tuesday, 25. 1. 2022, at 10.00 in 2.05
      • 2nd written exam: Thursday, 17. 3. 2022, at 16.00 in MFP
      • 3rd written exam: ??


    • Naloge z vaj