A003946 -id:A003946 - cp's OEIS frontend

A275131 T(n,k)=Number of nXk 0..2 arrays with no element equal to any value at offset (-2,-2) (-1,0) or (-1,1) and new values introduced in order 0..2.

1, 2, 1, 5, 4, 2, 14, 16, 12, 4, 41, 64, 45, 36, 8, 122, 256, 174, 129, 108, 16, 365, 1024, 675, 568, 373, 324, 32, 1094, 4096, 2607, 2545, 2178, 1083, 972, 64, 3281, 16384, 10077, 11092, 12423, 8321, 3148, 2916, 128, 9842, 65536, 38967, 48451, 71576, 62378

Offset: 1

R. H. Hardin, Jul 17 2016

Table starts
...1.....2.....5......14.......41.......122.........365.........1094
...1.....4....16......64......256......1024........4096........16384
...2....12....45.....174......675......2607.......10077........38967
...4....36...129.....568.....2545.....11092.......48451.......212897
...8...108...373....2178....12423.....71576......412306......2381629
..16...324..1083....8321....62378....473185.....3586068.....27224209
..32...972..3148...31772...315021...3146574....31446544....315531602
..64..2916..9157..121707..1591442..20970214...276145917...3669759648
.128..8748.26623..466252..8024937.139845553..2432426709..42807577389
.256.26244.77372.1783920.40445177.930732169.21443562178.499213473864

			Some solutions for n=4 k=4
..0..0..1..1. .0..0..1..1. .0..1..2..2. .0..1..1..1. .0..0..1..2
..2..2..0..2. .2..2..2..0. .2..0..1..0. .2..2..0..0. .1..2..0..1
..1..1..1..1. .0..0..1..2. .1..2..2..2. .1..1..1..2. .0..1..2..2
..0..0..0..0. .2..2..0..0. .0..1..1..1. .2..2..0..1. .2..0..0..1

R. H. Hardin, Table of n, a(n) for n = 1..312

Column 1 is A000079(n-2).
Column 2 is A003946(n-1).
Row 1 is A007051(n-1).
Row 2 is A000302(n-1).

Empirical for column k:
k=1: a(n) = 2*a(n-1) for n>2
k=2: a(n) = 3*a(n-1) for n>2
k=3: [order 9] for n>10
k=4: [order 17] for n>20
k=5: [order 28] for n>31
k=6: [order 67] for n>70
Empirical for row n:
n=1: a(n) = 4*a(n-1) -3*a(n-2)
n=2: a(n) = 4*a(n-1)
n=3: a(n) = 3*a(n-1) +2*a(n-2) +6*a(n-3) -2*a(n-4) -4*a(n-5) for n>6
n=4: [order 9] for n>11
n=5: [order 10] for n>14
n=6: [order 26] for n>28
n=7: [order 53] for n>58

A274895 T(n,k)=Number of nXk 0..2 arrays with no element equal to any value at offset (0,-1) (-1,-1) or (-2,0) and new values introduced in order 0..2.

Original entry on oeis.org

1, 1, 2, 2, 4, 3, 4, 12, 7, 6, 8, 36, 16, 14, 12, 16, 108, 37, 38, 26, 24, 32, 324, 86, 104, 84, 50, 48, 64, 972, 200, 290, 275, 192, 95, 96, 128, 2916, 465, 815, 913, 753, 436, 181, 192, 256, 8748, 1081, 2291, 3064, 3017, 2049, 990, 345, 384, 512, 26244, 2513, 6434, 10337

Offset: 1

R. H. Hardin, Jul 10 2016

Table starts
...1...1....2.....4......8......16.......32........64........128.........256
...2...4...12....36....108.....324......972......2916.......8748.......26244
...3...7...16....37.....86.....200......465......1081.......2513........5842
...6..14...38...104....290.....815.....2291......6434......18065.......50729
..12..26...84...275....913....3064....10337.....34921.....117975......398560
..24..50..192...753...3017...12217....49697....202749.....828828.....3391310
..48..95..436..2049...9863...48269...237807...1173787....5803040....28746995
..96.181..990..5602..32539..191974..1143185...6843349...41072451...246859250
.192.345.2253.15305.107369..767905..5539989..40156061..292253909..2133745005
.384.657.5121.41866.354366.3065418.26833885.236220817.2086382703.18485204565

			Some solutions for n=4 k=4
..0..1..0..2. .0..1..2..0. .0..1..0..2. .0..1..2..0. .0..1..2..1
..2..1..2..1. .1..2..0..1. .2..1..0..2. .1..2..0..1. .1..2..0..1
..1..0..2..1. .2..0..1..2. .1..0..2..1. .1..2..1..2. .1..0..1..2
..1..0..1..0. .2..0..1..0. .1..0..2..0. .2..0..1..2. .2..0..1..0

R. H. Hardin, Table of n, a(n) for n = 1..420

Column 1 is A003945(n-2).
Column 2 is A052535(n+1).
Row 1 is A000079(n-2).
Row 2 is A003946(n-1).
Row 3 is A010912(n-1).

Empirical for column k:
k=1: a(n) = 2*a(n-1) for n>3
k=2: a(n) = a(n-1) +2*a(n-2) -a(n-4) for n>5
k=3: a(n) = a(n-1) +4*a(n-2) -6*a(n-4) -a(n-5) +4*a(n-6) -a(n-8) for n>10
k=4: [order 16] for n>18
k=5: [order 32] for n>34
k=6: [order 64] for n>66
Empirical for row n:
n=1: a(n) = 2*a(n-1) for n>2
n=2: a(n) = 3*a(n-1) for n>2
n=3: a(n) = 3*a(n-1) -2*a(n-2) +a(n-3)
n=4: a(n) = 5*a(n-1) -9*a(n-2) +10*a(n-3) -6*a(n-4) +a(n-5) for n>6
n=5: [order 8] for n>9
n=6: [order 13] for n>14
n=7: [order 21] for n>22

A183362 T(n,k)=One quarter the number of nXk 1..4 arrays with no two neighbors of any element equal to each other.

Original entry on oeis.org

1, 4, 4, 12, 36, 12, 36, 144, 144, 36, 108, 576, 432, 576, 108, 324, 2304, 1296, 1296, 2304, 324, 972, 9216, 3888, 3600, 3888, 9216, 972, 2916, 36864, 11664, 9216, 9216, 11664, 36864, 2916, 8748, 147456, 34992, 24336, 24192, 24336, 34992, 147456, 8748

Offset: 1

R. H. Hardin Jan 04 2011

Table starts
.....1.......4.....12......36.....108.....324.....972.....2916.....8748
.....4......36....144.....576....2304....9216...36864...147456...589824
....12.....144....432....1296....3888...11664...34992...104976...314928
....36.....576...1296....3600....9216...24336...63504...166464...435600
...108....2304...3888....9216...24192...57600..137088...331776...802944
...324....9216..11664...24336...57600..147456..331776...746496..1679616
...972...36864..34992...63504..137088..331776..829440..1806336..3852288
..2916..147456.104976..166464..331776..746496.1806336..4460544..9437184
..8748..589824.314928..435600..802944.1679616.3852288..9437184.23003136
.26244.2359296.944784.1140624.1937664.3873024.8294400.19501056.47775744

			Some solutions for 6X5 with a(1,1)=1
..1..1..3..2..2....1..1..3..2..1....1..1..4..2..3....1..1..3..2..4
..4..4..3..1..1....2..2..4..4..3....3..3..4..1..3....4..4..3..1..1
..3..2..2..4..4....4..3..1..1..3....4..2..2..1..4....3..2..2..4..3
..3..1..1..3..2....4..3..2..2..4....4..1..3..3..4....3..1..1..4..3
..2..4..4..3..1....1..1..4..3..1....3..1..4..2..2....2..4..3..2..2
..1..3..2..2..1....2..2..4..3..1....3..2..4..1..3....1..4..3..1..4

R. H. Hardin, Table of n, a(n) for n = 1..335

Column 1 is A003946(n-1)

A209019 T(n,k)=Number of nXk 0..3 arrays with no element equal the average of immediate neighbors vertically above, diagonally above and left, and horizontally left of it.

Original entry on oeis.org

