

A171398


`X(n,k)' triangle read by rows. X(n,k) is the number of ksubsets of Z_n up to (u,z)equivalence.


1



1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 3, 3, 3, 1, 1, 1, 1, 1, 2, 2, 1, 1, 1, 1, 1, 3, 4, 6, 4, 3, 1, 1, 1, 1, 2, 3, 4, 4, 3, 2, 1, 1, 1, 1, 3, 4, 9, 9, 9, 4, 3, 1, 1, 1, 1, 1, 2, 4, 6, 6, 4, 2, 1, 1, 1, 1, 1, 5, 9, 21, 25, 34, 25, 21, 9, 5, 1, 1
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

0,13


COMMENTS

Let Z_n={0,1,...,n1} denote the integers mod n,
let U(n) denote the units mod n, the elements in Z_n relatively prime to n.
Let S and S' be two ksubsets of Z_n.
Define an equivalence relation on the set of ksubsets as follows:
S is (u,z)equivalent to S' iff there is a u in U(n) and a z in Z_n such that S=uS'+z.
Then define X(n,k) to be the number of such (u,z)equivalence classes.
This sequence is the `X(n,k)' triangle read by rows.


LINKS



EXAMPLE

The triangle begins
1;
1,1;
1,1,1;
1,1,1,1;
1,1,2,1,1;
1,1,1,1,1,1;
1,1,3,3,3,1,1;
1,1,1,2,2,1,1,1;
1,1,3,4,6,4,3,1,1;
...
For example row 8 is 1,1,3,4,6,4,3,1,1.
We have X(8,3)=4 because there are 4 (u,z)equivalence classes of 3subsets in Z_8, their representatives are: {0,1,2}, {0,1,3}, {0,1,4}, and {0,2,4}.


PROG

(PARI)
Follow(s, f)={my(t=f(s), k=1); while(t>s, k++; t=f(t)); if(s==t, k, 0)}
C(n, k, t, x)=prod(u=0, n1, my(t=Follow(u, v>(v*k+t)%n)); 1 + if(t, x^t));
row(n)=Vecrev(if(n==0, 1, sum(t=0, n1, sum(k=1, n, if (gcd(k, n)==1, C(n, k, t, 'x), 0)))/(n * eulerphi(n))));


CROSSREFS



KEYWORD



AUTHOR



EXTENSIONS

Offset corrected and terms a(45) and beyond from Andrew Howroyd, Apr 04 2023


STATUS

approved



