login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A249796 Triangle T(n,k), n>=3, 3<=k<=n, read by rows. Number of ways to make n selections without replacement from a circular array of n unlabeled cells (ignoring rotations and reflection), such that the first selection of a cell adjacent to previously selected cells occurs on the k-th selection. 2
1, 1, 2, 2, 6, 4, 6, 18, 28, 8, 24, 72, 128, 120, 16, 120, 360, 672, 840, 496, 32, 720, 2160, 4128, 5760, 5312, 2016, 64, 5040, 15120, 29280, 43200, 47616, 32928, 8128, 128, 40320, 120960, 236160, 360000, 435264, 387072, 201728, 32640, 256, 362880, 1088640, 2136960, 3326400, 4249920, 4314240, 3121152, 1226880, 130816, 512 (list; table; graph; refs; listen; history; text; internal format)
OFFSET

1,3

COMMENTS

With m=n+3, T(m,3) = n!, T(m,m) = 2^n (easy proofs), and T(m,m-1) = A006516(n) = 2^(n-1) * (2^n - 1). Remaining supplied elements generated by exhaustive examination of permutations.

LINKS

Table of n, a(n) for n=1..55.

EXAMPLE

T(3,3) = 1 since, given any permutation of <1,2,3>, the third element will be the first to be adjacent to previous elements (modulo 3), and these 6 permutations are indistinguishable given rotations and reflection. Sample table (left-justified):

.....1

.....1........2

.....2........6........4

.....6.......18.......28........8

....24.......72......128......120.......16

...120......360......672......840......496.......32

...720.....2160.....4128.....5760.....5312.....2016.......64

..5040....15120....29280....43200....47616....32928.....8128......128

.40320...120960...236160...360000...435264...387072...201728....32640......256

362880..1088640..2136960..3326400..4249920..4314240..3121152..1226880...130816......512

PROG

(Sage)

# Counting by exhaustive examination after a C program by Bartoletti.

def A249796_row(n):

    def F(p, n):

        for k in range(2, n):

            a = mod(p[k] + 1, n)

            b = mod(p[k] - 1, n)

            fa, fb = false, false

            for i in range(k):

                if a == p[i] : fa = true

                if b == p[i] : fb = true

            if fa and fb:

               counts[k] += 1

               return

    counts = [0]*n

    for p in Permutations(n):

        F(p, n)

    for k in range(2, n):

        counts[k] = counts[k] / (2*n)

    return counts

for n in range(9): A249796_row(n) # Peter Luschny, Nov 11 2014

CROSSREFS

Sequence in context: A222404 A081111 A092686 * A182411 A067804 A074911

Adjacent sequences:  A249793 A249794 A249795 * A249797 A249798 A249799

KEYWORD

nonn,tabl

AUTHOR

Tony Bartoletti, Nov 05 2014

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified October 31 11:50 EDT 2020. Contains 338101 sequences. (Running on oeis4.)