Rob Arthan - cp's OEIS frontend

A247943 2-dimensional array T(n, k) listed by antidiagonals giving the number of acyclic paths in the graph G(n, k) whose vertices are the integer lattice points (p, q) with 0 <= p < n and 0 <= q < k and with an edge between v and w iff the line segment [v, w] contains no other integer lattice points.

0, 2, 2, 6, 60, 6, 12, 1058, 1058, 12, 20, 25080, 140240, 25080, 20, 30, 822594, 58673472, 58673472, 822594, 30, 42, 36195620, 28938943114, 490225231968, 28938943114, 36195620, 42, 56, 2069486450

Offset: 1

Rob Arthan, Sep 27 2014

There is an edge between v = (p, q) and w = (r, s) iff p - r and q - s are coprime.
G(3, 3) is used for Android screen lock security patterns (see StackExchange link).
The nonzero entries on the diagonal of this sequence comprise the row sums of A247944.

			G(2,2) is the complete graph on 4 vertices, hence T(2, 2) = 4*3 + 4*3*2 + 4*3*2*1 = 60.
T(n, k) for n + k <= 8 is as follows:
.0........2...........6...........12..........20.......30..42
.2.......60........1058........25080......822594.36195620
.6.....1058......140240.....58673472.28938943114
12....25080....58673472.490225231968
20...822594.28938943114
30.36195620
42

StackExchange, Combination of smartphones' pattern password, 2014

Cf. A247944.

A247944 2-dimensional array T(n, k) listed by antidiagonals for n >= 2, k >= 1 giving the number of acyclic paths of length k in the graph G(n) whose vertices are the integer lattice points (p, q) with 0 <= p, q < n and with an edge between v and w iff the line segment [v, w] contains no other integer lattice points.

Original entry on oeis.org

12, 24, 56, 24, 304, 172, 0, 1400, 1696, 400, 0, 5328, 15580, 6072, 836, 0, 16032, 132264, 88320, 18608, 1496, 0, 35328, 1029232, 1225840, 403156, 44520, 2564, 0, 49536, 7286016, 16202952, 8471480, 1296952, 100264, 4080, 0, 32256, 46456296, 203422072, 172543276, 36960168, 3864332, 201992, 6212

Offset: 2

Rob Arthan, Sep 27 2014

G(3) is used for Android screen lock security patterns (see StackExchange link).
There is an edge between v = (p, q) and w = (r, s) iff p - r and q - s are coprime.
T(n, k) is nonzero for 1 <= k < n^2 and is zero for k >= n^2, because G(n) always has an acyclic path that contains all n^2 vertices and hence has length n^2 - 1, while a path in G(n) of length n^2 or more cannot be acyclic.
The row sums of this sequence form the nonzero entries on the diagonal of A247943.

			In G(3), the 4 vertices at the corners have valency 5, the vertex in the middle has valency 8 and the other 4 vertices have valency 7, therefore T(3, 2) = 4*5*4 + 8*7 + 4*7*6 = 304.
T(n, k) for n + k <= 11 is as follows:
..12.....24......24........0.........0.........0........0.....0.0
..56....304....1400.....5328.....16032.....35328....49536.32256
.172...1696...15580...132264...1029232...7286016.46456296
.400...6072...88320..1225840..16202952.203422072
.836..18608..403156..8471480.172543276
1496..44520.1296952.36960168
2564.100264.3864332
4080.201992
6212
T(4, k) is nonzero iff k <= 15 and the 15 nonzero values are: 172, 1696, 15580, 132264, 1029232, 7286016, 46456296, 263427744, 1307755352, 5567398192, 19756296608, 56073026336, 119255537392, 168794504832, 119152364256. The sum of these 15 values is A247943(4, 4). - _Rob Arthan_, Oct 19 2014

StackExchange, Combination of smartphones' pattern password, 2014.

Cf. A247943.

