Even though you "definitely want the permutations", it sounds like you don't really want that, you actually want the Cartesian product of your sequence with itself from 1 to len(sequence) times, with results with neighbouring equal elements filtered out.
Something like:
In [16]: from itertools import product
In [17]: def has_doubles(x): return any(i==j for i,j in zip(x, x[1:]))
In [18]: seq = ["a","b","c"]
In [19]: [x for n in range(len(seq)) for x in product(seq, repeat=n+1)
if not has_doubles(x)]
Out[19]:
[('a',),
('b',),
('c',),
('a', 'b'),
('a', 'c'),
('b', 'a'),
('b', 'c'),
('c', 'a'),
('c', 'b'),
('a', 'b', 'a'),
('a', 'b', 'c'),
('a', 'c', 'a'),
('a', 'c', 'b'),
('b', 'a', 'b'),
('b', 'a', 'c'),
('b', 'c', 'a'),
('b', 'c', 'b'),
('c', 'a', 'b'),
('c', 'a', 'c'),
('c', 'b', 'a'),
('c', 'b', 'c')]
In [20]: len(_)
Out[20]: 21