A171477 -id:A171477 - cp's OEIS frontend

A134057 a(n) = binomial(2^n-1,2).

0, 0, 3, 21, 105, 465, 1953, 8001, 32385, 130305, 522753, 2094081, 8382465, 33542145, 134193153, 536821761, 2147385345, 8589737985, 34359345153, 137438167041, 549754241025, 2199020109825, 8796086730753, 35184359505921

Offset: 0

Ross La Haye, Jan 11 2008, Jun 01 2008

Let P(A) be the power set of an n-element set A. Then a(n) = the number of pairs of elements {x,y} of P(A) for which either 0) x and y are disjoint and for which x is not a subset of y and y is not a subset of x, or 1) x and y are intersecting but for which x is not a subset of y and y is not a subset of x, or 2) x and y are intersecting and for which either x is a proper subset of y or y is a proper subset of x.
Or: Number of connections between the nodes of the perfect depth n binary tree and the nodes of a perfect depth (n-1) binary tree. - Alex Ratushnyak, Jun 02 2013
a(n) is the number of positive entries in the positive rows and columns of a Walsh matrix of order 2^n. It is also the size of the smallest nontrivial conjugacy class in the general linear group GL(n,2). See the link "3-bit Walsh permutation...". - Tilman Piesk, Sep 15 2022

			a(2) = 3 because for P(A) = {{},{1},{2},{1,2}} we have for case 0 {{1},{2}} and we have for case 2 {{1},{1,2}}, {{2},{1,2}}. There are 0 {x,y} of P(A) in this example that fall under case 1.

Robert Israel, Table of n, a(n) for n = 0..1600
Ross La Haye, Binary Relations on the Power Set of an n-Element Set, Journal of Integer Sequences, Vol. 12 (2009), Article 09.2.6. - _Ross La Haye_, Feb 22 2009
Tilman Piesk, 3-bit Walsh permutation; conjugacy class 2+2 (Wikiversity)
Index entries for linear recurrences with constant coefficients, signature (7,-14,8).

Cf. A000217, A000225, A000392, A032263, A028243, A171477.

[Binomial(2^n-1, 2): n in [0..30]]; // Vincenzo Librandi, Nov 30 2015

seq((2^n-1)*(2^(n-1)-1), n=0..100); # Robert Israel, Nov 30 2015

Table[Binomial[2^n - 1, 2], {n, 0, 30}] (* Vincenzo Librandi, Nov 30 2015 *)

a(n) = binomial(2^n-1, 2); \\ Michel Marcus, Nov 30 2015

print([(2**n-1)*(2**(n-1)-1) for n in range(23)])
# Alex Ratushnyak, Jun 02 2013

a(n) = (1/2)*(4^n - 3*2^n + 2) = 3*(Stirling2(n+1,4) + Stirling2(n+1,3)).
a(n) = 3 *A006095(n).
a(n) = (2^n-1)*(2^(n-1)-1). - Alex Ratushnyak, Jun 02 2013
a(n) = Stirling2(2^n - 1,2^n - 2).
G.f.: 3*x^2/(1-x)/(1-2*x)/(1-4*x). - Colin Barker, Feb 22 2012
a(n) = A000225(n)*A000225(n-1). - Michel Marcus, Nov 30 2015
a(n) = A000217(2^n-2). - Michel Marcus, Nov 30 2015
a(n) = 7*a(n-1) - 14*a(n-2) + 8*a(n-3). - Wesley Ivan Hurt, May 17 2021
E.g.f.: exp(x)*(exp(x) - 1)^2*(exp(x) + 2)/2. - Stefano Spezia, Apr 06 2022

A249993 Expansion of 1/((1+x)(1+2x)(1-4x)).

Original entry on oeis.org

1, 1, 11, 29, 147, 525, 2227, 8653, 35123, 139469, 559923, 2235597, 8950579, 35785933, 143176499, 572640461, 2290692915, 9162509517, 36650562355, 146601200845, 586406900531, 2345623407821, 9382502019891, 37529991302349, 150119998763827, 600479927946445

Offset: 0

Alex Ratushnyak, Dec 27 2014

Colin Barker, Table of n, a(n) for n = 0..1000
Index entries for linear recurrences with constant coefficients, signature (1,10,8).

Cf. A249992.
Cf. A006095, A171477 for g.f. 1/((1-x)*(1-2*x)*(1-4*x)).
Cf. A015249, A084152, A084175 for g.f. 1/((1-x)*(1+2*x)*(1-4*x)).
Cf. A109765 for g.f. 1/((1+x)*(1-2*x)*(1-4*x)).

[(2^(2*n+3) +(-1)^n*(5*2^(n+1)-3))/15: n in [0..40]]; // G. C. Greubel, Oct 10 2022

CoefficientList[Series[1/((1+x)(1+2x)(1-4x)),{x,0,30}],x] (* or *) LinearRecurrence[{1,10,8},{1,1,11},30] (* Harvey P. Dale, Dec 13 2018 *)

Vec(1/((1+x)*(1+2*x)*(1-4*x)) + O(x^40)) \\ Michel Marcus, Dec 28 2014

[(2^(2*n+3) +(-1)^n*(5*2^(n+1)-3))/15 for n in range(41)] # G. C. Greubel, Oct 10 2022

G.f.: 1/((1+x)*(1+2*x)*(1-4*x)).
a(n) = ( 2^(3+2*n) + (5*2^(1+n) - 3)*(-1)^n )/15. Colin Barker, Dec 28 2014
a(n) = a(n-1) + 10*a(n-2) + 8*a(n-3). - Colin Barker, Dec 28 2014
E.g.f.: (1/15)*(10*exp(-2*x) - 3*exp(-x) + 8*exp(4*x)). - G. C. Greubel, Oct 10 2022

A334638 Three-column array pPT read by rows: subsequence of primitive Pythagorean triples (x, y, z) with x = A153893^2 - A000079^2, y = 2A153893A000079, z = A153893^2 + A000079^2, ordered by increasing z.

Original entry on oeis.org

3, 4, 5, 21, 20, 29, 105, 88, 137, 465, 368, 593, 1953, 1504, 2465, 8001, 6080, 10049, 32385, 24448, 40577, 130305, 98048, 163073, 522753, 392704, 653825, 2094081, 1571840, 2618369, 8382465, 6289408, 10479617, 33542145, 25161728, 41930753, 134193153, 100655104, 167747585, 536821761, 402636800, 671039489, 2147385345, 1610579968, 2684256257

Offset: 0

Ralf Steiner, May 07 2020

Let [h21] = {{1, 3}, {0, 2}} be the matrix [h_2]*[h_1] in Firstov's notation, from eqs. (24) and (39). Then primitive Pythagorean triples (pPT) (x(n), y(n), z(n)) = (u(n)^2 - v(n)^2, 2*u(n)*v(n), u(n)^2 + v(n)^2), with u(n) and v(n) of different parity, gcd(u(n), v(n)) = 1, and u(n) > v(n) > 0, are generated by (u(n), v(n))^T = [h21]^n*(2,1)^T (T for transpose).
For n > 0: (x(n), y(n), z(n)) = (1, 0, 1) (mod 4). Thus some z are Pythagorean primes (A002144).
The triples converge to the proportion (4:3:5) with:
lim_{n->infinity} x(n)/y(n) = 4/3, lim_{n->infinity} y(n)/z(n) = 3/5.
Altitude h(n) = x(n)*y(n)/z(n) is an irreducible fraction because of primitivity.
From Wolfdieter Lang, Jun 13 2020: (Start)
[h21]^n = sqrt(2)^n*(S(n, 3/sqrt(2))*[1_3] + S(n-1, 3/sqrt(2))*(1/sqrt(2))*([h21] - 3*[1_3])) with the Chebyshev S polynomials (A049310).
u(n) = sqrt(2)^n*(2*S(n, 3/sqrt(2)) - (1/sqrt(2))*S(n-1, 3/sqrt(2)))
     = A153893(n),
v(n) = sqrt(2)^n*(S(n, 3/sqrt(2)) - (1/sqrt(2))*S(n-1, 3/sqrt(2)))
     = A000079(n). Proof from the recurrence, using the Cayley-Hamilton theorem.
With the monic Chebyshev T polynomials, called R in A127672:
x(n)/3 = 2^(n+1)*(R(2*(n+1), 3/sqrt(2)) - (sqrt(2)/3)*R(2*n+1,3/sqrt(2)) - 1) = A171477(n),
y(n)/4 = 3*2^(n-1)*(sqrt(2)*R(2*n+1,3/sqrt(2)) - R(2*n,3/sqrt(2)) - 1/3)
= A010036(n),
z(n) = 3*2^(n+1)*((3/sqrt(2))*R(2*n+1, 3/sqrt(2)) - (4/3)*R(2*n,3/sqrt(2)) - 1).
Using 2^n*Rnx(2*n, 3/sqrt(2)) = A052539(n) = 2^(2*n) + 1, and
  2^(n)*(sqrt(2)/3)*Rnx(2*n+1, 3/sqrt(2)) = A007583(n) = (2^(2*n + 1) + 1)/3,
produces the explicit formulas given by the author in the formula section.
G.f.s for {x(n)} G0(x) = 3/((1 - 4*x)*(1 - 2*x)*(1 - x)), for {y(n)} G1(x) =  4*(1-x)/((1 - 4*x)*(1 - 2*x)), and for {z(n)} = (5 - 6*x + 4*x^2)/((1 - 4*x)*(1 - 2*x)*(1 - x)). This produces the g.f. for the array, read as sequence {a(n)}: G(x) = G0(x^3) + x*G1(x^3) + x^2*G2(x^3) given in the formula section by Colin Barker.
(End)

			The three-column array pPT(n,k) begins:
n\k        0        1         2
-------------------------------
0:         3        4         5
1:        21       20        29
2:       105       88       137
3:       465      368       593
4:      1953     1504      2465
5:      8001     6080     10049
6:     32385    24448     40577
7:    130305    98048    163073
8:    522753   392704    653825
9:   2094081  1571840   2618369
10:  8382465  6289408  10479617
... - _Wolfdieter Lang_, Jun 13 2020

V. E. Firstov, A Special Matrix Transformation Semigroup of Primitive Pairs and the Genealogy of Pythagorean Triples; Mathematical Notes, volume 84, number 2, August 2008, pages 263-279; Link of the page (for the Russian article).
Ralf Steiner, Weitere spezielle Folge primitiver pythagoraischer Dreiecke, ResearchGate.
Wikipedia, Tree of primitive Pythagorean triples.
Index entries for linear recurrences with constant coefficients, signature (0,0,7,0,0,-14,0,0,8).

Cf. A000079, A010035, A049310, A083329, A093357, A010036, A134057, A153893, A171477.

h21={{1, 3}, {0, 2}}; l = {}; Do[v = MatrixPower[h21, n, {2, 1}]; p = v[[1]]; q = v[[2]];
a = p^2 - q^2; b = 2 p q; c = p^2 + q^2; l = AppendTo[l, {a, b, c}], {n, 0, 14}]; l // Flatten

Vec((3 + 4*x + 5*x^2 - 8*x^4 - 6*x^5 + 4*x^7 + 4*x^8) / ((1 - x)*(1 + x + x^2)*(1 - 2*x^3)*(1 - 4*x^3)) + O(x^35)) \\ Colin Barker, Jun 12 2020

The three-column array PT(n, k) is for k = 0, 1, 2:  x(n), y(n), z(n), for n >= 0, with
x(n) = a(3*n + 0) = A153893(n)^2 - A000079(n)^2 = 1 - 3*2^(n+1) + 2^(2*n+3) = binomial(2^(n+2) - 1, 2) = 3*A171477(n),
y(n) = a(3*n + 1) = 2*A153893(n)*A000079(n) = 2^(n+1)*(-1 + 3*2^n) = 4*A010036(n),
z(n) = a(3*n + 2) = A153893(n)^2 + A000079(n)^2 = 1 - 6*2^n + 10*2^(2*n).
From Colin Barker, May 08 2020: (Start)
G.f. (read as sequence {a(n)}): (3 + 4*x + 5*x^2 - 8*x^4 - 6*x^5 + 4*x^7 + 4*x^8) / ((1 - x)*(1 + x + x^2)*(1 - 2*x^3)*(1 - 4*x^3)).
a(n) = 7*a(n-3) - 14*a(n-6) + 8*a(n-9), for n > 8.
(End)

Edited, and corrected proportion by Wolfdieter Lang, Jun 13 2020

Minor grammatical edits. - N. J. A. Sloane, Sep 12 2020

A227209 Expansion of 1/((1-x)^2(1-2x)(1-4x)).

Original entry on oeis.org

1, 8, 43, 198, 849, 3516, 14311, 57746, 231997, 930024, 3724179, 14904894, 59635945, 238576532, 954371647, 3817617642, 15270732693, 61083455040, 244334868715, 977341571990, 3909370482241, 15637490317548

Offset: 0

Yahia Kahloune, Sep 19 2013

This sequence was chosen to illustrate a method of solution.
In general, for the expansion of 1/((1-t*x)^2*(1-s*x)*(1-r*x)) with r>s>t we have the formula: a(n) = ( K*r^(n+3) + L*s^(n+3) + M*t^(n+3) + N*t^(n+3) )/D where K,L,M,N,D have the following values:
   K = (s-t)^2;
   L = -(r-t)^2;
   M = (r-s)*(r+s-2*t);
   N = (r-t)*(s-t)*(r-s)*(n+3);
   D = (r-s)*(r-t)^2*(s-t)^2.
Directly using formula we get a(n) = ( 4^(n+3) - 9*2^(n+3) + 8 + 6*(n+3) )/18. After transformation we obtain previous formula.

Index entries for linear recurrences with constant coefficients, signature (8,-21,22,-8).

Cf. A229026.

Partial sums of A171477.

nn = 25; CoefficientList[Series[1/((1 - x)^2*(1 - 2 x)*(1 - 4 x)), {x, 0, nn}], x] (* T. D. Noe, Sep 19 2013 *)

G.f.: 1/((1-x)^2*(1-2*x)*(1-4*x)).
a(n) = ( 4^(n+3) - 9*2^(n+3) + 6*n + 26 )/18.
E.g.f.: exp(x)*(13 - 36*exp(x) + 32*exp(3*x) + 3*x)/9. - Stefano Spezia, Feb 23 2025

A334909 Area/6 of primitive Pythagorean triangles given in A334638 as triples.

Original entry on oeis.org

1, 35, 770, 14260, 244776, 4053840, 65979040, 1064678720, 17107266176, 274296689920, 4393395202560, 70331527418880, 1125602147608576, 18012016334950400, 288211318352814080, 4611533554425610240, 73785756576381566976, 1180581862943988449280

Offset: 0

Ralf Steiner, May 16 2020

See A334638 for these triangles, and also for the Firstov reference.
For primitive Pythagorean triangle (x, y, z) = (u^2 - v^2, 2*u*v, u^2 + v^2) the area is A = x*y/2 = u*v*(u^2 - v^2) = z*h/2 with altitude h, and h is an irreducible fraction.
From A334638 follows A(n)/6 = (x(n)/3)*(y(n)/4) = A171477(n)*A010036(n), for n >= 0. See the formula section.
Limit_{n->infinity} A(n)/(3*2^(4*n+3)) = 1. See the formula section. - Wolfdieter Lang, Jun 14 2020

			a(0) = 3*4/12 = 1 for (3, 4, 5).

Index entries for linear recurrences with constant coefficients, signature (30,-280,960,-1024).

Cf. A010036, A171477, A334638.

Table[ 2^(-1 + n) (-1 + 3 2^n) (-1 + 2^(1 + n)) (-1 + 2^(2 + n))/3, {n, 0, 17}]

Vec((1 + 5*x) / ((1 - 2*x)*(1 - 4*x)*(1 - 8*x)*(1 - 16*x)) + O(x^20)) \\ Colin Barker, May 17 2020

a(n) = 2^(n-1)*(3*2^n - 1)*(2^(n+1) - 1)*(2^(n+2) - 1)/3.
a(n) = 2^(4*n+2)*(1 - 13/(3*2^(n+2)) + 3/2^(2*n+3) - 1/(3*2^(3*(n+1)))), for n >= 0.
From Colin Barker: (Start)
G.f.: (1 + 5*x) / ((1 - 2*x)*(1 - 4*x)*(1 - 8*x)*(1 - 16*x)).
a(n) = 30*a(n-1) - 280*a(n-2) + 960*a(n-3) - 1024*a(n-4) for n > 3. (End)

Edited by Wolfdieter Lang, Jun 14 2020

cp's OEIS Frontend

A134057 a(n) = binomial(2^n-1,2).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

Python

Formula

A249993 Expansion of 1/((1+x)*(1+2*x)*(1-4*x)).

Views

Author

Keywords

Links

Crossrefs

Programs

Magma

Mathematica

PARI

SageMath

Formula

A334638 Three-column array pPT read by rows: subsequence of primitive Pythagorean triples (x, y, z) with x = A153893^2 - A000079^2, y = 2*A153893*A000079, z = A153893^2 + A000079^2, ordered by increasing z.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A227209 Expansion of 1/((1-x)^2*(1-2*x)*(1-4*x)).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Formula

A334909 Area/6 of primitive Pythagorean triangles given in A334638 as triples.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A249993 Expansion of 1/((1+x)(1+2x)(1-4x)).

A334638 Three-column array pPT read by rows: subsequence of primitive Pythagorean triples (x, y, z) with x = A153893^2 - A000079^2, y = 2A153893A000079, z = A153893^2 + A000079^2, ordered by increasing z.

A227209 Expansion of 1/((1-x)^2(1-2x)(1-4x)).