15 people in a row

samuel.bradley.99 · 2016-04-04 06:01:49

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.

bobbym · 2016-04-04 11:34:34

How many of each do you have?

samuel.bradley.99 · 2016-04-04 11:40:35

We don't know.

bobbym wrote:

How many of each do you have?

bobbym · 2016-04-04 12:02:28

You want a general formula?

samuel.bradley.99 · 2016-04-04 18:58:12

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

anna_gg · 2016-04-07 06:25:52

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

Relentless · 2016-04-07 22:23:21

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.

Relentless · 2016-04-08 01:13:05

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)

anna_gg · 2016-04-09 01:31:06

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?

bobbym · 2016-04-09 03:19:28

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

Relentless · 2016-04-09 04:02:07

I can find the answer from what anna_gg has provided. Thanks!
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)

samuel.bradley.99 · 2016-04-09 23:01:30

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

Relentless · 2016-04-10 01:01:42

Hi, unfortunately I don't have a good intuitive understanding of the answers myself 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.

samuel.bradley.99 · 2016-04-10 03:22:34

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

anna_gg · 2016-04-11 00:23:24

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.

anna_gg · 2016-04-11 00:39:45

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.

Relentless · 2016-04-11 21:14:15

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

Relentless · 2016-04-11 23:00:33

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)

anna_gg · 2016-04-12 01:08:10

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}

anna_gg · 2016-04-12 01:10:46

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

Relentless · 2016-04-12 02:15:15

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.

anna_gg · 2016-04-12 06:41:39

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.

Relentless · 2016-04-12 13:15:27

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

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)

Relentless · 2016-04-12 14:52:16

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)

Relentless · 2016-04-12 17:34:57

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

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

Math Is Fun Forum

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

15 people in a row

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

Re: 15 people in a row

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

Re: 15 people in a row

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

Re: 15 people in a row

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

Re: 15 people in a row

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

Re: 15 people in a row

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

Re: 15 people in a row

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

Re: 15 people in a row

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

Re: 15 people in a row

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

Re: 15 people in a row

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

Re: 15 people in a row

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

Re: 15 people in a row

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

Re: 15 people in a row

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

Re: 15 people in a row

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

Re: 15 people in a row

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

Re: 15 people in a row

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

Re: 15 people in a row

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

Re: 15 people in a row

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

Re: 15 people in a row

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

Re: 15 people in a row

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

Re: 15 people in a row

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

Re: 15 people in a row

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

Re: 15 people in a row

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

Re: 15 people in a row

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

Re: 15 people in a row

Board footer