A171398 - OEIS

%I #10 Apr 04 2023 23:07:12

%S 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,

%T 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,

%U 1,2,4,6,6,4,2,1,1,1,1,1,5,9,21,25,34,25,21,9,5,1,1

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

%C Let Z_n={0,1,...,n-1} denote the integers mod n,

%C let U(n) denote the units mod n, the elements in Z_n relatively prime to n.

%C Let S and S' be two k-subsets of Z_n.

%C Define an equivalence relation on the set of k-subsets as follows:

%C 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.

%C Then define X(n,k) to be the number of such (u,z)-equivalence classes.

%C This sequence is the `X(n,k)' triangle read by rows.

%H Andrew Howroyd, <a href="/A171398/b171398.txt">Table of n, a(n) for n = 0..1325</a> (rows 0..50).

%e The triangle begins

%e   1;

%e   1,1;

%e   1,1,1;

%e   1,1,1,1;

%e   1,1,2,1,1;

%e   1,1,1,1,1,1;

%e   1,1,3,3,3,1,1;

%e   1,1,1,2,2,1,1,1;

%e   1,1,3,4,6,4,3,1,1;

%e ...

%e For example row 8 is 1,1,3,4,6,4,3,1,1.

%e We have X(8,3)=4 because there are 4 (u,z)-equivalence classes of 3-subsets in Z_8, their representatives are: {0,1,2}, {0,1,3}, {0,1,4}, and {0,2,4}.

%o (PARI)

%o Follow(s, f)={my(t=f(s), k=1); while(t>s, k++; t=f(t)); if(s==t, k, 0)}

%o C(n, k, t, x)=prod(u=0, n-1, my(t=Follow(u, v->(v*k+t)%n)); 1 + if(t, x^t));

%o row(n)=Vecrev(if(n==0, 1, sum(t=0, n-1, sum(k=1, n, if (gcd(k, n)==1, C(n, k, t, 'x), 0)))/(n * eulerphi(n))));

%o { for(n=0, 10, print(row(n))) } \\ _Andrew Howroyd_, Apr 04 2023

%Y Row sums are A002729.

%K nonn,tabl

%O 0,13

%A _John P. McSorley_, Dec 07 2009

%E Offset corrected and terms a(45) and beyond from _Andrew Howroyd_, Apr 04 2023