A091940 -id:A091940 - cp's OEIS frontend

A053644 Most significant bit of n, msb(n); largest power of 2 less than or equal to n; write n in binary and change all but the first digit to zero.

0, 1, 2, 2, 4, 4, 4, 4, 8, 8, 8, 8, 8, 8, 8, 8, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64

Offset: 0

Henry Bottomley, Mar 22 2000

Except for the initial term, 2^n appears 2^n times. - Lekraj Beedassy, May 26 2005
a(n) is the smallest k such that row k in triangle A265705 contains n. - Reinhard Zumkeller, Dec 17 2015
a(n) is the sum of totient function over powers of 2 <= n. - Anthony Browne, Jun 17 2016
Given positive n, reverse the bits of n and divide by 2^floor(log_2 n). Numerators are in A030101. Ignoring the initial 0, denominators are in this sequence. - Alonso del Arte, Feb 11 2020

Reinhard Zumkeller, Table of n, a(n) for n = 0..10000
N. J. A. Sloane, Transforms
Ralf Stephan, Some divide-and-conquer sequences ...
Ralf Stephan, Table of generating functions

See A000035 for least significant bit(n).
MASKTRANS transform of A055975 (prepended with 0), MASKTRANSi transform of A048678.
Bisection of A065267, A065279, A065291, A072376.
First differences of A063915. Cf. A076877, A073121.
This is Guy Steele's sequence GS(5, 5) (see A135416).
Equals for n >= 1 the first right hand column of A160464. - Johannes W. Meijer, May 24 2009
Diagonal of A088370. - Alois P. Heinz, Oct 28 2011
Cf. A265705, A000010.

a053644 n = if n <= 1 then n else 2 * a053644 (div n 2)
-- Reinhard Zumkeller, Aug 28 2014
a053644_list = 0 : concat (iterate (\zs -> map (* 2) (zs ++ zs)) [1])
-- Reinhard Zumkeller, Dec 08 2012, Oct 21 2011, Oct 17 2010

[0] cat [2^Ilog2(n): n in [1..90]]; // Vincenzo Librandi, Dec 11 2018

a:= n-> 2^ilog2(n):
seq(a(n), n=0..80);  # Alois P. Heinz, Dec 20 2016

A053644[n_] := 2^(Length[ IntegerDigits[n, 2]] - 1); A053644[0] = 0; Table[A053644[n], {n, 0, 74}] (* Jean-François Alcover, Dec 01 2011 *)
nv[n_] := Module[{c = 2^n}, Table[c, {c}]]; Join[{0}, Flatten[Array[nv, 7, 0]]] (* Harvey P. Dale, Jul 17 2012 *)

a(n)=my(k=1);while(k<=n,k<<=1);k>>1 \\ Charles R Greathouse IV, May 27 2011

a(n) = if(!n, 0, 2^exponent(n)) \\ Iain Fox, Dec 10 2018

def a(n): return 0 if n==0 else 2**(len(bin(n)[2:]) - 1) # Indranil Ghosh, May 25 2017

def A053644(n): return 1<Chai Wah Wu, Jul 27 2022

(0 to 127).map(Integer.highestOneBit()) // _Alonso del Arte, Feb 26 2020

a(n) = a(floor(n / 2)) * 2.
a(n) = 2^A000523(n).
From n >= 1 onward, A053644(n) = A062383(n)/2.
a(0) = 0, a(1) = 1 and a(n+1) = a(n)*floor(n/a(n)). - Benoit Cloitre, Aug 17 2002
G.f.: 1/(1 - x) * (x + Sum_{k >= 1} 2^(k - 1)*x^2^k). - Ralf Stephan, Apr 18 2003
a(n) = (A003817(n) + 1)/2 = A091940(n) + 1. - Reinhard Zumkeller, Feb 15 2004
a(n) = Sum_{k = 1..n} (floor(2^k/k) - floor((2^k - 1)/k))*A000010(k). - Anthony Browne, Jun 17 2016
a(2^m+k) = 2^m, m >= 0, 0 <= k < 2^m. - Yosu Yurramendi, Aug 07 2016

A182406 Square array A(n,k), n>=1, k>=1, read by antidiagonals: A(n,k) is the number of n-colorings of the square grid graph G_(k,k).

Original entry on oeis.org

1, 0, 2, 0, 2, 3, 0, 2, 18, 4, 0, 2, 246, 84, 5, 0, 2, 7812, 9612, 260, 6, 0, 2, 580986, 6000732, 142820, 630, 7, 0, 2, 101596896, 20442892764, 828850160, 1166910, 1302, 8, 0, 2, 41869995708, 380053267505964, 50820390410180, 38128724910, 6464682, 2408, 9

Offset: 1

Alois P. Heinz, Apr 27 2012

The square grid graph G_(n,n) has n^2 = A000290(n) vertices and 2*n*(n-1) = A046092(n-1) edges. The chromatic polynomial of G_(n,n) has n^2+1 = A002522(n) coefficients.

			Square array A(n,k) begins:
  1,   0,       0,           0,                 0, ...
  2,   2,       2,           2,                 2, ...
  3,  18,     246,        7812,            580986, ...
  4,  84,    9612,     6000732,       20442892764, ...
  5, 260,  142820,   828850160,    50820390410180, ...
  6, 630, 1166910, 38128724910, 21977869327169310, ...

Eric Weisstein's World of Mathematics, Grid Graph
Wikipedia, Chromatic Polynomial

Columns k=1-7 give: A000027, A091940, A068239*2, A068240*2, A068241*2, A068242*2, A068243*2.
Rows n=1-20 give: A000007, A007395, A068253*3, A068254*4, A068255*5, A068256*6, A068257*7, A068258*8, A068259*9, A068260*10, A068261*11, A068262*12, A068263*13, A068264*14, A068265*15, A068266*16, A068267*17, A068268*18, A068269*19, A068270*20.
Cf. A182368.

A100019 a(n) = n^4 + n^3 + n^2.

Original entry on oeis.org

0, 3, 28, 117, 336, 775, 1548, 2793, 4672, 7371, 11100, 16093, 22608, 30927, 41356, 54225, 69888, 88723, 111132, 137541, 168400, 204183, 245388, 292537, 346176, 406875, 475228, 551853, 637392, 732511, 837900, 954273, 1082368, 1222947

Offset: 0

Douglas Winston (douglas.winston(AT)srupc.com), Nov 19 2004

a(n) are the numbers m such that: j^2 = j + m + sqrt(j*m) with corresponding numbers j given by A002061(n+1), and with sqrt(j*m) = A027444(n) = n* A002061(n+1). - Richard R. Forberg, Sep 03 2013.

Vincenzo Librandi, Table of n, a(n) for n = 0..1000

Cf. A000583, A002523, A091940, A071253, A059826, A027445, A053699.

[n^4+n^3+n^2: n in [0..50]]; // Vincenzo Librandi, Jun 09 2011

A100019:=n->n^4+n^3+n^2: seq(A100019(n), n=0..50); # Wesley Ivan Hurt, Apr 14 2017

f[n_]:=n^4+n^3+n^2;Array[f,50,0] (* Vladimir Joseph Stephan Orlovsky, Apr 12 2011 *)

a(n) = n^4 + n^3 + n^2 \\ Indranil Ghosh, Apr 15 2017

From Indranil Ghosh, Apr 15 2017: (Start)
G.f.: -x(3 + 13x + 7x^2 + x^3)/(x - 1)^5
E.g.f.: exp(x)*x*(3 + 11x + 7x^2 + x^3)
(End)

A334159 Irregular triangle read by rows: T(n,k) is the number of colorings of the n-hypercube graph using exactly k unlabeled colors, k = 1..2^n.

Original entry on oeis.org

1, 0, 1, 0, 1, 2, 1, 0, 1, 18, 92, 146, 80, 16, 1, 0, 1, 494, 54583, 1507094, 12630906, 40096740, 58031885, 43419502, 18212138, 4498756, 670366, 60220, 3156, 88, 1, 0, 1, 197546, 5427041958, 17973998149410, 10961517110194516, 1450479305675145412, 56507865332978414188

Offset: 0

Andrew Howroyd, Apr 21 2020

			Triangle begins:
0 | 1;
1 | 0, 1;
2 | 0, 1, 2, 1;
3 | 0, 1, 18, 92, 146, 80, 16, 1;
4 | 0, 1, 494, 54583, 1507094, 12630906, 40096740, 58031885, 43419502, 18212138, 4498756, 670366, 60220, 3156, 88, 1;

Andrew Howroyd, Table of n, a(n) for n = 0..62 (rows 0..5)
Andrew Howroyd, Chromatic Polynomials of Hypercubes Q_0 to Q_5
Eric Weisstein's World of Mathematics, Chromatic Polynomial
Eric Weisstein's World of Mathematics, Hypercube Graph

Cf. A091940, A140986, A158348, A296914, A295176, A334247.

A106512 Array read by antidiagonals: a(n,k) = number of k-colorings of a circle of n nodes (n >= 1, k >= 1).

Original entry on oeis.org

0, 0, 0, 0, 2, 0, 0, 6, 0, 0, 0, 12, 6, 2, 0, 0, 20, 24, 18, 0, 0, 0, 30, 60, 84, 30, 2, 0, 0, 42, 120, 260, 240, 66, 0, 0, 0, 56, 210, 630, 1020, 732, 126, 2, 0, 0, 72, 336, 1302, 3120, 4100, 2184, 258, 0, 0, 0, 90, 504, 2408, 7770, 15630, 16380, 6564, 510, 2, 0, 0, 110

Offset: 1

Joshua Zucker, May 29 2005

Note that we keep one edge in the circular graph even when there's only one node (so there are 0 colorings of one node with k colors).

Number of closed walks of length n on the complete graph K_{k}. - Andrew Howroyd, Mar 12 2017

			From _Andrew Howroyd_, Mar 12 2017: (Start)
Table begins:
  0 0   0     0      0       0        0        0         0 ...
  0 2   6    12     20      30       42       56        72 ...
  0 0   6    24     60     120      210      336       504 ...
  0 2  18    84    260     630     1302     2408      4104 ...
  0 0  30   240   1020    3120     7770    16800     32760 ...
  0 2  66   732   4100   15630    46662   117656    262152 ...
  0 0 126  2184  16380   78120   279930   823536   2097144 ...
  0 2 258  6564  65540  390630  1679622  5764808  16777224 ...
  0 0 510 19680 262140 1953120 10077690 40353600 134217720 ...
(End)
a(4,3) = 18 because there are three choices for the first node's color (call it 1) and then two choices for the second node's color (call it 2) and then the remaining two nodes can be 12, 13, or 32. So in total there are 3*2*3 = 18 ways. a(3,4) = 4*3*2 = 24 because the three nodes must be three distinct colors.

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

Columns include A092297, A226493. Main diagonal is A118537.
Rows 2-7 are A002378, A007531, A091940, A061167, A131472, A133499.
Cf. A090860, A208535.

a(n, k) = (k-1)^n + (-1)^n * (k-1).

a(67) corrected by Andrew Howroyd, Mar 12 2017

A123656 a(n) = 1 + n^4 + n^6.

Original entry on oeis.org

3, 81, 811, 4353, 16251, 47953, 120051, 266241, 538003, 1010001, 1786203, 3006721, 4855371, 7567953, 11441251, 16842753, 24221091, 34117201, 47176203, 64160001, 85960603, 113614161, 148315731, 191434753, 244531251, 309372753, 387951931

Offset: 1

Jonathan Vos Post, Oct 04 2006

G. C. Greubel, Table of n, a(n) for n = 1..1000
Index entries for linear recurrences with constant coefficients, signature (7,-21,35,-35,21,-7,1).

Cf. A001358, A002523, A091940, A123177, A123657-A123659.

[1 + n^4 + n^6: n in [1..25]]; // G. C. Greubel, Oct 17 2017

Table[1 + n^4 + n^6, {n, 1, 50}] (* G. C. Greubel, Oct 17 2017 *)
LinearRecurrence[{7,-21,35,-35,21,-7,1},{3,81,811,4353,16251,47953,120051},30] (* Harvey P. Dale, May 10 2020 *)

a(n)=1+n^4+n^6 \\ Charles R Greathouse IV, Oct 07 2015

a(n) = 1 + n^4 + n^6.

G.f.: x*(3 +60*x +307*x^2 +272*x^3 +81*x^4 -4*x^5 +x^6)/(1-x)^7. - Colin Barker, May 25 2012

A131471 a(n) = n^5+n.

Original entry on oeis.org

0, 2, 34, 246, 1028, 3130, 7782, 16814, 32776, 59058, 100010, 161062, 248844, 371306, 537838, 759390, 1048592, 1419874, 1889586, 2476118, 3200020, 4084122, 5153654, 6436366, 7962648, 9765650, 11881402, 14348934, 17210396, 20511178, 24300030, 28629182, 33554464

Offset: 0

Mohammad K. Azarian, Jul 27 2007

Vincenzo Librandi, Table of n, a(n) for n = 0..10000
Index entries for linear recurrences with constant coefficients, signature (6,-15,20,-15,6,-1).

