A068293 -id:A068293

A151724

First differences of A151723.

+10
19

0, 1, 6, 6, 18, 6, 18, 30, 42, 6, 18, 30, 54, 54, 42, 78, 90, 6, 18, 30, 54, 54, 54, 102, 150, 102, 42, 78, 138, 162, 114, 186, 186, 6, 18, 30, 54, 54, 54, 102, 150, 102, 54, 102, 174, 222, 198, 246, 342, 198, 42, 78, 138, 162, 162, 258, 402, 354, 162, 186

(list; graph; refs; listen; history; text; internal format)

OFFSET

0,3

REFERENCES

S. M. Ulam, On some mathematical problems connected with patterns of growth of figures, pp. 215-224 of R. E. Bellman, ed., Mathematical Problems in the Biological Sciences, Proc. Sympos. Applied Math., Vol. 14, Amer. Math. Soc., 1962 (see Example 6, page 224).

LINKS

N. J. A. Sloane, Table of n, a(n) for n = 0..4095 [First 1024 terms from David Applegate and N. J. A. Sloane]

David Applegate, The movie version

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.]

David Applegate and N. J. A. Sloane, Table of n, A151724(n), A151723(n) for n = 0..1025

N. J. A. Sloane, Catalog of Toothpick and Cellular Automata Sequences in the OEIS

N. J. A. Sloane, Exciting Number Sequences (video of talk), Mar 05 2021.

EXAMPLE

When written as a triangle:

0,

1,

6,

6,18,

6,18,30,42,

6,18,30,54,54,42,78,90,

6,18,30,54,54,54,102,150,102,42,78,138,162,114,186,186,

...

Right border gives 0 together with A068293. - Omar E. Pol, Mar 19 2015

CROSSREFS

Cf. A151723, A170898 (after dividing by 6), A170899, A169759.

KEYWORD

nonn

AUTHOR

David Applegate and N. J. A. Sloane, Jun 13 2009

STATUS

approved

A212209

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

+10
19

1, 0, 2, 0, 0, 3, 0, 0, 0, 4, 0, 0, 0, 24, 5, 0, 0, 0, 72, 120, 6, 0, 0, 0, 168, 6720, 360, 7, 0, 0, 0, 360, 935040, 126360, 840, 8, 0, 0, 0, 744, 325061760, 265035240, 1128960, 1680, 9, 0, 0, 0, 1512, 283192323840, 3322711053720, 17160407040, 6510000, 3024, 10

(list; table; graph; refs; listen; history; text; internal format)

OFFSET

1,3

COMMENTS

The square diagonal grid graph DG_(n,n) has n^2 = A000290(n) vertices and 2*(n-1)*(2*n-1) = A002943(n-1) edges; see A212208 for example. The chromatic polynomial of DG_(n,n) has n^2+1 = A002522(n) coefficients.

This graph is also called the king graph. - Andrew Howroyd, Jun 25 2017

LINKS

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

Eric Weisstein's World of Mathematics, King Graph

Wikipedia, Chromatic Polynomial

EXAMPLE

Square array A(n,k) begins:

1, 0, 0, 0, 0, ...

2, 0, 0, 0, 0, ...

3, 0, 0, 0, 0, ...

4, 24, 72, 168, 360, ...

5, 120, 6720, 935040, 325061760, ...

6, 360, 126360, 265035240, 3322711053720, ...

7, 840, 1128960, 17160407040, 2949948395735040, ...

CROSSREFS

Columns 1-5 give: A000027, A052762 = 24*A000332, 24*A068250, 24*A068251, 24*A068252.

Rows n=1-16 give: A000007, A000038, 3*A000007, 4*A068293, 5*A068294, 6*A068295, 7*A068296, 8*A068297, 9*A068298, 10*A068299, 11*A068300, 12*A068301, 13*A068302, 14*A068303, 15*A068304, 16*A068305.

Cf. A000290, A002943, A212208, A208021.

KEYWORD

nonn,tabl

AUTHOR

Alois P. Heinz, May 04 2012

STATUS

approved

A091344

a(n) = 2*3^n - 3*2^n + 1.

+10
10

0, 1, 7, 31, 115, 391, 1267, 3991, 12355, 37831, 115027, 348151, 1050595, 3164071, 9516787, 28599511, 85896835, 257887111, 774054547, 2322950071, 6970423075, 20914414951, 62749536307, 188261191831, 564808741315, 1694476555591

(list; graph; refs; listen; history; text; internal format)

OFFSET

0,3

COMMENTS

Starting with offset 1 = binomial transform of A068293: (1, 6, 18, 42, 90, ...) and double binomial transform of (1, 5, 7, 5, 7, 5, ...). - Gary W. Adamson, Jan 13 2009

Number of pairs (A,B) where A and B are nonempty subsets of {1,2,...,n} and one of these subsets is a subset of the other. - For the case that one of these subsets is a proper subset of the other see a(n+1) in A260217. - If empty subsets are included, see A027649 (all subsets) and A056182 (proper subsets). - Manfred Boergens, Aug 02 2023

LINKS

Table of n, a(n) for n=0..25.

Christian Ballot and Florian Luca, Prime factors of a^f(n)-1 with an irreducible polynomial f(x),New York J. Math. 12 (2006), 39-45 (electronic).

Christian Ballot and Florian Luca, Common prime factors of a^n-b and c^n-d, Unif. Distrib. Theory 2 (2007), no. 2, 19-34 (electronic).

John Elias, Illustration of initial terms: Sixfold Sierpinski Stars

Index entries for linear recurrences with constant coefficients, signature (6,-11,6).

FORMULA

a(n) = Sum_{i=1..n} i!*i^2*Stirling2(n,i)*(-1)^(n-i).

From Christian Ballot via R. K. Guy, Jan 13 2009: (Start)

a(n) = 6*a(n-1) - 11*a(n-2) + 6*a(n-3);

G.f.: x*(1+x)/((1-x)*(2-x)*(3-x)). (End)

a(n) = 5*a(n-1) - 6*a(n-2) + 2, a(0)=0, a(1)=1. - Vincenzo Librandi, Nov 25 2010

E.g.f.: exp(x)*(1 - 3*exp(x) + 2*exp(2*x)). - Stefano Spezia, May 18 2024

MAPLE

a:=n->sum((3^(n-j-1)-2^(n-2-j))*12, j=0..n): seq(a(n), n=-1..24); # Zerinvary Lajos, Feb 11 2007

with (combinat):a:=n->stirling2(n, 3)+stirling2(n+1, 3): seq(a(n), n=1..26); # Zerinvary Lajos, Oct 07 2007

MATHEMATICA

Table[Sum[i!i^2 StirlingS2[n, i](-1)^(n - i), {i, 1, n}], {n, 0, 30}]

Table[2*3^n-3*2^n+1, {n, 0, 30}] (* or *) LinearRecurrence[{6, -11, 6}, {0, 1, 7}, 30] (* Harvey P. Dale, Dec 31 2013 *)

CROSSREFS

Cf. A027649, A056182, A068293, A260217.

KEYWORD

easy,nonn

AUTHOR

Mario Catalani (mario.catalani(AT)unito.it), Jan 01 2004

EXTENSIONS

Edited by N. J. A. Sloane, Jan 13 2009 at the suggestion of R. K. Guy; the concise definition was provided by Vladeta Jovovic, Jan 01 2004

STATUS

approved

A175164

a(n) = 16*(2^n - 1).

+10
6

0, 16, 48, 112, 240, 496, 1008, 2032, 4080, 8176, 16368, 32752, 65520, 131056, 262128, 524272, 1048560, 2097136, 4194288, 8388592, 16777200, 33554416, 67108848, 134217712, 268435440

(list; graph; refs; listen; history; text; internal format)

OFFSET

0,2

LINKS

G. C. Greubel, Table of n, a(n) for n = 0..1000

Index entries for linear recurrences with constant coefficients, signature (3,-2).

FORMULA

a(n) = 2^(n+4) - 16.

a(n) = A173787(n+4, 4).

a(2*n) = A140504(n+2)*A028399(n).

a(n) = 3*a(n-1) - 2*a(n-2), a(0)=0, a(1)=16. - Vincenzo Librandi, Dec 28 2010

From G. C. Greubel, Jul 08 2021: (Start)

G.f.: 16*x/((1-x)*(1-2*x)).

E.g.f.: 16*(exp(2*x) - exp(x)). (End)

MATHEMATICA

16*(2^Range[0, 40] - 1) (* G. C. Greubel, Jul 08 2021 *)

PROG

(Magma) I:=[0, 16]; [n le 2 select I[n] else 3*Self(n-1) - 2*Self(n-2): n in [1..41]]; // G. C. Greubel, Jul 08 2021

(Sage) [16*(2^n -1) for n in (0..40)] # G. C. Greubel, Jul 08 2021

(Python)

def A175164(n): return (1<<n)-1<<4 # Chai Wah Wu, Jun 27 2023

CROSSREFS

Sequences of the form m*(2^n - 1): A000225 (m=1), A000918 (m=2), A068156 (m=3), A028399 (m=4), A068293 (m=6), A159741 (m=8), this sequence (m=16), A175165 (m=32), A175166 (m=64).

Cf. A140504, A173787.

KEYWORD

nonn

AUTHOR

Reinhard Zumkeller, Feb 28 2010

STATUS

approved

A175166

a(n) = 64*(2^n - 1).

+10
6

0, 64, 192, 448, 960, 1984, 4032, 8128, 16320, 32704, 65472, 131008, 262080, 524224, 1048512, 2097088, 4194240, 8388544, 16777152, 33554368, 67108800, 134217664, 268435392, 536870848, 1073741760

(list; graph; refs; listen; history; text; internal format)

OFFSET

0,2

LINKS

G. C. Greubel, Table of n, a(n) for n = 0..1000

Index entries for linear recurrences with constant coefficients, signature (3,-2).

FORMULA

a(n) = 2^(n+6) - 64.

a(n) = A173787(n+6, 6).

a(2*n) = A175161(n)*A159741(n) for n > 0.

a(n) = 3*a(n-1) - 2*a(n-2), a(0)=0, a(1)=64. - Vincenzo Librandi, Dec 28 2010

From G. C. Greubel, Jul 08 2021: (Start)

G.f.: 64*x/((1-x)*(1-2*x)).

E.g.f.: 64*(exp(2*x) - exp(x)). (End)

MATHEMATICA

LinearRecurrence[{3, -2}, {0, 64}, 30] (* Harvey P. Dale, Apr 08 2015 *)

PROG

(Magma) I:=[0, 64]; [n le 2 select I[n] else 3*Self(n-1) - 2*Self(n-2): n in [1..41]]; // G. C. Greubel, Jul 08 2021

(Sage) [64*(2^n -1) for n in (0..40)] # G. C. Greubel, Jul 08 2021

(Python)

def A175166(n): return (1<<n)-1<<6 # Chai Wah Wu, Jun 27 2023

CROSSREFS

Sequences of the form m*(2^n - 1): A000225 (m=1), A000918 (m=2), A068156 (m=3), A028399 (m=4), A068293 (m=6), A159741 (m=8), A175164 (m=16), A175165 (m=32), this sequence (m=64).

Cf. A173787, A175161.

KEYWORD

nonn

AUTHOR

Reinhard Zumkeller, Feb 28 2010

STATUS

approved

A175165

a(n) = 32*(2^n - 1).

+10
5

0, 32, 96, 224, 480, 992, 2016, 4064, 8160, 16352, 32736, 65504, 131040, 262112, 524256, 1048544, 2097120, 4194272, 8388576, 16777184, 33554400, 67108832, 134217696, 268435424, 536870880

(list; graph; refs; listen; history; text; internal format)

OFFSET

0,2

LINKS

G. C. Greubel, Table of n, a(n) for n = 0..1000

Index entries for linear recurrences with constant coefficients, signature (3,-2).

FORMULA

a(n) = 2^(n+5) - 32.

a(n) = A173787(n+5, 5).

a(n) = 3*a(n-1) - 2*a(n-2); a(0)=0, a(1)=32. - Vincenzo Librandi, Dec 28 2010

From G. C. Greubel, Jul 08 2021: (Start)

G.f.: 32*x/((1-x)*(1-2*x)).

E.g.f.: 32*(exp(2*x) - exp(x)). (End)

MATHEMATICA

32(2^Range[0, 30] -1) (* or *) LinearRecurrence[{3, -2}, {0, 32}, 30] (* Harvey P. Dale, Mar 23 2015 *)

PROG

(Magma) I:=[0, 32]; [n le 2 select I[n] else 3*Self(n-1) - 2*Self(n-2): n in [1..41]]; // G. C. Greubel, Jul 08 2021

(Sage) [32*(2^n -1) for n in (0..40)] # G. C. Greubel, Jul 08 2021

(Python)

def A175165(n): return (1<<n)-1<<5 # Chai Wah Wu, Jun 27 2023

CROSSREFS

Sequences of the form m*(2^n - 1): A000225 (m=1), A000918 (m=2), A068156 (m=3), A028399 (m=4), A068293 (m=6), A159741 (m=8), A175164 (m=16), this sequence (m=32), A175166 (m=64).

Cf. A173787.

KEYWORD

nonn

AUTHOR

Reinhard Zumkeller, Feb 28 2010

STATUS

approved

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).

+10
5

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

(list; table; graph; refs; listen; history; text; internal format)

OFFSET

1,3

COMMENTS

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

LINKS

Alois P. Heinz, Antidiagonals n = 1..141, flattened

Eric Weisstein's World of Mathematics, Complete Bipartite Graph

Wikipedia, Chromatic Polynomial

FORMULA

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).

