|
Search: id:A132892
|
|
|
| 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]. |
|
+0
1
|
|
| 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
(list; graph; listen)
|
|
|
OFFSET
|
1,5
|
|
|
COMMENT
|
T(n,n)=A000108(n) (the Catalan numbers; see R. P. Stanley, Catalan addendum, problem starting "Equivalence classes of the equivalence relation ..."). T(m,m+1)=A007595(m+1); T(m,m+2)=A003441(m+1); T(m,m+3)=A003444(m+3); T(n+2,n)=A001453(n+1) (Catalan numbers - 1); T(m,1)=1; T(m,2)=m; T(m,3)=A080827(m)=A099392(m+1); T(m,4)=A004006(m).
|
|
REFERENCES
|
E. Deutsch and Ira Gessel, Problem 10525, Amer. Math. Monthly, 105, No. 8, 1998, 774-775 (published solution by D. Beckwith).
|
|
LINKS
|
R. P. Stanley, Catalan addendum. See the interpretation (www, "Vertices of height n-1 of the tree T ...").
|
|
FORMULA
|
T(m,n)=Sum_{d | gcd(m,n+1)}(phi(n)*(binom((m+n+1)/d - 1, (n+1)/d - 1) - binom(m/d - 1, (n+1)/d - 1))/(n+1).
|
|
EXAMPLE
|
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.....4...
1....3.....5.....7.....10....12....15...
1....4.....9....14.....22....30....43...
1....5....13....25.....42....66....99...
|
|
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)
|
|
CROSSREFS
|
Cf. A000108, A007595, A003441, A003444, A001453, A080827, A099392, A004006.
Sequence in context: A096589 A099573 A107430 this_sequence A077028 A114225 A072704
Adjacent sequences: A132889 A132890 A132891 this_sequence A132893 A132894 A132895
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
Emeric Deutsch (deutsch(AT)duke.poly.edu) and Ira Gessel (gessel(AT)brandeis.edu), Oct 02 2007
|
|
|
Search completed in 0.002 seconds
|
