- #1

- 21

- 0

thanks

- Thread starter Wiz
- Start date

- #1

- 21

- 0

thanks

- #2

- 83

- 0

- #3

- 21

- 0

- #4

- 83

- 0

Another try: We have to select 7 persons with gaps (of at least one person) between them. This is equivalent to selecting 7 gaps (of at least one person) with exaclty one person in between. Now, in how many ways can you distribute the remaining 9 persons over the 7 gaps? We've got two different cases:

(1) We've got a gap of three persons, like: #000#0#0#0#0#0#0 (where # denotes selected). In how many ways can you do this?

(2) We've got two gaps of two persons, like: #00#00#0#0#0#0#0. In how many ways can you do this?

- #5

- 83

- 0

By the way: I get 14 + 42 = 56 possible ways.

- #6

- 21

- 0

- #7

- 83

- 0

(1) In this case the selection is characterized by the position (of the middle person) of the gap of three. So there are 16 different possible selections.

(2) Now the selection is characterized by the position of the two gaps of two persons. The 'first' gap (of two) can be chosen arbitrary, so 16 possibilities. The second gap (of two) can be chosen from the 7-1=6 remaining gaps between selected persons. Now we have to devide by two because the gaps (of two) could interchanged to yield the same selection. So we get 16 x 6 / 2 = 48 possible selections.

Conclusion there are 64 possible selections.

- #8

- 21

- 0

- #9

VietDao29

Homework Helper

- 1,423

- 2

First, build a matrix like

[tex]A = \left[ \begin{array}{ccccc} a_{11} & a_{12} & a_{13} & a_{14} & . . . \\ a_{21} & a_{22} & a_{23} & a_{24} & . . . \\ a_{31} & a_{32} & a_{33} & a_{34} & . . . \\ \vdots & \vdots & \vdots & \vdots & . . . \end{array} \right][/tex]

Where [tex]a_{1j} = 1 [/tex] and [tex]a_{n1} = 1 [/tex], and define : [tex]a_{ij} = a_{(i - 1)j} + a_{i(j - 1)}[/tex]

Your matrix will look like:

[tex]A = \left[ \begin{array}{ccccc} 1 & 1 & 1 & 1 & . . . \\ 1 & 2 & 3 & 4 & . . . \\ 1 & 3 & 6 & 10 & . . . \\ \vdots & \vdots & \vdots & \vdots & . . . \end{array} \right][/tex]

Problem: n people in a round table. No 2 selected people sits next to each other. Select p people.

Calculate: [tex]\delta = n - (2(p - 1) + 1)[/tex]. Then the total number of ways is :

[tex]C = a_{\delta p} + \sum_{x = 1}^{\delta} a_{xp}[/tex]

I wonder if anyone has discovered this. Anyway, if noone else has. Let’s call it ‘The little theorem of Viet Dao’.

EDIT : This formula can be horribly wrong if there is no way to select.

Viet Dao,

[tex]A = \left[ \begin{array}{ccccc} a_{11} & a_{12} & a_{13} & a_{14} & . . . \\ a_{21} & a_{22} & a_{23} & a_{24} & . . . \\ a_{31} & a_{32} & a_{33} & a_{34} & . . . \\ \vdots & \vdots & \vdots & \vdots & . . . \end{array} \right][/tex]

Where [tex]a_{1j} = 1 [/tex] and [tex]a_{n1} = 1 [/tex], and define : [tex]a_{ij} = a_{(i - 1)j} + a_{i(j - 1)}[/tex]

Your matrix will look like:

[tex]A = \left[ \begin{array}{ccccc} 1 & 1 & 1 & 1 & . . . \\ 1 & 2 & 3 & 4 & . . . \\ 1 & 3 & 6 & 10 & . . . \\ \vdots & \vdots & \vdots & \vdots & . . . \end{array} \right][/tex]

Problem: n people in a round table. No 2 selected people sits next to each other. Select p people.

Calculate: [tex]\delta = n - (2(p - 1) + 1)[/tex]. Then the total number of ways is :

[tex]C = a_{\delta p} + \sum_{x = 1}^{\delta} a_{xp}[/tex]

I wonder if anyone has discovered this. Anyway, if noone else has. Let’s call it ‘The little theorem of Viet Dao’.

EDIT : This formula can be horribly wrong if there is no way to select.

Viet Dao,

Last edited:

- #10

- 21

- 0

i understood absolutely nothing in ur previous post......could u plz explain??....

- #11

VietDao29

Homework Helper

- 1,423

- 2

Okay, a matrix m x n is defined as:

[tex]A_{m x n} = \left[ \begin{array}{ccccc} a_{11} & a_{12} & a_{13} & . . . & a_{1n} \\ a_{21} & a_{22} & a_{23} & . . . & a_{2n} \\ \vdots & \vdots & \vdots & \vdots & . . . \\ a_{m1} & a_{m2} & a_{m3} & . . . & a_{mn} \end{array} \right][/tex]

[tex]a_{ij}[/tex] 0 < i < m, 0 < j < n is one item in the matrix. For example, i = 1, j = 1, then you will have [tex]a_{ij} = a_{11}[/tex]

And my matrix will have [tex]a_{1j} = 1 \mbox{ and } a_{i1} = 1[/tex]

So it will look like:

An item [tex]a_{ij}[/tex] is the one that lies on the i row, and the j column of the matrix.

[tex]A = \left[ \begin{array}{ccccc} 1 & 1 & 1 & 1 & . . . \\ 1 & a_{22} & a_{23} & a_{24} & . . . \\ 1 & a_{32} & a_{33} & a_{34} & . . . \\ \vdots & \vdots & \vdots & \vdots & . . . \end{array} \right][/tex]

Then I say : [tex]a_{ij} = a_{(i - 1)j} + a_{i(j - 1)}[/tex]

Example : [tex]a_{22} = a_{12} + a_{21} = 1 + 1 = 2[/tex]

[tex]a_{23} = a_{13} + a_{22} = 1 + 2 = 3[/tex]

The item [tex]a_{ij}[/tex] is the sum of the item above it and the item to the left of it.

And so on, so my matrix will look like:

[tex]A = \left[ \begin{array}{ccccc} 1 & 1 & 1 & 1 & . . . \\ 1 & 2 & 3 & 4 & . . . \\ 1 & 3 & 6 & 10 & . . . \\ \vdots & \vdots & \vdots & \vdots & . . . \end{array} \right][/tex]

Then I calculate : [tex]\delta = n - (2(p - 1) + 1)[/tex]. There are 2 cases:

**1. **[tex]\delta \leq 0[/tex] : No selection.

**2. **[tex]\delta > 0[/tex]:

Then the number of selection will be:

[tex]C = a_{\delta p} + \sum_{x = 1}^{\delta} a_{xp}[/tex]

It means:

[tex]C = a_{\delta p} + a_{1p} + a_{2p} + a_{3p} + ... + a_{\delta p}[/tex]

Where p is the number of people you want to select, n is the total number of people sitting on the round table.

*** Solving your problem using my method:**

[tex]\delta = n - (2(p - 1) + 1) = 3[/tex]

p = 7, n = 16 (This is what you have total people = 16, number of selected people = 7).

[tex]A = \left[ \begin{array}{ccccccc} 1 & 1 & 1 & 1 & 1 & 1 & 1. . . \\ 1 & 2 & 3 & 4 & 5 & 6 & 7. . . \\ 1 & 3 & 6 & 10 & 15 & 21 & 28. . . \\ \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & . . . \end{array} \right][/tex]

So you will have:

[tex]C = a_{\delta p} + a_{1p} + a_{2p} + a_{3p} + ... + a_{\delta p}[/tex]

[tex]= a_{37} + a_{17} + a_{27} + a_{37} = 28 + 28 + 7 + 1 = 64.[/tex]

