Author Topic: How many ways can you combine the official expansions  (Read 219 times)

Offline tothederby

  • Villein
  • ***
  • Posts: 27
  • Merit: 1
  • I haven't updated my profile yet!
    • View Profile
How many ways can you combine the official expansions
« on: March 13, 2019, 02:48:59 PM »
How many ways can you combine the mini and major expansions with the base game?  For instance Watchtowers and the Crop Circles can be combined to form the following games: base game on its own, base game + crop circles, base game plus watchtower and base game plus watchtower plus crop circles.  Answer is 4.

So if there are 38 expansions how many games can you construct in this manner?

[I have included each of the following as an expansion: Inns & Cathedrals, Traders and Builders, The Princess and the Dragon, The Tower, Abbey and Mayor, The Catapult, Bridges, Castles & Bazaars, Hills & Sheep, Under the Big Top, The Wheel of Fortune, The Fliers, The Messengers, The Ferries, The Gold Mines, The Mage & Witch, The Robbers, The Crop Circles, The Cathars / Siege / Besiegers (counted as one expansion), The Mini-Expansion GQ11, The Tunnel, The Plague, The Halflings, The School, The Phantom, The Festival, The Little Buildings, The Wind Roses, The Special Monasteries (German, Dutch, Japanese - counted as one expansion), The German Castles, The Watchtowers, The German Cathedrals, The Labyrinths, The Markets of Leipzig, The Fruit-Bearing Trees, The Barber-Surgeons and from Expansion 6 each of (counted as separate expansions): The King, The Count / City of Carcassonne and The Cult / Shrines (counted as one expansion).

I appreciate this labelling of expansions has subjectivity but the challenge is not about the labelling, but about the number of combinations that arises.]

Linkback: http://www.carcassonnecentral.com/community/index.php?topic=4238.0

Offline Sinscerly

  • Marquis
  • ***
  • Posts: 520
  • Merit: 17
  • Loving to play.
    • View Profile
    • WikiCarpedia - Wiki-CAR
Re: How many ways can you combine the official expansions
« Reply #1 on: March 14, 2019, 04:23:11 AM »
Well there are to many  ;D in worst case you use all 38 expansions and in the minimal case you use 1

Note, not counting expansions of the same expansion. :o So not twice Crop Circles in ONE game.

So 38, for one.
So 38 * 37 for two
So 38 * 37 * 36 for three
ext...
So 38 * 37 * 36 * 35 * 34 .... * 2 * 1

Now count all up and you will come to the answer, I know there is a formula for this, but I cann't remember

Dunno if correct: 523022617466601111760007224100074291200000000
Correct if I wrote it good: 1421722876932548239555534242726381983188762660
Correct one: 523022617466601111760007224100074291200000000


I was to lazy to type all this in my calculator so a simple script that runs through all

« Last Edit: March 14, 2019, 05:22:42 AM by Sinscerly »
“It is not necessary to change. Survival is not mandatory.”

Offline whaleyland

  • Great Khan
  • Authors
  • Marquis Chevalier
  • *
  • *
  • Posts: 2473
  • Merit: 78
  • Toulouse: Carcassonne's insignificant neighbor.
    • View Profile
    • Derek R. Whaley | Historian & Writer
Re: How many ways can you combine the official expansions
« Reply #2 on: March 14, 2019, 05:00:10 AM »
Sinscerly, I think your first answer was correct. The formula is ! (factorial) and I got (for 38 expansions) 52,300,226,174,666,012^28. In other words, the combinations are near-infinite.

The list below is missing The River I, The River II, Darmstadt, and five separate Spiel tiles. And Halflings I and Corn Circles I are definitely both different expansions, albeit ones with the same rules, so those get added too. Total expansions are thus 46, giving us a grand total of 5,502,622,159,812,089^42 combinations. Just a bit more.  ;D

Offline Sinscerly

  • Marquis
  • ***
  • Posts: 520
  • Merit: 17
  • Loving to play.
    • View Profile
    • WikiCarpedia - Wiki-CAR
