Author Topic: TREES question for my next variant.  (Read 774 times)

Offline Carca_Maker

  • Freeman
  • ****
  • Posts: 66
  • Merit: 1
  • I haven't updated my profile yet!
    • View Profile
TREES question for my next variant.
« on: July 08, 2019, 02:06:07 PM »
Hi everybody!
I'm working on my Carcassonne variant about some "elements", but I'm stopped at this point:

To build a sets of 3, (and in the other side) , sets of 4 of this “elements". ("Triple",  and "Quaterna" respectively?).  Sets of one, and two elements are trivial.

So we are at this starting point:

*We have got an amount of 10 elements: one "1", two "2", three "3", and finally four "4“.

A) If we extract randomly  THREE of them without replacement, how many cases are at all at every single branch?. (See my accompanying trees of three extracted elements).

I think that repeated sets of this  three elements are considered as "different" cases, although they have got the same composition.

So it looks that it doesn't matter the way, the order in that this elements are considered.

Every branch of this could be ordered in any order. It only matters its composition and how many repeated times appears every case inside its own branch.

Very important: although for example, we have extracted one "2", this is DIFFERENT  from the other existing "2", this means that at the end we could have got apparently some "repeated cases", but they have to be seen as "DIFFERENT", although belonging to the same  branch, of course.

I estimated approximately among 720 cases at all, at all the "triplets" trees, but I'm not sure if it's true.

I followed my own describing graphical order, where I began by the most unusual, uncommon element to the most frequent elements, in my trees.

B)The same for the sets, branches,  of FOUR of this extracted elements from the total amount of this 10 possible elements, (without replacement, etc).

Finally, a basic question:
It would be a  clarification for me to knowing how many cases are the most representative branches "1234", and "4444“,  separately, for example. Thanks.

I would include the helpers and solvers of this questions at the acknowledgements of my variant, and I would give a "+1“s thanks to them.

POSDATA: I wonder also if anyone can tell me if I could write all this in Spanish, my usual language. Is it possible too?. Greetings from Carca_Maker.


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

Offline Carca_Maker

  • Freeman
  • ****
  • Posts: 66
  • Merit: 1
  • I haven't updated my profile yet!
    • View Profile
Re: TREES question for my next variant.
« Reply #1 on: July 08, 2019, 02:11:37 PM »
Sorry... Maybe the two images that I accompanied are too big for a smartphone screen? Tell me if it does. Carca_Maker.

Offline Meepledrone

  • Global Moderator
  • Viscount
  • *
  • Posts: 701
  • Merit: 66
  • It is full of... Meeples!!!
    • View Profile
Re: TREES question for my next variant.
« Reply #2 on: July 08, 2019, 02:22:23 PM »
The two images you uploaded are huge.

However, something weird is happening with images. I just uploaded one and the Forum is displaying it full size instead of a thumbnail you can click and magnify.

Offline Carca_Maker

  • Freeman
  • ****
  • Posts: 66
  • Merit: 1
  • I haven't updated my profile yet!
    • View Profile
Re: TREES question for my next variant.
« Reply #3 on: July 08, 2019, 02:31:38 PM »
Meepledrone, I sized both two images when I uploaded them, to a A4 printable size. I don't know if that is the matter of the trouble. I'm going to souper, it's late, and disconnect. Bye.

Offline wolnic

  • Marquis
  • ***
  • Posts: 569
  • Merit: 74
  • Ummm and Ahhh! Can't decide!
    • View Profile
Re: TREES question for my next variant.
« Reply #4 on: July 08, 2019, 03:04:12 PM »
The two images you uploaded are huge.

However, something weird is happening with images. I just uploaded one and the Forum is displaying it full size instead of a thumbnail you can click and magnify.

I noticed that last night, too, when I uploaded the sample Cliffs tile ...
Complete: Cliffs&W'falls (C1/2), Coast (C1/2), Fluvium (C2), Wells (C2), Jordan River 2 (AotC)
Development: Stone Circles (C1/2), Woodcutters/Forests/Autumn/Sakura (C2),  Rivers&Lakes (C1), Harvest (C1/2), WinterEdge (C1), WinterCoast (WD/WE), Catch Of The Day (C1/2/WD) and others.

Offline Meepledrone

  • Global Moderator
  • Viscount
  • *
  • Posts: 701
  • Merit: 66
  • It is full of... Meeples!!!
    • View Profile
Re: TREES question for my next variant.
« Reply #5 on: July 08, 2019, 04:15:10 PM »
Hi Carca_Maker,

The size of the images should be displayed smaller, no matter the real size.

In any case, I wanted to verify if I understood your question correctly.

1. The elements: As far as I understood your elements belong to 4 categories but they are different. If so, may I call them univocally with an ID the represents the category plus a letter to be able to tell them apart:
    - one "1": 1A
    - two "2": 2A, 2B
    - three "3": 3A, 3B, 3C
    - four "4“: 4A, 4B, 4C, 4D

2. Extractions: I'm assuming the order of the elements is irrelevant and you are only interested in the elements of the subsets. In this case, you are representing each extraction and sorting the elements by ID. This would lead to a series of sorted extractions that could be grouped and represented as tree branches.

If so all your elements are unique, the number triplets and quadruplas can be computed with binomial coefficients if the order of the elements in one extraction is irrelevant:



For triplets:
n = 10 and k = 3 --> 120 extractions

For quadruplas:
n = 10 and k = 4 --> 210 extractions

Let me know if this is what you were looking for.

Cheers!
« Last Edit: July 09, 2019, 12:02:34 AM by Meepledrone »

Offline Meepledrone

  • Global Moderator
  • Viscount
  • *
  • Posts: 701
  • Merit: 66
  • It is full of... Meeples!!!
    • View Profile
Re: TREES question for my next variant.
« Reply #6 on: July 09, 2019, 12:44:48 AM »
The two images you uploaded are huge.

However, something weird is happening with images. I just uploaded one and the Forum is displaying it full size instead of a thumbnail you can click and magnify.

I noticed that last night, too, when I uploaded the sample Cliffs tile ...

Hi wolnic,

I reported this issue to gantry along with the Download area issue just in case they are connected (although it seems unlikely to me.)

http://www.carcassonnecentral.com/community/index.php?topic=4299.msg63615#msg63615

Cheers!

Offline Carca_Maker

  • Freeman
  • ****
  • Posts: 66
  • Merit: 1
  • I haven't updated my profile yet!
    • View Profile
Re: TREES question for my next variant.
« Reply #7 on: July 09, 2019, 10:46:31 AM »
Hello Meepledrone!
I'm not still familiarized with "quote" action, though my smartphone, it's difficult seeing from it. Sorry. I'm going to talk from "recently" memory.

That's a good idea to identify the four kinds of elements with A, B, C, D.

I can say that your two calculations, look like, seem to "unify" some cases belonging to a "upper", category of cases. "120“ cases, and "210“ approximately in the other hand, it seems to me a nice approximation to the goal, because it's not a huge amount of rather cases. But I don't still know what does it means, so brief numbers. 

Now, the question is how to FIT  your first calculation,  to the most simple cases, that I know and I calculated too: the PAIRS of elements. (And the trivial singles cases too in one table).

I would be glad if your mathematical model can get to, describe the same as my table of pairs.
This is, how many cells are belonging to each pair, etc?. That's the question that I need for first approximation, for every trees and its branches.

Posdata: The cells of this pairs table are empty, because are an example.Thanks.


Offline Meepledrone

  • Global Moderator
  • Viscount
  • *
  • Posts: 701
  • Merit: 66
  • It is full of... Meeples!!!
    • View Profile
Re: TREES question for my next variant.
« Reply #8 on: July 09, 2019, 01:42:20 PM »
Hello Meepledrone!
I'm not still familiarized with "quote" action, though my smartphone, it's difficult seeing from it. Sorry. I'm going to talk from "recently" memory.

Hi there, Carca_Maker!

I've been using the "quote" action in several ways:

1. Quoting a previous message when posting a new message: You can do this by clicking on the "Quote" button on the right side of the header of the post you want to quote.

2. Quoting a previous message in the thread while you are editing: Just position your cursor where you want to insert the quote, scroll down and click on the "Insert Quote" button on the right side of the header of the post you want to insert.

3. Inserting a dummy quote in a message: click the "insert quote"  button on the toll bar represented by a text baloon () or type the following:

Code: [Select]
[quote]Blah blah blah [/quote]
You can edit the text of the quoted post to keep the parts you need or split it in sections by closing and opening "quote" tags to the text, as I'm doing in this post to reply inline.

Example:

Code: [Select]
[quote author=Carca_Maker link=topic=4332.msg63629#msg63629 date=1562694391]
Hello Meepledrone!
I'm not still familiarized with "quote" action, though my smartphone, it's difficult seeing from it. Sorry. I'm going to talk from "recently" memory.
[/quote]

My comments... before repeating the header and continuing with the quoted post

[quote author=Carca_Maker link=topic=4332.msg63629#msg63629 date=1562694391]
That's a good idea to identify the four kinds of elements with A, B, C, D.
....
[/quote]

Hope this helps.  :D

That's a good idea to identify the four kinds of elements with A, B, C, D.

Keep this in mind, I'm going to use it below.

I can say that your two calculations, look like, seem to "unify" some cases belonging to a "upper", category of cases. "120“ cases, and "210“ approximately in the other hand, it seems to me a nice approximation to the goal, because it's not a huge amount of rather cases. But I don't still know what does it means, so brief numbers. 

Now, the question is how to FIT  your first calculation,  to the most simple cases, that I know and I calculated too: the PAIRS of elements. (And the trivial singles cases too in one table).

We are closer than you think. The key point here is if you are considering permutations or not in your pairs: For example: In the "4,4" pairs you may have 4A-4B and 4B-4A... Are you considering them to be the same pair or not?

I was assuming they are, but your example is counting them as different pairs. If so, we have to factor back in the possible permutations of the elements in the triplets and quadruplas.

I would be glad if your mathematical model can get to, describe the same as my table of pairs.
This is, how many cells are belonging to each pair, etc?. That's the question that I need for first approximation, for every trees and its branches.

Posdata: The cells of this pairs table are empty, because are an example.Thanks.


Let me elaborate how you can simplify your computation if using pairs...

First, back to the binomial coefficient. This formula defines the number of subsets of size "k" you can make with "n" elements, where the order of the elements in a subset is unimportant (for example, how many different teams with 3 (k) people could you create with a total 10 people (n)?): 



The numerator N = n * (n - 1) * ... * (n - k + 1) calculates the number of subsets.

The denominator D = k * ( k - 1 ) *... * 2 * 1  calculates the number or permutations you have within a set.

In your example, n = 10 and k = 2. Thus,

N = 10 * ... * (10 - 2 + 1 ) = 10 * 9 = 90

D = 2 * 1 = 2

There is no magic here: You have 10 elements, you pick 1 out of 10 and then you have 9 left to choose from. So you have 10 for your first pick and 9 left for your second pick. That is, 10 * 9 = 90 combinations in total. So here you stop after two picks.

Analogously, the logic for the number of permutations with two elements is similar: you have 2 elements, you pick 1 out of 2 and then you have only 1. So you have 2 for your first pick and only 1 left for your second pick. That is, 2 * 1 = 2 permutations in total. For example, if you have a set with two elements 4A and 4B, there are two possible permutations (4A,4B) and (4B,4A.) Top notch?

So getting back to you example, we have the following two scenarios.

1. Element order is considered for pairs: the same elements in different order represent different pairs (as per your example)

Here the result is N, as per the equations above. We want to calculate all the possible subsets without removing the possible permutations within each set.

So the result is N = 90, that matches your result for pairs with 10 elements. By the way, this result matches as well the number of cells in your grid if you remove the cells in the diagonal. Makes sense, right?  :o

2. Element order is NOT considered for pairs: the same elements in different order represent different pairs (as per my calculations)

Here the result  is N/D = 90 / 2 = 45, This would match the number of cells in your grid above (or below) the diagonal. This reminds me s the distance charts you may find around:



You only need a triangle (half of the square grid) as the distance between any two cities is the same no matter which one you pick first.

So, in my previous post I was working with this scenario.



So how do we generalize all this?

Let n be the number of elements and K the size of the subsets you want to create.

Case #1: Elements in different order represent different sets

For this case use:

Combinations = N(n, k) = n * (n - 1) * ... * (n - k + 1)

* Pairs (same value as the example in your previous post):

N(10, 2) = 10 * 9 = 90

* Triplets:

N(10, 3) = 10 * 9 * 8 = 720

* Quadruplas:

N(10, 4) = 10 * 9 * 8 * 7 = 5040


Case #2: Elements in different order represent the same set

For this case use:

Combinations = C(n, k) = ( n * (n - 1) * ... * (n - k + 1) )  / ( k * (k - 1) * ... * 2 * 1 )

that is the same as




* Pairs:

C(10, 2) = ( 10 * 9 ) / ( 2 * 1 ) = 90 / 2 = 45

* Triplets (same value as my previous post):

C(10, 3) = ( 10 * 9 * 8 ) / ( 3 * 2 * 1 ) = 720 / 6 = 120

* Quadruplas (same value as my previous post):

C(10, 4) = ( 10 * 9 * 8 * 7 ) / ( 4 * 3 * 2 * 1 ) = 5040 / 24 = 210




So after all this, which one is your case?


Cheers!
« Last Edit: July 09, 2019, 03:52:09 PM by Meepledrone »

Offline Carca_Maker

  • Freeman
  • ****
  • Posts: 66
  • Merit: 1
  • I haven't updated my profile yet!
    • View Profile
Re: TREES question for my next variant.
« Reply #9 on: July 09, 2019, 03:12:47 PM »
Good evening, Meepledrone! First of all, I wish to give you a "+1" merit, no doubt, you are a math sage!. Afterwards I will have to read better what you wrote, but in a first approximation I think that "90" cases for pairs, "720" for triplets , etc is the right way.

Offline Carca_Maker

  • Freeman
  • ****
  • Posts: 66
  • Merit: 1
  • I haven't updated my profile yet!
    • View Profile
Re: TREES question for my next variant.
« Reply #10 on: July 09, 2019, 03:26:22 PM »
And written in the right way, I add : "Case #1: Elements in different order represent different sets", in the Meepledrone terms.

Offline Meepledrone

  • Global Moderator
  • Viscount
  • *
  • Posts: 701
  • Merit: 66
  • It is full of... Meeples!!!
    • View Profile
Re: TREES question for my next variant.
« Reply #11 on: July 09, 2019, 04:01:22 PM »
Good evening, Meepledrone! First of all, I wish to give you a "+1" merit, no doubt, you are a math sage!. Afterwards I will have to read better what you wrote, but in a first approximation I think that "90" cases for pairs, "720" for triplets , etc is the right way.

Hi there, Carca_Maker!

Thank you! I just like Combinatorics. Counting things is fun! (Maybe a byproduct of too much Sesame Street?  :o)

So have fun with the light reading. If you have any doubts, just let me know.

Cheers!

Offline Meepledrone

  • Global Moderator
  • Viscount
  • *
  • Posts: 701
  • Merit: 66
  • It is full of... Meeples!!!
    • View Profile
Re: TREES question for my next variant.
« Reply #12 on: July 09, 2019, 04:03:11 PM »
And written in the right way, I add : "Case #1: Elements in different order represent different sets", in the Meepledrone terms.

Great! This narrows down the solution space   :))