A088803 a(n) gives the number of steps taken in a process which manipulates piles of tokens arranged in a line. There are 2n (or 2n+1) tokens in all. Initially they are all in one pile. At each step every pile with more than 1 token is divided into two and half the token are added to the pile on the left and half to the pile on the right. If a pile has an odd number of tokens, the token left over stays where it is. The redistributions in each step are done in parallel.

Original entry on oeis.org

1, 3, 7, 11, 17, 25, 33, 41, 53, 65, 77, 93, 109, 123, 143, 163, 181, 203, 227, 249, 277, 303, 329, 357, 389, 417, 451, 485, 517, 555, 593, 629, 669, 711, 749, 795, 839, 883, 931, 981, 1025, 1077, 1131, 1179, 1235, 1293, 1343, 1403, 1465, 1519, 1583, 1649

Offset: 1

Rob Arthan, Oct 17 2003

nonn

			E.g., a(2) = 3 because there are 3 steps in the process beginning with 4 tokens:
0 0 4 0 0
0 2 0 2 0
1 0 2 0 1
1 1 0 1 1

R. Anderson, L. Lovász, P. Shor, J. Spencer, E. Tardos, S. Winograd, Disks, balls and walls: analysis of a combinatorial game, Amer. Math. Monthly, 6, 96, pp. 481-493, 1989.

Cf. A088804.

#include 
#include 
#define N 1000
#define NN (2 * (N / 2) + 1)
void e(int *t, int *T) {
    int i;
    for (i = 0; i < NN; i ++) {
        T[i] += (t[i] % 2); int f = (t[i] / 2);
        if (f) { T[i - 1] += f; T[i + 1] += f; }
    }
}
int f(int n) {
    int t[NN], T[NN], i = 0;
    memset(t, 0, sizeof(t)); memset(T, 0, sizeof(T));
    t[N / 2] = n; e(t, T);
    while (memcmp(t, T, sizeof(t)) != 0) { i ++; memcpy(t, T, sizeof(T)); memset(T, 0, sizeof(T)); e(t, T); }
    return i;
}
int main() { int n; for (n = 2; n <= N; n += 2) { printf("%d, ", f(n)); fflush(stdout); } printf("\n"); }
/* Luc Rousseau, Jun 29 2018 */

The sequence is asymptotically quadratic with a(n) ~= c*n^2, where c is between 0.33 and 0.65, with estimate 0.5973 for n = 10000.

A088804 a(n) gives the number of steps taken in a process which manipulates piles of tokens arranged in a line. There are 2n (or 2n+1) tokens in all. Initially they are all in one pile. At each step, from each pile with more than 1 token, one token is taken and added to the pile on its left and one is taken and added to the pile on its right. The redistributions in each step are done in parallel.

Original entry on oeis.org

1, 4, 8, 14, 21, 29, 39, 51, 63, 77, 93, 110, 128, 148, 170, 192, 216, 242, 268, 296, 326, 358, 390, 424, 460, 496, 534, 574, 615, 657, 701, 747, 793, 841, 891, 941, 993, 1047, 1103, 1159, 1217, 1277, 1337, 1399, 1463, 1529, 1595, 1663, 1733, 1803, 1875, 1949

Offset: 1

Rob Arthan, Oct 17 2003

nonn

			E.g., a(2) = 4 because there are 4 steps in the process beginning with 4 tokens:
0 0 4 0 0
0 1 2 1 0
0 2 0 2 0
1 0 2 0 1
1 1 0 1 1

R. Anderson, L. Lovasz, P. Shor, J. Spencer, E. Tardos, S. Winograd, Disks, balls and walls: analysis of a combinatorial game, Amer. Math. Monthly, 6, 96, pp. 481-493, 1989.
Anders Björner, László Lovászb, Peter W. Shor, Chip-firing games on graphs, European Journal of Combinatorics 12, pp. 283-291, 1991.
Mikkel Thorup, Firing Games

Cf. A088803.

The sequence is asymptotically quadratic with a(n) ~= c*n^2, where c is between 0.33 and 1, with estimate 0.7078 for n = 1, 000.

A079409 Array T(m,n) (m>=0, n>=0) read by antidiagonals: T(0, 0) = 1, T(0, n) = 0 if n > 0, T(m, n) = T(m-1, n - T(m-1, n)) + T(m-1, n - T(m-1, n-1)) if m > 0.

Original entry on oeis.org

1, 1, 0, 1, 1, 0, 1, 2, 0, 0, 1, 1, 1, 0, 0, 1, 2, 3, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 1, 2, 3, 4, 0, 0, 0, 0, 1, 1, 1, 1, 1, 0, 0, 0, 0, 1, 2, 3, 4, 5, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 1, 2, 3, 4, 5, 6, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 1, 2, 3, 4, 5, 6, 7, 0, 0, 0, 0, 0, 0, 0

Offset: 0

Rob Arthan, Jan 06 2003

This two-dimensional array is to Pascal's triangle as the Hofstadter Q-sequence A005185 is to Fibonacci's sequence.

Unlike the Hofstadter Q-sequence, it is very regular and admits a simple closed form: T(m, n) = 0 if n > m, T(m, n) = 1 if n <= m and m - n is even, T(m, n) = n + 1 if n <= m and m - n is odd.

			For 0 <= m <= 6 and 0 <= n <= 6, the array looks like:
1,0,0,0,0,0,0
1,1,0,0,0,0,0
1,2,1,0,0,0,0
1,1,3,1,0,0,0
1,2,1,4,1,0,0
1,1,3,1,5,1,0
1,2,1,4,1,6,1

Cf. A004001, A005185, A007318, A052553, A079408.

A079599 Numbers n for which the n-th impartial game is a second player win.

Original entry on oeis.org

0, 2, 8, 10, 16, 18, 24, 26, 32, 34, 40, 42, 48, 50, 56, 58, 64, 66, 72, 74, 80, 82, 88, 90, 96, 98, 104, 106, 112, 114, 120, 122, 128, 130, 136, 138, 144, 146, 152, 154, 160, 162, 168, 170, 176, 178, 184, 186, 192, 194, 200, 202, 208, 210, 216, 218, 224, 226, 232, 234, 240, 242, 248, 250, 512, 514

Offset: 0

Rob Arthan, Jan 28 2003

nonn

These are the indices n for which A034798(n) = 0.
From Antti Karttunen, Jan 30 2014: (Start)
A236678(a(n)) = n+1 for all n.
Differs from A047467 for the first time at a(64).
Differs from A126002(n+1) for the first time not later than at n=281474976710656 (= 2^48), as:
a((2^48)-1) = a(281474976710655) = 18085043209519168250 < 18446744073709551616 (= 2^64), while
a(2^48) = a(281474976710656) = 36893488147419103232 > 2^64.
(End)

			a(1) = 2 (rather than 1) because 1 = 2^0 = 2^a(0); a(64) = 512 (rather than 256) because 256 = 2^8 = 2^a(2).

J. H. Conway, On numbers and games.

Antti Karttunen, Table of n, a(n) for n = 0..16383
Index entries for sequences which agree for a long time but are different

Characteristic function: A236677, its partial sums: A236678.

Cf. A034798, A034797, A047467, A126002.

(define (A079599 n) (let loop ((n n) (i 0) (j 0) (s 0)) (cond ((zero? n) s) ((odd? n) (loop (/ (- n 1) 2) (+ i 1) (+ j 1 (A236677 j)) (+ s (expt 2 (+ j (A236677 j)))))) (else (loop (/ n 2) (+ i 1) (+ j 1 (A236677 j)) s)))))

a(0) = 0; a(n+1) = least x > a(n) such that the coefficient of 2^a(j) is zero in the binary expansion of x for all j < n+1

Alternatively: rewrite the binary representation of n in such a way that the forbidden bit-positions given by this sequence (with bit-position 0 standing for the least significant bit) are vacated, by shifting the rest of bits one bit left. E.g., bit-positions 0, 2, 8, 10, ... are forbidden, thus we rewrite 1 to 1x = 10 = 2, 2 (in binary 10) to 1x0x = 1000 = 8, 3 (in binary 11) to 1x1x = 1010 = 10, 4 (in binary 100) to 10x0x = 1000 = 16, 64 (in binary 1000000) to 1x00000x0x = 1000000000 = 512, etc. - Antti Karttunen, Jan 30 2014

More terms from Antti Karttunen, Jan 29 2014

A064034 2-dimensional table T(i, j) defined for any integers i and j, read by antidiagonals in the southeast quadrant. T(i, j) gives the "Fibonacci depth" of (i, j): form the Fibonacci sequence starting with i, j: w(0) = i, w(1) = j, w(n) = w(n-1) + w(n-2). It can be shown that for all but finitely many n, the w(n) have the same sign, i.e., are all positive, all negative or all zero. T(i, j), is the smallest number of iterations required to find out which of these cases holds.

Original entry on oeis.org

0, 1, 2, 1, 3, 2, 1, 1, 4, 2, 1, 1, 3, 2, 2, 1, 1, 1, 5, 2, 2, 1, 1, 1, 3, 4, 2, 2, 1, 1, 1, 1, 3, 2, 2, 2, 1, 1, 1, 1, 3, 6, 2, 2, 2, 1, 1, 1, 1, 1, 3, 4, 2, 2, 2, 1, 1, 1, 1, 1, 3, 5, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 3, 4, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 3, 3, 4, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 3, 7, 2, 2, 2, 2, 2

Offset: 0

Rob Arthan, Sep 18 2001

I.e. T(i, j) is the smallest n such that w(n) and w(n+1) have the same sign. T(i, j) is zero if i and j have the same sign and T(-i, -j) = T(i, j), so the values tabulated are T(i, -j) = T(-i, j) for 0 <= i, j.

The fact that the T(i, j) and related sequences are well-defined for all i and j can be used to construct dense subrings of the real numbers on the basis of integer arithmetic alone (i.e., without first constructing the real numbers or even the rational numbers). See the first reference.

			T(2, -1) = 4 because the generalized Fibonacci sequence 2 -1 1 0 1 1 requires 4 iterations before two consecutive values with the same sign occur.

R. D. Arthan. An Irrational Construction of R from Z. In Theorem Proving in Higher Order Logics, R. J. Boulton and P.B. Jackson Editors LNCS 2152. Springer Verlag, 2001.

R. D. Arthan An Irrational Construction of R from Z

Cf. A000045.

A063090 a(n)/(n*n!) is the average number of comparisons needed to find a node in a binary search tree containing n nodes inserted in a random order.

Original entry on oeis.org

1, 6, 34, 212, 1488, 11736, 103248, 1004832, 10733760, 124966080, 1575797760, 21403457280, 311623441920, 4842481190400, 80007869491200, 1400671686758400, 25902542427955200, 504597366114508800, 10328835149402112000

Offset: 1

Rob Arthan, Aug 06 2001

a(n) is the sum over all permutations, p, of {1, ..., n} of the number of comparisons required to find all the entries in the tree formed when the order of insertion is p(1), p(2), ... p(n). To derive the formula given, first group the trees according to the value of k = p(1). For a given k, p determines a permutation of {1, ..., k-1} that gives the structure of the left subtree. By symmetry, the contribution of the right subtrees will be the same as the left subtrees. Now count and simplify.

a(n) mod n is n-2 or 0 depending on whether n is prime or not. - Gary Detlefs, May 28 2012

D. E. Knuth, The Art of Computer Programming. Addison-Wesley, Reading, MA, Vol. 3, p. 427, C(n).

T. D. Noe, Table of n, a(n) for n = 1..100
Eric Weisstein's World of Mathematics, Quicksort.

Cf. A000108, A067699, A093418, A096620, A115107, A288964, A288965, A288970, A288971.

[Factorial(n)*((2*n+2)*HarmonicNumber(n) - 3*n): n in [1..30]]; // G. C. Greubel, Sep 01 2018

