|
Search: id:A039911
|
|
|
| A039911 |
|
Triangle read by rows: number of compositions of n into relatively prime summands. |
|
+0
2
|
|
| 1, 1, 2, 1, 3, 2, 1, 4, 6, 4, 1, 5, 10, 9, 2, 1, 6, 15, 20, 15, 6, 1, 7, 21, 35, 34, 18, 4, 1, 8, 28, 56, 70, 56, 27, 6, 1, 9, 36, 84, 126, 125, 80, 30, 4, 1, 10, 45, 120, 210, 252, 210, 120, 45, 10, 1, 11, 55, 165, 330, 462, 461, 325, 154, 42, 4, 1, 12, 66, 220, 495, 792, 924, 792
(list; table; graph; listen)
|
|
|
OFFSET
|
2,3
|
|
|
COMMENT
|
Let R_k(n) be the number of compositions (ordered partitions) of n with k relatively prime parts. We have the following expressions for R: Formula: R_k(n) = sum_{d|n} C(d-1,k-1)mobius(n/d) Recurrence: C(n,k) = sum_{j=k..n} [n/j]R_k(j) for k>1 and R_1(j) = delta_j1 (the Kronecker delta). G.f.: sum_{j=1..infty} R_k(j)(x^j/(1-x^j)) = (x/(1-x))^k - C. Ronaldo
|
|
REFERENCES
|
H. W. Gould, Binomial coefficients, the bracket function and compositions with relatively prime summands, Fib. Quart. 2 (1964), 2.
|
|
EXAMPLE
|
Triangle begins:
1;
1 2;
1 3 2;
1 4 6 4;
1 5 10 9 2;
1 6 15 20 15 6;
...
|
|
MAPLE
|
with(numtheory):R:=proc(n, k) local s, d: s:=0: for d from 1 to n do if irem(n, d)=0 then s:=s+binomial(d-1, k-1)*mobius(n/d) fi od: RETURN(s) : end; seq(seq(R(n, n-k+1), k=1..n-1), n=1..15); R:=proc(n, k) options remember: local j: if k=1 then RETURN(piecewise(n=1, 1)) else RETURN(binomial(n, k)-add(floor(n/j)*R(j, k), j=k..n-1)) fi: end; seq(seq(R(n, n-k+1), k=1..n-1), n=1..15); (Ronaldo)
|
|
CROSSREFS
|
Emeric Deutsch points out that the mirror-image, A101391, is a better version of this triangle.
Sequence in context: A089353 A136451 A066121 this_sequence A002335 A119441 A058399
Adjacent sequences: A039908 A039909 A039910 this_sequence A039912 A039913 A039914
|
|
KEYWORD
|
tabl,nonn,easy
|
|
AUTHOR
|
N. J. A. Sloane (njas(AT)research.att.com).
|
|
EXTENSIONS
|
More terms from C. Ronaldo (aga_new_ac(AT)hotmail.com), Dec 28 2004
|
|
|
Search completed in 0.002 seconds
|
