NumeriveMATH
CurriculumFamily workspaceStudentMy characterAchievementsContact
← Intermediate Counting and Probability levels

Intermediate Counting and Probability / LEVEL 4 · DIFFICULTY 4/5

Generating Functions and Graphs

Translate algebraic coefficients and network structure into counts.

3 stages · 24 practice problems · two 6-question assessment forms

Choose an island to read its lesson.

  1. MINI QUEST IC 4.1Generating FunctionsRead the lesson
  2. MINI QUEST IC 4.2Counting Edge EndsRead the lesson
  3. MINI QUEST IC 4.3Euler’s FormulaRead the lesson
  4. LEVEL CHECKCastle challenge

    6 questions across this level.

    Sign in for the level check →

STAGE IC 4.1 · 8 PRACTICE PROBLEMS · 2 NEW-CONTEXT APPLICATIONS

Generating Functions

Useful preparation: Reversing Conditional Probability

Goal: Understand and apply generating functions.

Before you begin: Reversing Conditional Probability

Understand the idea

A formal power series can record one choice per exponent. Multiplying series adds exponents, so a coefficient counts combinations of choices with the requested total.

[xᴺ](1+x+…)(1+x²+…)=⌊N/2⌋+1

Choose and carry out a method

Translate each factor into allowed contributions. For 1/(1−x) and 1/(1−x²), count nonnegative solutions to a+2b=N.

Check the reasoning

This is formal coefficient counting; no numerical convergence assumption is needed. Different powers can represent different token values.

WORKED EXAMPLE 1

Find the coefficient of x^5 in (1+x+x²+…)(1+x²+x⁴+…). Treat this as a formal power series.

  1. A coefficient counts pairs of selected exponents with the required sum.
  2. Solve a+2b=5, with a,b≥0. The value b may be 0 through 2.
  3. There are 3 choices; each b determines one a.

3

WORKED EXAMPLE 2

Find the coefficient of x^6 in (1+x+x²+…)(1+x²+x⁴+…). Treat this as a formal power series.

  1. A coefficient counts pairs of selected exponents with the required sum.
  2. Solve a+2b=6, with a,b≥0. The value b may be 0 through 3.
  3. There are 4 choices; each b determines one a.

4

Common pitfalls

Possible mix-up: Coefficients count ordered token sequences.

These factors record the counts of each token type, so order is ignored.

Possible mix-up: A correct numerical answer alone explains the method.

State the governing relationship and check the conditions described above.

Explain it to yourself

How would a factor 1+x³ change the choices available for a third token type?

Preview the eight practice prompts
  1. Find the coefficient of x^8 in (1+x+x²+…)(1+x²+x⁴+…). Treat this as a formal power series.
  2. Find the coefficient of x^9 in (1+x+x²+…)(1+x²+x⁴+…). Treat this as a formal power series.
  3. Find the coefficient of x^10 in (1+x+x²+…)(1+x²+x⁴+…). Treat this as a formal power series.
  4. Find the coefficient of x^11 in (1+x+x²+…)(1+x²+x⁴+…). Treat this as a formal power series.
  5. Find the coefficient of x^12 in (1+x+x²+…)(1+x²+x⁴+…). Treat this as a formal power series.
  6. Find the coefficient of x^13 in (1+x+x²+…)(1+x²+x⁴+…). Treat this as a formal power series.
  7. Using unlimited tokens of values 1 and 2, how many multisets have total value 14? Order is ignored. New context
  8. Using unlimited tokens of values 1 and 2, how many multisets have total value 15? Order is ignored. New context
Open stage IC 4.1 in the student workspace →

STAGE IC 4.2 · 8 PRACTICE PROBLEMS · 2 NEW-CONTEXT APPLICATIONS

Counting Edge Ends

Useful preparation: Generating Functions

Goal: Understand and apply counting edge ends.

Before you begin: Generating Functions

Understand the idea

Every edge of an undirected graph has two ends. Summing the degrees counts all those ends, so it counts each edge twice.

Σ degree(v)=2E

Choose and carry out a method

Add the vertex degrees, then divide by two. When every degree is equal, multiply that degree by the vertex count first.

Check the reasoning

The degree sum must be even. In a simple graph, a vertex degree cannot exceed the number of other vertices.

WORKED EXAMPLE 1

A finite undirected graph has 10 vertices, each of degree 3. How many edges does it have?

  1. Summing degrees counts each edge at both endpoints.
  2. 2E=10·3=30.
  3. E=15. Counting links once requires dividing the incidence total by two.

15

WORKED EXAMPLE 2

A finite undirected graph has 12 vertices, each of degree 3. How many edges does it have?

  1. Summing degrees counts each edge at both endpoints.
  2. 2E=12·3=36.
  3. E=18. Counting links once requires dividing the incidence total by two.

18

Common pitfalls

Possible mix-up: The degree sum equals the edge count.

Each edge contributes at both ends.

Possible mix-up: A correct numerical answer alone explains the method.

State the governing relationship and check the conditions described above.

Explain it to yourself

Why must the number of odd-degree vertices be even?

Preview the eight practice prompts
  1. A finite undirected graph has 16 vertices, each of degree 3. How many edges does it have?
  2. A finite undirected graph has 18 vertices, each of degree 3. How many edges does it have?
  3. A finite undirected graph has 20 vertices, each of degree 3. How many edges does it have?
  4. A finite undirected graph has 22 vertices, each of degree 3. How many edges does it have?
  5. A finite undirected graph has 24 vertices, each of degree 3. How many edges does it have?
  6. A finite undirected graph has 26 vertices, each of degree 3. How many edges does it have?
  7. A network has 28 stations and exactly three links meet each station. Each link joins two stations. How many links are present? New context
  8. A network has 30 stations and exactly three links meet each station. Each link joins two stations. How many links are present? New context
Open stage IC 4.2 in the student workspace →

STAGE IC 4.3 · 8 PRACTICE PROBLEMS · 2 NEW-CONTEXT APPLICATIONS

Euler’s Formula

Useful preparation: Counting Edge Ends

Goal: Understand and apply euler’s formula.

Before you begin: Counting Edge Ends

Understand the idea

A connected graph drawn in the plane without crossings divides the plane into bounded regions and one unbounded outside region. Its vertices, edges and faces satisfy an invariant relationship.

V−E+F=2 for a connected plane graph

Choose and carry out a method

Count all faces, including the outside. Rearrange V−E+F=2 to solve for the missing count when the graph is connected.

Check the reasoning

Adding a tree edge adds a vertex but no face; adding an edge around a new cycle adds a face. Both operations preserve the formula.

WORKED EXAMPLE 1

A connected planar graph is drawn without crossings and has 6 vertices and 9 edges. How many faces, including the unbounded face, does it have?

  1. Euler’s formula for a connected plane graph includes the outside face.
  2. V-E+F=2, so F=2-6+9.
  3. There are 5 faces. Omitting the outside would reduce the count by one.

5

WORKED EXAMPLE 2

A connected planar graph is drawn without crossings and has 7 vertices and 11 edges. How many faces, including the unbounded face, does it have?

  1. Euler’s formula for a connected plane graph includes the outside face.
  2. V-E+F=2, so F=2-7+11.
  3. There are 6 faces. Omitting the outside would reduce the count by one.

6

Common pitfalls

Possible mix-up: Count only enclosed regions as faces.

Euler’s formula includes the unbounded outside face.

Possible mix-up: A correct numerical answer alone explains the method.

State the governing relationship and check the conditions described above.

Explain it to yourself

Explain what happens to V, E and F when a new leaf is attached.

Preview the eight practice prompts
  1. A connected planar graph is drawn without crossings and has 9 vertices and 15 edges. How many faces, including the unbounded face, does it have?
  2. A connected planar graph is drawn without crossings and has 10 vertices and 17 edges. How many faces, including the unbounded face, does it have?
  3. A connected planar graph is drawn without crossings and has 11 vertices and 19 edges. How many faces, including the unbounded face, does it have?
  4. A connected planar graph is drawn without crossings and has 12 vertices and 21 edges. How many faces, including the unbounded face, does it have?
  5. A connected planar graph is drawn without crossings and has 13 vertices and 23 edges. How many faces, including the unbounded face, does it have?
  6. A connected planar graph is drawn without crossings and has 14 vertices and 25 edges. How many faces, including the unbounded face, does it have?
  7. A connected road network is drawn on a flat map with 15 junctions and 27 road segments, with no crossings away from junctions. How many regions, including the outside, does it form? New context
  8. A connected road network is drawn on a flat map with 16 junctions and 29 road segments, with no crossings away from junctions. How many regions, including the outside, does it form? New context
Open stage IC 4.3 in the student workspace →
Browse another level →