cp's OEIS Frontend

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.

%I A249796 #13 Jan 10 2018 20:25:14
%S A249796 1,1,2,2,6,4,6,18,28,8,24,72,128,120,16,120,360,672,840,496,32,720,
%T A249796 2160,4128,5760,5312,2016,64,5040,15120,29280,43200,47616,32928,8128,
%U A249796 128,40320,120960,236160,360000,435264,387072,201728,32640,256,362880,1088640,2136960,3326400,4249920,4314240,3121152,1226880,130816,512
%N 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.
%C A249796 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.
%e A249796 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):
%e A249796 .....1
%e A249796 .....1........2
%e A249796 .....2........6........4
%e A249796 .....6.......18.......28........8
%e A249796 ....24.......72......128......120.......16
%e A249796 ...120......360......672......840......496.......32
%e A249796 ...720.....2160.....4128.....5760.....5312.....2016.......64
%e A249796 ..5040....15120....29280....43200....47616....32928.....8128......128
%e A249796 .40320...120960...236160...360000...435264...387072...201728....32640......256
%e A249796 362880..1088640..2136960..3326400..4249920..4314240..3121152..1226880...130816......512
%o A249796 (Sage)
%o A249796 # Counting by exhaustive examination after a C program by Bartoletti.
%o A249796 def A249796_row(n):
%o A249796     def F(p, n):
%o A249796         for k in range(2, n):
%o A249796             a = mod(p[k] + 1, n)
%o A249796             b = mod(p[k] - 1, n)
%o A249796             fa, fb = false, false
%o A249796             for i in range(k):
%o A249796                 if a == p[i] : fa = true
%o A249796                 if b == p[i] : fb = true
%o A249796             if fa and fb:
%o A249796                counts[k] += 1
%o A249796                return
%o A249796     counts = [0]*n
%o A249796     for p in Permutations(n):
%o A249796         F(p, n)
%o A249796     for k in range(2, n):
%o A249796         counts[k] = counts[k] / (2*n)
%o A249796     return counts
%o A249796 for n in range(9): A249796_row(n) # _Peter Luschny_, Nov 11 2014
%K A249796 nonn,tabl
%O A249796 1,3
%A A249796 _Tony Bartoletti_, Nov 05 2014