Friday bridge math puzzle! 
[Jan. 19th, 200708:19 am]
Greg

onefishclappin forwarded me this fascinating puzzle yesterday, and I thought "Ooh, I should figure this out", then started thinking about it, then went back to work for about 5 seconds, then gave up and worked it out (roughly). Here it is:
After you've dealt out a hand, are there more different legal ways to play out the hand, or more ways to bid the hand?
Here, only legal plays and bids are counted, so no bids or plays out of turn, insufficient bids, revokes, etc. Other than that, the plays or bids don't have to make any particular bridge sense, they just have to be legal.
There are few things I like better than a good combinatorics puzzle. Here's the analysis I sent her, along with some better numbers: (don't read if you want to try it yourself!)
My gut instinct was that there were more ways to play out the hand, so let's look at that first. It depends what the hands are (since you have to follow suit), but there are at most 13!^4 ways to do this, and you can achieve this is each player is dealt a full suit of cards (each player can play their cards in any order). The least number of ways would be if each person got a 4333 distribution, and is something like (13!/(4!*3!*3!*3!))*(3!^4)^4 ((13!/(4!*3!*3!*3!) for the order the suits are played in, 3!^4 for the order of cards in a suit for each person, and the ^4 for all 4 suits). That's just an estimate, though: 13!^4 is definitely an upper bound.
The number of ways to bid is a little more tricky. If you're not familiar, there are 35 "normal" bids (17 in clubs, diamonds, hearts, spades, and notrump) and the bids have to be in ascending order (or pass). If the other team bid, you can double, which means that they can then redouble, both of which are cancelled when a new "normal" bid is made. The bidding is ended by three passes.
My first analysis said that there are 2^35 choices for which bids are made along the way, and there are around 10 ways for transitioning from bid to bid (number of passes and doubles & redoubles), so that would give (2*10)^35. This isn't quite right, though: firstly there are 21 ways to transition between bids (see below for a list). More importantly, it's really the sum from i=0 to 35 of 4*(35 C i)*21^(i1)*7, where i is the number of "normal" bids that are made (4 for number of passes at the beginning, 7 is the number of ways to go from the last bid to the end of the bidding). I think that's right (although the i=0 case is wrong; it should be 1, since the only way to have 0 bids is four passes). So, this is 1 + 28 * sum from i=1 to 35 of (35 C i)*21^(i1). Hmm, not sure off the top of my head to simplify this, but a quick script to compute this gives 128745650347030683120231926111609371363122697557 (1.287*10^47), which is the answer that the sender of the email got and the answer found elsewhere too. So I got lucky that my initial estimate was fairly wrong in concept, it ends up being close to the same! (20^35 is 3.44*10^45)
And 13!^4 is "only" 1.5*10^39, so the answer is that there are one million times as many ways to bid a hand than to play it (and really, more than that for most usual hands). Fascinating problem  thanks onefishclappin!
List of bid transitions: this is the list of the 21 ways to get from one bid (B1) to the next bid (B2) while keeping the auction alive. p=pass, D=double, R=redouble. It took a few minutes to get these right! B1 B2 B1 p B2 B1 p p B2 B1 D B2 B1 D p B2 B1 D p p B2 B1 p p D B2 B1 p p D p B2 B1 p p D p p B2 B1 D R B2 B1 D R p B2 B1 D R p p B2 B1 D p p R B2 B1 D p p R p B2 B1 D p p R p p B2 B1 p p D R B2 B1 p p D R p B2 B1 p p D R p p B2 B1 p p D p p R B2 B1 p p D p p R p B2 B1 p p D p p R p p B2
Update: a nice simplification of the number of auctions that doesn't require a script!


