Math Is Fun Forum
  Discussion about math, puzzles, games and fun.   Useful symbols: ÷ × ½ √ ∞ ≠ ≤ ≥ ≈ ⇒ ± ∈ Δ θ ∴ ∑ ∫ • π ƒ -¹ ² ³ °

You are not logged in.

#1 2016-04-04 06:01:49

samuel.bradley.99
Member
Registered: 2016-03-16
Posts: 51

15 people in a row

In how many different ways can 15 people (men, women and kids) sit in 15 seats in a row, given the following restrictions?

-The kids can be seated next to each other or to men or women without any problem
-No 3 men can be seated next to each other
-Women have problems when seated in two adjacent seats (no need to explain why!!)
We do not know the number of each.

Offline

#2 2016-04-04 11:34:34

bobbym
bumpkin
From: Bumpkinland
Registered: 2009-04-12
Posts: 109,606

Re: 15 people in a row

How many of each do you have?


In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

Offline

#3 2016-04-04 11:40:35

samuel.bradley.99
Member
Registered: 2016-03-16
Posts: 51

Re: 15 people in a row

We don't know.

bobbym wrote:

How many of each do you have?

Offline

#4 2016-04-04 12:02:28

bobbym
bumpkin
From: Bumpkinland
Registered: 2009-04-12
Posts: 109,606

Re: 15 people in a row

You want a general formula?


In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

Offline

#5 2016-04-04 18:58:12

samuel.bradley.99
Member
Registered: 2016-03-16
Posts: 51

Re: 15 people in a row

I would like to understand the method and the solution. Thanks!

Offline

#6 2016-04-07 06:25:52

anna_gg
Member
Registered: 2012-01-10
Posts: 232

Re: 15 people in a row

So we can have 10 men at maximum and 8 women at maximum, if this is of any help smile

Offline

#7 2016-04-07 22:23:21

Relentless
Member
Registered: 2015-12-15
Posts: 624

Re: 15 people in a row

It's a shame that you selected the number 15 for the seats. Math Is Fun's own Combinations and Permutations Calculator will give the answer for 14 seats or less.

Perhaps I will list the answers and information for lower numbers of seats and see if we can deduce a pattern.

Offline

#8 2016-04-08 01:13:05

Relentless
Member
Registered: 2015-12-15
Posts: 624

Re: 15 people in a row

I can only tentatively reason that the answer is probably between 8,460,000 - 8,490,000 and might be close to 8,482,000. But I am no good at sorting out complex sequences.

Last edited by Relentless (2016-04-08 01:23:34)

Offline

#9 2016-04-09 01:31:06

anna_gg
Member
Registered: 2012-01-10
Posts: 232

Re: 15 people in a row

Number of combinations with 3 adjacent males to 15 seats: 1586131 (pattern is 3^13 - 2^13)
Number of combinations with 2 adjacent females to 15 seats: 1586131 (pattern is 3^13 - 2^13)
Number of combinations with both 3 adjacent males and 2 adjacent females to 15 seats: 523250 (pattern is 3^(13-1) - 2*2^(13-1) + 1)

Now what?

Offline

#10 2016-04-09 03:19:28

bobbym
bumpkin
From: Bumpkinland
Registered: 2009-04-12
Posts: 109,606

Re: 15 people in a row

Hi;

Relentless wrote:

1: 3
2: 8
3: 21
4: 57
5: 161
6: 465
7: 1361
8: 4017
9: 11,921
10: 35,505
11: 106,001
12: 316,977

There are methods for dealing with sequences but they just ain't gonna shed much light on the problem, But since the OP's question seems vague to me here they are;

is the generating function.

If we consider only {21, 57, 161, 465, 1361, 4017, 11921, 35505, 106001, 316977,..}

y(n ) = 5 y(n -1) - 6 y(n-2) + 2

is the recurrence with y(1)=21 and y(2) = 57


In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

Offline

#11 2016-04-09 04:02:07

Relentless
Member
Registered: 2015-12-15
Posts: 624

Re: 15 people in a row

I can find the answer from what anna_gg has provided. Thanks! smile
Note that the number of combinations for two adjacent females given is for 14 seats, not 15. The number for 15 is presumably 4,766,585.

I believe the answer is 3^(number of seats) - (combinations with both adjacencies) - (combos with 3 adj. males - combos with both) - (combos with 2 adj. females - combos with both)

Substituting:

