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

Offline tothederby

  • Villein
  • ***
  • Posts: 32
  • 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: https://www.carcassonnecentral.com/community/index.php?topic=4238.0

Offline Sinscerly

  • Viscount
  • ****
  • Posts: 829
  • Merit: 30
  • 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 »
"What things can you find? Things that are hidden?
Do you know The WikiCarpedia?

Offline Whaleyland

  • Great Khan
  • Global Moderator
  • Marquis Chevalier
  • *
  • *
  • Posts: 2743
  • Merit: 101
  • Toulouse: Carcassonne's insignificant neighbor.
    • View Profile
    • Derek R. Whaley, PhD | Librarian, Historian, and 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

  • Viscount
  • ****
  • Posts: 829
  • Merit: 30
  • 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: 32
  • 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

  • Chatelain
  • ******
  • Posts: 1293
  • Merit: 49
  • 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: 32
  • 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: 32
  • 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

  • Viscount
  • ****
  • Posts: 829
  • Merit: 30
  • 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

  • Owner
  • Chatelain Grand Officier
  • *
  • *
  • Posts: 6292
  • Merit: 456
  • 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 »
Questions about rules? Check WICA: wikicarpedia.com

t2k

  • Guest
Re: How many ways can you combine the official expansions
« Reply #10 on: December 28, 2019, 12:54:55 PM »
This to me, is always a silly question unless you want to get just numbers like a math problem.  Just adding all the expansions together is like combining all the liquors  and ingredients from a bar and seeing how they will taste, and that is truly terrible.  The better question might be, "what expansions fit together to make a practical and more interesting game?"  Then, you have an experience worth noting and repeating.  Think around the box and not just inside or outside.

Offline Meepledrone

  • Owner
  • Chatelain Grand Officier
  • *
  • *
  • Posts: 6292
  • Merit: 456
  • It is full of... Meeples!!!
    • View Profile
Re: How many ways can you combine the official expansions
« Reply #11 on: December 29, 2019, 01:15:23 PM »
Of course, this was just a mathematical exercise.

In our case, as you mention, the interesting point is what expansions fit better together or even what expansions fit better together to boost/improve XXX, YYY, ZZZ in a game. This is the golden question for everyone.

Offline totor66

  • Count
  • **
  • Posts: 344
  • Merit: 18
  • Carcassonne semi completionnist
    • View Profile
Re: How many ways can you combine the official expansions
« Reply #12 on: January 03, 2020, 01:16:04 AM »
For me what's best is

base game + 1 large expansion + 2 minis (just one mini on 2 player game)

Not too complex but adds a bit of length to the game

I alternate CI and CII, depending on what's available on hand
Carcassonne Fan since 2014

Offline Decar

  • Owner
  • Chatelain Grand Officier
  • *
  • *
  • Posts: 6719
  • Merit: 317
  • Shut up and take my money!
    • View Profile
    • tehill.net
Re: How many ways can you combine the official expansions
« Reply #13 on: January 03, 2020, 01:57:18 AM »
base game + 1 large expansion + 2 minis (just one mini on 2 player game)

When playing with 2 players, I now like to play with base game + 1 mini, although this is good too.
For me it takes too long checking all the rule interactions otherwise, and there's too much going on for my little head.

The last big game I played was during the 1st International Meetup: Expansions 2, 3 & 10 and basegame with abbot and river.  That took us quite some time with 5 players!


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
Many ways to use a cxxx tile

Started by Vinçon

10 Replies
4169 Views
Last post December 11, 2017, 12:04:32 PM
by thodekey
xx
How many times can you score 3 points for a fairy in a single turn?

Started by rfielder

1 Replies
6594 Views
Last post June 06, 2014, 11:26:50 AM
by Carcking
xx
How to combine Robbers and Messages minis?

Started by CarcAddict

5 Replies
8432 Views
Last post November 04, 2017, 12:41:14 PM
by Halfling
xx
How many meeples can be placed one tile in a game - Challenge by LunarHexagon

Started by Bumsakalaka

10 Replies
2102 Views
Last post September 25, 2021, 04:21:55 AM
by Bumsakalaka
xx
Clarification -- "Count, King & Robber" -- how many meeples can be played?

Started by RJ-NoVA

2 Replies
354 Views
Last post January 16, 2024, 06:54:23 AM
by RJ-NoVA