Qm
BrainteasersJane StreetCitadel

1, 1, 2, 5, 14, 42, what next?

sequencescatalan-numberscountingrecursion

Find the next term of

1, 1, 2, 5, 14, 42, ?

Then name at least two different things these numbers count, give the recursion that generates them, and explain why the ratio of consecutive terms creeps towards 4.

Show a hint

Try the ratios: 42/14 = 3, 14/5 = 2.8, 5/2 = 2.5. They creep towards 4. Also try building each term from all previous pairs: 1 × 14 + 1 × 5 + 2 × 2 + 5 × 1 + 14 × 1.

Your answer

Solving needs a free account

Answers, streaks and solutions unlock when you are signed in. Reading the question and the hint stays free.

Create a free accountSign in

Discussion

Sign in to join the discussion · reading is open to everyone

💡 Discussion rules

  1. No full solutions here. Hints and approaches only.
  2. Complexity, edge cases and intuition are the point.
  3. Interview experiences are welcome. Respect your NDAs.

Loading discussion…

Learn the concepts

The theory behind this question.

Catalan NumbersTribonacci Numbers and Tiling CountsRecurrence RelationsBalls and Bins and the Birthday ProblemBinomial Coefficients and Pascal's Triangle

Related questions

Handshakes across a round table without crossingBinary strings with no two 1s in a rowA hundred empty glasses and the dregs1, 3, 4, 7, 11, 18, what next?Most regions from four circlesThe optimist, the pessimist and the longest sequence
All questions →