A327029 -id:A327029 - cp's OEIS frontend

A282750 Triangle read by rows: T(n,k) is the number of partitions of n into k parts x_1, x_2, ..., x_k such that gcd(x_1, x_2, ..., x_k) = 1 (where 1 <= k <= n).

1, 0, 1, 0, 1, 1, 0, 1, 1, 1, 0, 2, 2, 1, 1, 0, 1, 2, 2, 1, 1, 0, 3, 4, 3, 2, 1, 1, 0, 2, 4, 4, 3, 2, 1, 1, 0, 3, 6, 6, 5, 3, 2, 1, 1, 0, 2, 6, 8, 6, 5, 3, 2, 1, 1, 0, 5, 10, 11, 10, 7, 5, 3, 2, 1, 1, 0, 2, 8, 12, 12, 10, 7, 5, 3, 2, 1, 1, 0, 6, 14, 18, 18, 14

Offset: 1

N. J. A. Sloane, Mar 05 2017

Columns 2-10 are A023022-A023030. - Lars Blomberg Mar 08 2017

To base the triangle on (0, 0) a column (1, 0, 0, ...) has to be appended to the left hand side of the triangle. To compute this triangle with Michael De Vlieger's Mathematica program only the ranges of the indices have to be adapted. The SageMath program computes the extended triangle by default. - Peter Luschny, Aug 24 2019

			Triangle begins:
   n/k: 1,  2,  3,  4,  5,  6,  7,  8, ...
   1:   1;
   2:   0,  1;
   3:   0,  1,  1;
   4:   0,  1,  1,  1;
   5:   0,  2,  2,  1,  1;
   6:   0,  1,  2,  2,  1,  1;
   7:   0,  3,  4,  3,  2,  1,  1;
   8:   0,  2,  4,  4,  3,  2,  1,  1;
   9:   0,  3,  6,  6,  5,  3,  2,  1,  1;
  10:   0,  2,  6,  8,  6,  5,  3,  2,  1,  1;
  11:   0,  5, 10, 11, 10,  7,  5,  3,  2,  1,  1;
  12:   0,  2,  8, 12, 12, 10,  7,  5,  3,  2,  1,  1;
  ...
The partitions with their gcd value for n=8, k=2..5:
(1, 7)=1, (2, 6)=2, (3, 5)=1, (4, 4)=4, so T(8,2)=2.
(1, 1, 6)=1, (1, 2, 5)=1, (1, 3, 4)=1, (2, 2, 4)=2, (2, 3, 3)=1, so T(8,2)=4.
(1, 1, 1, 5)=1, (1, 1, 2, 4)=1, (1, 1, 3, 3)=1, (1, 2, 2, 3)=1, (2, 2, 2, 2)=2, so T(8,3)=4.
(1, 1, 1, 1, 4)=1, (1, 1, 1, 2, 3)=1, (1, 1, 2, 2, 2)=1, so T(8,4)=3.
(1, 1, 1, 1, 1, 3)=1, (1, 1, 1, 1, 2, 2)=1, so T(8,5)=2.

Michael De Vlieger, Table of n, a(n) for n = 1..5050 (rows 1 <= n <= 100)

Cf. A023022-A023030, A101391 (analog for compositions), A282749 (triangle of partitions into pairwise relatively prime parts).
Row sums = A000837. See also A051424.
For ordinary partition table see A008284.

Table[Length@ Select[IntegerPartitions[n, {k}], GCD @@ # == 1 &], {n, 13}, {k, n}] // Flatten (* Michael De Vlieger, Mar 08 2017 *)

# uses[DivisorTriangle from A327029, A008284]
DivisorTriangle(moebius, A008284, 13) # Peter Luschny, Aug 24 2019

T(n, k) = Sum_{d|n} Moebius(d) * A008284(n/d, k) for n >= 1, T(0, 0) = 1. - Peter Luschny, Aug 24 2019

Corrected a(30)-a(32) and more terms from Lars Blomberg, Mar 08 2017

A137651 Triangle read by rows: T(n,k) is the number of primitive (aperiodic) word structures of length n using exactly k different symbols.

Original entry on oeis.org

1, 0, 1, 0, 3, 1, 0, 6, 6, 1, 0, 15, 25, 10, 1, 0, 27, 89, 65, 15, 1, 0, 63, 301, 350, 140, 21, 1, 0, 120, 960, 1700, 1050, 266, 28, 1, 0, 252, 3024, 7770, 6951, 2646, 462, 36, 1, 0, 495, 9305, 34095, 42524, 22827, 5880, 750, 45, 1, 0, 1023, 28501, 145750, 246730, 179487, 63987, 11880, 1155, 55, 1

Offset: 1

Gary W. Adamson, Feb 01 2008

Row sums = A082951: (1, 1, 4, 13, 51, 197, ...).

			First few rows of the triangle are:
  1;
  0,   1;
  0,   3,   1;
  0,   6,   6,    1;
  0,  15,  25,   10,    1;
  0,  27,  89,   65,   15,   1;
  0,  63, 301,  350,  140,  21,  1;
  0, 120, 960, 1700, 1050, 266, 28, 1;
  ...
From _Andrew Howroyd_, Apr 03 2017: (Start)
Primitive word structures are:
n=1: a => 1
n=2: ab => 1
n=3: aab, aba, abb; abc => 3 + 1
n=4: aaab, aaba, aabb, abaa, abba, abbb => 6 (k=2)
     aabc, abac, abbc, abca, abcb, abcc => 6 (k=3)
(End)

Andrew Howroyd, Table of n, a(n) for n = 1..1275

Columns 2-6 are A056278 (or A000740), A056279, A056280, A056281, A056282.
Row sums are A082951.
Cf. A054525, A008277, A327029.

rows = 10; t[n_, k_] := If[Divisible[n, k], MoebiusMu[n/k], 0]; A054525 = Array[t, {rows, rows}]; A008277 = Array[StirlingS2, {rows, rows}]; T = A054525 . A008277; Table[T[[n, k]], {n, 1, rows}, {k, 1, n}] // Flatten (* Jean-François Alcover, Oct 07 2017 *)

T(n,k)={sumdiv(n, d, moebius(n/d)*stirling(d, k, 2))} \\ Andrew Howroyd, Aug 09 2018

# uses[DivisorTriangle from A327029]
# Computes an additional column (1,0,0,...)
# at the left hand side of the triangle.
DivisorTriangle(moebius, stirling_number2, 10) # Peter Luschny, Aug 24 2019

A054525 * A008277 as infinite lower triangular matrices. A054525 = Mobius transform, A008277 = Stirling2 triangle.

T(n,k) = Sum{d|n} mu(n/d) * Stirling2(d, k). - Andrew Howroyd, Aug 09 2018

Name changed and a(46)-a(66) from Andrew Howroyd, Aug 09 2018

A020921 Triangle read by rows: T(m,n) = number of solutions to 1 <= a(1) < a(2) < ... < a(m) <= n, where gcd( a(1), a(2), ..., a(m), n) = 1.

Original entry on oeis.org

1, 1, 1, 0, 1, 1, 0, 2, 3, 1, 0, 2, 5, 4, 1, 0, 4, 10, 10, 5, 1, 0, 2, 11, 19, 15, 6, 1, 0, 6, 21, 35, 35, 21, 7, 1, 0, 4, 22, 52, 69, 56, 28, 8, 1, 0, 6, 33, 83, 126, 126, 84, 36, 9, 1, 0, 4, 34, 110, 205, 251, 210, 120, 45, 10, 1, 0, 10, 55, 165, 330, 462, 462, 330, 165, 55, 11

Offset: 0

Michael Somos, Nov 17 2002

			From _R. J. Mathar_, Feb 12 2007: (Start)
Triangle begins
  1
  1 1
  0 1  1
  0 2  3   1
  0 2  5   4   1
  0 4 10  10   5   1
  0 2 11  19  15   6   1
  0 6 21  35  35  21   7   1
  0 4 22  52  69  56  28   8  1
  0 6 33  83 126 126  84  36  9  1
  0 4 34 110 205 251 210 120 45 10 1
The inverse of the triangle is
   1
  -1    1
   1   -1    1
  -1    1   -3    1
   1   -1    7   -4    1
  -1    1  -15   10   -5    1
   1   -1   31  -19   15   -6    1
  -1    1  -63   28  -35   21   -7    1
   1   -1  127  -28   71  -56   28   -8    1
  -1    1 -255    1 -135  126  -84   36   -9    1
   1   -1  511   80  255 -251  210 -120   45  -10    1
with row sums 1,0,1,-2,4,-9,22,-55,135,-319,721,...(cf. A038200).
(End)

Temba Shonhiwa, A Generalization of the Euler and Jordan Totient Functions, Fib. Quart., 37 (1999), 67-76.

(Left-hand) columns include A000010, A102309. Row sums are essentially A027375.

Cf. A327029.

A020921 := proc(n,k) option remember ; local divs ; if n <= 0 then 1 ; elif k > n then 0 ; else divs := numtheory[divisors](n) ; add(numtheory[mobius](op(i,divs))*binomial(n/op(i,divs),k),i=1..nops(divs)) ; fi ; end: nmax := 10 ; for row from 0 to nmax do for col from 0 to row do printf("%d,",A020921(row,col)) ; od ; od ; # R. J. Mathar, Feb 12 2007

nmax = 11; t[n_, k_] := Total[ MoebiusMu[#]*Binomial[n/#, k] & /@ Divisors[n]]; t[0, 0] = 1; Flatten[ Table[t[n, k], {n, 0, nmax}, {k, 0, n}]] (* Jean-François Alcover, Oct 20 2011, after PARI *)

{T(n, k) = if( n<=0, k==0 && n==0, sumdiv(n, d, moebius(d) * binomial(n/d, k)))}

# uses[DivisorTriangle from A327029]
DivisorTriangle(moebius, binomial, 13) # Peter Luschny, Aug 24 2019

A258170 T(n,k) = (1/k!) * Sum_{i=0..k} (-1)^(k-i) * C(k,i) * A185651(n,i); triangle T(n,k), n >= 0, 0 <= k <= n, read by rows.

Original entry on oeis.org

0, 0, 1, 0, 2, 1, 0, 3, 3, 1, 0, 4, 8, 6, 1, 0, 5, 15, 25, 10, 1, 0, 6, 36, 91, 65, 15, 1, 0, 7, 63, 301, 350, 140, 21, 1, 0, 8, 136, 972, 1702, 1050, 266, 28, 1, 0, 9, 261, 3027, 7770, 6951, 2646, 462, 36, 1, 0, 10, 530, 9355, 34115, 42526, 22827, 5880, 750, 45, 1

Offset: 0

Alois P. Heinz, May 22 2015

			Triangle T(n,k) begins:
  0;
  0,  1;
  0,  2,   1;
  0,  3,   3,    1;
  0,  4,   8,    6,     1;
  0,  5,  15,   25,    10,     1;
  0,  6,  36,   91,    65,    15,     1;
  0,  7,  63,  301,   350,   140,    21,    1;
  0,  8, 136,  972,  1702,  1050,   266,   28,   1;
  0,  9, 261, 3027,  7770,  6951,  2646,  462,  36,  1;
  0, 10, 530, 9355, 34115, 42526, 22827, 5880, 750, 45, 1;

Alois P. Heinz, Rows n = 0..140, flattened

Columns k=0-1 give: A000004, A000027.
Row sums give A258171.
Main diagonal gives A057427.
T(2*n+1,n+1) gives A129506(n+1).
Cf. A008277, A185651, A327029.

with(numtheory):
A:= proc(n, k) option remember;
      add(phi(d)*k^(n/d), d=divisors(n))
    end:
T:= (n, k)-> add((-1)^(k-i)*binomial(k, i)*A(n, i), i=0..k)/k!:
seq(seq(T(n, k), k=0..n), n=0..12);

A[n_, k_] := A[n, k] = DivisorSum[n, EulerPhi[#]*k^(n/#)&];
T[n_, k_] := Sum[(-1)^(k-i)*Binomial[k, i]*A[n, i], {i, 0, k}]/k!; T[0, 0] = 0;
Table[T[n, k], {n, 0, 12}, {k, 0, n}] // Flatten (* Jean-François Alcover, Mar 25 2017, translated from Maple *)

# uses[DivisorTriangle from A327029]
DivisorTriangle(euler_phi, stirling_number2, 10) # Peter Luschny, Aug 24 2019

T(n,k) = 1/k! * Sum_{i=0..k} (-1)^(k-i) * C(k,i) * A185651(n,i).
From Petros Hadjicostas, Sep 07 2018: (Start)
Conjecture 1: T(n,k) = Stirling2(n,k) for k >= 1 and k <= n <= 2*k - 1.
Conjecture 2: T(n,k) = Stirling2(n,k) for k >= 2 and n prime >= 2.
Here, Stirling2(n,k) = A008277(n,k).
(End)

A121775 T(n, k) = Sum_{d|n} phi(n/d)*binomial(d,k) for n>0, T(0, 0) = 1. Triangle read by rows, for 0 <= k <= n.

Original entry on oeis.org

1, 1, 1, 2, 3, 1, 3, 5, 3, 1, 4, 8, 7, 4, 1, 5, 9, 10, 10, 5, 1, 6, 15, 20, 21, 15, 6, 1, 7, 13, 21, 35, 35, 21, 7, 1, 8, 20, 36, 60, 71, 56, 28, 8, 1, 9, 21, 42, 86, 126, 126, 84, 36, 9, 1, 10, 27, 59, 130, 215, 253, 210, 120, 45, 10, 1, 11, 21, 55, 165, 330, 462, 462, 330, 165, 55

Offset: 0

Paul D. Hanna, Aug 23 2006

For n>0, (1/n)*Sum_{k=0..n} T(n,k)*(c-1)^k is the number of n-bead necklaces with c colors. See the cross references.

			Triangle begins:
[ 0]  1;
[ 1]  1,  1;
[ 2]  2,  3,  1;
[ 3]  3,  5,  3,   1;
[ 4]  4,  8,  7,   4,   1;
[ 5]  5,  9, 10,  10,   5,   1;
[ 6]  6, 15, 20,  21,  15,   6,   1;
[ 7]  7, 13, 21,  35,  35,  21,   7,   1;
[ 8]  8, 20, 36,  60,  71,  56,  28,   8,  1;
[ 9]  9, 21, 42,  86, 126, 126,  84,  36,  9,  1;
[10] 10, 27, 59, 130, 215, 253, 210, 120, 45, 10, 1;

Cf. A053635 (row sums), A121776 (antidiagonal sums), A054630, A327029.

Cf. A000031 (c=2), A001867 (c=3), A001868 (c=4), A001869 (c=5), A054625 (c=6), A054626 (c=7), A054627 (c=8), A054628 (c=9), A054629 (c=10).

PARI
```
T(n,k)=if(n
				
```

# uses[DivisorTriangle from A327029]
DivisorTriangle(euler_phi, binomial, 13) # Peter Luschny, Aug 24 2019

A181847 Triangle read by rows: T(n,k)= Sum_{c in C(n,k)}gcd(c) where C(n,k) is the set of all k-tuples of positive integers whose elements sum to n.

Original entry on oeis.org

1, 2, 1, 3, 2, 1, 4, 4, 3, 1, 5, 4, 6, 4, 1, 6, 9, 11, 10, 5, 1, 7, 6, 15, 20, 15, 6, 1, 8, 12, 24, 36, 35, 21, 7, 1, 9, 12, 30, 56, 70, 56, 28, 8, 1, 10, 17, 42, 88, 127, 126, 84, 36, 9, 1

Offset: 1

Peter Luschny, Dec 07 2010

C(n,k) counted by A007318(n-1,k-1) are also called compositions of n of size k (see A181842).

			[1]   1
[2]   2   1
[3]   3   2    1
[4]   4   4    3    1
[5]   5   4    6    4    1
[6]   6   9   11   10    5   1
[7]   7   6   15   20   15   6   1

Cf. A034738, A065567, A065568, A327029.

with(combstruct): # By generating the objects, very inefficient.
a181847_row := proc(n) local k,L,l,R,comp; R := NULL;
for k from 1 to n do
   L := 0;
   comp := iterstructs(Composition(n),size=k):
   while not finished(comp) do
      l := nextstruct(comp);
      L := L + igcd(op(l));
   od;
   R := R,L;
od;
R end:
# second Maple program:
with(numtheory):
T := (n, k) -> add(phi(d)*binomial(n/d-1, k-1), d = divisors(n)):
seq(seq(T(n, k), k=1..n), n=1..10); # Peter Luschny, Aug 27 2019

# uses[DivisorTriangle from A327029]
# DivisorTriangle Computes the (0,0)-based version.
DivisorTriangle(euler_phi, lambda n,k: binomial(n-1, k-1), 10) # Peter Luschny, Aug 27 2019

A327027 T(n, k) = (1/n) * Sum_{d|n} phi(d) * A241171(n/d, k) for n >= 1, T(0, k) = 0^k. Triangle read by rows for 0 <= k <= n.

Original entry on oeis.org

1, 0, 1, 0, 1, 3, 0, 1, 10, 30, 0, 1, 33, 315, 630, 0, 1, 102, 2646, 15120, 22680, 0, 1, 348, 21135, 263340, 1039500, 1247400, 0, 1, 1170, 167310, 4118400, 32432400, 97297200, 97297200, 0, 1, 4113, 1333080, 61757010, 871620750, 4937832900, 11918907000, 10216206000

Offset: 0

Peter Luschny, Aug 20 2019

We assume A241171 extended to its (0, 0)-based form.

			[0] 1;
[1] 0, 1;
[2] 0, 1, 3;
[3] 0, 1, 10,   30;
[4] 0, 1, 33,   315,    630;
[5] 0, 1, 102,  2646,   15120,   22680;
[6] 0, 1, 348,  21135,  263340,  1039500,  1247400;
[7] 0, 1, 1170, 167310, 4118400, 32432400, 97297200, 97297200;

Cf. A327021 (main diagonal), A327026 (row sums), A241171, A327029.

A327027 := (n, k)-> `if`(n=0, 1, (1/n)*add(phi(d)*A241171(n/d, k), d=divisors(n))):
seq(seq(A327027(n,k), k=0..n), n=0..6);

A327027[0,  k_] := 1;
A327027[n_, k_] := DivisorSum[n, EulerPhi[#] A241171[n/#, k] &] / n;
Table[A327027[n, k], {n, 0, 8}, {k, 0, n}] // Flatten

# uses[DivisorTriangle from A327029, A241171]
DivisorTriangle(euler_phi, A241171, 8, lambda n: 1/n if n > 1 else 1)

A327028 T(n, k) = k! * Sum_{d|n} phi(d) * A008284(n/d, k) for n >= 1, T(0, k) = 0^k. Triangle read by rows for 0 <= k <= n.

Original entry on oeis.org

1, 0, 1, 0, 2, 2, 0, 3, 2, 6, 0, 4, 6, 6, 24, 0, 5, 4, 12, 24, 120, 0, 6, 12, 24, 48, 120, 720, 0, 7, 6, 24, 72, 240, 720, 5040, 0, 8, 16, 36, 144, 360, 1440, 5040, 40320, 0, 9, 12, 54, 144, 600, 2160, 10080, 40320, 362880

Offset: 0

Peter Luschny, Aug 20 2019

			[0] 1
[1] 0, 1
[2] 0, 2,  2
[3] 0, 3,  2,  6
[4] 0, 4,  6,  6,  24
[5] 0, 5,  4, 12,  24, 120
[6] 0, 6, 12, 24,  48, 120,  720
[7] 0, 7,  6, 24,  72, 240,  720,  5040
[8] 0, 8, 16, 36, 144, 360, 1440,  5040, 40320
[9] 0, 9, 12, 54, 144, 600, 2160, 10080, 40320, 362880

Cf. A008284, A318144, A000142 (main diagonal), A327025 (row sums), A327029.

A327028 := (n,k) -> `if`(n=0, 1, k!*add(phi(d)*A008284(n/d, k), d = divisors(n))):
seq(seq(A327028(n, k), k=0..n), n=0..9);

A327028[0 , k_] := 1;
A327028[n_, k_] := DivisorSum[n, EulerPhi[#] A318144[n/#, k] (-1)^k &];
Table[A327028[n, k], {n, 0,  9}, {k, 0,  n}] // Flatten

# uses[DivisorTriangle from A327029]
from sage.combinat.partition import number_of_partitions_length
def A318144Abs(n, k): return number_of_partitions_length(n, k)*factorial(k)
DivisorTriangle(euler_phi, A318144Abs, 10)

cp's OEIS Frontend

A282750 Triangle read by rows: T(n,k) is the number of partitions of n into k parts x_1, x_2, ..., x_k such that gcd(x_1, x_2, ..., x_k) = 1 (where 1 <= k <= n).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Sage

Formula

Extensions

A137651 Triangle read by rows: T(n,k) is the number of primitive (aperiodic) word structures of length n using exactly k different symbols.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Sage

Formula

Extensions

A020921 Triangle read by rows: T(m,n) = number of solutions to 1 <= a(1) < a(2) < ... < a(m) <= n, where gcd( a(1), a(2), ..., a(m), n) = 1.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Sage

A258170 T(n,k) = (1/k!) * Sum_{i=0..k} (-1)^(k-i) * C(k,i) * A185651(n,i); triangle T(n,k), n >= 0, 0 <= k <= n, read by rows.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Sage

Formula

A121775 T(n, k) = Sum_{d|n} phi(n/d)*binomial(d,k) for n>0, T(0, 0) = 1. Triangle read by rows, for 0 <= k <= n.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

PARI

SageMath

A181847 Triangle read by rows: T(n,k)= Sum_{c in C(n,k)}gcd(c) where C(n,k) is the set of all k-tuples of positive integers whose elements sum to n.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Maple

Sage

A327027 T(n, k) = (1/n) * Sum_{d|n} phi(d) * A241171(n/d, k) for n >= 1, T(0, k) = 0^k. Triangle read by rows for 0 <= k <= n.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs