A060867 -id:A060867 - cp's OEIS frontend

A379587 Array read by ascending antidiagonals: A(n, k) = (k^n - 1)^2/(k - 1), with k >= 2.

0, 1, 0, 9, 2, 0, 49, 32, 3, 0, 225, 338, 75, 4, 0, 961, 3200, 1323, 144, 5, 0, 3969, 29282, 21675, 3844, 245, 6, 0, 16129, 264992, 348843, 97344, 9245, 384, 7, 0, 65025, 2389298, 5589675, 2439844, 335405, 19494, 567, 8, 0, 261121, 21516800, 89467563, 61027344, 12090125, 960000, 37303, 800, 9, 0

Offset: 0

Stefano Spezia, Dec 26 2024

			The array begins as:
    0,     0,      0,       0,        0,        0, ...
    1,     2,      3,       4,        5,        6, ...
    9,    32,     75,     144,      245,      384, ...
   49,   338,   1323,    3844,     9245,    19494, ...
  225,  3200,  21675,   97344,   335405,   960000, ...
  961, 29282, 348843, 2439844, 12090125, 47073606, ...
  ...

Cf. A027620, A060867 (k=2), A060868 (k=3), A060869 (k=4), A060870 (k=5), A060871 (k=7), A361475, A379588 (antidiagonal sums).

A[n_,k_]:=(k^n-1)^2/(k-1); Table[A[n-k+2,k],{n,0,9},{k,2,n+2}]//Flatten

G.f. of column k: (1 - k)*x*(1 + k*x)/((1 - x)*(1 - k*x)*(1 - k^2*x)).
E.g.f. of column k: exp(x)*(1 - 2*exp((k-1)*x) + exp((k^2-1)*x))/(k - 1).
A(2, n) = A027620(n-2) for n > 1.

A081474 Number of distinct lines through the origin in n-dimensional cube of side length n.

Original entry on oeis.org

0, 1, 5, 49, 529, 7471, 112825, 2078455, 42649281, 997784221, 25875851825, 742641202183, 23283999690561, 793616663524231, 29188521870580929, 1152885848976064513, 48659336030073207425, 2185894865613157551481, 104126348669497256201905, 5242869988601103651841105

Offset: 0

Joshua Zucker, Nov 25 2003

nonn

Equivalently, lattice points where the GCD of all coordinates = 1.

			a(3) = 49 because in the 3-dimensional lattice of side length 3, the lines through the origin are determined by all 37 points with at least one coordinate = 3 and 6 permutations of (2,1,0) and 3 permutations each of (2,1,1) and (2,2,1).

Alois P. Heinz, Table of n, a(n) for n = 0..386

Cf. A000225, A001047, A060867, A090020, A090021, A090022, A090023, A090024 are for n dimensions with side length 1, 2, 3, 4, 5, 6, 7, 8, respectively. A049691, A090025, A090026, A090027, A090028, A090029 are this sequence for 2, 3, 4, 5, 6, 7 dimensions. A090030 is the table for n dimensions, side length k.

a:= n-> add(numtheory[mobius](i)*((floor(n/i)+1)^n-1), i=1..n):
seq(a(n), n=0..20);  # Alois P. Heinz, Mar 09 2022

aux[n_, k_] := If[k == 0, 0, (k + 1)^n - k^n - Sum[aux[n, Divisors[k][[i]]], {i, 1, Length[Divisors[k]] - 1}]];lines[n_, k_] := (k + 1)^n - Sum[Floor[k/i - 1]*aux[n, i], {i, 1, Floor[k/2]}] - 1;Table[lines[k, k], {k, 0, 20}]

a(n) = A090030(n,n).

A088037 Smallest square k == 1 (mod some n-th power), k > 1.

Original entry on oeis.org

4, 9, 9, 49, 225, 961, 3969, 16129, 65025, 261121, 1046529, 4190209, 16769025, 67092481, 268402689, 1073676289, 4294836225, 17179607041, 68718952449, 274876858369, 1099509530625, 4398042316801, 17592177655809

Offset: 1

Amarnath Murthy, Sep 19 2003

From a(2) onwards the n-th power that divides a(n) -1 is 2^n ===> Second term onwards same as A060867 i.e. a(n+1) = (2^n-1)^2.

			a(6) = 961 and 960 = 64*15.

Index entries for linear recurrences with constant coefficients, signature (7,-14,8).

Cf. A060867.

From Colin Barker, Feb 05 2013: (Start)
a(n) = (2^n-2)^2/4 for n>2.
a(n) = 7*a(n-1)-14*a(n-2)+8*a(n-3) for n>5.
G.f.: x*(2*x+1)*(32*x^3-56*x^2+27*x-4) / ((x-1)*(2*x-1)*(4*x-1)). (End)

More terms from Ray Chandler, Oct 04 2003

A128832 Number of n-tuples where each entry is chosen from the subsets of {1,2,3,4} such that the intersection of all n entries is empty.

Original entry on oeis.org

1, 81, 2401, 50625, 923521, 15752961, 260144641, 4228250625, 68184176641, 1095222947841, 17557851463681, 281200199450625, 4501401006735361, 72040003462430721, 1152780773560811521, 18445618199572250625

Offset: 1

Peter C. Heinig (algorithms(AT)gmx.de), Apr 13 2007

The general formula where each entry is chosen from the subsets of {1,...,k} is (2^n-1)^k. This may be shown by exhibiting a bijection to a set whose cardinality is obviously (2^n-1)^k, namely the set of all k-tuples with each entry chosen from the 2^n-1 proper subsets of {1,...,n}, i.e., for of the k entries {1,...,n} is forbidden. The bijection is given by (X_1,...,X_n) |-> (Y_1,...,Y_k) where for each j in {1,...,k} and each i in {1,...,n}, i is in Y_j if and only if j is in X_i. Sequence A060867 is the case where the entries are chosen from subsets of {1,2}.

			a(1) = (2^1 - 1)^4 = 1 because only one tuple of length one, namely ({}), has an empty intersection of its sole entry.

Stanley, R. P.: Enumerative Combinatorics: Volume 1: Wadsworth & Brooks: 1986: p. 11

Index entries for linear recurrences with constant coefficients, signature (31,-310,1240,-1984,1024).

Cf. A000225 (2^n-1), A000583 (n^4).

for k from 1 to 20 do (2^k-1)^4; od;
with (combinat):seq(mul(stirling2(n,2),k=1..4),n=2..17); # Zerinvary Lajos, Dec 16 2007

LinearRecurrence[{31,-310,1240,-1984,1024},{1,81,2401,50625,923521},20] (* Harvey P. Dale, Mar 30 2019 *)

a(n) = (2^n - 1)^4.

G.f.: -x*(4*x+1)*(16*x^2+46*x+1)/((x-1)*(2*x-1)*(4*x-1)*(8*x-1)*(16*x-1)). [Colin Barker, Nov 17 2012]

A128833 Number of n-tuples where each entry is chosen from the subsets of {1,2,3,4,5} such that the intersection of all n entries is empty.

Original entry on oeis.org

1, 243, 16807, 759375, 28629151, 992436543, 33038369407, 1078203909375, 34842114263551, 1120413075641343, 35940921946155007, 1151514816750309375, 36870975646169341951, 1180231376725002502143, 37773167607267111108607

Offset: 1

Peter C. Heinig (algorithms(AT)gmx.de), Apr 13 2007

The general formula where each entry is chosen from the subsets of {1,..,k} is (2^n-1)^k. This may be shown by exhibiting a bijection to a set whose cardinality is obviously (2^n-1)^k, namely the set of all k-tuples with each entry chosen from the 2^n-1 proper subsets of {1,..,n}, i.e. for of the k entries {1,..,n} is forbidden. The bijection is given by (X_1,..,X_n) |-> (Y_1,..,Y_k) where for each j in {1,..,k} and each i in {1,..,n}, i is in Y_j if and only if j is in X_i. Sequence A060867 is the case where the entries are chosen from subsets of {1,2}.

			a(1)=(2^1-1)^5=1 because only one tuple of length one, namely ({}) has an empty intersection of its sole entry.

Richard P. Stanley, Enumerative Combinatorics, Volume 1, Wadsworth & Brooks, 1986, p. 11.

Harvey P. Dale, Table of n, a(n) for n = 1..664
Index entries for linear recurrences with constant coefficients, signature (63,-1302,11160,-41664,64512,-32768).

Cf. A060867.

Maple
```
for k from 1 to 20 do (2^k-1)^5; od;
```

(2^Range[20]-1)^5 (* or *) LinearRecurrence[{63,-1302,11160,-41664,64512,-32768},{1,243,16807,759375,28629151,992436543},20] (* or *) CoefficientList[Series[x (1024x^4+5760x^3+2800x^2+180x+1)/((x-1)(2x-1)(4x-1)(8x-1)(16x-1)(32x-1)),{x,0,20}],x] (* Harvey P. Dale, Aug 16 2021 *)

a(n) = (2^n-1)^5

G.f.: x*(1024*x^4+5760*x^3+2800*x^2+180*x+1)/((x-1)*(2*x-1)*(4*x-1)*(8*x-1)*(16*x-1)*(32*x-1)). [Colin Barker, Nov 17 2012]

A302761 Number of total dominating sets in the n-barbell graph.

Original entry on oeis.org

1, 4, 23, 136, 707, 3312, 14527, 61264, 252515, 1027192, 4147343, 16674984, 66887875, 267960544, 1072726271, 4292804896, 17175281987, 68709777768, 274857460111, 1099468636600, 4397956334051, 17591997301264, 70368349913663, 281474154627696, 1125898195567267

Offset: 1

Eric W. Weisstein, Apr 12 2018

Colin Barker, Table of n, a(n) for n = 1..1000
Eric Weisstein's World of Mathematics, Barbell Graph
Eric Weisstein's World of Mathematics, Total Dominating Set
Index entries for linear recurrences with constant coefficients, signature (11,-47,101,-116,68,-16).

Cf. A060867, A302650.

[(2^n-n)^2 - (2^n-2*n): n in [1..30]]; // Vincenzo Librandi, Apr 15 2018

Array[(2^# - #)^2 - (2^# - 2 #) &, 30] (* Michael De Vlieger, Apr 14 2018 *)
Table[(2^n - n)^2 - (2^n - 2*n), {n, 30}]
LinearRecurrence[{11, -47, 101, -116, 68, -16}, {1, 4, 23, 136, 707, 3312}, 30]
CoefficientList[Series[(1 - 7 x + 26 x^2 - 30 x^3 + 4 x^4)/((-1 + x)^3 (-1 + 2 x)^2 (-1 + 4 x)), {x, 0, 30}], x] (* Eric W. Weisstein, Apr 16 2018 *)

a(n)={(2^n-n)^2 - (2^n-2*n)} \\ Andrew Howroyd, Apr 14 2018

Vec(x*(1 - 7*x + 26*x^2 - 30*x^3 + 4*x^4) / ((1 - x)^3*(1 - 2*x)^2*(1 - 4*x)) + O(x^30)) \\ Colin Barker, Apr 15 2018

a(n) = (2^n-n)^2 - (2^n-2*n). - Andrew Howroyd, Apr 14 2018
From Colin Barker, Apr 15 2018: (Start)
G.f.: x*(1 - 7*x + 26*x^2 - 30*x^3 + 4*x^4) / ((1 - x)^3*(1 - 2*x)^2*(1 - 4*x)).
a(n) = 11*a(n-1) - 47*a(n-2) + 101*a(n-3) - 116*a(n-4) + 68*a(n-5) - 16*a(n-6) for n>6. (End)
E.g.f.: exp(x)*(exp(3*x) + x*(3 + x) - exp(x)*(1 + 4*x)). - Stefano Spezia, Sep 06 2023

a(1)-a(2) and a(11)-a(25) from Andrew Howroyd, Apr 14 2018

A354741 Triangular array read by rows. T(n,k) is the number of n X n Boolean matrices with row rank k, n >= 0, 0 <= k <= n.

Original entry on oeis.org

1, 1, 1, 1, 9, 6, 1, 49, 306, 156, 1, 225, 8550, 37488, 19272, 1, 961, 194850, 4811700, 17551800, 10995120

Offset: 0

Geoffrey Critzer, Jun 12 2022

Compare to A286331 which counts n X n matrices over the field GF(2). Note that the limit when n->oo of the probability that a matrix over GF(2) has rank n is equal to Product_{i>=1} (1-1/2^i) = 0.288... (see A048651). Here, it appears (from some empirical computations) that the limiting probability that a Boolean matrix has rank n is 1.

			Table begins:
  1;
  1,   1;
  1,   9,    6;
  1,  49,  306,   156;
  1, 225, 8550, 37488, 19272;
  ...

Wikipedia, Boolean matrix

Columns k = 0 and 1 give A000012, A060867.
Row sums give A002416.
Cf. A048651, A064230, A286331, A355333.

Table[B = Tuples[Tuples[{0, 1}, nn],nn]; bospan[matrix_]:= Sort[DeleteDuplicates[
     Map[Clip[Total[#]] &, Drop[Subsets[matrix], 1]]]]; rowrank[matrix_] :=
   If[Total[Map[Total, matrix]] == 0, 0, Length[Select[Drop[Subsets[DeleteCases[matrix, Table[0, {nn}]]], 1],
       bospan[#] == bospan[DeleteCases[matrix, Table[0, {nn}]]] &][[ 1]]]]; Tally[
    Table[rowrank[B[[i]]], {i, 1, 2^(nn^2)}]][[All,2]], {nn, 0, 4}] // Grid

T(n,0) = 1.
T(n,1) = (2^n-1)^2.
T(n,2) = (3^n - 2*2^n + 1)^2 + (1/2)*(4^n - 2*3^n + 2^n)^2.

Row n=5 from Pontus von Brömssen, Jul 14 2022

A384988 a(n) = Stirling2(n,2)^2 + Stirling2(n,3).

Original entry on oeis.org

0, 1, 10, 55, 250, 1051, 4270, 17095, 68050, 270451, 1075030, 4276735, 17030650, 67881451, 270777790, 1080817975, 4316294050, 17244046051, 68912400550, 275457464815, 1101251874250, 4403270396251, 17607863991310, 70415790601255, 281616141147250, 1126323450484051

Offset: 1

Julian Allagan, Jun 14 2025

Also, one third of the number of proper vertex colorings of the n-complete tripartite graph using exactly 5 interchangeable colors.

The complete 3-partite graph K(n,n,n) has 3n vertices partitioned into three sets of size n each, with edges between every pair of vertices from different sets. 3*a(n) = 0 for n < 2 because we need at least 2 vertices per partition to create 5 nonempty independent sets.

			3*a(2) = 3 because K(2,2,2) can be partitioned into 5 nonempty independent sets in exactly 3 ways.

Vincenzo Librandi, Table of n, a(n) for n = 1..500
Richard P. Stanley, Enumerative Combinatorics, Cambridge University Press.
Eric Weisstein's World of Mathematics, Complete Multipartite Graph.
Eric Weisstein's World of Mathematics, Stirling Number of the Second Kind.
Index entries for linear recurrences with constant coefficients, signature (10,-35,50,-24).

Cf. A000392, A000453, A060867, A385432.

[(6 - 3*2^(n+1) + 2*3^(n-1) + 4^n)/4: n in [1..30]]; // Vincenzo Librandi, Jul 24 2025

Table[(StirlingS2[n, 3] + StirlingS2[n, 2]^2), {n, 1, 20}]

3*a(n) = 2^(2*n - 2) + (1/2)*3^(n - 1) - 3*2^(n - 1) + 3/2 for n >= 1.
G.f.: 1/(4*(1 - 4*x)) + 1/(6*(1 - 3*x)) - 3/(2*(1 - 2*x)) + 3/(2*(1 - x)).
a(n) = A385432(n, 5) / 3 = A060867(n-1) + A000392(n).
From Stefano Spezia, Jun 14 2025: (Start)
a(n) = (6 - 3*2^(n+1) + 2*3^(n-1) + 4^n)/4.
E.g.f.: (exp(x) - 1)^2*(3*exp(2*x) + 8*exp(x) - 5)/12. (End)
a(n) = A000453(n+2) -10*A000453(n). - R. J. Mathar, Jul 20 2025

A233757 Triangle read by rows: T(n,k) = (2^n-1)*2^(k-1), for n >= 1 and 1<=k<=n.

Original entry on oeis.org

1, 3, 6, 7, 14, 28, 15, 30, 60, 120, 31, 62, 124, 248, 496, 63, 126, 252, 504, 1008, 2016, 127, 254, 508, 1016, 2032, 4064, 8128, 255, 510, 1020, 2040, 4080, 8160, 16320, 32640, 511, 1022, 2044, 4088, 8176, 16352, 32704, 65408, 130816, 1023, 2046, 4092

Offset: 1

Omar E. Pol, Jan 12 2014

Column 1 gives the positive terms of A000225.
Leading diagonal gives the positive terms of A006516.
The sum of row n is T(n,1)^2 = A000225(n)^2, hence row sums give A060867.
If n = A000043(m) then T(n,1) = A000668(m) and row n lists last n divisors of m-th even perfect number, which are also the divisors that are multiples of m-th Mersenne prime, for m >= 1.
If n = A000043(m) then T(n,n) = A000396(m), assuming there are no odd perfect numbers, for m >= 1.

			Triangle begins:
1;
3, 6;
7, 14, 28;
15, 30, 60, 120;
31, 62, 124, 248, 496;
63, 126, 252, 504, 1008, 2016;
127, 254, 508, 1016, 2032, 4064, 8128;
255, 510, 1020, 2040, 4080, 8160, 16320, 32640;
511, 1022, 2044, 4088, 8176, 16352, 32704, 65408, 130816;
...

Harvey P. Dale, Table of n, a(n) for n = 1..5000

Cf. A000043, A000079, A000225, A000396, A000668, A006516, A018254, A018487, A059268, A060867, A133024, A133025, A135652-A135655, A139247.

Table[(2^n-1)2^(k-1),{n,10},{k,n}]//Flatten (* Harvey P. Dale, Oct 10 2018 *)

T(n,k) = A000225(n)*A000079(k-1), n >= 1, 1<=k<=n.

A242078 Smallest square number > 10*a(n-1) with a(1) = 1.

Original entry on oeis.org

1, 16, 169, 1764, 17689, 177241, 1774224, 17749369, 177502329, 1775105424, 17751298756, 177513070329, 1775132540281, 17751332312289, 177513333968569, 1775133399758224, 17751334196261689, 177513342503762329

Offset: 1

J. Lowell, May 03 2014

nonn

			Term after 169 cannot be 1681 because 1681 is less than 10 times 169.

Jon E. Schoenfield, Table of n, a(n) for n = 1..250

Cf. other sequences with smallest square > k*a(n-1): A175627 (k=2), A060867 (k=4).

nMax:=100; a:=1; for n in [1..nMax] do a:=(Isqrt(a*10)+1)^2; a; end for; // Jon E. Schoenfield, May 06 2014

NestList[Ceiling[Sqrt[10#]]^2&,1,20] (* Harvey P. Dale, Sep 03 2020 *)

lista(nn, k=10) = {a=1; for (n=1, nn, print1(a, ", "); a = (sqrtint(a*k)+1)^2;);} \\ Michel Marcus, May 06 2014

cp's OEIS Frontend

A379587 Array read by ascending antidiagonals: A(n, k) = (k^n - 1)^2/(k - 1), with k >= 2.

Views

Author

Keywords

Examples

Crossrefs

Programs

Mathematica

Formula

A081474 Number of distinct lines through the origin in n-dimensional cube of side length n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A088037 Smallest square k == 1 (mod some n-th power), k > 1.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

Extensions

A128832 Number of n-tuples where each entry is chosen from the subsets of {1,2,3,4} such that the intersection of all n entries is empty.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A128833 Number of n-tuples where each entry is chosen from the subsets of {1,2,3,4,5} such that the intersection of all n entries is empty.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A302761 Number of total dominating sets in the n-barbell graph.

Views

Author

Keywords

Links

Crossrefs

Programs

Magma

Mathematica

PARI

PARI

Formula

Extensions

A354741 Triangular array read by rows. T(n,k) is the number of n X n Boolean matrices with row rank k, n >= 0, 0 <= k <= n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs