For those not familiar with Bridge, Whist, & similar games the following is all you need to know about this particular topic.A standard deck of 52 cards is used. The same deck that is used for poker. 13 cards are dealt to each player.Some getting started remarks.For purposes of analyzing the game of bridge or describing a hand, it is usually not necessary to consider the lower cards as being distinct. For example: AK432 is for almost all practical purposes is equivalent to AK765 or AK642. Players often refer to all such holdings as AKxxx. Cards designated by x are called spots, while cards like A, K, Q, & J are called honors. An easy combinatorial problem is to determine the number of possible holdings in a particular suit. This is 2[sup]13[/sup] = 8192 What about the number of holdings if the 2 through the Ten are considered to be spots? This is 10*2[sup]4[/sup] = 160 How about if the 2 through the 9 are considered to be spots? This is 9*2[sup]5[/sup]= 288 For the 2 though the 8 considered to be spots: 8*2[sup]6[/sup] = 512Now the real problem.There are 52!/39!13! = 635 013 559 600 possible hands a player can hold. How many hands are possible if the 2 through the ten are considered to be spot cards? How many if the 2 through the 9 are considered to be spot cards? How many if 2 though the 8 considered to be spot cards?I have not been able to come up with a simple analytical solution to the above problem. A laborious solution can be obtained by considering the 39 possible hand patterns: 4333, 4432, 4441, 5332 . . . . . . . 12 100, 13 000 & applying the values for holding in a suit (Id est: 160, 288, 512 from the easy analysis of suit holdings). Can anyone here come up with a simpler algorithm?
So you have 52 cards made up of 20 honors which are considered unique, and 32 spots which are considered fungible. There may be something more elegant, but off the top of my head I think you'll need to consider each possible number of honors in the hand separately. \({20 \choose 13} + {20 \choose 12} + {20 \choose 11} + {20 \choose 10} + {20 \choose 9}...= 998116\) Thanks WolframAlpha
R. J. Beery: Your post does not provide any real help. I did suggest a laborious approach to the problem, which I do not think you understood.
Yes, it's true that I did not understand your laborious approach to the problem but it appears that you didn't understand mine, either. \(\sum \limits_{n=0}^{x} {y \choose n}\) The above is your equation where {x = number of cards in a dealt hand} and {y = number of honors in the deck}. When x = 13, y = 20 then the answer to your question is 998116. Set y = 24 and solve the equation given. Set y = 28 and solve the equation given. "Simple" is subjective but what I've provided isn't too shabby IMO. EDIT: Back up. The equation is right but if you're considering a 10 to be a spot then there are only 16 honors in the deck, not 20. The answer I gave (998116) is the number of hands possible with 20 honors, which is technically the answer to your "second" question where you were considering 2-9 as spots...
R. J. Beery: Your equation is wrong. If all cards are considered to be significant, C(52,13) is the number of possible hands. In your explanation this would correspond to x = 13 and y = 52 Your equation would result in C(52,0) + C(52,1) + C(52,2) . . . . . + C(52,13) The last (14th) term in your equation is the total number of possible 13-card hands. The first 13 terms in the summation would add to that number, clearly indicating that your equation is incorrect. A correct analysis for 2 thru 10 viewed as spots would consider each of the 39 possible hand patterns.The first two would be 4333 & 4432. Note that there are 16 possible 4-Card suits, 15 possible 3-Cards suits, & 11 possible 2-card suits. If you start with 4333, there are 4 patterns (4333, 3433, 3343, & 3334). This seems to indicate 4*16*15[sup]3[/sup] = 216000 possible hands. Next, the analysis would consider 4432 patterns. There are 12 of these (4432, 4423, 4342, 4324, 4243, 4234, 3442, 3424, 3244, 2443, 2434, 2344). This seems to indicate 12*16[sup]2[/sup]*15*11 = 506880 possible hands Combinational analysis is tricky, so I am not certain of the above, but it is likely to be the start of a correct analysis. The analysis would next consider 4441, 5332, 5440, 5431 . . . . . .12 100 & 13 000 patterns. BTW: There are 24 variations of patterns like 5431 & 6421 It seems to me that 998116 is much lower than the correct number whatever it is for the 2 through the 9 being considered as spots (Id est: Equivalents).
I'm looking at generating functions at the moment in algebra. What you need to do is something like: Given there are 13 cards in each player's hand, how many can be spot cards and how many can be honors? That is, you want to know how many combinations of the two types of cards are possible. Call these c1 and c2, say. Each c is bounded by 0 and 13. So you have a product of two finite polynomials: (1 + c1 + c1[sup]2[/sup] + ... + c1[sup]13[/sup])(1 + c2 + c2[sup]2[/sup] + ... + c2[sup]13[/sup]). You don't actually need to use c1 and c2, just c (because they are the same kind of variable, namely cards, but they could be integers or anything at all like say, pizzas). In fact you don't need finite polynomials, infinite ones work too. They start with 1 because that's c[sup]0[/sup], and a hand can have zero spot cards or zero honors. So it's just (1 + c + c[sup]2[/sup] + ... + c[sup]13[/sup])[sup]2[/sup], and these ones have a closed form which is 1/1-x, so the square is 1/(1-x)[sup]2[/sup], and this is just the sum from k = 0 to infinity of C(n + k - 1, k)x[sup]k[/sup] where n is 2 because the closed form is actually 1/(1-x)[sup]n[/sup]; k is the exponent of the last term in the polynomial which is c[sup]13[/sup]. This is OTH, but I think it's close to the answer. The only other detail is that there are 52 cards to choose from.
Dinosaur: My equation assumes there are more spots in the deck than there are cards in a dealt hand, so it's possible to be dealt no honors, for example. How many "ways" are there to be dealt no honors? The answer is 1, or \(20 \choose 0\) Keep in mind, this says nothing about the ODDS of getting dealt these various hands. If you want to discuss odds then we need to consider the total number of cards in the deck...otherwise the number of cards in the deck is irrelevant, and only the number of honors matters (as long as the spots outnumber the cards in a dealt hand). Does that make sense? The reason your example of 52 honors breaks my equation is because there is no way to be dealt 12 honors, or 11, or 10, etc. Make it a deck of 1052 cards, with 1000 spots, and the equation works just fine. To generalize it for an arbitrary number of spots it would be... \(\sum \limits_{n=z}^{x} {y \choose n}\) The above is your equation where {x = number of cards in a dealt hand}, {y = number of honors in the deck} and {z = x - number of spots in deck, or zero, whichever is greater}.
R. J. Beery: Your POV amazes me: It indicates that you do not have the foggiest idea of how to analyze this type of problem. In post number 4 you made the following statement.The answer I gave (998,116) is the number of hands possible with 20 honors, which is technically the answer to your "second" question where you were considering 2-9 as spots...See if you can follow the following analysis of the 6421 hand pattern, which results in 2,285,568 possible hands for that one pattern.There are 32 possible 6-Card suits; 15 possible 4-card suits; 16 possible 2-cards suits; & 6 possible 1-cards suits. This is simple to analyze. It is based on the binomial coefficients: 1 5 10 10 5 1 The following enumerates the 6-Card suit possibilities. There is only one 6-Card suit with all spots; There are 5 with 1 Honor & 5 spots; There are 10 suits with 2 Honors & 4 spots; 10 with 3 Honors & 3 spots; 5 with 4 honors & 2 spots; 1 with 5 honors & one spot. Total 32 possible 6-card suits. A similar enumeration results in the values of 31, 16, & 6 for suits of 4, 2, & 1 card suits. Hence, there are 32*31*16*6 = 95,232 hands with exactly 6 Spades, 4 hearts, 2 Diamonds, & one Club. There are 24 ways to permute the suit holdings (6421, 6412, 6241, 6214 . . . . . .). This results in 24*95,232 = 2,285,568 possible hands for the 6421 pattern.The above is far larger than the number 998,116 which your formula provided. Note that there are 38 other hand patterns to consider, making your result ridiculously small. Arfa Brane: I would be astonished if this problem can be analyzed using polynomials. It surely seems to require working with permutations & combinations. What do you think of the above analysis of the 6421 hand pattern? A laborious analysis would require including consideration of the other 38 hand patterns. A reality check on my basic approach to analyzing this problem indicates that it will not come up with some silly result.There are 52!/39!13! = 635,013,559,600 possible hands when you treat the 52 cards as distinct. The above analysis indicates 2,285,568 hands with a 6421 pattern: This is one of the 39 possible hand paterns. 39*2,285,568 = 89,137,152 is a rough estimate of the total number of hands if the 2 through the 9 are considered to be equivalent. This is about 1/7000 of the total possible hands. This seems like a plausible number BTW: The 39 basic hand patterns result in 560 permuted patterns when you consider the 4 distinct suits. Permutation & combination problems are tricky. It is easy to come up with erroneous results even when the analysis is reasonable valid. I have been hoping to come up with some easy program which generates the possible hands & counts them. It would be time consuming to program the basic concept suggested above. I could do the calculations on a hand calculator in less time than it would take to write the program & convince myself that it was bug-free.
I know where our problem lies. Due to the wording above I had assumed that a spot was a spot was a spot. This is apparently not true, as the spot's SUIT is still relevant as your previous post suggests. My original analysis counts the number of distinct hands if we ignore the suit of the spots completely, which is why you thought the numbers looked low. The irony here is that, while I don't appreciate the rules of bridge, my father holds a (US) national title in it! Please Register or Log in to view the hidden image! Anyway, if we want to account for the spot suits we would have to multiply each summand by the number of suit combinations which exist for that summand's number of spots. Call this function phi, and we have: \(\sum \limits_{n=z}^{x} {y \choose n}\phi(x-n)\) The above is your equation where {x = number of cards in a dealt hand}, {y = number of honors in the deck}, {z = x - number of spots in deck, or zero, whichever is greater}, and {phi(x-n) = the number of suit combinations of (x-n) spots}. The remaining question would be, how do we calculate phi? If we have a hand with 6 spots, for example, how many potential combinations of Hearts, Clubs, Diamonds and Spades are there? It's a partition function, capped at 4 summands (or addends, if you prefer). It also has the limitation of each summand not being able to exceed the number of spots for a given suit. For example, if I have 2 honors in my hand, I cannot have 11 Heart spots. Sticky but not impossible to formalize. I think you'll find that my analysis works just fine. Perhaps later when I have more time I can write a script to do an exhaustive search of a more limited problem (say, with 5 cards in a dealt hand) and compare that with what my function above produces... Anyway good luck :thumbsup:
R. J. Beery: It is a waste of my time to pay attention to your remarks on this subject or make any further comments directed to you.
You don't follow what I'm saying, fair enough. May I presume that an apology will be forthcoming if and when the script I'll try to find the time to write produces the same answer as my formula?
R. J. Beery: I did intend to ignore further posts by you to this thread. You do have an uncanny ability to be annoying, which prompted this post. Your following post is more nonsense & a pretense to have knowledge/abilities which you obviously lack.You don't follow what I'm saying, fair enough. May I presume that an apology will be forthcoming if and when the script I'll try to find the time to write produces the same answer as my formula?I follow what you are saying very well.You made an insulting implication that I am too dumb to understand your brilliant analysis. You made an arrogant request for a future apology. This is an obvious ploy intended to imply that you have the ability to analyze & solve this problem. The last post you made included some mathematical notation which included an undefined function. Another obvious ploy intended to imply knowledge/ability on your part. Why include the mathematical notation? You could merely write an undefined function, claim it will solve the problem, & say that you will determine the function when you have some time to do so.Put up or shut up! You have posted enough outright nonsense. Please no more verbal diarrhea. If you come up with a solution, be sure to give credit to the person who did the work. You will get no apology from me because I will know that you did not do the work yourself. Perhaps you will deserve some credit for being able to find a person who solved the problem or credit for being clever with Web Searches. BTW: In one of your posts you claim that your father won a national bridge title. You might have mentioned what type of event he won. There several different national events: Life Master Pairs, Men's Pairs, Vanderbilt Teams, the Spingold, et cetera. Please do not do a search & come up with a description of the event to back up your claim. You should have done that when you made the claim. If we were discussing quantum theory would you claim to have an uncle who was a Noble candidate for his work in that discipline?
Dinosaur: Your attitude here is confounding. I was pretty explicit about what phi does; this means there's no wiggle room for it, and replacing it with someone else's solution would not work...unless they were the same solution. The only "sticky" point, I already mentioned: Regarding this: Check out 2004. If you think I had to go find a National Title holder that shared my name, or that I'm writing drivel to impress some Brit on an obscure Physics website...don't flatter yourself. I'm only helping because I found the problem interesting.
Dinosaur: OK the script is done. Click below http://69.175.21.195/bridgehands.php?handsize=13&suithonors=5&verbose=true Changing the parameters should be self-explanatory and should provide access to edge cases that are easy to verify by hand. The code is of my own creation and is precisely what I described in the earlier post (after the clarification of what you were after). I'd also like to say that you seem to have completely misinterpreted by tone, Dinosaur. I wasn't intending to come across as condescending, it was just that it didn't surprise me that you were unable to follow my logic. Your brute-force approach breaks things down by suit FIRST, whereas I delineate between honors and spots, then multiply. Other than that we were both on the same track, I believe. Code: // this function returns the number of ways to partition cards into unique suit arrangements function phi($spots_in_hand, $spots_in_suit, $verbose) { // the partitions shall always be arranged in SHDC order $answer = 0; for ($S = 0; $S <= $spots_in_suit; $S++) { for ($H = 0; $H <= $spots_in_suit; $H++) { for ($D = 0; $D <= $spots_in_suit; $D++) { for ($C = 0; $C <= $spots_in_suit; $C++) { if ($S+$H+$D+$C == $spots_in_hand) { $answer++; if ($verbose) echo($answer.": ".str_repeat("s", $S).str_repeat("h", $H).str_repeat("d", $D).str_repeat("c", $C)."<br>"); } } } } } return $answer; } // calculate binomial coefficient function binomial_coeff($n, $k) { $j = $res = 1; if($k < 0 || $k > $n) return 0; if(($n - $k) < $k) $k = $n - $k; while($j <= $k) { $res *= $n--; $res /= $j++; } return $res; } $hand_size = $_GET['handsize']; $honors_in_suit = $_GET['suithonors']; $verbose = ($_GET['verbose']=="true"); // *********************************************************************************************************************************************** // COUNTING UNIQUE BRIDGE HANDS: honors are unique, spot suits matter, spot values do not matter and are fungible // The theory here is to multiply the number of combinations a specific number of honors can be held in the hand (i.e. a simple "choose" function) // MULTIPLIED by the number of combinations the remaining spots can be represented by the 4 suits (i.e. the "phi" function) // If we do this for all possible numbers of honors held in the hand, we have our answer. The math is therefore in the form of // Sum((nCk)*phi(#spots)) // // Rhoderick J Beery 4/2/2012 // *********************************************************************************************************************************************** // enumerate number of honors in hand $totalhands = 0; $honors_in_deck = 4*$honors_in_suit; for ($honors_in_hand = 0; (($honors_in_hand <= $hand_size) && ($honors_in_hand <= $honors_in_deck)); $honors_in_hand++) { $spots_in_hand = $hand_size - $honors_in_hand; $spots_in_suit = 13 - $honors_in_suit; $number_of_honor_combos = binomial_coeff($honors_in_deck, $honors_in_hand); $number_of_spot_combos = phi($spots_in_hand, $spots_in_suit, $verbose); $product = $number_of_honor_combos*$number_of_spot_combos; $totalhands += $product; echo ("For '$honors_in_hand' honors in the hand there are '$number_of_honor_combos' honor combinations and '$number_of_spot_combos' spot combinations for a total of '$product' combinations.<br>"); } echo ("<br>Hand size: $hand_size<br>Honors in Suit: $honors_in_suit<br>Number of possible hands: $totalhands");
No response, Dinosaur? I gave you exactly what you were looking for. I don't really expect an apology from you but even a "thanks" would go over nicely.
R. J. Beery: Siforums is a very interesting activity for me, but it has a low priority, which is why you have not heard from me for circa 2 weeks.No response, Dinosaur? I gave you exactly what you were looking for. I don't really expect an apology from you but even a "thanks" would go over nicely.Due to trusting some family members, I have meager retirement funds & supplement my social security by directing Bridge games & other activities. The first two weeks in April are very busy for me. I have been helping people with their income tax by allowing them to use TurboTax on my system & giving them some help with mouse clicking, et cetera. Also, quite a few of my affluent computer illiterate friends have returned from warmer climates & need help. Also, the weather starts allowing more golf. Following is a summary of my response to your latest posts.I do owe you an apology for the remark about your father winning a national bridge title. I owe you thanx for coming up with the value of 34,033,880 which verifies some calculations I just finished. Without data from an alternative method, it is always difficult to be certain that permutation/combination calculations are correct. I do not think you devised the method programmed in your Post #14 & may not have actually done the programming.Following are more details relating to the above summary. Mea maxima culpa for my remark about your father. I came to hasty erroneous conclusion. I have seen many take advantage of Web anonymity & make false claims. Since you did not mention your father’s accomplishment in your first or second post, I assumed it was not a valid claim. If I were involved in a bridge-related discussion & had a father who won an important title, one of my early remarks would be something like: “BTW: My father . . . . . ." The ACBL Bridge Encyclopedia (7th Edition) lists a Rod Beery as having over 7500 Master Points (a note worthy achievement); It also lists him as winning the Grant Baze Senior Knockout Teams in 2004. I assume that this is your father. BTW: Acquiring 7500 master points is an achievement (less than 600 have that many), perhaps more noteworthy than winning the Team of 4 title. Except for the Spingold, Vanderbilt & some international team events, it is possible to win Knockout team events by unusual luck. It takes more than luck to get 7500+ master points. I know some good bridge players who hire professional partners & fail to get even 3000-4000 master points. Not sure why you think I am a Brit (Your Post #13). It is a trivial unimportant error. I live in SE Pennsylvania, & wonder if your father will be coming to Philadelphia in July for the Summer North American Bridge Championships. I will be entered in the Von Zedwitz Life Master Pairs & perhaps the Wernher Open Pairs. I do not expect to be in the top 50 in either event & might not qualify for the finals of either. The competition is those events is formidable. Might your father have been in Philadelphia for the World Bridge Federation Championships in 2010? I played in the Mixed Pairs with my life partner, Gloria. I did not expect to be in the top 50, but expected to do better than we did. Gloria was unnerved by the diagonal barrier separating us (your father can explain). It was her first experience with the playing conditions encountered in major events. Due to the SciForum Thread, I took time to use a Spread Sheet to implement the method mentioned in my Post #5 & described in slightly more detail in my Post #8. Attached is a Word Document to which the spread sheet data was copied. I owe thanx for your post #14, which verifies the data I generated. I also have spreadsheet data for suits consisting of AKQJ & 9 Spots; AKQJT9 & 7 spots. Totals are 4,582,640 & 194,911,952 total hands. My interest in this analysis is due to an intent to write a program which generates all possible hands & which will derive statistics enabling comparison of various bidding systems. This analysis will allow me to estimate runtime & storage requirements for the programming project. Writing programs for fun is one of my time consuming activities. Now regarding your solution/analysis from Post #14First: It is an implementation of the method briefly described at the end of my Post #8: “I have been hoping to come up with some easy program which generates the possible hands & counts them.” Second: Your Post #9 describes a method using a summation of products. Each product has a multiplicand which is Combination(y,n) & a multiplier with is a function of (x-n). The method used in your Post #14 does not use a function: It uses a program which generates possible spot holdings & counts them. This is an implementation of my Post #8 suggestion, which you probably did not notice at the time you wrote up Post #9 If you really devised the method of Post #14, why did you describe the use of a function instead of describing the counting of possible spot combinations? I think the answer is obvious: You either did not devise this method or else you reread my Post #8 & implemented the counting process with a program. It is my guess that you found the solution via a Web Search or have a friend who did the job for you. If you wrote the program used in your Post # 14, you got the method from somebody else. It is a counting method, not a method using a function.BTW: Due to being a bridge player, I am focused on hands consisting of 4 suits. I probably would not have conceived the program used in your post #14, which treats sginificant cards without regard to their suit.
Dinosaur: I had written off hearing back from you, and then you write back with both a thanks AND an apology; your maturity level is noteworthy and I respect that. Yes, my dad kicks ass but I didn't ask if you knew him because I erroneously thought you were British. No biggie. I cannot tell you his tournament plans but our last name is fairly unique so you could always keep an eye out for him. He dabbled as a professional bridge player for a bit, but lately he's been playing poker... As far as the script goes, I wrote it all, with no supplemental sources. The script is not generating all possible hands. It's an algorithm. If you doubt me, check out 26 hand sizes with 10 suit honors. It produces the answer 28,771,969,976,808 in a fraction of a second. I mean, I'm a decent programmer but no amount of genius would be able to do this by simply "counting the hands" on normal hardware. Yes, my post #9 is a summation of products and the script is a summation of products! My "phi" function is certainly function in the CS sense. It does exactly what I described before: I didn't use the partition function but that's still an option. Actually your post #5 refers extensively to "partition function capped at 4 summands" but you were probably unaware of it (and of course you were combining the honors and spots which caused problems). Anyway my phi solution in code is much simpler, actually, if not as elegant, as implementing the partition function (which wasn't native to PHP...so I went a lazier route). Plus, it gives the RIGHT ANSWER...isn't that the point? After the thanks and the apology, you end your post with a slap in the face. Tell you what, Dinosaur, YOU find my script or anything close to it on a Web Search; I challenge you to. I tell you it's my own work and if you're going to continue questioning that point then you're willfully blind for mysterious reasons. Anyway, you posted an interesting puzzle and I'm satisfied that I found the solution. I don't really care one way or the other how you think I arrived at the solution but it does affect how I'll interact with you in the future. Cheers
