We have a deck of $2n$ cards.
We will shuffle it in a particular way:
Split the deck into a lower half $A$ and an upper half $B$. Each will have $n$ cards.
Merge $A$ and $B$ to create a new deck $C$, such that all cards in $A$ are in the same order in $A$ as in $C$, and all cards in $B$ are in the same order in $B$ as in $C$.
Equivalently:
Split the deck into a lower half $A$ and an upper half $B$. Each will have $n$ cards.
Create an empty new deck. Take one card either from the bottom of $A$ or the bottom of $B$, and add it to the top of the new deck. Repeat until $A$ and $B$ are empty.
For example, this is a valid shuffle for $n=5$:
Start: $[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]$
Split: $A=[1, 2, 3, 4, 5], B=[6, 7, 8, 9, 10]$
Merge: $[1, 6, 7, 2, 3, 4, 8, 5, 9, 10]$
Let $P(n, m)$ be the number of possible permutations of a deck of cards after shuffling in this way $m$ times.
What is $P(n, m)$?
I tried the first few cases in hopes that I might stumble upon a formula, but I got stuck at $m=2$.
$m=0$
There is only one possible permutation of the deck, which is whatever it starts as.
$P(n, 0)=1$
$m=1$
With only one shuffle, every possible shuffle produces a different end permutation. By the second definition of the shuffle, we can uniquely select a shuffle by picking which $n$ of the $2n$ final positions will come from $A$, or equivalently, from $B$. For each such combination there is one shuffle.
$P(n, 1)=\binom{2n}{n}$
$m=2$
At this point I'm stumped. I think the basic combinatorics I used so far won't work for $m\ge 2$.
We may define a shuffle operator $p$ which for a permutation produces the set of permutations reachable by one shuffle. We may then define it for a set of permutations like so:
$p\{v_1,v_2,v_3,\cdots,v_k\}=pv_1\cup pv_2\cup pv_3\cup \cdots \cup pv_k$
Then we can define our permutations counting function based on this shuffle operator and the identity permutation:
$P(n, m) = |p^m I_n|$
This is pretty much the problem statement, so it wouldn't count as a solution.
At each application of $p$ after the first, some permutations will be produced multiple times. I would try the overcounting method but I don't know which permutations will be duplicated and how many times. I don't think a working solution would be based on overcounting, since there is a bound $P(n,m)\le (2n)!$ but no bound on the overcount, and it seems silly to subtract a huge number of duplicates from a huge overcount to get a comparatively small true count.