Cf. A002378, A007531, A034262, A091940, A058895, A059826.

Cf. A271208, A271209.

[n^5+n: n in [0..30]]; // Vincenzo Librandi, Oct 01 2011

Table[n^5 + n, {n, 0, 50}] (* Paolo Xausa, Nov 03 2024 *)

a(n) = n^5+n; \\ Michel Marcus, Apr 02 2016

G.f.: 2*x*(1+11*x+36*x^2+11*x^3+x^4)/(-1+x)^6. - R. J. Mathar, Nov 14 2007

a(n) = A271208(n) + 1 = A271209(n) - 1. - Paolo Xausa, Nov 03 2024

A334278 Irregular table read by rows: T(n, k) is the coefficient of x^k in the chromatic polynomial of the cubical graph Q_n, 0 <= k <= 2^n.

Original entry on oeis.org

0, 1, 0, -1, 1, 0, -3, 6, -4, 1, 0, -133, 423, -572, 441, -214, 66, -12, 1, 0, -3040575, 14412776, -31680240, 43389646, -41821924, 30276984, -17100952, 7701952, -2794896, 818036, -191600, 35264, -4936, 496, -32, 1

Offset: 0

Peter Kagey, Apr 21 2020

The sums of the absolute values of the entries in each row gives A334247, the number of acyclic orientations of edges of the n-cube.

			Table begins:
n/k| 0     1    2     3    4     5   6    7  8
---+-------------------------------------------
  0| 0,    1
  1| 0,   -1,   1
  2| 0,   -3,   6,   -4,   1
  3| 0, -133, 423, -572, 441, -214, 66, -12, 1

Peter Kagey, Table of n, a(n) for n = 0..68 (rows 0..5; row 5 from Andrew Howroyd's file)
Andrew Howroyd, Chromatic Polynomials of Hypercubes Q_0 to Q_5
Eric Weisstein's World of Mathematics, Chromatic Polynomial.
Eric Weisstein's World of Mathematics, Hypercube Graph.

Cf. A296914 is the reverse of row 3.
Cf. A334279 is analogous for the n-dimensional cross-polytope, the dual of the n-cube.
Cf. A001787, A002378, A091940, A140986, A158348.
Cf. A334159, A334247, A334358.

with(GraphTheory): with(SpecialGraphs):
T:= n-> (p-> seq(coeff(p, x, i), i=0..degree(p)))(
    ChromaticPolynomial(HypercubeGraph(n), x)):
seq(T(n), n=0..4);  # Alois P. Heinz, Jan 14 2025

T[n_, k_] := Coefficient[ChromaticPolynomial[HypercubeGraph[n], x], x, k]

T(n,0) = 0.

T(n,k) = Sum_{i=1..2^n}, Stirling1(i,k) * A334159(n,i). - Andrew Howroyd, Apr 25 2020

A212085 Square array A(n,k), n>=1, k>=1, read by antidiagonals: A(n,k) is the number of n-colorings of the complete bipartite graph K_(k,k).

Original entry on oeis.org

0, 0, 2, 0, 2, 6, 0, 2, 18, 12, 0, 2, 42, 84, 20, 0, 2, 90, 420, 260, 30, 0, 2, 186, 1812, 2420, 630, 42, 0, 2, 378, 7332, 18500, 9750, 1302, 56, 0, 2, 762, 28884, 127220, 121590, 30702, 2408, 72, 0, 2, 1530, 112740, 825860, 1324470, 583422, 81032, 4104, 90

Offset: 1

Alois P. Heinz, Apr 30 2012

The complete bipartite graph K_(n,n) has 2*n vertices and n^2 = A000290(n) edges. The chromatic polynomial of K_(n,n) has 2*n+1 coefficients.

A(n,k) is the number of pairs of strings of length k over an alphabet of size n such that the strings do not share any letter. - Lin Zhangruiyu, Aug 19 2022

			A(3,1) = 6 because there are 6 3-colorings of the complete bipartite graph K_(1,1): 1-2, 1-3, 2-1, 2-3, 3-1, 3-2.
Square array A(n,k) begins:
   0,   0,    0,      0,       0,        0,         0, ...
   2,   2,    2,      2,       2,        2,         2, ...
   6,  18,   42,     90,     186,      378,       762, ...
  12,  84,  420,   1812,    7332,    28884,    112740, ...
  20, 260, 2420,  18500,  127220,   825860,   5191220, ...
  30, 630, 9750, 121590, 1324470, 13284630, 126657750, ...

Alois P. Heinz, Antidiagonals n = 1..141, flattened
Eric Weisstein's World of Mathematics, Complete Bipartite Graph
Wikipedia, Chromatic Polynomial

Rows n=1-3 give: A000004, A007395, A068293(k+1).
Columns k=1-2 give: A002378(n-1), A091940.
Cf. A008277, A212084, A266695, A282245.

A:= (n, k)-> add(Stirling2(k, j) *mul(n-i, i=0..j-1) *(n-j)^k, j=1..k):
seq(seq(A(n, 1+d-n), n=1..d), d=1..12);

a[n_, k_] := Sum[(-1)^j*(n-j)^k*Pochhammer[-n, j]*StirlingS2[k, j], {j, 1, k}]; Table[a[n-k, k], {n, 1, 11}, {k, n-1, 1, -1}] // Flatten (* Jean-François Alcover, Dec 11 2013 *)

A(n,k) = Sum_{j=1..k} (n-j)^k * S2(k,j) * Product_{i=0..j-1} (n-i).

A(n,n)/n = A282245(n).

A334281 Number of n-colorings of the vertices of the 4-dimensional cross polytope such that no two adjacent vertices have the same color.

Original entry on oeis.org

0, 0, 0, 0, 24, 600, 7560, 61320, 351120, 1515024, 5266800, 15531120, 40308840, 94534440, 204228024, 412284600, 786283680, 1428742560, 2490276960, 4186173024, 6816915000, 10793253240, 16666437480, 25164280680, 37233759024, 54090894000, 77278702800

Offset: 0

Peter Kagey, Apr 21 2020

The 4-dimensional cross-polytope is sometimes called the 16-cell. It is one of the six convex regular 4-polytopes.

Colin Barker, Table of n, a(n) for n = 0..1000
Eric Weisstein's World of Mathematics, Chromatic Polynomial
Wikipedia, Cross-polytope
Wikipedia, Turán graph
Index entries for linear recurrences with constant coefficients, signature (9,-36,84,-126,126,-84,36,-9,1).

Cf. A091940 (2-dimensional), A115400 (3-dimensional).

Cf. A334279.

concat([0,0,0,0], Vec(24*x^4*(1 + 16*x + 126*x^2 + 536*x^3 + 1001*x^4) / (1 - x)^9 + O(x^30))) \\ Colin Barker, Apr 22 2020

a(n) = n*(n - 1)*(n - 2)*(n - 3)*(465 - 392n + 125n^2 - 18n^3 + n^4).
a(n) = -2790n + 7467n^2 - 7852n^3 + 4300n^4 - 1346n^5 + 244n^6 - 24n^7 + n^8.
From Colin Barker, Apr 22 2020: (Start)
G.f.: 24*x^4*(1 + 16*x + 126*x^2 + 536*x^3 + 1001*x^4) / (1 - x)^9.
a(n) = 9*a(n-1) - 36*a(n-2) + 84*a(n-3) - 126*a(n-4) + 126*a(n-5) - 84*a(n-6) + 36*a(n-7) - 9*a(n-8) + a(n-9) for n>8.
(End)

cp's OEIS Frontend

A053644 Most significant bit of n, msb(n); largest power of 2 less than or equal to n; write n in binary and change all but the first digit to zero.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Haskell

Magma

Maple

Mathematica

PARI

PARI

Python

Python

Scala

Formula

A182406 Square array A(n,k), n>=1, k>=1, read by antidiagonals: A(n,k) is the number of n-colorings of the square grid graph G_(k,k).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A100019 a(n) = n^4 + n^3 + n^2.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

Formula

A334159 Irregular triangle read by rows: T(n,k) is the number of colorings of the n-hypercube graph using exactly k unlabeled colors, k = 1..2^n.

Views

Author

Keywords

Examples

Links

Crossrefs

A106512 Array read by antidiagonals: a(n,k) = number of k-colorings of a circle of n nodes (n >= 1, k >= 1).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

Extensions

A123656 a(n) = 1 + n^4 + n^6.

Views

Author

Keywords

Links

Crossrefs

Programs

Magma

Mathematica

PARI

Formula

A131471 a(n) = n^5+n.

Views

Author

Keywords

Links

Crossrefs

Programs

Magma

Mathematica

PARI

Formula

A334278 Irregular table read by rows: T(n, k) is the coefficient of x^k in the chromatic polynomial of the cubical graph Q_n, 0 <= k <= 2^n.