Lesson goal: Card Pickup Passes and Eulerian Numbers (AMC 10A Problem 22)

Previous: Integer-preserving nonlinear recurrence | Home | Next: Introduction: combining exponents

In the 2022 AMC 10A competition, Problem #22 explores how array sorting passes connect to a famous family of combinatorial values known as Eulerian numbers:

Contest Problem Statement:
"Suppose that 13 cards numbered 1, 2, 3, ..., 13 are arranged in a row. The task is to pick them up in numerically increasing order, working repeatedly from left to right. In the example below, cards 1, 2, 3 are picked up on the first pass, 4 and 5 on the second pass, 6 on the third pass, 7, 8, 9, 10 on the fourth pass, and 11, 12, 13 on the fifth pass:
[7, 8, 11, 6, 4, 5, 9, 12, 1, 13, 10, 2, 3]
For how many of the $13!$ possible orderings of the cards will the 13 cards be picked up in exactly two passes?"

Understanding the Mechanics of a Pass

Let pos[k] denote the index where card $k$ is located in the row:
  • Card $1$ is picked up first on Pass 1.
  • Card $2$ can be picked up on the same pass if and only if it appears to the right of Card 1: pos[2] > pos[1].
  • If Card $2$ is to the left of Card 1 (pos[2] < pos[1]), we cannot pick it up until we reach the end of the row and return to the left to begin Pass 2!
In general, each time pos[k + 1] < pos[k], a new pass must begin.
In mathematics, any index where a sequence decreases ($s_{k+1} < s_k$) is called a descent.
  • 1 Pass: $0$ descents — only the already-sorted row $[1, 2, \dots, 13]$ ($1$ way).
  • 2 Passes: Exactly $1$ descent in the position sequence!

The Eulerian Number Formula

The number of permutations of $n$ elements having exactly $k$ descents is given by the Eulerian numbers, denoted $\left\langle \begin{matrix} n \\ k \end{matrix} \right\rangle$.

For permutations with exactly $1$ descent ($2$ passes), there is a known closed formula:
$$\left\langle \begin{matrix} n \\ 1 \end{matrix} \right\rangle = 2^n - (n + 1)$$
Let's check small values of $n$:
  • For $n = 3$ cards: $2^3 - (3 + 1) = 8 - 4 = 4$ orderings.
  • For $n = 4$ cards: $2^4 - (4 + 1) = 16 - 5 = 11$ orderings.
  • For $n = 5$ cards: $2^5 - (5 + 1) = 32 - 6 = 26$ orderings.
For the contest problem with $n = 13$ cards:
$$2^{13} - (13 + 1) = 8,192 - 14 = 8,178$$
In this lesson, we build an array pass counter in Lua to test the contest example and verify the formula!
function count_passes(row)
  local pos = {}
  for i = 1, #row do pos[row[i = i end
  local passes = 1
  for k = 1, #row - 1 do
    if pos[k + 1] < pos[k] then passes = passes + 1 end
  end
  return passes
end
Move the mouse over a dotted box for more information.

The Eulerian formula $2^n - (n + 1)$ counts all partitions of the $n$ elements into two non-empty increasing runs, giving exactly 8,178 valid orderings.

Now you try. Replace ???? with 1 and click Run to evaluate Eulerian number (13, 2) = 8178$. Try creating your own card rows like {3, 1, 4, 2, 5} and see how many passes it takes!

Type your code here:


See your results here: