A059153 -id:A059153 - cp's OEIS frontend

A006516 a(n) = 2^(n-1)*(2^n - 1), n >= 0.

0, 1, 6, 28, 120, 496, 2016, 8128, 32640, 130816, 523776, 2096128, 8386560, 33550336, 134209536, 536854528, 2147450880, 8589869056, 34359607296, 137438691328, 549755289600, 2199022206976, 8796090925056, 35184367894528, 140737479966720, 562949936644096

Offset: 0

N. J. A. Sloane

a(n) is also the number of different lines determined by pair of vertices in an n-dimensional hypercube. The number of these lines modulo being parallel is in A003462. - Ola Veshta (olaveshta(AT)my-deja.com), Feb 15 2001
Let G_n be the elementary Abelian group G_n = (C_2)^n for n >= 1: A006516 is the number of times the number -1 appears in the character table of G_n and A007582 is the number of times the number 1. Together the two sequences cover all the values in the table, i.e., A006516(n) + A007582(n) = 2^(2n). - Ahmed Fares (ahmedfares(AT)my-deja.com), Jun 01 2001
a(n) is the number of n-letter words formed using four distinct letters, one of which appears an odd number of times. - Lekraj Beedassy, Jul 22 2003 [See, e.g., the Balakrishnan reference, problems 2.67 and 2.68, p. 69. - Wolfdieter Lang, Jul 16 2017]
Number of 0's making up the central triangle in a Pascal's triangle mod 2 gasket. - Lekraj Beedassy, May 14 2004
m-th triangular number, where m is the n-th Mersenne number, i.e., a(n)=A000217(A000225(n)). - Lekraj Beedassy, May 25 2004
Number of walks of length 2n+1 between two nodes at distance 3 in the cycle graph C_8. - Herbert Kociemba, Jul 02 2004
The sequence of fractions a(n+1)/(n+1) is the 3rd binomial transform of (1, 0, 1/3, 0, 1/5, 0, 1/7, ...). - Paul Barry, Aug 05 2005
Number of monic irreducible polynomials of degree 2 in GF(2^n)[x]. - Max Alekseyev, Jan 23 2006
(A007582(n))^2 + a(n)^2 = A007582(2n). E.g., A007582(3) = 36, a(3) = 28; A007582(6) = 2080. 36^2 + 28^2 = 2080. - Gary W. Adamson, Jun 17 2006
The sequence 6*a(n), n>=1, gives the number of edges of the Hanoi graph H_4^{n} with 4 pegs and n>=1 discs. - Daniele Parisse, Jul 28 2006
8*a(n) is the total border length of the 4*n masks used when making an order n regular DNA chip, using the bidimensional Gray code suggested by Pevzner in the book "Computational Molecular Biology." - Bruno Petazzoni (bruno(AT)enix.org), Apr 05 2007
If we start with 1 in binary and at each step we prepend 1 and append 0, we construct this sequence: 1 110 11100 1111000 etc.; see A109241(n-1). - Artur Jasinski, Nov 26 2007
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 x does not equal y. - Ross La Haye, Jan 02 2008
Wieder calls these "conjoint usual 2-combinations." The set of "conjoint strict k-combinations" is the subset of conjoint usual k-combinations where the empty set and the set itself are excluded from possible selection. These numbers C(2^n - 2,k), which for k = 2 (i.e., {x,y} of the power set of a set) give {1, 0, 1, 15, 91, 435, 1891, 7875, 32131, 129795, 521731, ...}. - Ross La Haye, Jan 15 2008
If n is a member of A000043 then a(n) is also a perfect number (A000396). - Omar E. Pol, Aug 30 2008
a(n) is also the number whose binary representation is A109241(n-1), for n>0. - Omar E. Pol, Aug 31 2008
From Daniel Forgues, Nov 10 2009: (Start)
If we define a spoof-perfect number as:
A spoof-perfect number is a number that would be perfect if some (one or more) of its odd composite factors were wrongly assumed to be prime, i.e., taken as a spoof prime.
And if we define a "strong" spoof-perfect number as:
A "strong" spoof-perfect number is a spoof-perfect number where sigma(n) does not reveal the compositeness of the odd composite factors of n which are wrongly assumed to be prime, i.e., taken as a spoof prime.
The odd composite factors of n which are wrongly assumed to be prime then have to be obtained additively in sigma(n) and not multiplicatively.
Then:
If 2^n-1 is odd composite but taken as a spoof prime then 2^(n-1)*(2^n - 1) is an even spoof perfect number (and moreover "strong" spoof-perfect).
For example:
a(8) = 2^(8-1)*(2^8 - 1) = 128*255 = 32640 (where 255 (with factors 3*5*17) is taken as a spoof prime);
sigma(a(8)) = (2^8 - 1)*(255 + 1) = 255*256 = 2*(128*255) = 2*32640 = 2n is spoof-perfect (and also "strong" spoof-perfect since 255 is obtained additively);
a(11) = 2^(11-1)*(2^11 - 1) = 1024*2047 = 2096128 (where 2047 (with factors 23*89) is taken as a spoof prime);
sigma(a(11)) = (2^11 - 1)*(2047 + 1) = 2047*2048 = 2*(1024*2047) = 2*2096128 = 2n is spoof-perfect (and also "strong" spoof-perfect since 2047 is obtained additively).
I did a Google search and didn't find anything about the distinction between "strong" versus "weak" spoof-perfect numbers. Maybe some other terminology is used.
An example of an even "weak" spoof-perfect number would be:
n = 90 = 2*5*9 (where 9 (with factors 3^2) is taken as a spoof prime);
sigma(n) = (1+2)*(1+5)*(1+9) = 3*(2*3)*(2*5) = 2*(2*5*(3^2)) = 2*90 = 2n is spoof-perfect (but is not "strong" spoof-perfect since 9 is obtained multiplicatively as 3^2 and is thus revealed composite).
Euler proved:
If 2^k - 1 is a prime number, then 2^(k-1)*(2^k - 1) is a perfect number and every even perfect number has this form.
The following seems to be true (is there a proof?):
If 2^k - 1 is an odd composite number taken as a spoof prime, then 2^(k-1)*(2^k - 1) is a "strong" spoof-perfect number and every even "strong" spoof-perfect number has this form?
There is only one known odd spoof-perfect number (found by Rene Descartes) but it is a "weak" spoof-perfect number (cf. 'Descartes numbers' and 'Unsolved problems in number theory' links below). (End)
a(n+1) = A173787(2*n+1,n); cf. A020522, A059153. - Reinhard Zumkeller, Feb 28 2010
Also, row sums of triangle A139251. - Omar E. Pol, May 25 2010
Starting with "1" = (1, 1, 2, 4, 8, ...) convolved with A002450: (1, 5, 21, 85, 341, ...); and (1, 3, 7, 15, 31, ...) convolved with A002001: (1, 3, 12, 48, 192, ...). - Gary W. Adamson, Oct 26 2010
a(n) is also the number of toothpicks in the corner toothpick structure of A153006 after 2^n - 1 stages. - Omar E. Pol, Nov 20 2010
The number of n-dimensional odd theta functions of half-integral characteristic. (Gunning, p.22) - Michael Somos, Jan 03 2014
a(n) = A000217((2^n)-1) = 2^(2n-1) - 2^(n-1) is the nearest triangular number below 2^(2n-1); cf. A007582, A233327. - Antti Karttunen, Feb 26 2014
a(n) is the sum of all the remainders when all the odd numbers < 2^n are divided by each of the powers 2,4,8,...,2^n. - J. M. Bergot, May 07 2014
Let b(m,k) = number of ways to form a sequence of m selections, without replacement, from a circular array of m labeled cells, such that the first selection of a cell whose adjacent cells have already been selected (a "first connect") occurs on the k-th selection. b(m,k) is defined for m >=3, and for 3 <= k <= m. Then b(m,k)/2m ignores rotations and reflection. Let m=n+2, then a(n) = b(m,m-1)/2m. Reiterated, a(n) is the (m-1)th column of the triangle b(m,k)/2m, whose initial rows are (1), (1 2), (2 6 4), (6 18 28 8), (24 72 128 120 16), (120 360 672 840 496 32), (720 2160 4128 5760 5312 2016 64); see A249796. Note also that b(m,3)/2m = n!, and b(m,m)/2m = 2^n. Proofs are easy. - Tony Bartoletti, Oct 30 2014
Beginning at a(1) = 1, this sequence is the sum of the first 2^(n-1) numbers of the form 4*k + 1 = A016813(k). For example, a(4) = 120 = 1 + 5 + 9 + 13 + 17 + 21 + 25 + 29. - J. M. Bergot, Dec 07 2014
a(n) is the number of edges in the (2^n - 1)-dimensional simplex. - Dimitri Boscainos, Oct 05 2015
a(n) is the number of linear elements in a complete plane graph in 2^n points. - Dimitri Boscainos, Oct 05 2015
a(n) is the number of linear elements in a complete parallelotope graph in n dimensions. - Dimitri Boscainos, Oct 05 2015
a(n) is the number of lattices L in Z^n such that the quotient group Z^n / L is C_4. - Álvar Ibeas, Nov 26 2015
a(n) gives the quadratic coefficient of the polynomial ((x + 1)^(2^n) + (x - 1)^(2^n))/2, cf. A201461. - Martin Renner, Jan 14 2017
Let f(x)=x+2*sqrt(x) and g(x)=x-2*sqrt(x). Then f(4^n*x)=b(n)*f(x)+a(n)*g(x) and g(4^n*x)=a(n)*f(x)+b(n)*g(x), where b is A007582. - Luc Rousseau, Dec 06 2018
For n>=1, a(n) is the covering radius of the first order Reed-Muller code RM(1,2n). - Christof Beierle, Dec 22 2021
a(n) =

			G.f. = x + 6*x^2 + 28*x^3 + 120*x^4 + 496*x^5 + 2016*x^6 + 8128*x^7 + 32640*x^8 + ...