EXAMPLE

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, ...

MAPLE

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);

MATHEMATICA

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 *)

CROSSREFS

Rows n=1-3 give: A000004, A007395, A068293(k+1).

Columns k=1-2 give: A002378(n-1), A091940.

Cf. A008277, A212084, A266695, A282245.

KEYWORD

nonn,tabl

AUTHOR

Alois P. Heinz, Apr 30 2012

STATUS

approved

A185739

Accumulation array of A185738, by antidiagonals.

+10
3

1, 3, 4, 6, 10, 11, 10, 18, 25, 26, 15, 28, 42, 56, 57, 21, 40, 62, 90, 119, 120, 28, 54, 85, 128, 186, 246, 247, 36, 70, 111, 170, 258, 378, 501, 502, 45, 88, 140, 216, 335, 516, 762, 1012, 1013, 55, 108, 172, 266, 417, 660, 1030, 1530, 2035, 2036, 66, 130, 207, 320, 504, 810, 1305, 2056, 3066, 4082, 4083, 78, 154, 245, 378, 596, 966, 1587, 2590, 4106, 6138, 8177, 8178, 91

(list; table; graph; refs; listen; history; text; internal format)

OFFSET

1,2

COMMENTS

This arrays is a member of a chain; see A185738.

LINKS

G. C. Greubel, Table of n, a(n) for the first 50 rows, flattened

FORMULA

T(n,k) = k*(4*(2^n-1)+(k-3)*n), k>=1, n>=1.

EXAMPLE

Northwest corner:

1....3....6....10....15

4....10...18...28....40

11...25...42...62....85

26...56...90...128...170

MATHEMATICA

(* See A185738 *)

f[n_, k_] := (k/2)*(4*(2^n - 1) + (k - 3)*n);

TableForm[Table[f[n, k], {n, 1, 10}, {k, 1, 10}]] (* Array A185739 *)

Table[f[n - k + 1, k], {n, 10}, {k, n, 1, -1}] // Flatten (* G. C. Greubel, Jul 11 2017 *)

CROSSREFS

Rows 1 to 4: A000217, A028562, A140675, 2*A098847

Columns 1 to 3: A000295, A000247, A068293.

Cf. A185738, A185740.

KEYWORD

nonn,tabl

AUTHOR

Clark Kimberling, Feb 02 2011

STATUS

approved

A178923

Rectangular array T(m,k)= StirlingS2(k-1,m-1)*m! (The Coupon Collectors Problem)

+10
2

1, 0, 0, 0, 2, 0, 0, 2, 0, 0, 0, 2, 6, 0, 0, 0, 2, 18, 0, 0, 0, 0, 2, 42, 24, 0, 0, 0, 0, 2, 90, 144, 0, 0, 0, 0, 0, 2, 186, 600, 120, 0, 0, 0, 0, 0, 2, 378, 2160, 1200, 0, 0, 0, 0, 0

(list; table; graph; refs; listen; history; text; internal format)

OFFSET

1,5

COMMENTS

T(m,k) is the number of functions f:{1,2,...}->(1,2,...,m} such that the image of f[{1,2,...,k}] is {1,2,...,m} but the image of f[{1,2,...,k-1}] is not.

T(m,k)/m^k is the probability that a collector of m different objects will require exactly k trials (uniform random selection with replacement) to complete the collection.

LINKS

Table of n, a(n) for n=1..55.

FORMULA

O.g.f.: for row m: m!x^m/Product_{i=1...m-1}1-i*x

EXAMPLE

1 0 0 0 0 0 0 0 0 ...

0 2 2 2 2 2 2 2 2 ...

0 0 6 18 42 90 186 378 762 ...

0 0 0 24 144 600 2160 7224 23184 ...

0 0 0 0 120 1200 7800 42000 204120 ...

0 0 0 0 0 720 10800 100800 756000 ...

0 0 0 0 0 0 5040 105840 1340640 ...

0 0 0 0 0 0 0 40320 1128960 ...

0 0 0 0 0 0 0 0 362880 ...

MAPLE

A178923 := proc(m, k)

combinat[stirling2](k-1, m-1)*m! ;

end proc:

seq(seq(A178923(m, d-m), m=1..d-1), d=2..15) ; # R. J. Mathar, Jan 19 2024

MATHEMATICA

Table[Table[StirlingS2[k - 1, m - 1] m!, {k, 1, 10}], {m, 1, 10}] // Grid

CROSSREFS

Cf. A068293 (row m=3), A000142 (diagonal), A001804 (subdiagonal).

KEYWORD

nonn,tabl

AUTHOR

Geoffrey Critzer, Dec 29 2010

STATUS

approved