login
A323953
Regular triangle read by rows where T(n, k) is the number of ways to split an n-cycle into singletons and connected subsequences of sizes > k.
6
1, 2, 1, 5, 2, 1, 12, 6, 2, 1, 27, 12, 7, 2, 1, 58, 23, 14, 8, 2, 1, 121, 44, 23, 16, 9, 2, 1, 248, 82, 38, 26, 18, 10, 2, 1, 503, 149, 65, 38, 29, 20, 11, 2, 1, 1014, 267, 112, 57, 42, 32, 22, 12, 2, 1, 2037, 475, 189, 90, 57, 46, 35, 24, 13, 2, 1
OFFSET
1,2
LINKS
Andrew Howroyd, Table of n, a(n) for n = 1..1275 (rows 1..50)
FORMULA
T(n,k) = 2 - n + Sum_{i=1..floor(n/k)} n*binomial(n-i*k+i-1, 2*i-1)/i for 1 <= k < n. - Andrew Howroyd, Jan 19 2023
EXAMPLE
Triangle begins:
1
2 1
5 2 1
12 6 2 1
27 12 7 2 1
58 23 14 8 2 1
121 44 23 16 9 2 1
248 82 38 26 18 10 2 1
503 149 65 38 29 20 11 2 1
1014 267 112 57 42 32 22 12 2 1
2037 475 189 90 57 46 35 24 13 2 1
4084 841 312 146 80 62 50 38 26 14 2 1
Row 4 counts the following connected partitions:
{{1234}} {{1234}} {{1234}} {{1}{2}{3}{4}}
{{1}{234}} {{1}{234}} {{1}{2}{3}{4}}
{{12}{34}} {{123}{4}}
{{123}{4}} {{124}{3}}
{{124}{3}} {{134}{2}}
{{134}{2}} {{1}{2}{3}{4}}
{{14}{23}}
{{1}{2}{34}}
{{1}{23}{4}}
{{12}{3}{4}}
{{14}{2}{3}}
{{1}{2}{3}{4}}
MATHEMATICA
cyceds[n_, k_]:=Union[Sort/@Join@@Table[1+Mod[Range[i, j]-1, n], {i, n}, {j, Prepend[Range[i+k, n+i-1], i]}]];
spsu[_, {}]:={{}}; spsu[foo_, set:{i_, ___}]:=Join@@Function[s, Prepend[#, s]&/@spsu[Select[foo, Complement[#, Complement[set, s]]=={}&], Complement[set, s]]]/@Cases[foo, {i, ___}];
Table[Length[spsu[cyceds[n, k], Range[n]]], {n, 10}, {k, n}]
PROG
(PARI) T(n, k) = {1 + if(k<n, 1-n) + sum(i=1, n\k, n*binomial(n-i*k+i-1, 2*i-1)/i)} \\ Andrew Howroyd, Jan 19 2023
CROSSREFS
First column is A000325. Second column is A323950.
Sequence in context: A126125 A221876 A128514 * A126075 A134032 A137151
KEYWORD
nonn,tabl
AUTHOR
Gus Wiseman, Feb 10 2019
STATUS
approved