Number of nodes in a game tree for a binary choice card game

Question

Say you have a game played with a deck of $M$ cards. Every turn, you draw a card and either choose to add the card to your hand, or decline to add it to your hand. If you take the card, your opponent draws a new card and play continues as normal. If you decline to take the card, your opponent doesn't draw a new card and instead decides on whether to take the card you passed up; if they don't, the card is discarded, and play returns to you. The game ends when either player reaches $N$ cards in their hand, or the deck is empty. (Normally at the end of the game scores would be determined by the contents of each player's hands, but for the purposes of this question that's irrelevant.)

I want to know how many nodes there are in the game tree for various values of $M$ and $N$, and also how many of those are leaf nodes. I wrote a program to brute-force the solution by searching every possible game state (see below), but I feel like there should be a way to calculate the answer in constant time. Does such a solution exist?

---

Brute force script:

import datetime
import time

class GameState ():
    DECK_SIZE = 16
    HAND_LIMIT = 8
    INITIAL_DECK = list(range(DECK_SIZE))
    INITIAL_HAND = []

    def __init__(self, otherState = None):
        # global state
        self.deck = getattr(otherState, 'deck', self.INITIAL_DECK).copy()
        self.player = getattr(otherState, 'player', True) # True for player one, False for player two
        self.passed = getattr(otherState, 'passed', False)
        # per-player state
        self.playerOneHand = getattr(otherState, 'playerOneHand', self.INITIAL_HAND).copy()
        self.playerTwoHand = getattr(otherState, 'playerTwoHand', self.INITIAL_HAND).copy()

    @property
    def terminal (self):
        return (
            not self.deck or
            len(self.playerOneHand) == self.HAND_LIMIT or
            len(self.playerTwoHand) == self.HAND_LIMIT
        )

    def takeTurn (self, takeCard):
        if takeCard:
            hand = self.playerOneHand if self.player else self.playerTwoHand
            hand.append(self.deck.pop())
            self.passed = False
        elif self.passed:
            # discard
            self.deck.pop()
            self.passed = False
        else:
            # don't discard and give other player a chance to take
            self.passed = True

        self.player = not self.player

        return self

    def __repr__ (self):
        innards = [
            f"deck={self.deck}",
            f"player={self.player}",
            f"passed={self.passed}",
            f"playerOneHand={self.playerOneHand}",
            f"playerTwoHand={self.playerTwoHand}",
            f"terminal={self.terminal}"
        ]

        return f"GameState({', '.join(innards)})"


node_count = 0
leaf_count = 0

to_visit = [GameState()]

start = time.monotonic()
while to_visit:
    node = to_visit.pop()
    node_count += 1

    print(node)

    if node.terminal:
        leaf_count += 1
    else:
        to_visit.extend([
            GameState(node).takeTurn(True),
            GameState(node).takeTurn(False),
        ])
end = time.monotonic()

calc_seconds = end - start

print()
print(f"leaves: {leaf_count:,}")
print(f"total nodes: {node_count:,}")
print(f"calculated in {datetime.timedelta(seconds=calc_seconds)}")

One interesting property I noticed from this is that there are always $(TotalNodes+1)/2$ leaf nodes. I would have expected something more like $(TotalNodes-1)/2$, with the $-1$ accounting for the root node.

Here are the values I've gotten so far, excluding leaf node counts:

M   N   Nodes
1   1   5 
1   2   5 
1   3   5 
1   4   5 
1   5   5 
1   6   5 
1   7   5 
1   8   5 
2   1   9 
2   2   17 
2   3   17 
2   4   17 
2   5   17 
2   6   17 
2   7   17 
2   8   17 
3   1   13 
3   2   45 
3   3   53 
3   4   53 
3   5   53 
3   6   53 
3   7   53 
3   8   53 
4   1   17 
4   2   97 
4   3   153 
4   4   161 
4   5   161 
4   6   161 
4   7   161 
4   8   161 
5   1   21 
5   2   181 
5   3   405 
5   4   477 
5   5   485 
5   6   485 
5   7   485 
5   8   485 
6   1   25 
6   2   305 
6   3   969 
6   4   1,361 
6   5   1,449 
6   6   1,457 
6   7   1,457 
6   8   1,457 
7   1   29 
7   2   477 
7   3   2,101 
7   4   3,693 
7   5   4,261 
7   6   4,365 
7   7   4,373 
7   8   4,373 
8   1   33 
8   2   705 
8   3   4,177 
8   4   9,409 
8   5   12,217 
8   6   12,993 
8   7   13,113 
8   8   13,121 
9   1   37 
9   2   997 
9   3   7,717 
9   4   22,357 
9   5   33,845 
9   6   38,205 
9   7   39,221 
9   8   39,357 
10  1   41 
10  2   1,361 
10  3   13,409 
10  4   49,553 
10  5   89,769 
10  6   110,257 
10  7   116,649 
10  8   117,937 
11  1   45 
11  2   1,805 
11  3   22,133 
11  4   102,917 
11  5   226,293 
11  6   310,285 
11  7   343,557 
11  8   352,525 
12  1   49 
12  2   2,337 
12  3   34,985 
12  4   201,569 
12  5   540,105 
12  6   845,857 
12  7   997,401 
12  8   1,048,609 
13  1   53 
13  2   2,965 
13  3   53,301 
13  4   374,765 
13  5   1,220,181 
13  6   2,219,725 
13  7   2,840,661 
13  8   3,094,621 
14  1   57 
14  2   3,697 
14  3   78,681 
14  4   665,553 
14  5   2,614,929 
14  6   5,581,009 
14  7   7,897,353 
14  8   9,029,905 
15  1   61 
15  2   4,541 
15  3   113,013 
15  4   1,135,229 
15  5   5,334,853 
15  6   13,410,037 
15  7   21,323,973 
15  8   25,957,165 
16  3   158,497 
16  4   1,868,673 
16  8   73,224,577 
24  3   1,309,809 
24  4   41,210,945 
32  3   5,779,521 
32  4   354,275,073