2 discrete problems: one involving inclusion exclusion principle.
Maths and statistics discussion, revision, exam and homework help.
-
- Reputation:
- Thread Starter
- Respected Member
- Posts: 156
2 discrete problems: one involving inclusion exclusion principle.1) Triominoes are triangular tiles, all equilateral, the same size and blank on the
back. The front of the tile has a number in each angle, chosen from 0,1, ..., 6
with repeats allowed.
The top of each number is towards the centre of the triangle.
How many distinct triominoes are there ?
2) Use the Inclusion/Exclusion principle to find the number of ways to put
seven balls of di erent colours into four boxes of different shapes, at least
one in each.
I have no idea where to being on either of these
.
I'm not sure to how to allow for rotations on the first question
nor how to apply the I-E principle on the second. -
- Reputation:
- Vengeful, Imperial Overlord of The Student Room
- Posts: 3,691
Re: 2 discrete problems: one involving inclusion exclusion principle.1) You can split it into cases depending on how many different numbers there are on the triomino - either 1, 2 or 3. If there's 1 number then there are 7 triominoes of that form. If there's 2 numbers then you have 7 choices for the number that appears twice then 6 choices for the number that appears once. If there are 3 numbers then you can calculate the number of combinations of numbers that can appear, then consider the number of orders there are for those numbers.
2) First remove the restriction requiring at least 1 ball in each box and calculate the total number of ways. Then for each i, let
be the set of ways of putting balls in boxes, but requiring box i to be empty. You can then calculate 
.
-
- Reputation:
- Thread Starter
- Respected Member
- Posts: 156
Re: 2 discrete problems: one involving inclusion exclusion principle.1) So i can basically say,(Original post by ttoby)
1) You can split it into cases depending on how many different numbers there are on the triomino - either 1, 2 or 3. If there's 1 number then there are 7 triominoes of that form. If there's 2 numbers then you have 7 choices for the number that appears twice then 6 choices for the number that appears once. If there are 3 numbers then you can calculate the number of combinations of numbers that can appear, then consider the number of orders there are for those numbers.
2) First remove the restriction requiring at least 1 ball in each box and calculate the total number of ways. Then for each i, let be the set of ways of putting balls in boxes, but requiring box i to be empty. You can then calculate .
If there is only one distinct number there are 7 triominoes,
If there are 2 distinct numbers there are 7x6=42 triominoes,
And if there are 3 distinct numbers there are 7x6x5/3=70 triominoes (dividing by 3 as a,b,c = b,c,a etc.)
So there are 7+42+70=119 triominoes??
And 2) Before I go any further am I right in saying that there are 4^7 total ways with no restrictions?
-
- Reputation:
- Vengeful, Imperial Overlord of The Student Room
- Posts: 3,691
Re: 2 discrete problems: one involving inclusion exclusion principle.Yes and yes(Original post by daretodream-x)
1) So i can basically say,
If there is only one distinct number there are 7 triominoes,
If there are 2 distinct numbers there are 7x6=42 triominoes,
And if there are 3 distinct numbers there are 7x6x5/3=70 triominoes (dividing by 3 as a,b,c = b,c,a etc.)
So there are 7+42+70=119 triominoes??
And 2) Before I go any further am I right in saying that there are 4^7 total ways with no restrictions?
.
