A132892 Square array T(m,n) read by antidiagonals; T(m,n) is the number of equivalence classes in the set of sequences of n nonnegative integers that sum to m, generated by the equivalence relation defined in the following manner: we write a sequence in the form a[1]0a[2]0...0a[p], where each a[i] is a (possibly empty) sequence of positive integers; two sequences in this form, a[1]0a[2]0...0a[p] and b[1]0b[2]0...0b[q] are said to be equivalent if p=q and b[1],b[2],...,b[q] is a cyclic permutation of a[1],a[2],...a[p].
1, 1, 1, 1, 2, 1, 1, 3, 3, 1, 1, 4, 5, 3, 1, 1, 5, 9, 7, 4, 1, 1, 6, 13, 14, 10, 4, 1, 1, 7, 19, 25, 22, 12, 5, 1, 1, 8, 25, 41, 42, 30, 15, 5, 1, 1, 9, 33, 63, 79, 66, 43, 19, 6, 1, 1, 10, 41, 92, 131, 132, 99, 55, 22, 6, 1, 1, 11, 51, 129, 213, 245, 217, 143, 73, 26, 7, 1, 1, 12, 61, 175, 325, 428, 429, 335, 201, 91, 31, 7, 1
Offset: 1
Examples
T(2,4) = 3 because we have {2000, 0200, 0020, 0002}, {1100, 0110, 0011} and {1010, 0101, 1001}.
T(4,2) = 4 because we have {40, 04}, {31}, {13} and {22}.
The square array starts:
1....1.....1.....1......1.....1.....1...
1....2.....3.....3......4.....4.....5...
1....3.....5.....7.....10....12....15...
1....4.....9....14.....22....30....43...
1....5....13....25.....42....66....99...
Links
- Alois P. Heinz, antidiagonals n = 1..200, flattened
- Emeric Deutsch and Ira Gessel, Equivalence Classes and Cyclic Arrangements:Problem 10525, Amer. Math. Monthly, 105, No. 8, 1998, 774-775 (published solution by D. Beckwith).
- R. P. Stanley, Catalan addendum. See the interpretation (www, "Vertices of height n-1 of the tree T ...").
Programs
-
Maple
with(numtheory): T:=proc(m,n) local r, div, N: r:=igcd(m,n+1): div:=divisors(r): N:=nops(div): (sum(phi(div[j])*(binomial((m+n+1)/div[j]-1,(n+1)/div[j]-1) -binomial(m/div[j]-1,(n+1)/div[j]-1)),j=1..N))/(n+1) end proc: for m to 12 do seq(T(m, n),n=1..12) end do; # yields the upper left 12 by 12 block of the infinite matrix T(m,n) # second Maple program: T:= proc(m, n) uses numtheory; (C-> add(phi(d)*(C((m+n+1)/d-1, (n+1)/d-1) -C(m/d-1, (n+1)/d-1))/(n+1), d=divisors(igcd(m, n+1))))(binomial) end: seq(seq(T(1+d-n, n), n=1..d), d=1..14); # Alois P. Heinz, Jan 28 2025 -
Mathematica
T[m_, n_] := Module[{r, div, N}, r = GCD[m, n + 1]; div = Divisors[r]; N = Length[div]; (Sum[EulerPhi[div[[j]]]*(Binomial[(m + n + 1)/div[[j]] - 1, (n + 1)/div[[j]] - 1] - Binomial[m/div[[j]] - 1, (n + 1)/div[[j]] - 1]), {j, 1, N}])/(n + 1)]; Table[T[m - n + 1, n], {m, 1, 13}, {n, 1, m}] // Flatten (* Jean-François Alcover, Sep 01 2024, after Maple program *)
Formula
T(m,n) = Sum_{d | gcd(m,n+1)} phi(d)*(C((m+n+1)/d-1, (n+1)/d-1) - C(m/d-1, (n+1)/d-1))/(n+1). [corrected by Jason Yuen, Jan 28 2025]
Comments