So there are 64 different ways to randomly choose 7 people, in which in every 2 selected people, they don't sit next to each other.

You can try another number of people sitting on the table (n), and the number of selected people (p).

You can use this as a method to check your answer.

Viet Dao,

[tex]A_{m x n} = \left[ \begin{array}{ccccc} a_{11} & a_{12} & a_{13} & . . . & a_{1n} \\ a_{21} & a_{22} & a_{23} & . . . & a_{2n} \\ \vdots & \vdots & \vdots & \vdots & . . . \\ a_{m1} & a_{m2} & a_{m3} & . . . & a_{mn} \end{array} \right][/tex]

[tex]a_{ij}[/tex] 0 < i < m, 0 < j < n is one item in the matrix. For example, i = 1, j = 1, then you will have [tex]a_{ij} = a_{11}[/tex]

And my matrix will have [tex]a_{1j} = 1 \mbox{ and } a_{i1} = 1[/tex]

So it will look like:

An item [tex]a_{ij}[/tex] is the one that lies on the i row, and the j column of the matrix.

[tex]A = \left[ \begin{array}{ccccc} 1 & 1 & 1 & 1 & . . . \\ 1 & a_{22} & a_{23} & a_{24} & . . . \\ 1 & a_{32} & a_{33} & a_{34} & . . . \\ \vdots & \vdots & \vdots & \vdots & . . . \end{array} \right][/tex]

Then I say : [tex]a_{ij} = a_{(i - 1)j} + a_{i(j - 1)}[/tex]

Example : [tex]a_{22} = a_{12} + a_{21} = 1 + 1 = 2[/tex]

[tex]a_{23} = a_{13} + a_{22} = 1 + 2 = 3[/tex]

The item [tex]a_{ij}[/tex] is the sum of the item above it and the item to the left of it.

And so on, so my matrix will look like:

[tex]A = \left[ \begin{array}{ccccc} 1 & 1 & 1 & 1 & . . . \\ 1 & 2 & 3 & 4 & . . . \\ 1 & 3 & 6 & 10 & . . . \\ \vdots & \vdots & \vdots & \vdots & . . . \end{array} \right][/tex]

Then I calculate : [tex]\delta = n - (2(p - 1) + 1)[/tex]. There are 2 cases:

Then the number of selection will be:

[tex]C = a_{\delta p} + \sum_{x = 1}^{\delta} a_{xp}[/tex]

It means:

[tex]C = a_{\delta p} + a_{1p} + a_{2p} + a_{3p} + ... + a_{\delta p}[/tex]

Where p is the number of people you want to select, n is the total number of people sitting on the round table.

[tex]\delta = n - (2(p - 1) + 1) = 3[/tex]

p = 7, n = 16 (This is what you have total people = 16, number of selected people = 7).

[tex]A = \left[ \begin{array}{ccccccc} 1 & 1 & 1 & 1 & 1 & 1 & 1. . . \\ 1 & 2 & 3 & 4 & 5 & 6 & 7. . . \\ 1 & 3 & 6 & 10 & 15 & 21 & 28. . . \\ \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & . . . \end{array} \right][/tex]

So you will have:

[tex]C = a_{\delta p} + a_{1p} + a_{2p} + a_{3p} + ... + a_{\delta p}[/tex]

[tex]= a_{37} + a_{17} + a_{27} + a_{37} = 28 + 28 + 7 + 1 = 64.[/tex]

So there are 64 different ways to randomly choose 7 people, in which in every 2 selected people, they don't sit next to each other.

You can try another number of people sitting on the table (n), and the number of selected people (p).

You can use this as a method to check your answer.

Viet Dao,

Last edited:

- Last Post

- Replies
- 4

- Views
- 2K

- Last Post

- Replies
- 1

- Views
- 2K

- Last Post

- Replies
- 1

- Views
- 2K

- Replies
- 6

- Views
- 1K