Shel Kaphan - cp's OEIS frontend

A370469 Triangle read by columns where T(n,k) is the number of points in Z^n such that |x1| + ... + |xn| = k, |x1|, ..., |xn| > 0.

2, 2, 4, 2, 8, 8, 2, 12, 24, 16, 2, 16, 48, 64, 32, 2, 20, 80, 160, 160, 64, 2, 24, 120, 320, 480, 384, 128, 2, 28, 168, 560, 1120, 1344, 896, 256, 2, 32, 224, 896, 2240, 3584, 3584, 2048, 512, 2, 36, 288, 1344, 4032, 8064, 10752, 9216, 4608, 1024

Offset: 1

Shel Kaphan, Mar 30 2024

T(n,k) is the number of points on the n-dimensional cross polytope with facets at distance k from the origin which have no coordinate equal to 0.
T(n,n) = 2^n. The (n-1)-dimensional simplex at distance n from the origin in Z^n has exactly 1 point with no zero coordinates, at (1,1,...,1). There are 2^n (n-1)-dimensional simplexes at distance n from the origin as part of the cross polytope in Z^n. (The lower dimensional facets do not count as they have at least one 0 coordinate.)
T(2*n,3*n) = T(2*n+1,3*n), and this is A036909.

			 n\k 1 2 3  4  5   6   7    8    9    10    11    12     13     14      15
   -----------------------------------------------------------------------
 1 | 2 2 2  2  2   2   2    2    2     2     2     2      2      2       2
 2 |   4 8 12 16  20  24   28   32    36    40    44     48     52      56
 3 |     8 24 48  80 120  168  224   288   360   440    528    624     728
 4 |       16 64 160 320  560  896  1344  1920  2640   3520   4576    5824
 5 |          32 160 480 1120 2240  4032  6720 10560  15840  22880   32032
 6 |              64 384 1344 3584  8064 16128 29568  50688  82368  128128
 7 |                 128  896 3584 10752 26880 59136 118272 219648  384384
 8 |                      256 2048  9216 30720 84480 202752 439296  878592
 9 |                           512  4608 23040 84480 253440 658944 1537536
10 |                                1024 10240 56320 225280 732160 2050048
11 |                                      2048 22528 135168 585728 2050048
12 |                                            4096  49152 319488 1490944
13 |                                                   8192 106496  745472
14 |                                                         16384  229376
15 |                                                                 32768
The cross polytope in Z^3 (the octahedron) with points at distance 3 from the origin has 8 triangle facets, each with edge length 4. There is one point in the center of each triangle with coordinates (+-1,+-1,+-1).

Cf. A033996, A333714 (n=3)
Cf. A102860 (n=4).
Cf. A036289, A097064, A134401 (+1-diagonal).
Cf. A001815 (+2-diagonal).
Cf. A371064.
Cf. A036909.
2 * A013609.

T[n_,k_]:=Binomial[k-1,n-1]*2^n; Table[T[n,k],{k,10},{n,k}]//Flatten

from math import comb
def A370469_T(n,k): return comb(k-1,n-1)<Chai Wah Wu, Apr 25 2024

T(n,k) = binomial(k-1,n-1)*2^n.

G.f.: 2*x*y/(1 - y - 2*x*y). - Stefano Spezia, Apr 27 2024

A371568 Array read by ascending antidiagonals: A(n, k) is the number of paths of length k in Z^n from the origin to points such that x1+x2+...+xn = k with x1,...,xn > 0.

Original entry on oeis.org

1, 0, 1, 0, 2, 1, 0, 0, 6, 1, 0, 0, 6, 14, 1, 0, 0, 0, 36, 30, 1, 0, 0, 0, 24, 150, 62, 1, 0, 0, 0, 0, 240, 540, 126, 1, 0, 0, 0, 0, 120, 1560, 1806, 254, 1, 0, 0, 0, 0, 1800, 8400, 5796, 510, 1

Offset: 1

Shel Kaphan, Mar 28 2024

T(n, k) can also be seen as the number of ordered partitions of k items into n nonempty buckets.
T(n, n) = n!, which is readily seen because to go from the origin to a point in Z^n a distance n away, with at least one step taken in each dimension, the first step can be in any of n dimensions, the second step in any of n-1 dimensions, and so on.
This array is the image of Pascal's triangle A007318 under the Akiyama-Tanigawa transformation. See the Python program. - Peter Luschny, Apr 19 2024

			 n\k 1 2 3  4   5    6     7      8       9       10
  --------------------------------------------------
 1|  1 1 1  1   1    1     1      1       1        1
 2|  0 2 6 14  30   62   126    254     510     1022
 3|  0 0 6 36 150  540  1806   5796   18150    55980
 4|  0 0 0 24 240 1560  8400  40824  186480   818520
 5|  0 0 0  0 120 1800 16800 126000  834120  5103000
 6|  0 0 0  0   0  720 15120 191520 1905120 16435440
 7|  0 0 0  0   0    0  5040 141120 2328480 29635200
 8|  0 0 0  0   0    0     0  40320 1451520 30240000
 9|  0 0 0  0   0    0     0      0  362880 16329600
10|  0 0 0  0   0    0     0      0       0  3628800

Cf. A000918 (n=2), A001117 (n=3), A000919 (n=4), A001118 (n=5), A000920 (n=6).
Cf. A135456 (n=7), A133068 (n=8), A133360 (n=9), A133132 (n=10).
Cf. A371064, A007318.
See A019538 and A131689 for other versions.

A[n_,k_] := Sum[(-1)^(n-i) * i^k * Binomial[n,i], {i,1,n}]

# The Akiyama-Tanigawa algorithm for the binomial generates the rows.
# Adds row(0) = 0^k and column(0) = 0^n.
from math import comb as binomial
def ATBinomial(n, len):
    A = [0] * len
    R = [0] * len
    for k in range(len):
        R[k] = binomial(k, n)
        for j in range(k, 0, -1):
            R[j - 1] = j * (R[j] - R[j - 1])
        A[k] = R[0]
    return A
for n in range(11): print([n], ATBinomial(n, 11))  # Peter Luschny, Apr 19 2024

A(n,k) = Sum_{i=1..n} (-1)^(n-i) * binomial(n,i) * i^k

A371064 Array read by ascending antidiagonals where T(n,k) is the number of paths of length k from the origin to a facet of the cross polytope of size k in Z^n.

Original entry on oeis.org

2, 4, 2, 6, 12, 2, 8, 30, 28, 2, 10, 56, 126, 60, 2, 12, 90, 344, 462, 124, 2, 14, 132, 730, 1880, 1566, 252, 2, 16, 182, 1332, 5370, 9368, 5070, 508, 2, 18, 240, 2198, 12372, 36250, 43736, 15966, 1020, 2, 20, 306, 3376, 24710, 106452, 228090, 195224, 49422, 2044, 2

Offset: 1

Shel Kaphan, Mar 09 2024

In the cross polytope of dimension n, each facet of dimension i-1 (i=1..n) has i^k paths of length k from the origin to its surface, and there are binomial(n,i)*2^i such facets. To avoid double counting, an alternating sum is used to add up the paths to all the facets.

			distance
 k      1   2    3      4       5        6         7          8
dims ----------------------------------------------------------
 n 1 |  2   2    2      2       2        2         2          2
   2 |  4  12   28     60     124      252       508       1020
   3 |  6  30  126    462    1566     5070     15966      49422
   4 |  8  56  344   1880    9368    43736    195224     844760
   5 | 10  90  730   5370   36250   228090   1359130    7771770
   6 | 12 132 1332  12372  106452   856212   6505812   47189652
   7 | 14 182 2198  24710  259574  2562182  23928758  213041990
   8 | 16 240 3376  44592  554416  6511920  72592816  772172592

Columns: A002939 (k=2).

Rows: A028399 (n=2), A366058 (n=3).

T(n,k) = Sum_{i=1..n} (-1)^(n-i) * binomial(n,i) * 2^i * i^k.

A361364 Number of 5-dimensional cubic lattice walks that start and end at origin after 2n steps, not touching origin at intermediate stages.

Original entry on oeis.org

1, 10, 170, 6500, 332050, 19784060, 1296395700, 90616189800, 6637652225250, 503852804991500, 39337349077483420, 3142010167321271000, 255747325678297576100, 21150729618673827139000, 1773152567858996728205000, 150409554094012703302602000, 12890454660664800562838261250

Offset: 0

Shel Kaphan, Mar 09 2023

In Novak's note it is mentioned that if P(z) and Q(z) are the g.f.s for the probabilities of indecomposable and decomposable loops, respectively, that P(z) = 1 - 1/Q(z). This works equally well using loop counts rather than probabilities. The g.f.s may be expressed by the series constructed from the sequences of counts of loops of length 2*n. Q(z) for the 5-d case is the series corresponding to A287317.
To satisfy this g.f. equation, a(0) should be 0, but we give it as 1 since there is one trivial loop of 0 steps, and for consistency with related sequences.
To obtain the probability of returning to the point of origin for the first time after 2*n steps, divide a(n) by the total number of walks of length 2*n in d dimensions: (2*d)^(2*n) = 100^n.

Alois P. Heinz, Table of n, a(n) for n = 0..503
Jonathan Novak, Pólya's Random Walk Theorem.

Cf. A287317, A039699 (number of walks that return to the origin in 2n steps).
Number of walks that return to the origin for the first time in 2n steps, in 1..4 dimensions: |A002420|, A054474, A049037, A359801.
Column k=5 of A361397.
Cf. A169714.

walk5d[n_] :=
 Sum[(2 n)!/(i! j! k! l! (n - i - j - k - l)!)^2, {i, 0, n}, {j, 0,
   n - i}, {k, 0, n - i - j}, {l, 0, n - i - j - k}]; invertSeq[seq_] :=
 CoefficientList[1 - 1/SeriesData[x, 0, seq, 0, Length[seq], 1], x]; invertSeq[Table[walk5d[n], {n, 0, 15}]]

G.f.: 2 - 1/Integral_{t=0..oo} exp(-t)*BesselI(0,2*t*sqrt(x))^5 dt.

INVERTi transform of A169714.

A359801 Number of 4-dimensional cubic lattice walks that start and end at origin after 2n steps, not touching origin at intermediate stages.

Original entry on oeis.org

1, 8, 104, 2944, 108136, 4525888, 204981888, 9792786432, 486323201640, 24874892400064, 1302278744460352, 69474942954714112, 3764568243058030208, 206675027529594291200, 11473858525271117889536, 643154944963894079717376, 36355546411928157876528744, 2070313613815122857027563200

Offset: 0

Shel Kaphan, Mar 08 2023

In Novak's note it is mentioned that if P(z) and Q(z) are the g.f.s for the probabilities of indecomposable and decomposable loops, respectively, that P(z) = 1 - 1/Q(z). This works equally well using loop counts rather than probabilities. The g.f.s may be expressed by the series constructed from the sequences of counts of loops of length 2*n. Q(z) for the 4-d case is the series corresponding to A039699.

To obtain the probability of returning to the point of origin for the first time after 2*n steps, divide a(n) by the total number of walks of length 2*n in d dimensions: (2*d)^(2*n) = 64^n.

Vaclav Kotesovec, Table of n, a(n) for n = 0..550
Dorin Dumitraşcu and Liviu Suciu, Asymptotics for the Number of Random Walks in the Euclidean Lattice, arXiv:2212.01702 [math.CO], 2022, p.11.
Jonathan Novak, Pólya's Random Walk Theorem, The American Mathematical Monthly, Vol. 121, No. 8 (October 2014), pp. 711-716.

Cf. A039699, A287317 (number of walks that return to the origin in 2n steps).
Number of walks that return to the origin for the first time in 2n steps, in 1..3 dimensions: |A002420|, A054474, A049037.
Column k=4 of A361397.

walk4d[n_] :=
 Sum[(2 n)!/(i! j! k! (n - i - j - k)!)^2, {i, 0, n}, {j, 0,
   n - i}, {k, 0, n - i - j}]; invertSeq[seq_] :=
  CoefficientList[1 - 1/SeriesData[x, 0, seq, 0, Length[seq], 1], x]; invertSeq[Table[walk4d[n], {n, 0, 17}]]

seq(n) = {my(v=Vec(2 - 1/serlaplace(besseli(0, 2*x + O(x^(2*n+1)))^4))); vector(n+1, i, v[2*i-1])} \\ Andrew Howroyd, Mar 08 2023

G.f.: 2 - 1/Q(x) where Q(x) is the g.f. of A039699.
G.f.: 2 - 1/Integral_{t=0..oo} exp(-t)*BesselI(0,2*t*sqrt(x))^4 dt.
INVERTi transform of A039699.

A190952 Largest integer k for which exp(k) < k^n, n>=3.

Original entry on oeis.org

4, 8, 12, 16, 21, 26, 30, 35, 40, 45, 51, 56, 61, 67, 72, 78, 84, 89, 95, 101, 107, 113, 119, 125, 131, 137, 144, 150, 156, 163, 169, 175, 182, 188, 195, 201, 208, 214, 221, 228, 234, 241, 248, 254, 261, 268, 275, 282, 288, 295, 302, 309, 316, 323, 330, 337, 344, 351

Offset: 3

Shel Kaphan, May 24 2011

nonn

n=3 is the starting index because exp(x)>x^n for all x>=0 when n=1,2.

Conjecture: There are floor((n+1)/log(n+1))-2 terms less than or equal to n. - Benedict W. J. Irwin, Jun 15 2016

Cf. A088346 (Smallest integer k where exp(x)>x^n for all x>=k)

Cf. A190951 (Closest integer to the largest real x such that exp(x) = x^n)

a[n_] := Floor[E^-ProductLog[-1, -1/n]]; Table[a[n], {n, 3, 60}]

Conjecture: G.f.: Sum_{ j>=1 } (Sum_{ k>=1 } x^(j+floor((k+1)/log(k+1)))) + x^j. - Benedict W. J. Irwin, Jun 15 2016

a(n) = floor(-n*LambertW(-1,-1/n)). - Vaclav Kotesovec, Jun 29 2016

A190951 Closest integer to the largest real number x such that exp(x) = x^n, for n>=3.

Original entry on oeis.org

5, 9, 13, 17, 21, 26, 31, 36, 41, 46, 51, 56, 62, 67, 73, 79, 84, 90, 96, 102, 108, 114, 120, 126, 132, 138, 144, 150, 157, 163, 169, 176, 182, 189, 195, 202, 208, 215, 221, 228, 235, 241, 248, 255, 262, 268, 275, 282, 289, 296, 303, 310, 317, 324, 331, 338, 345, 352

Offset: 3

Shel Kaphan, May 23 2011

nonn

n=3 is the starting index because exp(x) > x^n for all x>=0 when n=1,2.

Cf. A088346 (Smallest integer k where exp(x)>x^n for all x>=k).

Cf. A190952 (Largest integer k for which exp(k) < k^n).

a[n_] := Round[ E^-ProductLog[-1, -1/n]]; Table[a[n], {n, 3, 60}]

A000374 Number of cycles (mod n) under doubling map.

Original entry on oeis.org

1, 1, 2, 1, 2, 2, 3, 1, 3, 2, 2, 2, 2, 3, 5, 1, 3, 3, 2, 2, 6, 2, 3, 2, 3, 2, 4, 3, 2, 5, 7, 1, 5, 3, 6, 3, 2, 2, 5, 2, 3, 6, 4, 2, 8, 3, 3, 2, 5, 3, 8, 2, 2, 4, 5, 3, 5, 2, 2, 5, 2, 7, 13, 1, 7, 5, 2, 3, 6, 6, 3, 3, 9, 2, 8, 2, 6, 5, 3, 2, 5, 3, 2, 6, 12, 4, 5, 2, 9, 8, 10, 3, 14, 3, 5, 2, 3, 5, 8, 3

Offset: 1

Shel Kaphan

nonn

Number of cycles of the function f(x) = 2x mod n. Number of irreducible factors in the factorization of the polynomial x^n-1 over GF(2). - T. D. Noe, Apr 16 2003

			a(14) = 3 because (1) the function 2x mod 14 has the three cycles (0),(2,4,8),(6,12,10) and (2) the factorization of x^14-1 over integers mod 2 is (1+x)^2 (1+x+x^3)^2 (1+x^2+x^3)^2, which has three unique factors. Note that the length of the cycles is the same as the degree of the factors.

R. Lidl and H. Niederreiter, Finite Fields, Addison-Wesley, 1983, p. 65.

T. D. Noe, Table of n, a(n) for n = 1..10000
Jean-Paul Allouche, Manon Stipulanti, and Jia-Yan Yao, Doubling modulo odd integers, generalizations, and unexpected occurrences, arXiv:2504.17564 [math.NT], 2025.
Jarkko Peltomäki and Aleksi Saarela, Standard words and solutions of the word equation X_1^2 ... X_n^2 = (X_1 ... X_n)^2, Journal of Combinatorial Theory, Series A (2021) Vol. 178, 105340. See also arXiv:2004.14657 [cs.FL], 2020.

Cf. A000005, A023135-A023142.
Cf. A081844 (number of irreducible factors of x^(2n+1) - 1 over GF(2)).
Cf. A037226 (number of primitive irreducible factors of x^(2n+1) - 1 over integers mod 2).

Table[Length[FactorList[x^n - 1, Modulus -> 2]] - 1, {n, 100}]
CountFactors[p_, n_] := Module[{sum=0, m=n, d, f, i}, While[Mod[m, p]==0, m/=p]; d=Divisors[m]; Do[f=d[[i]]; sum+=EulerPhi[f]/MultiplicativeOrder[p, f], {i, Length[d]}]; sum]; Table[CountFactors[2, n], {n, 100}]

a(n)={sumdiv(n >> valuation(n,2), d, eulerphi(d)/znorder(Mod(2,d)));}
vector(100,n,a(n)) \\ Andrew Howroyd, Nov 12 2018

from sympy import totient, n_order, divisors
def A000374(n): return sum(totient(d)//n_order(2,d) for d in divisors(n>>(~n & n-1).bit_length(),generator=True) if d>1)+1 # Chai Wah Wu, Apr 09 2024

a(n) = Sum_{d|m} phi(d)/ord(2, d), where m is n with all factors of 2 removed. - T. D. Noe, Apr 19 2003

a(n) = (1/ord(2,m))*Sum_{j = 0..ord(2,m)-1} gcd(2^j - 1, m), where m is n with all factors of 2 removed. - Nihar Prakash Gargava, Nov 12 2018

cp's OEIS Frontend

User: Shel Kaphan

A370469 Triangle read by columns where T(n,k) is the number of points in Z^n such that |x1| + ... + |xn| = k, |x1|, ..., |xn| > 0.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Python

Formula

A371568 Array read by ascending antidiagonals: A(n, k) is the number of paths of length k in Z^n from the origin to points such that x1+x2+...+xn = k with x1,...,xn > 0.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Python

Formula

A371064 Array read by ascending antidiagonals where T(n,k) is the number of paths of length k from the origin to a facet of the cross polytope of size k in Z^n.

Views

Author

Keywords

Comments

Examples

Crossrefs

Formula

A361364 Number of 5-dimensional cubic lattice walks that start and end at origin after 2n steps, not touching origin at intermediate stages.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Formula

A359801 Number of 4-dimensional cubic lattice walks that start and end at origin after 2n steps, not touching origin at intermediate stages.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A190952 Largest integer k for which exp(k) < k^n, n>=3.

Views

Author

Keywords

Comments

Crossrefs

Programs

Mathematica

Formula

A190951 Closest integer to the largest real number x such that exp(x) = x^n, for n>=3.

Views

Author

Keywords

Comments

Crossrefs

Programs

Mathematica

A000374 Number of cycles (mod n) under doubling map.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs