login
Square array read by antidiagonals: T(n,k) = number of n-tuples of nonnegative integers (u_0,...,u_{n-1}) satisfying Sum_{j=0..n-1} j*u_j == 1 mod n and Sum_{j=0..n-1} u_j = m.
8

%I #49 Apr 15 2024 09:24:13

%S 1,1,1,1,1,1,1,2,2,1,1,2,3,2,1,1,3,5,5,3,1,1,3,7,8,7,3,1,1,4,9,14,14,

%T 9,4,1,1,4,12,20,25,20,12,4,1,1,5,15,30,42,42,30,15,5,1,1,5,18,40,66,

%U 75,66,40,18,5,1,1,6,22,55,99,132,132,99,55,22,6,1

%N Square array read by antidiagonals: T(n,k) = number of n-tuples of nonnegative integers (u_0,...,u_{n-1}) satisfying Sum_{j=0..n-1} j*u_j == 1 mod n and Sum_{j=0..n-1} u_j = m.

%C The array is symmetric; for the entries on or below the diagonal see A245559.

%C If the congruence in the definition is changed from Sum_{j=0..n-1} j*u_j == 1 mod n to Sum_{j=0..n-1} j*u_j == 0 mod n we get the array shown in A241926, A047996, and A037306.

%C Differs from A011847 from row n = 9, k = 4 on; if the rows are surrounded by 0's, this yields A051168 without its rows 0 and 1, i.e., a(1) is A051168(2,1). - _M. F. Hasler_, Sep 29 2018

%C This array was first studied by Fredman (1975). - _Petros Hadjicostas_, Jul 10 2019

%H Taylor Brysiewicz, <a href="https://arxiv.org/abs/1807.03408">Necklaces count polynomial parametric osculants</a>, arXiv:1807.03408 [math.AG], 2018.

%H A. Elashvili, M. Jibladze, <a href="http://dx.doi.org/10.1016/S0019-3577(98)80021-9">Hermite reciprocity for the regular representations of cyclic groups</a>, Indag. Math. (N.S.) 9 (1998), no. 2, 233-238. MR1691428 (2000c:13006).

%H A. Elashvili, M. Jibladze, D. Pataraia, <a href="http://dx.doi.org/10.1023/A:1018727630642">Combinatorics of necklaces and "Hermite reciprocity"</a>, J. Algebraic Combin. 10 (1999), no. 2, 173-188. MR1719140 (2000j:05009). See p. 174.

%H M. L. Fredman, <a href="https://doi.org/10.1016/0097-3165(75)90008-4">A symmetry relationship for a class of partitions</a>, J. Combinatorial Theory Ser. A 18 (1975), 199-202.

%H I. M. Gessel and C. Reutenauer, <a href="http://dx.doi.org/10.1016/0097-3165(93)90095-P">Counting permutations with given cycle structure and descent set</a>, J. Combin. Theory, Ser. A, 64, 1993, 189-215, Theorem 9.4.

%H J. E. Iglesias, <a href="https://doi.org/10.1524/zkri.2006.221.4.237">Enumeration of closest-packings by the space group: a simple approach</a>, Z. Krist. 221 (2006) 237-245, eq. (5).

%e Square array begins:

%e 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, ...

%e 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, ...

%e 1, 2, 3, 5, 7, 9, 12, 15, 18, 22, ...

%e 1, 2, 5, 8, 14, 20, 30, 40, 55, 70, ...

%e 1, 3, 7, 14, 25, 42, 66, 99, 143, 200, ...

%e 1, 3, 9, 20, 42, 75, 132, 212, 333, 497, ...

%e 1, 4, 12, 30, 66, 132, 245, 429, 715, 1144, ...

%e 1, 4, 15, 40, 99, 212, 429, 800, 1430, 2424, ...

%e 1, 5, 18, 55, 143, 333, 715, 1430, 2700, 4862, ...

%e 1, 5, 22, 70, 200, 497, 1144, 2424, 4862, 9225, ...

%e ...

%e Reading by antidiagonals, we get:

%e 1;

%e 1, 1;

%e 1, 1, 1;

%e 1, 2, 2, 1;

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

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

%e 1, 3, 7, 8, 7, 3, 1;

%e 1, 4, 9, 14, 14, 9, 4, 1;

%e 1, 4, 12, 20, 25, 20, 12, 4, 1;

%e 1, 5, 15, 30, 42, 42, 30, 15, 5, 1;

%e 1, 5, 18, 40, 66, 75, 66, 40, 18, 5, 1;

%e 1, 6, 22, 55, 99, 132, 132, 99, 55, 22, 6, 1;

%e ...

%p # To produce the first 10 rows and columns (as on page 174 of the Elashvili et al. 1999 reference):

%p with(numtheory):

%p cnk:=(n,k) -> add(mobius(n/d)*d, d in divisors(gcd(n,k)));

%p anmk:=(n,m,k)->(1/(n+m))*add( cnk(d,k)*binomial((n+m)/d,n/d), d in divisors(gcd(n,m))); # anmk(n,m,k) is the value of a_k(n,m) as in Theorem 1, Equation (4), of the Elashvili et al. 1999 reference.

%p r2:=(n,k)->[seq(anmk(n,m,k),m=1..10)];

%p for n from 1 to 10 do lprint(r2(n,1)); od:

%t rows = 12;

%t cnk[n_, k_] := Sum[MoebiusMu[n/d] d, {d , Divisors[GCD[n, k]]}];

%t anmk[n_, m_, k_] := (1/(n+m)) Sum[cnk[d, k] Binomial[(n+m)/d, n/d], {d, Divisors[GCD[n, m]]}];

%t r2[n_, k_] := Table[anmk[n, m, k], {m, 1, rows}];

%t T = Table[r2[n, 1], {n, 1, rows}];

%t Table[T[[n-k+1, k]], {n, 1, rows}, {k, 1, n}] // Flatten (* _Jean-François Alcover_, Nov 05 2018, from Maple *)

%Y This array is very similar to but different from A011847.

%Y Cf. A051168, A092964, A241926, A047996, A037306, A245559.

%Y Rows include A001840, A006918, A051170, A011796, A011797, A031164. Main diagonal is A022553.

%K nonn,tabl

%O 1,8

%A _N. J. A. Sloane_, Aug 07 2014