A[1]:= 1:
for n from 2 to 30 do A[n]:= (2*n-1)*(n-1)!+(n+1)*A[n-1] od:
seq(A[n],n=1..30); # Robert Israel, Sep 21 2014

a[n_] := n!*((2*n+2)*HarmonicNumber[n] - 3*n); Table[a[n], {n, 1, 20}] (* Jean-François Alcover, Sep 20 2012, after Gary Detlefs *)

{h(n) = sum(k=1,n, 1/k)};
for(n=1,30, print1(n!*(2*(n+1)*h(n) - 3*n), ", ")) \\ G. C. Greubel, Sep 01 2018

a(1) = 1, a(n) = n*n! + 2 * Sum_{k=1}^{n-1} (n-1)!/k! * a(k).
a(n) = (2*n - 1)*(n - 1)! + (n + 1)*a(n-1).
E.g.f.: -(x+2*log(1-x))/(1-x)^2. - Vladeta Jovovic, Sep 15 2003
a(n) = Sum_{k=0..n} |Stirling1(n, k)|*A000337(k). - Vladeta Jovovic, Jul 06 2004
a(n) = 2*(n+1)*abs(Stirling1(n+1, 2))-3*n*n!. - Vladeta Jovovic, Jul 06 2004
a(n) = n!*((2*n+2)*h(n) - 3*n), where h(n) is the n-th harmonic number. - Gary Detlefs, May 28 2012
a(n) = A288964(n) + n!*n (because this sequence and A288964 have the same definition related to quicksort but under slightly different assumptions). - Petros Hadjicostas, May 03 2020

More terms from Vladeta Jovovic, Aug 08 2001

Missing brackets in the formula in the name inserted by Rob Arthan, Sep 21 2014

A079408 Array T(m,n) (m>=0, n>=0) read by antidiagonals: T(0, 0) = 1, T(0, n) = 0 if n != 0, T(m, n) = T(m-1, T(m-1, n)) + T(m-1, n - T(m-1, n-1)) if m > 0.

Original entry on oeis.org

1, 1, 0, 3, 2, 0, 6, 2, 1, 0, 12, 6, 3, 1, 0, 24, 12, 6, 3, 1, 0, 48, 24, 12, 6, 3, 1, 0, 96, 48, 24, 12, 5, 3, 1, 0, 192, 96, 48, 24, 12, 6, 3, 1, 0, 384, 192, 96, 48, 24, 12, 6, 3, 1, 0, 768, 384, 192, 96, 48, 24, 12, 6, 3, 1, 0, 1536, 768, 384, 192, 96, 48, 24, 12, 6, 3, 1, 0, 3072, 1536

Offset: 0

Rob Arthan, Jan 06 2003

This two-dimensional array is to Pascal's triangle as sequence A004001 is to Fibonacci's sequence. The sequence gives the values for nonnegative n read by antidiagonals. For negative n, T(0, n) = 0 and T(m, n) = T(m, 0) for m > 0.

Unlike A004001 this sequence admits a simple closed form: T(1, n) = 1 if n != 1, T(1, 1) = 2, T(m, n) = 3*2^(m-2) if m > 1, n != 3*2^(m-2) - 2, T(m, 3*2^(m-2) - 2) = 3*2^(m-2) - 1 if m > 1.

			For 0 <= m <= 3 and 0 <= n <= 5, the array of values looks like:
1,0,0,0,0,0,0
1,2,1,1,1,1,1
3,2,3,3,3,3,3
6,6,6,6,5,6,6

Cf. A004001, A005185, A007318, A052553, A079409.

A053440 Number of k-simplices in the first derived complex of the standard triangulation of an n-simplex. Equivalently, T(n,k) is the number of ascending chains of length k+1 of nonempty subsets of the set {1, 2, ..., n+1}.

Original entry on oeis.org

1, 3, 2, 7, 12, 6, 15, 50, 60, 24, 31, 180, 390, 360, 120, 63, 602, 2100, 3360, 2520, 720, 127, 1932, 10206, 25200, 31920, 20160, 5040, 255, 6050, 46620, 166824, 317520, 332640, 181440, 40320, 511, 18660, 204630, 1020600, 2739240, 4233600, 3780000, 1814400, 362880