V. K. Balakrishnan, Theory and problems of Combinatorics, "Schaum's Outline Series", McGraw-Hill, 1995, p. 69.
Martin Gardner, Mathematical Carnival, "Pascal's Triangle", p. 201, Alfred A. Knopf NY, 1975.
Richard K. Guy, Unsolved problems in number theory, (p. 72).
Ross Honsberger, Mathematical Gems, M.A.A., 1973, p. 113.
Clifford A. Pickover, Wonders of Numbers, Chap. 55, Oxford Univ. Press NY 2000.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

T. D. Noe, Table of n, a(n) for n=0..200
David Applegate, Omar E. Pol and N. J. A. Sloane, The Toothpick Sequence and Other Sequences from Cellular Automata, Congressus Numerantium, Vol. 206 (2010), 157-191. [There is a typo in Theorem 6: (13) should read u(n) = 4.3^(wt(n-1)-1) for n >= 2.]
M. Archibald, A. Blecher, A. Knopfmacher and M. E. Mays, Inversions and Parity in Compositions of Integers, J. Int. Seq., Vol. 23 (2020), Article 20.4.1.
William Banks, Ahmet Güloğlu, Wesley Nevans and Filip Saidak, Descartes numbers, Anatomy of integers, 167-173, CRM Proc. Lecture Notes, 46, Amer. Math. Soc., Providence, RI, 2008. MathSciNet review (subscription required).
Taylor Brysiewicz, Holger Eble, and Lukas Kühne, Enumerating chambers of hyperplane arrangements with symmetry, arXiv:2105.14542 [math.CO], 2021.
John Elias, Illustration of initial terms: Mersenne-Sierpinski Triangles
Farideh Firoozbakht and M. F. Hasler, Variations on Euclid's formula for Perfect Numbers, JIS 13 (2010) #10.3.1.
R. C. Gunning, Riemann Surfaces and Second-Order Theta Functions, Springer-Verlag, 1976. See page 22.
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.
T. Helleseth, T. Klove and J.Mykkeltveit, On the covering radius of binary codes (Corresp.), IEEE Transactions on Information Theory, Vol. 24 (1978).
V. Meally, Letter to N. J. A. Sloane, May 1975
Axel Muller, Metod Saniga, Alain Giorgetti, Henri de Boutray, and Frédéric Holweck, New and improved bounds on the contextuality degree of multi-qubit configurations, arXiv:2305.10225 [quant-ph], 2023.
Simon Plouffe, Approximations de séries génératrices et quelques conjectures, Dissertation, Université du Québec à Montréal, 1992; arXiv:0911.4975 [math.NT], 2009.
Simon Plouffe, 1031 Generating Functions, Appendix to Thesis, Montreal, 1992.
O. S. Rothaus, On "bent" functions, Journal of Combinatorial Theory, Series A, Vol. 20 (1976).
N. J. A. Sloane, Catalog of Toothpick and Cellular Automata Sequences in the OEIS
Thomas Wieder, The number of certain k-combinations of an n-set, Applied Mathematics Electronic Notes, vol. 8 (2008).
Index entries for linear recurrences with constant coefficients, signature (6,-8).

