Matryoshka Sequences

How many ways can you arrange N Russian nesting dolls when each one comes apart into a top and a bottom half? Four versions of the puzzle (with or without stacking, with distinct or repeated sizes), with every arrangement drawn for up to four dolls.

NestingPieces go inside larger pieces: bottoms in bottoms, tops in tops, dolls in dolls.2, 10, 75, 780, 10556, …Bell(N)·Bell(N+1), OEIS A124426 StackingThe dolls also have flat heads, so a smaller piece can stand on a top half or a closed doll.2, 19, 312, 7643, 256020, …New sequence, submitted to the OEIS Repeated sizes: nestingSeveral dolls can share a size. Equal dolls are identical and never nest in each other; only the order of sizes matters.2, 13, 117, 1485, 24508, …New sequence Repeated sizes: stackingRepeated sizes with flat heads for stacking. Equal sizes never nest or stack.2, 22, 415, 12160, 493998, …New sequence

The four counts

Dolls	Nesting	Stacking	Repeated sizes: nesting	Repeated sizes: stacking
1	2	2	2	2
2	10	19	13	22
3	75	312	117	415
4	780	7,643	1,485	12,160
5	10,556	256,020	24,508	493,998
6	178,031	11,096,168	505,381	26,174,898
7	3,630,780	598,896,401	12,612,491	1,735,381,834
8	87,548,580	39,139,847,188	372,322,941	139,755,623,586
9	2,452,523,325	3,031,322,144,533	12,770,803,390	13,367,574,533,502
10	78,697,155,750	273,521,581,657,006	501,779,797,457	1,492,053,442,567,399

Where the formulas come from

With nesting only, the closed dolls and bottom halves form stacks of nested pieces, and any grouping of the N dolls into stacks works: Bell(N) ways. The loose tops nest among themselves, and choosing which dolls are open and how their tops nest gives Bell(N+1) ways. Carlo Sanna noted in OEIS A000110 that Bell(N) counts nestings of whole dolls; splitting the dolls into halves multiplies in the second Bell number.

Stacking ties the tops to everything else: a tower can alternate dolls, bottoms and tops, except that a top can never sit inside an open bottom. Whether that rule applies depends on how the sizes of the tops and bottoms interleave, so the count no longer splits into a product. The terms come from a recurrence that places pieces from largest to smallest and tracks four kinds of free slot. A brute-force enumeration of every arrangement agrees for N ≤ 5. With every doll closed, the stacking count is OEIS A000258, the sum of Stirling2(N,k)·Bell(k).

Repeated sizes

When sizes can repeat, a size set is just how many dolls share each size, smallest first, so there are 2^N−1 size sets and the count adds them all up. Equal dolls are identical, which makes direct counting overcount the symmetric arrangements. Burnside's lemma fixes that: average, over the ways of permuting equal pieces, the number of arrangements each permutation leaves unchanged. Each of those counts reduces to the same slot recurrence as the distinct-size case. A brute-force enumeration agrees for N ≤ 4, and a Pólya multiset count agrees for N ≤ 6.

Code and data

The repository has the brute-force enumerators, the fast counters, b-files for the stacking count (N = 0 to 180) and the two repeated-size counts, and Rust programs for the longer runs. The same material is archived with other results in oeis-results.