4, 12, 12, 36, 130, 36, 108, 1430, 1430, 108, 324, 15724, 57412, 15724, 324, 972, 172936, 2303052, 2303052, 172936, 972, 2916, 1901964, 92409982, 337083370, 92409982, 1901964, 2916, 8748, 20918008, 3707858104, 49349902246, 49349902246

Offset: 1

R. H. Hardin Mar 04 2012

Table starts
....4........12............36................108....................324
...12.......130..........1430..............15724.................172936
...36......1430.........57412............2303052...............92409982
..108.....15724.......2303052..........337083370............49349902246
..324....172936......92409982........49349902246.........26361689168962
..972...1901964....3707858104......7224768704460......14081479775124768
.2916..20918008..148774643618...1057701934285612....7521858792951566188
.8748.230058424.5969451726624.154846841369187254.4017924265572698697072

			Some solutions for n=4 k=3
..3..1..2....1..3..0....0..2..0....1..2..0....0..1..3....3..2..3....0..1..0
..1..3..3....2..1..3....3..0..0....3..3..3....2..3..1....0..2..3....3..2..2
..3..1..3....0..2..0....2..1..1....0..0..0....1..3..0....3..0..1....1..3..1
..1..3..3....1..2..0....0..2..1....2..1..3....2..0..0....2..3..2....2..3..2

R. H. Hardin, Table of n, a(n) for n = 1..180

Column 1 is A003946

A209047 T(n,k)=Number of nXk 0..3 arrays with no element equal the average of immediate neighbors vertically above and horizontally left of it.

Original entry on oeis.org

4, 12, 12, 36, 124, 36, 108, 1300, 1300, 108, 324, 13644, 47700, 13644, 324, 972, 143212, 1752148, 1752148, 143212, 972, 2916, 1503212, 64369764, 225262148, 64369764, 1503212, 2916, 8748, 15778340, 2364812680, 28964458546, 28964458546

Offset: 1

R. H. Hardin Mar 04 2012

Table starts
....4........12............36...............108....................324
...12.......124..........1300.............13644.................143212
...36......1300.........47700...........1752148...............64369764
..108.....13644.......1752148.........225262148............28964458546
..324....143212......64369764.......28964458546.........13034933066892
..972...1503212....2364812680.....3724317998214.......5866193355938718
.2916..15778340...86878417604...478881915072688....2640002203816927226
.8748.165616044.3191736905988.61575811582924326.1188097914449381928076

			Some solutions for n=4 k=3
..0..3..0....3..1..2....0..2..0....0..1..2....1..3..2....2..0..1....0..1..3
..1..1..3....1..3..3....3..0..1....3..3..0....2..0..2....0..2..0....1..2..1
..2..1..1....3..1..3....2..2..1....0..1..1....3..1..1....1..2..2....2..0..2
..3..1..2....1..3..0....0..2..1....3..3..1....0..1..2....3..0..0....3..1..0

R. H. Hardin, Table of n, a(n) for n = 1..220

Column 1 is A003946

A287839 Number of words of length n over the alphabet {0,1,...,10} such that no two consecutive terms have distance 9.

Original entry on oeis.org

1, 11, 117, 1247, 13289, 141619, 1509213, 16083463, 171399121, 1826575451, 19465548357, 207441511727, 2210673955769, 23558830139779, 251063019088173, 2675542001860183, 28512861152219041, 303857405535211691, 3238164083417650197, 34508642672922983807

Offset: 0

David Nacin, Jun 07 2017

In general, the number of sequences on {0,1,...,10} such that no two consecutive terms have distance 6+k for k in {0,1,2,3,4} has generating function (-1 - x)/(-1 + 10*x + (2*k+1)*x^2).

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

Cf. A040000, A003945, A083318, A078057, A003946, A126358, A003946, A055099, A003947, A015448, A126473. A287804-A287819. A287825-A287839.

a:=proc(n) option remember; if n=0 then 1 elif n=1 then 11 elif n=2 then 117 else 10*a(n-1)+7*a(n-2); fi; end: seq(a(n), n=0..30); # Wesley Ivan Hurt, Nov 25 2017

