This is part 3 of our series on generating functions. Part 1 handled the quicksort recurrence. Part 2 used ordinary generating functions to count marbles in a can.

In this post we introduce exponential generating functions, which are what you reach for when the order of the objects you are counting matters. As with the earlier posts, our working notes live on the Generating Functions page of our wiki.

When Order Matters

The marbles-in-a-can problem from part 2 was order-independent. A can containing three reds, two blues, and one yellow is the same can no matter what order you put …

This is the third in a series of three blog posts describing our solution to a bioinformatics problem from Rosalind.info, Problem BA1(i) (Find most frequent words with mismatches in a string). To solve this problem and generate variations of a DNA string as required, we implemented a recursive backtracking method in the Go programming language.

• Part 1: Counting Variations
• Part 2: Generating Variations
• Part 3: Go Implementation of Recursive Backtracking

This is the second in a series of three blog posts describing our solution to a bioinformatics problem from Rosalind.info, Problem BA1(i) (Find most frequent words with mismatches in a string). To solve this problem and generate variations of a DNA string as required, we implemented a recursive backtracking method in the Go programming language.

• Part 1: Counting Variations
• Part 2: Generating Variations (you are here)
• Part 3: Go Implementation of Recursive Backtracking

Table of Contents

• Problem Description
• Permutations vs Combinations vs Variations
• Recursion
  • Recursive Backtracking Pseudocode
• Appying to DNA Variations
  • Generating Visits with Binary Numbers
  • Assembling the …

This is the first in a series of three blog posts describing our solution to a bioinformatics problem from Rosalind.info, Problem BA1(i) (Find most frequent words with mismatches in a string). To solve this problem and generate variations of a DNA string as required, we implemented a recursive backtracking method in the Go programming language.

• Part 1: Counting Variations (you are here)
• Part 2: Generating Variations
• Part 3: Go Implementation of Recursive Backtracking

Table of Contents

• Problem Description
• Useful Functions
  • Binomial Function
  • Factorial Function
• Counting Permutations
  • Deriving the Formula
  • Term 1: Picking DNA Indices
  • Term 1: Side Note …