Given anna_gg's information, we can also find a general formula for any number of seats.


Last edited by Relentless (2016-04-09 04:23:29)

Offline

#12 2016-04-09 23:01:30

samuel.bradley.99
Member
Registered: 2016-03-16
Posts: 51

Re: 15 people in a row

Any chance I understand the reasoning and solution? Am pretty novice smile
Only thing I understand is 3^15 for the total possible number of arrangements without the restrictions smile

Offline

#13 2016-04-10 01:01:42

Relentless
Member
Registered: 2015-12-15
Posts: 624

Re: 15 people in a row

Hi, unfortunately I don't have a good intuitive understanding of the answers myself tongue I just know that the math works, by computer-generating answers and then finding equations that produce those answers.

Another thing confirmed this way is that if you want the number of combinations with a particular number x of one type sitting adjacent to each other, that is given by 3^(15-x+1) - 2^(15-x+1). So in other words, if we want to know the number of combinations with at least one male, that is 3^15 - 2^15 (which is pretty intuitive, since 2^15 is the number with males excluded). For some reason, the number with two adjacent males, 3^14 - 2^14. With three, 3^13 - 2^13.

The formula for when there are both 3 adjacent males and two adjacent females, 3^12 - 2*2^12 + 1, I must confess I don't understand at all.

As for the formula for the final answer, that involves the total number of combinations with the numbers with three adjacent males (but not two adj. females), two adj. females (but not three adj. males), and both two females and three males taken out.

Offline

#14 2016-04-10 03:22:34

samuel.bradley.99
Member
Registered: 2016-03-16
Posts: 51

Re: 15 people in a row

Thanks a lot!
So let's hope some of the others can explain smile

Offline

#15 2016-04-11 00:23:24

anna_gg
Member
Registered: 2012-01-10
Posts: 232

Re: 15 people in a row

Answers up to 12 seats: For up to 3, I agree (have tried listing all of them). For 4 seats, I get 55 instead of 57 - and of course I haven't tried the rest of them.

Relentless wrote:

I can only tentatively reason that the answer is probably between 8,460,000 - 8,490,000 and might be close to 8,482,000. But I am no good at sorting out complex sequences.

Offline

#16 2016-04-11 00:39:45

anna_gg
Member
Registered: 2012-01-10
Posts: 232

Re: 15 people in a row

