A124094 Table T(n,m) giving number of partitions of n such that all parts are coprime to m. Read along antidiagonals (increasing n, decreasing m).

1, 1, 1, 1, 1, 2, 1, 1, 1, 3, 1, 1, 2, 2, 5, 1, 1, 1, 2, 2, 7, 1, 1, 2, 2, 4, 3, 11, 1, 1, 1, 3, 2, 5, 4, 15, 1, 1, 2, 1, 5, 3, 7, 5, 22, 1, 1, 1, 3, 1, 6, 4, 9, 6, 30, 1, 1, 2, 2, 5, 2, 10, 5, 13, 8, 42, 1, 1, 1, 2, 2, 7, 2, 13, 6, 16, 10, 56, 1, 1, 2, 2, 4, 3, 11, 3, 19, 8, 22, 12, 77, 1, 1, 1, 3, 2, 5, 4

Offset: 0

Author

R. J. Mathar, Nov 26 2006

Keywords

• easy
• nonn
• tabl

Examples

			Upper left corner of table starts with row m=1 and column n=0:
1,1,2,3,5,7,11,15,22,30,42,56,77,101,135,176,231,297,385,490,627,792,1002,1255,
1,1,1,2,2,3, 4, 5, 6, 8,10,12,15, 18, 22, 27, 32, 38, 46, 54, 64, 76,  89, 104,
1,1,2,2,4,5, 7, 9,13,16,22,27,36, 44, 57, 70, 89,108,135,163,202,243, 297, 355,
1,1,1,2,2,3, 4, 5, 6, 8,10,12,15, 18, 22, 27, 32, 38, 46, 54, 64, 76,  89, 104,
1,1,2,3,5,6,10,13,19,25,34,44,60, 76,100,127,164,205,262,325,409,505, 628, 769,
1,1,1,1,1,2, 2, 3, 3, 3, 4, 5, 6,  7,  8,  9, 10, 12, 14, 16, 18, 20,  23,  26,
1,1,2,3,5,7,11,14,21,28,39,51,70, 90,119,153,199,252,324,406,515,642, 804, 994,
1,1,1,2,2,3, 4, 5, 6, 8,10,12,15, 18, 22, 27, 32, 38, 46, 54, 64, 76,  89, 104,
1,1,2,2,4,5, 7, 9,13,16,22,27,36, 44, 57, 70, 89,108,135,163,202,243, 297, 355,
1,1,1,2,2,2, 3, 4, 4, 6, 7, 8,10, 12, 14, 16, 19, 22, 26, 30, 35, 41,  47,  54,
1,1,2,3,5,7,11,15,22,30,42,55,76, 99,132,171,224,286,370,468,597,750, 945,1177,
1,1,1,1,1,2, 2, 3, 3, 3, 4, 5, 6,  7,  8,  9, 10, 12, 14, 16, 18, 20,  23,  26,
1,1,2,3,5,7,11,15,22,30,42,56,77,100,134,174,228,292,378,479,612,770, 972,1213,
1,1,1,2,2,3, 4, 4, 5, 7, 8,10,12, 14, 17, 21, 24, 28, 34, 39, 46, 53,  61,  71,
1,1,2,2,4,4, 6, 7,11,12,16,19,25, 29, 37, 44, 56, 65, 80, 94,114,133, 160, 187,
1,1,1,2,2,3, 4, 5, 6, 8,10,12,15, 18, 22, 27, 32, 38, 46, 54, 64, 76,  89, 104,
1,1,2,3,5,7,11,15,22,30,42,56,77,101,135,176,231,296,384,488,624,787, 995,1244,
1,1,1,1,1,2, 2, 3, 3, 3, 4, 5, 6,  7,  8,  9, 10, 12, 14, 16, 18, 20,  23,  26,
1,1,2,3,5,7,11,15,22,30,42,56,77,101,135,176,231,297,385,489,626,790, 999,1250,
1,1,1,2,2,2, 3, 4, 4, 6, 7, 8,10, 12, 14, 16, 19, 22, 26, 30, 35, 41,  47,  54,
		

Links

• Alois P. Heinz, Antidiagonals n = 0..140, flattened
• N. Robbins, On partition functions and divisor sums, J. Int. Sequences, 5 (2002) 02.1.4.

Crossrefs

Row m=1 is A000041. Rows m=2, 4, 8, ... (where m is a power of 2) are A000009. Rows m=3, 9, ... (where m is a power of 3) are A000726. Row m=5 is A035959. Row=7 is A035985. Row m=10 is A096938.

Programs

Maple

b:= proc(n, i, m) option remember;
      if n<0 then 0
    elif n=0 then 1
    elif i<1 then 0
    else b(n, i-1, m) +`if`(igcd(m, i)=1, b(n-i, i, m), 0)
      fi
    end:
T:= (n, m)-> b(n, n, m):
seq (seq (T(n, 1+d-n), n=0..d), d=0..13);  # Alois P. Heinz, Sep 28 2011

Mathematica

b[n_, i_, m_] := b[n, i, m] = Which[n < 0, 0, n == 0, 1, i < 1, 0, True, b[n, i-1, m] + If[GCD[m, i] == 1, b[n-i, i, m], 0]]; t[n_, m_] := b[n, n, m]; Table[Table[t[n, 1+d-n], {n, 0, d}], {d, 0, 13}] // Flatten (* Jean-François Alcover, Jan 10 2014, translated from Alois P. Heinz's Maple code *)

PARI

sigmastar(n,m)= { local(d,res=0) ; d=divisors(n) ; for(i=1,matsize(d)[2], if( gcd(d[i],m)==1, res += d[i] ; ) ; ) ; return(res) ; } f(n,m)= { local(qvec=vector(n+1,i,gcd(1,m))) ; for(i=1,n, qvec[i+1]=sum(k=1,i,sigmastar(k,m)*qvec[i-k+1])/i ; ) ; return(qvec[n+1]) ; } { for(d=1,18, for(c=0,d-1, r=d-c ; print1(f(c,r),",") ; ) ; ) ; }