Re: How many ways can you combine the official expansions
« Reply #3 on: March 14, 2019, 05:21:39 AM »
Sinscerly, I think your first answer was correct. The formula is ! (factorial) and I got (for 38 expansions) 52,300,226,174,666,012^28. In other words, the combinations are near-infinite.

The list below is missing The River I, The River II, Darmstadt, and five separate Spiel tiles. And Halflings I and Corn Circles I are definitely both different expansions, albeit ones with the same rules, so those get added too. Total expansions are thus 46, giving us a grand total of 5,502,622,159,812,089^42 combinations. Just a bit more.  ;D

Hmm I am not sure... as it's the sum of all the combinations with 38 expansions. I thought the first one is only when I don't add them up, but I have to revisit maybe my code.  ::) It's quite a difference if it's the first one :))

But I think you are right. As I see an error in my code

Offline tothederby

  • Villein
  • ***
  • Posts: 27
  • Merit: 1
  • I haven't updated my profile yet!
    • View Profile
Re: How many ways can you combine the official expansions
« Reply #4 on: March 14, 2019, 07:03:23 AM »
Thanks for the responses Sinscerly and Whaleyland.

I think its a good sized number but not as big as you are suggesting.

Offline Halfling

  • Baron
  • *****
  • Posts: 993
  • Merit: 47
  • Welcome tournament 2015 winner.
    • View Profile
Re: How many ways can you combine the official expansions
« Reply #5 on: March 14, 2019, 07:14:18 AM »
I have played a good number of combinations at work where we have weekly games. We have also enjoyed 7 different campaigns each of which included all available expansions at time of playing. I thought we must be doing well with perhaps 200 to 300 different Combinations over the 4.5 years.... But if there are really that many combinations out there we have barely scratched the surface.
The Geek shall inherit the earth if we get a good die role

Offline tothederby

  • Villein
  • ***
  • Posts: 27
  • Merit: 1
  • I haven't updated my profile yet!
    • View Profile
Re: How many ways can you combine the official expansions
« Reply #6 on: March 15, 2019, 11:16:38 AM »
The figure I come up with, rounded, is 275 billion.  If two more expansions were added, options suggested by Sinscerly and Whaleyland, this would bring the figure to approx. 1.1 trillion (or exactly 1 terabyte of game combinations).

Offline tothederby

  • Villein
  • ***
  • Posts: 27
  • Merit: 1
  • I haven't updated my profile yet!
    • View Profile
Re: How many ways can you combine the official expansions
« Reply #7 on: March 15, 2019, 01:18:02 PM »
Just to give my working:

with 1 base game (B) plus 2 expansions (E1 & E2), the combinations are: B, B+E1, B+E2,B+E1+E2 = 4 combinations = 2 to the power of 2
with 1 base game plus 3 expansions: B, B+E1, B+E2, B+E3, B+E1+E2, B+E1+E3, B+E2+E3, B+E1+E2+E3 = 8 = 2 to the power of 3
with 1 base game plus n expansions: combinations = 2 to the power of n

I guess sticking with the expansions you like best is a good approach - there is not enough time to play all the combinations!
 
Pinning down the rules well with so many possible interactions is also important......

Offline Sinscerly

  • Marquis
  • ***
  • Posts: 520
  • Merit: 17
  • Loving to play.
    • View Profile
    • WikiCarpedia - Wiki-CAR
Re: How many ways can you combine the official expansions
« Reply #8 on: March 16, 2019, 02:07:34 AM »
I don't count the base game as combination. So, only counting all the combinations that were possible to make with the expansions. So in that case I would only need to put 1 more on my numbers  ::) C:-)

Offline Meepledrone

  • Nobleman
  • ******
  • Posts: 106
  • Merit: 18
  • It is full of... Meeples!!!
    • View Profile
Re: How many ways can you combine the official expansions
« Reply #9 on: March 16, 2019, 05:19:48 AM »
Hi all!

This question has an easy mathematical answer if you apply basic Combinatorics.

Short answer:

