login
This site is supported by donations to The OEIS Foundation.

 

Logo

Thanks to everyone who made a donation during our annual appeal!
To see the list of donors, or make a donation, see the OEIS Foundation home page.

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A039911 Triangle read by rows: number of compositions of n into relatively prime summands. 1
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; refs; listen; history; text; internal format)
OFFSET

2,3

COMMENTS

From C. Ronaldo: (Start)

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} floor(n/j)*R_k(j) for k > 1 and R_1(j) = delta_j1 (the Kronecker delta).

G.f.: Sum_{j>=1} R_k(j)(x^j/(1-x^j)) = (x/(1-x))^k. (End)

LINKS

Table of n, a(n) for n=2..75.

H. W. Gould, Binomial coefficients, the bracket function and compositions with relatively prime summands, Fib. Quart. 2(4) (1964), 241-260.

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); # C. Ronaldo

CROSSREFS

Emeric Deutsch points out that the mirror-image, A101391, is a better version of this triangle.

Sequence in context: A089353 A136451 A066121 * A208945 A209073 A220901

Adjacent sequences:  A039908 A039909 A039910 * A039912 A039913 A039914

KEYWORD

tabl,nonn,easy

AUTHOR

N. J. A. Sloane

EXTENSIONS

More terms from C. Ronaldo (aga_new_ac(AT)hotmail.com), Dec 28 2004

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified January 19 18:27 EST 2019. Contains 319309 sequences. (Running on oeis4.)