|
| |
|
|
A119963
|
|
Triangle T(n,k), 0 <= k <= n, read by rows, with T(2n,2k) = T(2n+1,2k) = T(2n+1,2k+1) = T(2n+2,2k+1) = binomial(n,k).
|
|
17
|
|
|
|
1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 2, 2, 1, 1, 1, 1, 3, 2, 3, 1, 1, 1, 1, 3, 3, 3, 3, 1, 1, 1, 1, 4, 3, 6, 3, 4, 1, 1, 1, 1, 4, 4, 6, 6, 4, 4, 1, 1, 1, 1, 5, 4, 10, 6, 10, 4, 5, 1, 1, 1, 1, 5, 5, 10, 10, 10, 10, 5, 5, 1, 1, 1, 1, 6, 5, 15, 10, 20, 10, 15, 5, 6, 1, 1, 1, 1, 6, 6, 15, 15, 20, 20, 15, 15, 6, 6, 1, 1, 1, 1, 7, 6, 21, 15, 35, 20, 35, 15, 21, 6, 7, 1, 1
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
0,13
|
|
|
COMMENTS
|
A combinatorial interpretation of this triangle is as follows:
Ignore the first column of 1's of the above triangle and the call the (n,k) entry of the new triangle formed RE(n,k).
Hence row 8 of the 'RE(n,k)' triangle is 1 4 3 6 3 4 1 1.
Now see sequence A180171 for the definition of a k-reverse of n.
Briefly, a k-reverse of n is a k-composition of n which is cyclically equivalent to its reverse.
Sequence A180171 is the 'R(n,k)' triangle read by rows where R(n,k) is the total number of k-reverses of n.
Then RE(n,k) is the number of k-reverses of n up to cyclic equivalence.
In sequence A180171 we have R(8,3)=9 because there are 9 3-reverses of 8.
In cyclically equivalent classes: {116,611,161} {224,422,242}, and {233,323,332}; since there are 3 such classes we have RE(8,3)=3.
Similarly, in A180171, we have R(8,6)=21 because all 21 6-compositions of 8 are 6-reverses of 8, but they come in 4 cyclically equivalent classes (with representatives 111113, 111122, 111212, and 112112) hence RE(8,6)=4.
There is another (equivalent) interpretation for RE(n,k) involving k-subsets of Z_n, the integers modulo n, and the multiplier -1. See the McSorley/Schoen paper below for more details.
In this case it is convenient to count k-subsets up to dihedral equivalence, rather than cyclic equivalence.
The counts are the same. The row sums of the 'RE(n,k)' triangle give sequence A052955.
(End)
When 1 <= k <= n, each cyclically equivalence class of k-reverses of n is a "Sommerville symmetrical cyclic composition," which was introduced by Sommerville (1909). On pp. 301-304 of his paper, he proves that the number of such (equivalence classes of) compositions of n with length k is exactly T(n,k) = RE(n,k).
The equivalence class of a Sommerville symmetrical cyclic composition contains at least one palindromic composition (type I) or a composition that becomes a palindromic composition if we remove the first part (type II). A composition with only one part is a palindromic composition of both types. Hadjicostas and Zhang (2017) have proved that each equivalence class of k-reverses of n contains exactly two compositions that are either of type I or type II (except in the case when k | n and all the parts are the same).
For example, consider the case with n=8 and k=3, where RE(8,3)=3. As pointed above by J. P. McSorley, in cyclically equivalent classes we have {116,611,161} {224,422,242}, and {233,323,332}. The first class contains one composition of type I (161) and one of type II (611); the second class contains one composition of type I (242) and one of type II (422); and the last class contains one composition of type I (323) and one of type II (233).
When n = 6 and k = 4, the class of 4-reverses {1221, 2211, 2112, 1122} contains two compositions of type I (1221 and 2112).
If A is a set of positive integers and 1 <= k <= n, let RE_A(n,k) be the total number of Sommerville symmetrical cyclic compositions of n with length k and parts only in A (= number of cyclically equivalence classes of k-reverses of n with parts only in A). Then the g.f. of RE_A(n,k) is Sum_{n,k >= 1} RE_A(n,k) * x^n * y^k = (-1/2) + (1 + y * f_A(x))^2/(2 * (1 - y^2 * f_A(x^2)), where f_A(x) = Sum_{m in A} x^m. (For this sequence, A = all positive integers.)
Sequence A292200 contains the total number of Sommerville symmetrical cyclic compositions of n that are Carlitz (compositions that have length one, or have length >= 1 and adjacent parts of the composition on a circle are distinct).
(End)
|
|
|
REFERENCES
|
John P. McSorley, Counting k-compositions of n with palindromic and related structures, preprint, 2010. [From John P. McSorley, Aug 24 2010]
|
|
|
LINKS
|
John P. McSorley and Alan H. Schoen, Rhombic tilings of (n,k)-Ovals, (n, k, lambda)-Cyclic Difference Sets, and Related Topics, Discrete Math., 313 (2013), 129-154. - From N. J. A. Sloane, Nov 26 2012
|
|
|
FORMULA
|
G.f.: Sum_{n,k >= 1} RE(n,k)*x^n*y^k = (1+x*y-x^2)*x*y/((1-x)*(1-x^2-x^2*y^2)). - Petros Hadjicostas, Oct 12 2017
G.f.: Sum_{n,k >= 0} T(n,k)*x^n*y^k = (1+x*y)*(1+x)/(1-x^2-x^2*y^2) as above, but adding 1/(1-x) to include n,k = 0 terms. - Paul Sampson, Nov 22 2017
T(n, k) = binomial(floor(n/2) - (k mod 2) * (1 - (n mod 2)), floor(k/2)) for 0 <= k <= n. - Petros Hadjicostas, May 29 2019
|
|
|
EXAMPLE
|
Triangle begins (with rows for n >= 0 and columns for k >= 0) as follows:
1;
1, 1;
1, 1, 1;
1, 1, 1, 1;
1, 1, 2, 1, 1;
1, 1, 2, 2, 1, 1;
1, 1, 3, 2, 3, 1, 1;
1, 1, 3, 3, 3, 3, 1, 1;
1, 1, 4, 3, 6, 3, 4, 1, 1;
1, 1, 4, 4, 6, 6, 4, 4, 1, 1;
...
|
|
|
MATHEMATICA
|
|
|
|
PROG
|
(PARI) T(n, k) = binomial((n-k%2)\2, k\2); \\ Andrew Howroyd, Oct 08 2017
|
|
|
CROSSREFS
|
The row sums of the T(n,k) triangle give sequence A029744 whose terms are 1 more than the terms of sequence A052955 (row sums of RE(n,k) triangle). See sequence A029744 where there is a reference to necklaces relevant to the combinatorial interpretation and the McSorley and McSorley/Schoen papers given here. - John P. McSorley, Aug 31 2010
|
|
|
KEYWORD
|
|
|
|
AUTHOR
|
|
|
|
EXTENSIONS
|
|
|
|
STATUS
|
approved
|
| |
|
|