The number of combinations will be (2 ^ n) - 1, where n is the number of expansions considered, as we want to rule out the base game alone.

For n = 38, you get 274,877,906,943 combinations.

The figure I come up with, rounded, is 275 billion.  If two more expansions were added, options suggested by Sinscerly and Whaleyland, this would bring the figure to approx. 1.1 trillion (or exactly 1 terabyte of game combinations).

@tothederby, you are right.  ;D


Long answer:

>> Naughty factors!

Using factors (and factorials) is okay to count permutations of n elements, but misses the point when counting subsets a larger group as repetitions are not ruled out. Let me explain:

Well there are to many  ;D in worst case you use all 38 expansions and in the minimal case you use 1

Note, not counting expansions of the same expansion. :o So not twice Crop Circles in ONE game.

So 38, for one.
So 38 * 37 for two
So 38 * 37 * 36 for three
ext...
So 38 * 37 * 36 * 35 * 34 .... * 2 * 1

Now count all up and you will come to the answer, I know there is a formula for this, but I cann't remember


For 38 expansions E1... E38, it is okay: there 38 options.
For 37 expansions we start to have problems. as you will count twice each subset: E1+E2 and E2+E1 are considered different permutations, so they are counted twice. So you should consider 38 * 37 / 2.
For 36 expansions, we have a similar situation but each subset is counted six times: E1+E2+E3, E1+E3+E2, E2+E1+E3, E2+E3+E1, E3+E1+E2, E3+E2+E1 are considered different permutations. So you should consider 38 * 37 * 36 / 6
And so on...

So we need to remove those repetitions...


>> k-Combinations and Binomial Coefficients are my friends :))

In order to count subsets (formally k-combinations) you have to use binomial coefficients. Don't run away yet! This is simpler than it looks.

A k-combination of a set S is a subset of k distinct elements of S.  In our case S represents our 38 expansions and k is the size of the subsets from 1 to 38. 0 would represent the base game alone.

Binomial coefficients, simply put, use factorials but correct the result to eliminate the repetitions I mentioned earlier:



If you pay attention, you'll see that the numerator n * (n-1) *...* (n - k + 1) corresponds to the factors Sinscerly was using. The denominator represents k! (i.e., 2! = 2, 3! = 6,... ) that eliminates the repetitions I mentioned above.

So, now we can count "easily" the number of combinations for our  n = 38 expansions in groups of k expansions. What if we want to sum them all for k = 1 to 38?

Well, we are lucky that binomial coefficients behave well and, long story short, the can be added easily:



So, this means that the sum of all our n= 38 expansions in subsets of sizes from k=0 to k = 38 would be 2 ^ n. In order to eliminate the base game, we have to subtract the subset with k = 0. Taking into account that



we will have that our final result will be (2 ^ n) - 1.

So for n = 38 expansions, we will have  (2 ^ 38) - 1 = 274,877,906,943 combinations without the base game alone.


For more background info, see: https://en.wikipedia.org/wiki/Combination

Cheers!
« Last Edit: March 18, 2019, 06:35:00 AM by Meepledrone »


Share via delicious Share via digg Share via facebook Share via furl Share via linkedin Share via myspace Share via reddit Share via stumble Share via technorati Share via twitter

  Subject / Started by Replies / Views Last post
xx
Where to download official expansions?

Started by Qball

3 Replies
1744 Views
Last post July 02, 2013, 12:27:11 PM
by Scott
xx
CC fan expansions going official ... any progress ?

Started by Sekim

3 Replies
2128 Views
Last post February 21, 2013, 06:29:11 AM
by Scott
xx
How to combine Robbers and Messages minis?

Started by CarcAddict

5 Replies
2226 Views
Last post November 04, 2017, 12:41:14 PM
by Halfling
xx
Many ways to use a cxxx tile

Started by Vinçon

10 Replies
882 Views
Last post December 11, 2017, 12:04:32 PM
by thodekey
xx
Will We Ever Get an Official Announcement?

Started by Ry4Christ

5 Replies
1272 Views
Last post December 21, 2016, 02:25:29 PM
by Decar