A323954 - OEIS

A323954

Regular triangle read by rows where T(n, k) is the number of ways to split an n-cycle into connected subsequences of sizes > k, n >=1, 0 <= k < n.

%I #17 Jan 19 2023 12:23:14

%S 1,2,1,5,1,1,12,3,1,1,27,6,1,1,1,58,12,4,1,1,1,121,22,8,1,1,1,1,248,

%T 39,13,5,1,1,1,1,503,67,22,10,1,1,1,1,1,1014,113,36,16,6,1,1,1,1,1,

%U 2037,188,56,23,12,1,1,1,1,1,1,4084,310,86,35,19,7,1,1,1,1,1,1

%N Regular triangle read by rows where T(n, k) is the number of ways to split an n-cycle into connected subsequences of sizes > k, n >=1, 0 <= k < n.

%H Andrew Howroyd, <a href="/A323954/b323954.txt">Table of n, a(n) for n = 1..1275</a> (rows 1..50)

%F T(n,k) = 1 - n + Sum_{i=1..floor(n/(k+1))} n*binomial(n-i*k-1, i-1)/i. - _Andrew Howroyd_, Jan 19 2023

%e Triangle begins:

%e 1

%e 2 1

%e 5 1 1

%e 12 3 1 1

%e 27 6 1 1 1

%e 58 12 4 1 1 1

%e 121 22 8 1 1 1 1

%e 248 39 13 5 1 1 1 1

%e 503 67 22 10 1 1 1 1 1

%e 1014 113 36 16 6 1 1 1 1 1

%e 2037 188 56 23 12 1 1 1 1 1 1

%e 4084 310 86 35 19 7 1 1 1 1 1 1

%e Row 4 counts the following partitions:

%e {{1234}} {{1234}} {{1234}} {{1234}}

%e {{1}{234}} {{12}{34}}

%e {{12}{34}} {{14}{23}}

%e {{123}{4}}

%e {{124}{3}}

%e {{134}{2}}

%e {{14}{23}}

%e {{1}{2}{34}}

%e {{1}{23}{4}}

%e {{12}{3}{4}}

%e {{14}{2}{3}}

%e {{1}{2}{3}{4}}

%t cycedsprop[n_,k_]:=Union[Sort/@Join@@Table[1+Mod[Range[i,j]-1,n],{i,n},{j,i+k,n+i-1}]];

%t spsu[_,{}]:={{}};spsu[foo_,set:{i_,___}]:=Join@@Function[s,Prepend[#,s]&/@spsu[Select[foo,Complement[#,Complement[set,s]]=={}&],Complement[set,s]]]/@Cases[foo,{i,___}];

%t Table[Length[spsu[cycedsprop[n,k],Range[n]]],{n,12},{k,0,n-1}]

%o (PARI) T(n,k) = 1 - n + sum(i=1, n\(k+1), n*binomial(n-i*k-1, i-1)/i) \\ _Andrew Howroyd_, Jan 19 2023

%Y Column k = 0 is A000325. Column k = 1 is A066982. Column k = 2 is A323951. Column k = 3 is A306351.

%Y Cf. A001610, A001680, A005251, A323950, A323951, A323952, A323953.

%K nonn,tabl

%O 1,2

%A _Gus Wiseman_, Feb 10 2019