I'm intrigued with what you will use all this for...

Keep us posted, please.
« Last Edit: July 10, 2019, 04:01:56 AM by Meepledrone »

Offline Carca_Maker

  • Freeman
  • ****
  • Posts: 66
  • Merit: 1
  • I haven't updated my profile yet!
    • View Profile
Re: TREES question for my next variant.
« Reply #13 on: July 10, 2019, 02:58:04 AM »
Good morning! As Meepledrone said at his "Case #1: Elements in different order represent different sets" the triplets, 720 cases match with my old solution, here you are a picture.

So, it's only needed by me the solution and solving for Quaternas branches, at the beginning, supposing "Case #1: Elements in different order represent different sets". Ok and thanks.

Offline Carca_Maker

  • Freeman
  • ****
  • Posts: 66
  • Merit: 1
  • I haven't updated my profile yet!
    • View Profile
Re: TREES question for my next variant.
« Reply #14 on: July 10, 2019, 08:35:17 AM »
It's important to say that the my triplets notation at the previous picture, means that, for example "432“ means every triplet containing that three elements. Because of it, the total amount of triplets is 720 cases, and no the other smaller result of Meepledrone's supose #2.


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
Questions about Trees

Started by jungleboy

19 Replies
3906 Views
Last post April 15, 2016, 08:20:21 PM
by Neil
xx
Fruit-bearing trees

Started by Maurice Poucave

15 Replies
993 Views
Last post April 24, 2019, 03:53:29 PM
by Meepledrone
xx
The Circus comes to a town full of fruit trees

Started by dirk2112

0 Replies
376 Views
Last post January 30, 2019, 06:31:13 AM
by dirk2112
xx
Variant Rules in CAR

Started by Just a Bill

8 Replies
1219 Views
Last post October 02, 2017, 11:05:00 AM
by ny1050220
xx
Expansion/Variant Contest

Started by Big Guy

12 Replies
4382 Views
Last post April 06, 2014, 04:22:16 PM
by Carcking