Flower Pot Problem

A probably easier way to imagine this, instead of counting the number of permutations where no two adjacent elements are consecutive, is to count the number of Hamiltonian paths in the following graph: a complete graph of $n$ vertices, but one Hamiltonian path (with $n-1$ edges) have been removed. In the left diagram, we remove the red Hamiltonian path from the complete graph $K_5$ .

The good thing for $n=5$ is that the graph is isomorphic to one that is way easier to discern, to the right. There are two classes of paths:

• Those going around the pentagon ACEBD. For each edge we remove, the rest is a path, and there are two directions to traverse the path. For example, removing the edge AD means we're left with ACEBD, and its reverse DBECA. There are $5 \cdot 2 = 10$ paths.
• Those using the edge AE. Clearly C must be one of the endpoints as otherwise we use both AC and CE, and that makes a loop. After putting C as an endpoint, the situation is now completely symmetric so we can assume we use the edge CA and double the count later (for the other way of using edge CE). This apparently forces the path CAEBD, so we get two more paths (CAEBD and its reverse DBEAC). This sums up to $2 \cdot 2 = 4$ paths.

In total there are $\boxed{14}$ paths.

---

There doesn't seem to be any obvious pattern for the generalization. However, OEIS says the following recursion is true: $a_0 = a_1 = 1, a_2 = a_3 = 0$ , and $a_n = (n+1)a_{n-1} - (n-2)a_{n-2} - (n-5)a_{n-3} + (n-3)a_{n-4}$ for all $n \ge 4$ . Anyone interested on proving it?

Let's assume the original order of pots to be “ABCDE”

There are 14 orders satisfying Manoj ’s condition ,they are:

ACEBD ADBEC

BDACE BDAEC

BECAD CADBE

CAEBD CEADB

CEBDA DACEB

DBEAC DBECA

EBDAC ECADB

Well I did it by observation, but I desire a better and analytical approach towards this question if it was for 9 pots or so. Any solution posted will be appreciated .

Consider the people to be ABCDE.

1)Putting A in the Center, we have 2 pairs CD and DE and their reversals (DC and ED) that can go around A. So that's 4 possible ways.

2)Same for the other extreme letter E in the center. We have 2 pairs AB and BC and their reversals (BA and CB) that go around E. Another 4 ways.

3)Putting B in center we have only pair DE and its reversal ED around it so 2 more.

4)Putting C in center we have only pair AE and its reversal EA around it so 2 more.

5)Putting D in center we have only pair AB and its reversal BA around it so 2 more.

Total 14 ways.

I used numbers 1,2,3,4,5 instead of colors (or names), and wrote a simple program. It found these 14 ways:

13524 14253 24135 24153 25314 31425 31524 35142 35241 41352 42513 42531 52413 53142

Here is the program in JustBasic:

for a=1 to 5

for b=1 to 5: if b=a then [nb]

for c=1 to 5: if c=a or c=b then [nc]

for d=1 to 5: if d=a or d=b or d=c then [nd]

for e=1 to 5: if e=a or e=b or e=c or e=d then [ne]

c1=(abs(a-b)>1): c2=(abs(b-c)>1) : c3=(abs(c-d)>1): c4=(abs(d-e)>1)

if c1 c2 c3*c4 then print a;b;c;d;e

[ne] next e

[nd] next d

[nc] next c

[nb] next b

[na] next a

All it is doing is 1- create the first of all permutations of 1,2,3,4,5; 2- ensure that it does not have adjacent numbers; 3- print it; 4-create next permutation

Note: Adjacent numbers have absolute value of their difference equal to 1.

I just counted the permutations. Labeling the people A, B, C, D, E, we start with A:

A cannot be next to B, so we have A, C or A, D, or A, E. We take the first of these, A, C, and continue:

C cannot be next to B or D, so we have A, C, E.

E cannot be next to D, so we have one complete permutation: A, C, E, B, D.

Using this process, I found two permutations beginning with A, three beginning with B, And four beginning with C. To make it easier, beginning with E gives the same result as beginning with A, and beginning with D gives the same result as beginning with B.

Therefore, we have 2+2+3+3+4= 14 possible permutations where no people are next to someone they were next to initially.

Disclaimer: I am a sophomore in college and have not taken any classes in discrete mathematics or graph theory yet. I know there are easier and more ubiquitous ways to solve this problem, but this is what I could come up with knowing only the basics of permutations. Hope it helps anyone at my same level!

ABCDE. ACE could have any order. 3! = 6. I cant place B or D close to C, so: - if C is in the middle (2 possibilities), I can put BD in front, DB at the end or one at ths start and one at the end. That makes 6 possibilities. - if C is at the beginning, BD can go at the end (1 poss.) or between AE (1 poss). - 4*2=8 possibilities. 6+8=14

Trying to generalizing..... If there are 3 pots -> 0 If there are 4 pots -> 1 If there are 5 pots -> 14

I can't find an easy way to count them if they're 6....they're many :(