Equals A006095(n+1) - A006095(n). In other words, A006095 gives the partial sums.
Cf. A000108, A007582, A010036, A016290, A003462, A079598, A134346, A048473, A151821, A010684.
Cf. A000043, A000396. - Omar E. Pol, Aug 30 2008
Cf. A109241, A139251, A153006. - Omar E. Pol, Aug 31 2008, May 25 2010, Nov 20 2010
Cf. A002450, A002001. - Gary W. Adamson, Oct 26 2010
Cf. A049072, A000384, A201461, A005059 (binomial transform, and special 5-letter words), A065442, A211705.
Cf. A171476.

List([0..25],n->2^(n-1)*(2^n-1)); # Muniru A Asiru, Dec 06 2018

a006516 n = a006516_list !! n
a006516_list = 0 : 1 :
    zipWith (-) (map (* 6) $ tail a006516_list) (map (* 8) a006516_list)
-- Reinhard Zumkeller, Oct 25 2013

[2^(n-1)*(2^n - 1): n in [0..30]]; // Vincenzo Librandi, Oct 31 2014

GBC := proc(n,k,q) local i; mul( (q^(n-i)-1)/(q^(k-i)-1),i=0..k-1); end; # define q-ary Gaussian binomial coefficient [ n,k ]_q
[ seq(GBC(n+1,2,2)-GBC(n,2,2), n=0..30) ]; # produces A006516
A006516:=1/(4*z-1)/(2*z-1); # Simon Plouffe in his 1992 dissertation
seq(binomial(2^n, 2), n=0..19); # Zerinvary Lajos, Feb 22 2008

Table[2^(n - 1)(2^n - 1), {n, 0, 30}] (* or *) LinearRecurrence[{6, -8}, {0, 1}, 30] (* Harvey P. Dale, Jul 15 2011 *)

A006516(n):=2^(n-1)*(2^n - 1)$ makelist(A006516(n),n,0,30); /* Martin Ettl, Nov 15 2012 */

a(n)=(1<Charles R Greathouse IV, Jun 10 2011

vector(100, n, n--; 2^(n-1)*(2^n-1)) \\ Altug Alkan, Oct 06 2015

for n in range(0, 30): print(2**(n-1)*(2**n - 1), end=', ') # Stefano Spezia, Dec 06 2018

[lucas_number1(n,6,8) for n in range(24)]  # Zerinvary Lajos, Apr 22 2009

[(4**n - 2**n) / 2 for n in range(24)]  # Zerinvary Lajos, Jun 05 2009

G.f.: x/((1 - 2*x)*(1 - 4*x)).
E.g.f. for a(n+1), n>=0: 2*exp(4*x) - exp(2*x).
a(n) = 2^(n-1)*Stirling2(n+1,2), n>=0, with Stirling2(n,m)=A008277(n,m).
Second column of triangle A075497.
a(n) = Stirling2(2^n,2^n-1) = binomial(2^n,2). - Ross La Haye, Jan 12 2008
a(n+1) = 4*a(n) + 2^n. - Philippe Deléham, Feb 20 2004
Convolution of 4^n and 2^n. - Ross La Haye, Oct 29 2004
a(n+1) = Sum_{k=0..n} Sum_{j=0..n} 4^(n-j)*binomial(j,k). - Paul Barry, Aug 05 2005
a(n+2) = 6*a(n+1) - 8*a(n), a(1) = 1, a(2) = 6. - Daniele Parisse, Jul 28 2006 [Typo corrected by Yosu Yurramendi, Aug 06 2008]
Row sums of triangle A134346. Also, binomial transform of A048473: (1, 5, 17, 53, 161, ...); double bt of A151821: (1, 4, 8, 16, 32, 64, ...) and triple bt of A010684: (1, 3, 1, 3, 1, 3, ...). - Gary W. Adamson, Oct 21 2007
a(n) = 3*Stirling2(n+1,4) + Stirling2(n+2,3). - Ross La Haye, Jun 01 2008
a(n) = (4^n - 2^n)/2.
a(n) = A153006(2^n-1). - Omar E. Pol, Nov 20 2010
Sum_{n>=1} 1/a(n) = 2 * (A065442 - 1) = A211705 - 2. - Amiram Eldar, Dec 24 2020
a(n) = binomial(2*n+2, n+1) - Catalan(n+2). - N. J. A. Sloane, Apr 01 2021
a(n) = A171476(n-1), for n >= 1, and a(0) = 0. - Wolfdieter Lang, Jul 27 2022

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

Original entry on oeis.org

0, 2, 12, 56, 240, 992, 4032, 16256, 65280, 261632, 1047552, 4192256, 16773120, 67100672, 268419072, 1073709056, 4294901760, 17179738112, 68719214592, 274877382656, 1099510579200, 4398044413952, 17592181850112, 70368735789056, 281474959933440

Offset: 0

N. J. A. Sloane, Simon Plouffe

Number of walks of length 2*n+2 between any two diametrically opposite vertices of the cycle graph C_8. - Herbert Kociemba, Jul 02 2004
If we consider a(4*k+2), then 2^4 == 3^4 == 3 (mod 13); 2^(4*k+2) + 3^(4*k+2) == 3^k*(4+9) == 3*0 == 0 (mod 13). So a(4*k+2) can never be prime. - Jose Brox, Dec 27 2005
If k is odd, then a(n*k) is divisible by a(n), since: a(n*k) = (2^n)^k + (3^n)^k = (2^n + 3^n)*((2^n)^(k-1) - (2^n)^(k-2) (3^n) + - ... + (3^n)^(k-1)). So the only possible primes in the sequence are a(0) and a(2^n) for n>=1. I've checked that a(2^n) is composite for 3 <= n <= 15. As with Fermat primes, a probabilistic argument suggests that there are only finitely many primes in the sequence. - Dean Hickerson, Dec 27 2005
Let x,y,z be elements from some power set P(n), i.e., the power set of a set of n elements. Define a function f(x,y,z) in the following manner: f(x,y,z) = 1 if x is a subset of y and y is a subset of z and x does not equal z; f(x,y,z) = 0 if x is not a subset of y or y is not a subset of z or x equals z. Now sum f(x,y,z) for all x,y,z of P(n). This gives a(n). - Ross La Haye, Dec 26 2005
Number of monic (irreducible) polynomials of degree 1 over GF(2^n). - Max Alekseyev, Jan 13 2006
Let P(A) be the power set of an n-element set A and B be the Cartesian product of P(A) with itself. Then a(n) = the number of (x,y) of B for which x does not equal y. - Ross La Haye, Jan 02 2008
For n>1: central terms of the triangle in A173787. - Reinhard Zumkeller, Feb 28 2010
Pronic numbers of the form: (2^n - 1)*2^n, which is the n-th Mersenne number times 2^n, see A000225 and A002378. - Fred Daniel Kline, Nov 30 2013
Indices where records of A037870 occur. - Philippe Beaudoin, Sep 03 2014
Half the total edge length for a minimum linear arrangement of a hypercube of dimension n. (See Harper's paper below for proof). - Eitan Frachtenberg, Apr 07 2017
Number of pairs in GF(2)^{n+1} whose dot product is 1. - Christopher Purcell, Dec 11 2021

			n=5: a(5) = 4^5 - 2^5 = 1024 - 32 = 992 -> '1111100000'.

Vincenzo Librandi, Table of n, a(n) for n = 0..170
M. Archibald, A. Blecher, A. Knopfmacher, and M. E. Mays, Inversions and Parity in Compositions of Integers, J. Int. Seq., Vol. 23 (2020), Article 20.4.1.
Tom Copeland, The Kervaire-Milnor formula
John Elias, Illustration of initial terms: Twin 2^n hexagonal numbers
L. H. Harper, Optimal Assignment of Numbers to Vertices, J. SIAM 12(1), p. 131--135, March 1964; alternative link.
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.
The Sixtieth William Lowell Putnam Mathematical Competition, Question A6, Amer. Math. Monthly 107 (Oct 2000), 721-732; see p. 725.
Index entries for linear recurrences with constant coefficients, signature (6,-8).

Ratio of successive terms of A028365.
Cf. A000225, A060867, A161168, A006516, A059153, A065442.
Cf. A000079, A265736, A020988, A047849.
Cf. A000079, A000302.

a020522 = (* 2) . a006516  -- Reinhard Zumkeller, Dec 15 2015

[4^n - 2^n: n in [0..60]]; // Vincenzo Librandi, Apr 26 2011

A020522:=n->4^n-2^n; seq(A020522(n), n=0..50); # Wesley Ivan Hurt, Nov 29 2013

Table[4^n - 2^n, {n, 40}] (* or *) LinearRecurrence[{6, -8}, {0, 2}, 40] (* Vladimir Joseph Stephan Orlovsky, Feb 20 2012 *)

a(n)=4^n-2^n \\ Charles R Greathouse IV, Jan 30 2012

def A020522(n): return (1<Chai Wah Wu, Mar 10 2025

[4^n - 2^n for n in range(0,23)] # Zerinvary Lajos, Jun 05 2009

From Herbert Kociemba, Jul 02 2004: (Start)
G.f.: 2*x/((-1 + 2*x)*(-1 + 4*x)).
a(n) = 6*a(n-1) - 8*a(n-2). (End)
E.g.f.: exp(4*x) - exp(2*x). - Mohammad K. Azarian, Jan 14 2009
From Reinhard Zumkeller, Feb 07 2006, Jaroslav Krizek, Aug 02 2009: (Start)
a(n) = A099393(n)-A000225(n+1) = A083420(n)-A099393(n).
In binary representation, n>0: n 1's followed by n 0's (A138147(n)).
A000120(a(n)) = n.
A023416(a(n)) = n.
A070939(a(n)) = 2*n.
2*a(n)+1 = A030101(A099393(n)). (End)
a(n) = A085812(n) - A001700(n). - John Molokach, Sep 28 2013
a(n) = 2*A006516(n) = A000079(n)*A000225(n) = A265736(A000225(n)). - Reinhard Zumkeller, Dec 15 2015
a(n) = (4^(n/2) - 4^(n/4))*(4^(n/2) + 4^(n/4)). - Bruno Berselli, Apr 09 2018
Sum_{n>0} 1/a(n) = E - 1, where E is the Erdős-Borwein constant (A065442). - Peter McNair, Dec 19 2022
a(n) = A000302(n) - A000079(n). - John Reimer Morales, Aug 04 2025

A173787 Triangle read by rows: T(n,k) = 2^n - 2^k, 0 <= k <= n.

Original entry on oeis.org

0, 1, 0, 3, 2, 0, 7, 6, 4, 0, 15, 14, 12, 8, 0, 31, 30, 28, 24, 16, 0, 63, 62, 60, 56, 48, 32, 0, 127, 126, 124, 120, 112, 96, 64, 0, 255, 254, 252, 248, 240, 224, 192, 128, 0, 511, 510, 508, 504, 496, 480, 448, 384, 256, 0, 1023, 1022, 1020, 1016, 1008, 992, 960, 896, 768, 512, 0

Offset: 0

Reinhard Zumkeller, Feb 28 2010

			Triangle begins as:
   0;
   1,  0;
   3,  2,  0;
   7,  6,  4,  0;
  15, 14, 12,  8,  0;
  31, 30, 28, 24, 16, 0;

G. C. Greubel, Rows n = 0..50 of the triangle, flattened

[2^n -2^k: k in [0..n], n in [0..15]]; // G. C. Greubel, Jul 13 2021

Table[2^n -2^k, {n,0,15}, {k,0,n}]//Flatten (* G. C. Greubel, Jul 13 2021 *)

flatten([[2^n -2^k for k in (0..n)] for n in (0..15)]) # G. C. Greubel, Jul 13 2021

A000120(T(n,k)) = A025581(n,k).
Row sums give A000337.
Central terms give A020522.
T(2*n+1, n) = A006516(n+1).
T(2*n+3, n+2) = A059153(n).
T(n, k) = A140513(n,k) - A173786(n,k), 0 <= k <= n.
T(n, k) = A173786(n,k) - A059268(n+1,k+1), 0 < k <= n.
T(2*n, 2*k) = T(n,k) * A173786(n,k), 0 <= k <= n.
T(n, 0) = A000225(n).
T(n, 1) = A000918(n) for n>0.
T(n, 2) = A028399(n) for n>1.
T(n, 3) = A159741(n-3) for n>3.
T(n, 4) = A175164(n-4) for n>4.
T(n, 5) = A175165(n-5) for n>5.
T(n, 6) = A175166(n-6) for n>6.
T(n, n-4) = A110286(n-4) for n>3.
T(n, n-3) = A005009(n-3) for n>2.
T(n, n-2) = A007283(n-2) for n>1.
T(n, n-1) = A000079(n-1) for n>0.
T(n, n) = A000004(n).

A342202 T(n,k) = V(n,k)/k!, where V(n,k) = k^(nk) - Sum_{t=1..k-1} binomial(k,t)k^(n(k-t))V(n,t) for n, k >= 1; square array T read by upwards antidiagonals.

Original entry on oeis.org

1, 1, 0, 1, 4, 0, 1, 24, 45, 0, 1, 112, 2268, 816, 0, 1, 480, 76221, 461056, 20225, 0, 1, 1984, 2245320, 152978176, 160977375, 632700, 0, 1, 8064, 62858025, 43083161600, 673315202500, 85624508376, 23836540, 0, 1, 32512, 1723364748, 11442561314816, 2331513459843750, 5508710472669120, 64363893844726, 1048592640, 0

Offset: 1

Petros Hadjicostas, Mar 04 2021

To prove Paul D. Hanna's formula for the row n o.g.f. A(x,n) = Sum_{m >= 1} T(n,m)*x^m, we use Leibniz's rule for the k-th derivative of a product of functions: dx^k(exp(k^n*x) * (1 - A(x,n)))/dx = Sum_{s=0..k} binomial(k,s) * d^s(exp(k^n*x))/dx^s * d^(k-s) (1 - A(x,n))/dx^(k-s) = k^(n*k) * exp(k^n*x) * (1 - Sum_{m>=1} T(n,m) * x^m) - Sum_{s=0..k-1} binomial(k,s) * k^(n*s) * exp(k^n*x) * (Sum_{m>=1} (m!/(m-(k-s))!) * T(n,m) * x^(m-(k-s))). The coefficient of x^k for exp(k^n*x) * (1 - A(x,n)) is obtained by setting x = 0 in the k-the derivative, and it is equal to k^(n*k) - Sum_{s=0..k-1} binomial(k,s) * k^(n*s) * (k-s)! * T(n,k-s) = k! * (k^(n*k)/k! - Sum_{s=0..k-1} k^(n*s)/s! * T(n,k-s)) = 0 because of the recurrence that T(n,k) satisfies.
To prove the formula below for T(n,k) that involves the compositions of k, we use mathematical induction on k. For k = 1, it is obvious. Assume it is true for all n and all m < k. Consider the compositions of k.
There is only one of size r = 1, namely k, and corresponds to the term k^(n*k)/k! in the recurrence T(n,k) = k^(n*k)/k! - Sum_{s=1..k-1} k^(n*s)/s! * T(n,k-s).
For the other compositions (s_1, ..., s_r) of k (of any size r >= 2), we group them according to the their last element s_r = s in {1, 2, ..., k - 1}, which gives rise to the factor k^(n*s)/s! = (Sum_{i=1..r} s_i)^(n*s_r)/s_r!. Using the inductive hypothesis, we substitute the expression for T(n,k-s) in the recurrence T(n,k) = k^(n*k)/k! - Sum_{s=1..k-1} k^(n*s)/s! * T(n,k-s). Each term in the expression for T(n,k-s) corresponds to a composition of k - s and is postmultiplied by k^(n*s)/s! = (Sum_{i=1..r} s_i)^(n*s_r)/s_r!. We thus get a term in the expression for T(n,k) that corresponds to a composition of the form (composition of k - s) + s, and the sign of this term is (-1)^((size of composition of k - s) + 1). The rest of the proof follows easily.

			Square array T(n,k) (n, k >= 1) begins:
  1,    0,        0,              0,                   0, ...
  1,    4,       45,            816,               20225, ...
  1,   24,     2268,         461056,           160977375, ...
  1,  112,    76221,      152978176,        673315202500, ...
  1,  480,  2245320,    43083161600,    2331513459843750, ...
  1, 1984, 62858025, 11442561314816, 7570813415735296875, ...
  ...

Michael A. Harrison, A census of finite automata, Canadian Journal of Mathematics, 17 (1965), 100-113.
Valery A. Liskovets [ Liskovec ], Enumeration of nonisomorphic strongly connected automata, (in Russian); Vesti Akad. Nauk. Belarus. SSR, Ser. Phys.-Mat., No. 3, 1971, pp. 26-30, esp. p. 30 (Math. Rev. 46 #5081; Zentralblatt 224 #94053).
Valery A. Liskovets [ Liskovec ], A general enumeration scheme for labeled graphs, (in Russian); Dokl. Akad. Nauk. Belarus. SSR, Vol. 21, No. 6 (1977), pp. 496-499 (Math. Rev. 58 #21797; Zentralblatt 412 #05052).
Michel Marcus, PARI program that implements the formula for T(n,k) that involves compositions of k, 2021.
Robert W. Robinson, Counting strongly connected finite automata, in: Graph Theory with Applications to Graph Theory and Computer Science, Wiley, 1985, pp. 671-685.

Cf. A027834, A027835, A059153 (shifted column 2), A342405 (column 3).

Shifted rows: A000007 (row 1), A107668 (row 2), A107675 (row 3), A304394 (row 4), A304395 (row 5).

/* The recurrence for V(n,k) is due to Valery A. Liskovets. See his 1971 paper. A second program that implements the formula above involving the compositions of k appears in the links and was written by Michel Marcus. */
V(n,k) = k^(n*k) - sum(t=1, k-1, binomial(k, t)*k^(n*(k-t))*V(n,t));
T(n,k) = V(n,k)/k!

T(n,k) = k^(n*k)/k! - Sum_{s=1..k-1} k^(n*s)/s! * T(n,k-s).
For each n >= 1, the row n o.g.f. A(x,n) = Sum_{k >= 1} T(n,k)*x^k satisfies [x^k] (exp(k^n*x) * (1 - A(x,n))) = 0 for each k >= 1. (This is Paul D. Hanna's formula from the shifted rows 2-5: A107668, A107675, A304394, A304395.)
A027834(k) = T(2, k)*k! + Sum_{t=1..k-1} binomial(k-1, t-1) * T(2, k-t) * (k-t)! * A027834(t), where A027834(k) = number of strongly connected k-state 2-input automata. (See Theorem 2 in Valery A. Liskovets's 1971 paper.)
T(n,k) = Sum_{r=1..k} (-1)^(r-1) * Sum_{s_1, ..., s_r} (1/(Product_{j=1..r} s_j!)) * Product_{j=1..r} (Sum_{i=1..j} s_i)^(n*s_j)), where the second sum is over lists (s_1, ..., s_r) of positive integers s_i such that Sum_{i=1..r} s_i = k. (Thus the second sum is over all ordered partitions (i.e., compositions) of k.)
T(n,k=1) = 1 and T(n,k=2) = 2^n*(2^(n-1) - 1) = A059153(n-2) (with A059153(-1) := 0).
T(n,k=3) = (27^n - 3*9^n - 3*12^n)/6 + 6^n.
T(n,k=4) = 256^n/24 - (5/12)*64^n - 108^n/6 + 32^n/2 + 36^n/2 + 48^n/2 - 24^n.

cp's OEIS Frontend

A163663 a(0) = 0 and A059153(n-1) written in base 2 otherwise.

Views

Author

Keywords

Comments

Links

Programs

Mathematica

PARI

Formula

Extensions

A006516 a(n) = 2^(n-1)*(2^n - 1), n >= 0.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

GAP

Haskell

Magma

Maple

Mathematica

Maxima

PARI

PARI

Python

Sage

Sage

Formula

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Magma

Maple

Mathematica

PARI

Python

Sage

Formula

A173787 Triangle read by rows: T(n,k) = 2^n - 2^k, 0 <= k <= n.

Views

Author

Keywords

Examples

Links

Programs

Magma

Mathematica

Sage

Formula

A342202 T(n,k) = V(n,k)/k!, where V(n,k) = k^(n*k) - Sum_{t=1..k-1} binomial(k,t)*k^(n*(k-t))*V(n,t) for n, k >= 1; square array T read by upwards antidiagonals.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula

A063480 C(n+3)=2*C(n), where C(n) is Cototient(n) := n - phi(n) (A051953).

Views

Author

Keywords

Examples

Links

Crossrefs

A342202 T(n,k) = V(n,k)/k!, where V(n,k) = k^(nk) - Sum_{t=1..k-1} binomial(k,t)k^(n(k-t))V(n,t) for n, k >= 1; square array T read by upwards antidiagonals.