LinearRecurrence[{10, 7}, {1, 11, 117}, 20]

Vec((1 + x) / (1 - 10*x - 7*x^2) + O(x^30)) \\ Colin Barker, Nov 25 2017

def a(n):
 if n in [0,1,2]:
  return [1, 11, 117][n]
 return 10*a(n-1) + 7*a(n-2)

For n>2, a(n) = 10*a(n-1) + 7*a(n-2), a(0)=1, a(1)=11, a(2)=117.
G.f.: (-1 - x)/(-1 + 10 x + 7 x^2).
a(n) = (((5-4*sqrt(2))^n*(-3+2*sqrt(2)) + (3+2*sqrt(2))*(5+4*sqrt(2))^n)) / (4*sqrt(2)). - Colin Barker, Nov 25 2017

A052156 Number of compositions of n into 2*j-1 kinds of j's for all j>=1.

Original entry on oeis.org

1, 1, 4, 12, 36, 108, 324, 972, 2916, 8748, 26244, 78732, 236196, 708588, 2125764, 6377292, 19131876, 57395628, 172186884, 516560652, 1549681956, 4649045868, 13947137604, 41841412812, 125524238436, 376572715308, 1129718145924

Offset: 0

Barry E. Williams, Jan 24 2000

First differences of A025192, also second differences of A000244.

			1 + x + 4*x^2 + 12*x^3 + 36*x^4 + 108*x^5 + 324*x^6 + 972*x^7 + 2916*x^8 + ...

A. H. Beiler, Recreations in the Theory of Numbers, Dover, N.Y., 1964, pp. 189, 194-196.
P. Ribenhoim, The Little Book of Big Primes, Springer-Verlag, N.Y., 1991, p. 53.

Vincenzo Librandi, Table of n, a(n) for n = 0..1000
Index entries for linear recurrences with constant coefficients, signature (3).

Cf. A025192, A000244, A003462.

CoefficientList[Series[(1 - x)^2/(1 - 3 x), {x, 0, 40}], x ] (* Vincenzo Librandi, Apr 29 2014 *)

{a(n) = local(A); if( n<1, n==0, A = vector(n); A[1] = 1; for( k=2, n, A[k] = (-4*k + 9) * A[k-1] + 3 * sum( j=1, k-1, A[j] * A[k-j])); A[n])} /* Michael Somos, Jul 23 2011 */

a(n) = 4*3^(n-2); n >= 2; a(0) = 1; a(1) = 1.
G.f.: (1-x)^2/(1-3*x).
G.f.: 1/(1-sum(j>=1, (2*j-1)*x^j )). - Joerg Arndt, Jul 06 2011
a(n) = 3*a(n-1)+(-1)^n*C(2, 2-n).
a(n) = A003946(n-1), n>0. - R. J. Mathar, Oct 13 2008
a(n) = (-4*n + 9) * a(n-1) + 3 * Sum_{k=1..n-1} a(k) * a(n-k) if n>1. - Michael Somos, Jul 23 2011
a(n) = Sum_{k, 0<=k<=n} A201780(n,k). - Philippe Deléham, Dec 05 2011

New name from Joerg Arndt, Jul 06 2011

A167882 Number of reduced words of length n in Coxeter group on 4 generators S_i with relations (S_i)^2 = (S_i S_j)^16 = I.

Original entry on oeis.org

1, 4, 12, 36, 108, 324, 972, 2916, 8748, 26244, 78732, 236196, 708588, 2125764, 6377292, 19131876, 57395622, 172186848, 516560496, 1549681344, 4649043600, 13947129504, 41841384624, 125524142208, 376572391632, 1129717069920

Offset: 0

John Cannon and N. J. A. Sloane, Dec 03 2009

nonn

The initial terms coincide with those of A003946, although the two sequences are eventually different.

Computed with MAGMA using commands similar to those used to compute A154638.

G. C. Greubel, Table of n, a(n) for n = 0..500
Index entries for linear recurrences with constant coefficients, signature (2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,-3).

Cf. A003946, A154638, A169452.

R:=PowerSeriesRing(Integers(), 40); Coefficients(R!( (1+x)*(1-x^16)/(1-3*x+5*x^16-3*x^17) )); // G. C. Greubel, Dec 06 2024

CoefficientList[Series[(1+t)*(1-t^16)/(1-3*t+5*t^16-3*t^17), {t,0,50}], t] (* G. C. Greubel, Jun 29 2016; Dec 06 2024 *)
coxG[{16,3,-2}] (* The coxG program is at A169452 *) (* G. C. Greubel, Dec 06 2024 *)

def A167882_list(prec):
    P. = PowerSeriesRing(ZZ, prec)
    return P( (1+x)*(1-x^16)/(1-3*x+5*x^16-3*x^17) ).list()
print(A167882_list(40)) # G. C. Greubel, Dec 06 2024

G.f.: (t^16 + 2*t^15 + 2*t^14 + 2*t^13 + 2*t^12 + 2*t^11 + 2*t^10 + 2*t^9 + 2*t^8 + 2*t^7 + 2*t^6 + 2*t^5 + 2*t^4 + 2*t^3 + 2*t^2 + 2*t + 1) / ( 3*t^16 - 2*t^15 - 2*t^14 - 2*t^13 - 2*t^12 - 2*t^11 - 2*t^10 - 2*t^9 - 2*t^8 - 2*t^7 - 2*t^6 - 2*t^5 - 2*t^4 - 2*t^3 - 2*t^2 - 2*t + 1).
From G. C. Greubel, Jan 17 2023: (Start)
a(n) = 2*Sum_{j=1..15} a(n-j) - 3*a(n-16).
G.f.: (1+x)*(1-x^16)/(1 - 3*x + 5*x^16 - 3*x^17). (End)

A203378 T(n,k)=Number of (n+1)X(k+1) 0..1 arrays with every 2X2 subblock having equal diagonal elements or equal antidiagonal elements.

Original entry on oeis.org

12, 36, 36, 108, 164, 108, 324, 748, 748, 324, 972, 3412, 5208, 3412, 972, 2916, 15564, 36300, 36300, 15564, 2916, 8748, 70996, 253068, 387324, 253068, 70996, 8748, 26244, 323852, 1764360, 4136292, 4136292, 1764360, 323852, 26244, 78732, 1477268

Offset: 1

R. H. Hardin Dec 31 2011

Table starts
....12......36......108........324..........972...........2916.............8748
....36.....164......748.......3412........15564..........70996...........323852
...108.....748.....5208......36300.......253068........1764360.........12301020
...324....3412....36300.....387324......4136292.......44183028........471988172
...972...15564...253068....4136292.....67731264.....1109832180......18189909480
..2916...70996..1764360...44183028...1109832180....27913330472.....702420750924
..8748..323852.12301020..471988172..18189909480...702420750924...27149753088792
.26244.1477268.85762188.5042151644.298154846436.17679917387404.1049837466171436

			Some solutions for n=4 k=3
..0..0..1..0....1..0..1..1....1..1..0..0....1..1..1..1....1..0..0..0
..0..1..1..1....0..1..1..0....1..1..1..0....1..1..0..1....0..1..0..0
..1..0..1..1....0..0..1..1....1..0..1..1....0..1..1..1....1..0..1..0
..1..1..0..1....1..0..0..1....0..1..1..1....1..1..0..1....1..1..1..1
..1..1..1..1....0..1..0..0....0..0..1..1....1..0..0..0....1..1..0..1

R. H. Hardin, Table of n, a(n) for n = 1..420

Column 1 is A003946(n+1)

Column 2 is A147722(n+2)

A265583 Array T(n,k) = k*(k-1)^(n-1) read by ascending antidiagonals; k,n >= 1.

Original entry on oeis.org

1, 0, 2, 0, 2, 3, 0, 2, 6, 4, 0, 2, 12, 12, 5, 0, 2, 24, 36, 20, 6, 0, 2, 48, 108, 80, 30, 7, 0, 2, 96, 324, 320, 150, 42, 8, 0, 2, 192, 972, 1280, 750, 252, 56, 9, 0, 2, 384, 2916, 5120, 3750, 1512, 392, 72, 10, 0, 2, 768, 8748, 20480, 18750, 9072, 2744, 576, 90, 11