Offset: 0

Rob Arthan, Jan 12 2000

T(n,k) is the number of length k+1 sequences of nonempty mutually disjoint subsets of {1,2,...,n+1}. The e.g.f. for the column corresponding to k is exp(x)*(exp(x)-1)^(k+1). - Geoffrey Critzer, Dec 20 2011

			T(2,1) = 12 because there are 12 such length 2 sequences of subsets of {1,2,3}: ({1},{2}), ({1},{3}), ({2},{3}), ({1},{2,3}), ({2},{1,3}), ({3},{1,2}) with two orderings for each. - _Geoffrey Critzer_, Dec 20 2011
Triangle begins:
   1
   3      2
   7     12      6
  15     50     60     24
  31    180    390    360    120

G. C. Greubel, Table of n, a(n) for the first 50 rows, flattened
F. Brenti and V. Welker, f-vectors of barycentric subdivisions Math. Z., 259(4), 849-865, 2008.
Wikipedia, Barycentric subdivision

Other versions are A028246, A142071.
Columns k=0..1 are A000225(n+1), A028243(n+2).
Cf. A000142 (main diagonal), A002050 (row sums), A019538.

a := (n, k) -> (k+1)!*Stirling2(n+2, k+2):
seq(print(seq(a(n, k), k = 0..n)), n = 0..10);

nn = 5; a = Exp[ x] - 1 ; f[list_] := Select[list, # > 0 &];Map[f, Transpose[Table[Drop[Range[0, nn]!CoefficientList[Series[a^k  Exp[x], {x, 0, nn}],x], 1], {k, 1, 5}]]] // Grid (* Geoffrey Critzer, Dec 20 2011 *)
Table[(k+1)!*StirlingS2[n+2,k+2], {n,0,10}, {k,0,n}]//Flatten (* G. C. Greubel, Nov 19 2017 *)

for(n=0,10, for(k=0,n, print1((k+1)!*stirling(n+2,k+2,2), ", "))) \\ G. C. Greubel, Nov 19 2017

T(0,k) = delta(0,k), T(n,k) = delta(0,k) + (k+1)(T(n-1,k-1) + (k+2)T(n-1,k)).
E.g.f.: exp(x)*(exp(x)-1)/(1-y*(exp(x)-1)). - Vladeta Jovovic, Apr 13 2003
T(n,k) = Sum_{i = 0..n} binomial(n+1,i+1)*(k+1)!*Stirling2(i+1,k+1) = (k+1)!*Stirling2(n+2,k+2) (Brenti and Welker). - Peter Bala, Jul 12 2014
T(n,k) = (k+1)!*Stirling2(n+2, k+2). - G. C. Greubel, Nov 19 2017

More terms from James Sellers, Jan 14 2000

cp's OEIS Frontend

User: Rob Arthan

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

C

Formula

Views

Author

Keywords

Examples

Links

Crossrefs

Formula

A079409 Array T(m,n) (m>=0, n>=0) read by antidiagonals: T(0, 0) = 1, T(0, n) = 0 if n > 0, T(m, n) = T(m-1, n - T(m-1, n)) + T(m-1, n - T(m-1, n-1)) if m > 0.

Views

Author

Keywords

Comments

Examples

Crossrefs

A079599 Numbers n for which the n-th impartial game is a second player win.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Scheme

Formula

Extensions

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

A063090 a(n)/(n*n!) is the average number of comparisons needed to find a node in a binary search tree containing n nodes inserted in a random order.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

Formula

Extensions

A079408 Array T(m,n) (m>=0, n>=0) read by antidiagonals: T(0, 0) = 1, T(0, n) = 0 if n != 0, T(m, n) = T(m-1, T(m-1, n)) + T(m-1, n - T(m-1, n-1)) if m > 0.

Views

Author

Keywords

Comments