A059222 Minimal number of disjoint edge-paths into which the graph of the n-ary cube can be partitioned.

1, 1, 4, 1, 16, 1, 64, 1, 256, 1, 1024, 1, 4096, 1, 16384, 1, 65536, 1, 262144, 1, 1048576, 1, 4194304, 1, 16777216, 1, 67108864, 1, 268435456, 1, 1073741824, 1, 4294967296, 1, 17179869184, 1, 68719476736, 1, 274877906944, 1, 1099511627776, 1, 4398046511104

Offset: 1

Author

Felix Golderg (felixg(AT)tx.technion.ac.il), Jan 19 2001

Keywords

• nonn
• easy

Comments

The formula for this sequence is easily derived from a generalization of Euler's famous "Eulerian Path" theorem (see Theorem 11.2.4 in p. 419 of the reference).

Examples

			a(5)=16 because 2^(5-1)=16. Consequently, the minimal number of disjoint edge-paths into which the 5-ary cube can be partitioned is 16.
		

References

• R. A. Brualdi, Introductory Combinatorics, 3rd ed. Prentice-Hall, 1999.

Links

• Vincenzo Librandi, Table of n, a(n) for n = 1..400
• Index entries for linear recurrences with constant coefficients, signature (0,5,0,-4).

Crossrefs

Cf. A057979.

Programs

Mathematica

Table[If[EvenQ[n],1,2^(n-1)],{n,80}] (* or *) Riffle[2^(2Range[0,50]),1] (* Harvey P. Dale, Nov 02 2011 *)

Formula

a(n) = 1 if n is even and 2^(n-1) if n is odd.

G.f. -x*(-1-x+x^2+4*x^3) / ( (x-1)*(2*x+1)*(2*x-1)*(1+x) ). - R. J. Mathar, Apr 25 2013

E.g.f.: cosh(x)*(1 + sinh(x)) - 1. - Stefano Spezia, Mar 26 2022

Extensions

More terms from Harvey P. Dale, Nov 02 2011