Also,
Number of combinations with two adjacent females to 4 seats: I get 21 instead of 19 (and of course I haven't yet checked the bigger numbers). So this is where our difference of 57 vs 55 comes from (yours is 81-19-5 while mine is 81-21-5).

Relentless wrote:

I can only tentatively reason that the answer is probably between 8,460,000 - 8,490,000 and might be close to 8,482,000. But I am no good at sorting out complex sequences.

Offline

#17 2016-04-11 21:14:15

Relentless
Member
Registered: 2015-12-15
Posts: 624

Re: 15 people in a row

Hi anna_gg,

That is strange. The numbers I have given are not in doubt assuming the truth of your formulas. I calculated them using the combinations and permutations calculator from this site with the help of the "pattern" rule. Perhaps you could give it a try here https://www.mathsisfun.com/combinatorics/combinations-permutations-calculator.html
I suppose it is possible that I made a logical error

Offline

#18 2016-04-11 23:00:33

Relentless
Member
Registered: 2015-12-15
Posts: 624

Re: 15 people in a row

19, right?

man, woman, kid
{m,m,w,w}
{m,w,w,m}
{m,w,w,w}
{m,w,w,k}
{m,k,w,w}
{w,w,m,m}
{w,w,m,w}
{w,w,m,k}
{w,w,w,m}
{w,w,w,w}
{w,w,w,k}
{w,w,k,m}
{w,w,k,w}
{w,w,k,k}
{k,m,w,w}
{k,w,w,m}
{k,w,w,w}
{k,w,w,k}
{k,k,w,w}

Last edited by Relentless (2016-04-11 23:04:28)

Offline

#19 2016-04-12 01:08:10

anna_gg
Member
Registered: 2012-01-10
Posts: 232

Re: 15 people in a row

Apparently your list is missing {w,w,w,m} and {w,w,w,w}.

Relentless wrote:

19, right?

man, woman, kid
{m,m,w,w}
{m,w,w,m}
{m,w,w,w}
{m,w,w,k}
{m,k,w,w}
{w,w,m,m}
{w,w,m,w}
{w,w,m,k}
{w,w,w,m}
{w,w,w,w}
{w,w,w,k}
{w,w,k,m}
{w,w,k,w}
{w,w,k,k}
{k,m,w,w}
{k,w,w,m}
{k,w,w,w}
{k,w,w,k}
{k,k,w,w}

Offline

#20 2016-04-12 01:10:46

anna_gg
Member
Registered: 2012-01-10
Posts: 232

Re: 15 people in a row

I had tried the calculator myself but the results I get, when compared with some tests I did through programming (of course, for numbers smaller than 15), do not match! No idea why!! I have made all possible combinations for the syntax of "pattern" rule, with * and ?, in case I was missing something!

Relentless wrote:

Hi anna_gg,

That is strange. The numbers I have given are not in doubt assuming the truth of your formulas. I calculated them using the combinations and permutations calculator from this site with the help of the "pattern" rule. Perhaps you could give it a try here https://www.mathsisfun.com/combinatorics/combinations-permutations-calculator.html
I suppose it is possible that I made a logical error

Offline

#21 2016-04-12 02:15:15

Relentless
Member
Registered: 2015-12-15
Posts: 624

Re: 15 people in a row

Hi (:

The list does include {w,w,w,m} and {w,w,w,w} in the 9th and 10th rows.
I used "pattern *,w,w,*" for this.
"pattern *,m,m,m,*" for the males,
and both for both.

Offline

#22 2016-04-12 06:41:39

anna_gg
Member
Registered: 2012-01-10
Posts: 232

Re: 15 people in a row

Sorry, {w,k,w,w} and {w,m,w,w} - if not mistaken (after 11 hours of work, this is normal!!).

Relentless wrote:

Hi (:

The list does include {w,w,w,m} and {w,w,w,w} in the 9th and 10th rows.
I used "pattern *,w,w,*" for this.
"pattern *,m,m,m,*" for the males,
and both for both.

Offline

#23 2016-04-12 13:15:27

Relentless
Member
Registered: 2015-12-15
Posts: 624

Re: 15 people in a row

Oh my gosh, you are correct. 21 is definitely right. But I haven't the faintest why the darn thing isn't picking those up.

*,w,w,* fails to search w,*,w,w. How... irritating smile

Similarly 5 seats is missing
{w,k,k,w,w}
{w,k,m,w,w}
{w,k,w,w,k}
{w,k,w,w,m}
{w,k,w,w,w}
{w,m,k,w,w}
{w,m,m,w,w}
{w,m,w,w,k}
{w,m,w,w,m}
{w,m,w,w,w}

so the right number is 75 instead of 65...

The problem is not too difficult to overcome, however. I will list the numbers of combinations of w,*,w,w as well as the numbers of duplicates between w,*,w,w and *,w,w,* shortly. All we have to do is add the first and subtract the second from our given numbers and general rule. Since the result then agrees so far with manual and exhaustive listing, this should be the only quirk.

Last edited by Relentless (2016-04-12 14:01:47)

Offline

#24 2016-04-12 14:52:16

Relentless
Member
Registered: 2015-12-15
Posts: 624

Re: 15 people in a row

Fortunately, the patterns became evident almost immediately.

I believe the real formula for number of combinations with 2 adjacent women for n number of seats is:

For three adjacent males:

In general, for the number of combinations with x adjacent types for n seats:

I will post the new duplicates between two females and three males later, and then we are basically done.





The patterns for correcting the number of duplicates also become evident after some calculation. It appears the correct number of duplicates is

in terms of the previous formula
This time I cross-referenced all combinations of *,m,m,m,* and m,*,m,m,m with *,w,w,* and w,*,w,w and manually (with a spreadsheet) counted the unique combinations.
To derive a formula for the numbers thus obtained from the formula we have, I believe the correct expression for the number of combinations with both two adjacent females and three adjacent males, for n seats, is:

(this is not applicable to one or two seats)

Last edited by Relentless (2016-04-12 17:25:57)

Offline

#25 2016-04-12 17:34:57

Relentless
Member
Registered: 2015-12-15
Posts: 624

Re: 15 people in a row

From all of the new formulas, the updated general formula for the answer in terms of n seats is:

The updated answer for n=15:


(about 51.19% of the total arrangements)

And we are as far as ever from an intuitive explanation smile



Last edited by Relentless (2016-04-12 17:47:13)

Offline

Board footer

Powered by FluxBB