Offset: 1

R. J. Mathar, Dec 10 2015

T(n,k) is the number of n-letter words in a k-letter alphabet with no adjacent letters the same. The factor k represents the number of choices of the first letter, and the n-1 times repeated factor k-1 represents the choices of the next n-1 letters avoiding their predecessor.

The antidiagonal sums are s(d) = 1, 2, 5, 12, 31, 88, 275, 942, 3513, 14158, 61241, 282632, .. for d = n+k >= 2.

			      1       2       3       4       5       6       7
      0       2       6      12      20      30      42
      0       2      12      36      80     150     252
      0       2      24     108     320     750    1512
      0       2      48     324    1280    3750    9072
      0       2      96     972    5120   18750   54432
      0       2     192    2916   20480   93750  326592
T(3,3)=12 counts aba, abc, aca, acb, bab, bac, bca, bcb, cab, cac, cba, cbc. Words like aab or cbb are not counted.

Robert Israel, Table of n, a(n) for n = 1..10011(first 141 antidiagonals, flattened)

Cf. A007283 (column 3), A003946 (column 4), A003947 (column 5), A002378 (row 2), A011379 (row 3), A179824 (row 4), A055897 (diagonal), A265584.

T:= function(n,k)
    if (n=1 and k=1) then return 1;
    else return k*(k-1)^(n-k-1);
    fi;
  end;
Flat(List([2..15], n-> List([1..n-1], k-> T(n,k) ))); # G. C. Greubel, Aug 10 2019

T:= func< n,k | (n eq 1 and k eq 1) select 1 else k*(k-1)^(n-k-1) >;
[T(n,k): k in [1..n-1], n in [2..15]]; // G. C. Greubel, Aug 10 2019

A265583 := proc(n,k)
    k*(k-1)^(n-1) ;
end proc:
seq(seq( A265583(d-k,k),k=1..d-1),d=2..13) ;

T[1,1] = 1; T[n_, k_] := If[k==1, 0, k*(k-1)^(n-1)]; Table[T[n-k,k], {n,2,12}, {k,1,n-1}] // Flatten (* Amiram Eldar, Dec 13 2018 *)

T(n,k) = if(n==k==1, 1, k*(k-1)^(n-k-1) );
for(n=2,15, for(k=1,n-1, print1(T(n,k), ", "))) \\ G. C. Greubel, Aug 10 2019

def T(n, k):
    if (n==k==1): return 1
    else: return k*(k-1)^(n-k-1)
[[T(n, k) for k in (1..n-1)] for n in (2..15)] # G. C. Greubel, Aug 10 2019

T(n,k) = k*A051129(n-1,k-1) = k*A003992(k-1,n-1).
G.f. for column k: k*x/(1-(k-1)*x). - R. J. Mathar, Dec 12 2015
G.f. for array: y/(y-1) - (1+1/x)*y*LerchPhi(y,1,-1/x). - Robert Israel, Dec 13 2018

cp's OEIS Frontend

A275131 T(n,k)=Number of nXk 0..2 arrays with no element equal to any value at offset (-2,-2) (-1,0) or (-1,1) and new values introduced in order 0..2.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

A274895 T(n,k)=Number of nXk 0..2 arrays with no element equal to any value at offset (0,-1) (-1,-1) or (-2,0) and new values introduced in order 0..2.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

A183362 T(n,k)=One quarter the number of nXk 1..4 arrays with no two neighbors of any element equal to each other.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A209019 T(n,k)=Number of nXk 0..3 arrays with no element equal the average of immediate neighbors vertically above, diagonally above and left, and horizontally left of it.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A209047 T(n,k)=Number of nXk 0..3 arrays with no element equal the average of immediate neighbors vertically above and horizontally left of it.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A287839 Number of words of length n over the alphabet {0,1,...,10} such that no two consecutive terms have distance 9.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Python

Formula

A052156 Number of compositions of n into 2*j-1 kinds of j's for all j>=1.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A167882 Number of reduced words of length n in Coxeter group on 4 generators S_i with relations (S_i)^2 = (S_i S_j)^16 = I.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Magma

Mathematica