Ryota Inagaki - cp's OEIS frontend

A381463 Limiting sequence of the possible number of inversions in stable configurations of 4^n-1 chips in a chip firing-game directed 4-ary tree resulting from a permutation-based strategy of firing chips.

0, 1, 4, 5, 6, 16, 17, 20, 21, 22, 24, 25, 26, 27, 64, 65, 68, 69, 70, 80, 81, 84, 85, 86, 88, 89, 90, 91, 96, 97, 100, 101, 102, 104, 105, 106, 107, 108, 109, 110, 111, 112, 256, 257, 260, 261, 262, 272, 273, 276, 277, 278, 280, 281, 282, 283, 320, 321, 324, 325, 326, 336, 337, 340

Offset: 1

Ryota Inagaki, Tanya Khovanova, and Austin Luo, Feb 24 2025

nonn

Consider a 4-ary, rooted infinite directed tree where each vertex has outdegree 4. A chip firing game on this tree is defined as in Section 2 of Inagaki, Khovanova, and Luo (2025). Here we start with 4^n chips labeled 0,1, ..., 4^n-1 at the root.
Let A(4, n) be the increasing sequence of all possible numbers of inversions in stable configurations in a chip-firing game on a directed regular 4-ary tree starting with 4^n chips resulting from applying a permutation-based strategy corresponding to permutation w of 1,2,..., n. In the strategy, for each i = 1, 2, ..., n, chips with j as the w_i-th most significant digit sent to the (j+1)-th leftmost child of the fired vertex. For each n divide each element in A(4, n) by 4^(n-1) * 9 and put the resulting elements in order from smallest to greatest. These are the first several terms of the sequence.
This sequence was defined at the end of Section 4.3 of Inagaki, Khovanova, and Luo (2025).

Wikipedia, Chip-firing game
Ryota Inagaki, Tanya Khovanova, and Austin Luo, Permutation-based Strategies for Labeled Chip-Firing on k-ary Trees, arXiv:2503.09577 [math.CO], 2025.

Cf. A376116, A381462.

k = 4
s = set()
for i in range(2):
    for j in range(3):
        for l in range(4):
            for m in range(5):
                for n in range(6):
                    s.add(((k** 5 - k ** (5-n)) + (k** 4 - k ** (4-m)) + (k ** 3 - k ** (3-l)) + (k ** 2 - k ** (2-j))+ (k ** 1 - k ** (1-i)))// (k-1))
l = list(s)
l.sort()
print(l)

A381462 Limiting sequence of the possible number of inversions in stable configurations of 3^n-1 chips in a chip firing-game directed 3-ary tree resulting from a permutation-based strategy of firing chips.

Original entry on oeis.org

0, 1, 3, 4, 5, 9, 10, 12, 13, 14, 15, 16, 17, 18, 27, 28, 30, 31, 32, 36, 37, 39, 40, 41, 42, 43, 44, 45, 46, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 81, 82, 84, 85, 86, 90, 91, 93, 94, 95, 96, 97, 98, 99, 108, 109, 111, 112, 113, 117, 118, 120, 121, 122, 123, 124, 125

Offset: 1

Ryota Inagaki, Tanya Khovanova, and Austin Luo, Feb 24 2025

nonn

Consider a 3-ary, rooted infinite directed tree where each vertex has outdegree 3. Consider the chip firing game on this tree defined in Section 2 of Inagaki, Khovanova, and Luo (2025) with 3^n chips, which are labeled 0, 1, 2, ..., 3^n-1, at the root vertex.
Let A(3, n) be the increasing sequence of all possible numbers of inversions in stable configurations in a chip-firing game on a 3-ary tree starting with 3^n chips resulting from applying a permutation-based strategy corresponding to permutation w of 1,2,..., n. In the strategy, for each i = 1, 2, ..., n, chips with j as the w_i-th most significant digit are sent to the (j+1)-st leftmost child of the fired vertex. For each n, divide each element in A(3, n) by 9^n and put the resulting elements in order from smallest to greatest. These are the first several terms of the sequence.
This sequence is defined at the end of Section 4.3 of "Permutation-based Strategies for Labeled Chip-Firing on k-ary Trees."

Wikipedia, Chip-firing game
Ryota Inagaki, Tanya Khovanova, and Austin Luo, Permutation-based Strategies for Labeled Chip-Firing on k-ary Trees, arXiv:2503.09577 [math.CO], 2025.

Cf. A376116, A381463.

k = 3
s = set()
for i in range(2):
    for j in range(3):
        for l in range(4):
            for m in range(5):
                for n in range(6):
                    s.add(((k ** 5 - k ** (5-n)) + (k ** 4 - k ** (4-m)) + (k ** 3 - k ** (3-l)) + (k ** 2 - k ** (2-j))+ (k ** 1 - k ** (1-i)))// (k-1))
l = list(s)
l.sort()
print(l)

A376790 Table T(n,k) read by antidiagonals: T(n,k) (n >=1, k >= 2) is the number of inversions in the radix-k digit reversal permutation of 0, 1, ..., k^n-1.

Original entry on oeis.org

0, 0, 1, 0, 9, 8, 0, 36, 135, 44, 0, 100, 864, 1458, 208, 0, 225, 3500, 15552, 14094, 912, 0, 441, 10800, 95000, 258048, 130491, 3840, 0, 784, 27783, 413100, 2425000, 4174848, 1187541, 15808

Offset: 1

Ryota Inagaki, Tanya Khovanova, and Austin Luo, Oct 04 2024

T(n,k) is also the maximum possible number of inversions in the sequence of chips in the (n+1)-st layer of the tree in the stable configuration resulting from directed chip-firing of k^n labeled chips 1, 2, ..., k^n starting at the root of an infinite, rooted directed k-ary tree. See Theorem 6.1 in Inagaki, Khovanova, and Luo (2024).

			For n=3, k=2, the radix-2 digit reversal permutation of 0, 1, 2, ..., 2^3-1 is 0, 4, 2, 6, 1, 5, 3, 7. This permutation has 8 inversions.
Array begins:
=======================================================
n/k |    2        3          4           5            6
----+--------------------------------------------------
  1 |    0        0          0           0            0 ...
  2 |    1        9         36         100          225 ...
  3 |    8      135        864        3500        10800 ...
  4 |   44     1458      15552       95000       413100 ...
  5 |  208    14094     258048     2425000     15066000 ...
  6 |  912   130491    4174848    60937500    543834000 ...
  7 | 3840  1187541   67018752  1525312500  19588521600 ...
  ...

David M. W. Evans, An Improved Digit-Reversal Permutation Algorithm for the Fast Fourier and Hartley Transforms, IEEE Transactions on Acoustics, Speech, and Signal Processing, Vol. ASSP-35, No. 8 (1987), 1120-1125.
Ryota Inagaki, Tanya Khovanova, and Austin Luo, Chip Firing on Directed k-ary Trees, arXiv:2410.23265 [math.CO], 2024.
Wikipedia, Bit-reversal Permutation

Cf. A100575 (column 2).

s = ""
for d in range(3, 11):
    for n in range(1, d-1):
        k = d-n
        s = s + str((k**(2*n) -  (n* (k**(n+1))) + (n-1) * (k**n))//4) + ", "
print(s)

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

A376132 First differences of A376131.

Original entry on oeis.org

1, 1, 4, 1, 4, 1, 11, 1, 4, 1, 11, 1, 4, 1, 26, 1, 4, 1, 11, 1, 4, 1, 26, 1, 4, 1, 11, 1, 4, 1, 57, 1, 4, 1, 11, 1, 4, 1, 26, 1, 4, 1, 11, 1, 4, 1, 57, 1, 4, 1, 11, 1, 4, 1, 26, 1, 4, 1, 11, 1, 4, 1, 120, 1, 4, 1, 11, 1, 4, 1, 26, 1, 4, 1, 11, 1, 4, 1, 57, 1, 4, 1, 11, 1, 4, 1, 26, 1

Offset: 1

Ryota Inagaki, Tanya Khovanova, and Austin Luo, Sep 11 2024

nonn

The sequence consists of Eulerian numbers from A000295.

The total number of fires for 2n and 2n-1 chips is the same, this is why the interesting increase is 2.

Dillan Agrawal, Selena Ge, Jate Greene, Tanya Khovanova, Dohun Kim, Rajarshi Mandal, Tanish Parida, Anirudh Pulugurtha, Gordon Redwine, Soham Samanta, and Albert Xu, Chip-Firing on Infinite k-ary Trees, arXiv:2501.06675 [math.CO], 2025. See p. 17.
Ryota Inagaki, Tanya Khovanova, and Austin Luo, On Chip-Firing on Undirected Binary Trees, Ann. Comb. (2025). See p. 24.
Wikipedia, Chip-firing game.

Cf. A000295, A091090, A376116, A376131.

b:= n-> (l-> add(((i-2)*2^(i-1)+1)*(l[i]+1), i=2..nops(l)-1))(Bits[Split](2*n+1)):
a:= n-> b(n+1)-b(n):
seq(a(n), n=1..88);  # Alois P. Heinz, Sep 12 2024

a(n) = A000295(A376116(n+1) - A376116(n) + 1).

A376131 Total number of times all nodes fire in a chip-firing game starting with 2n chips at the root on an infinite binary tree with a loop at the root.

Original entry on oeis.org

0, 1, 2, 6, 7, 11, 12, 23, 24, 28, 29, 40, 41, 45, 46, 72, 73, 77, 78, 89, 90, 94, 95, 121, 122, 126, 127, 138, 139, 143, 144, 201, 202, 206, 207, 218, 219, 223, 224, 250, 251, 255, 256, 267, 268, 272, 273, 330, 331, 335, 336, 347, 348, 352, 353, 379, 380, 384, 385, 396, 397, 401, 402, 522, 523

Offset: 1

Ryota Inagaki, Tanya Khovanova, and Austin Luo, Sep 11 2024

nonn

Adding a loop at the root makes the graph 3-regular: each vertex has degree 3.

The first differences of this sequence give A376132.

			If there are four chips at the root, then the root fires and the process ends in a stable configuration.
If there are eight chips at the root, the root can fire three times, sending 3 chips to each child. After this, each child can fire once. After that the root has 4 chips and can fire again. The total number of fires is 6.

Yifan Xie, Table of n, a(n) for n = 1..10000
Dillan Agrawal, Selena Ge, Jate Greene, Tanya Khovanova, Dohun Kim, Rajarshi Mandal, Tanish Parida, Anirudh Pulugurtha, Gordon Redwine, Soham Samanta, and Albert Xu, Chip-Firing on Infinite k-ary Trees, arXiv:2501.06675 [math.CO], 2025. See p. 13.
Ryota Inagaki, Tanya Khovanova, and Austin Luo, On Chip-Firing on Undirected Binary Trees, Ann. Comb. (2025). See p. 24.
Wikipedia, Chip-firing game.

Cf. A091090, A376116, A376132.

a:= n-> (l-> add(((i-2)*2^(i-1)+1)*(l[i]+1), i=2..nops(l)-1))(Bits[Split](2*n+1)):
seq(a(n), n=1..65);  # Alois P. Heinz, Sep 12 2024

def f0(n):
    if n <= 2:
        return 0
    else:
        return (n+1) // 2 - 1 + f0((n+1)//2 - 1)
def a(n):
    numchip = 2*n
    total = 0
    firetime = f0(numchip)
    l = 0
    while firetime > 0:
        total += (2**l) * firetime
        numchip = (numchip+1)//2 - 1
        firetime = f0(numchip)
        l += 1
    return total
print([a(n) for n in range(1, 66)])

a(n) = Sum_{k=1..m-1}((k-1)*2^k+1)(b(k)+1), where m = floor(log_2(2*n+1)) and b(m)b(m-1)b(m-2)...b(1)b(0) is a binary representation of 2*n+1 in m+1 bits.

A376116 Number of times the root fires in a chip-firing game starting with 2n chips placed at the root on an infinite binary tree with a loop at the root.

Original entry on oeis.org

0, 1, 2, 4, 5, 7, 8, 11, 12, 14, 15, 18, 19, 21, 22, 26, 27, 29, 30, 33, 34, 36, 37, 41, 42, 44, 45, 48, 49, 51, 52, 57, 58, 60, 61, 64, 65, 67, 68, 72, 73, 75, 76, 79, 80, 82, 83, 88, 89, 91, 92, 95, 96, 98, 99, 103, 104, 106, 107, 110, 111, 113, 114, 120, 121, 123, 124, 127, 128, 130

Offset: 1

Ryota Inagaki, Tanya Khovanova, and Austin Luo, Sep 10 2024

nonn

Adding a loop at the root makes the graph 3-regular: each vertex has degree 3.

The first differences of this sequence give A091090.

			If there are four chips at the root, then the root fires and the process ends in a stable configuration.
If there are eight chips at the root, the root can fire three times, sending 3 chips to each child. After this, each child can fire once. After that the root has 4 chips and can fire again. The root fires a total of 4 times.

Yifan Xie, Table of n, a(n) for n = 1..10000
Dillan Agrawal, Selena Ge, Jate Greene, Tanya Khovanova, Dohun Kim, Rajarshi Mandal, Tanish Parida, Anirudh Pulugurtha, Gordon Redwine, Soham Samanta, and Albert Xu, Chip-Firing on Infinite k-ary Trees, arXiv:2501.06675 [math.CO], 2025. See p. 10.
Ryota Inagaki, Tanya Khovanova, and Austin Luo, On Chip-Firing on Undirected Binary Trees, Ann. Comb. (2025). See p. 22.
Wikipedia, Chip-firing game.

Cf. A091090, A376131, A376132, A000120, A070939.

a:= n-> (l-> add((2^(i-1)-1)*(l[i]+1), i=2..nops(l)-1))(Bits[Split](2*n+1)):
seq(a(n), n=1..70);  # Alois P. Heinz, Sep 12 2024

def a(n):
    if n <= 2:
        return 0
    else:
        return (n+1) // 2 - 1 + a((n+1)//2 - 1)
print([a(2*n) for n in range(1, 51)])

def A376116(n): return (n<<1)-n.bit_count()-n.bit_length() # Chai Wah Wu, Sep 18 2024

a(n) = Sum_{j=1..m-1} (2^j-1)(b(j)+1), where m = floor(log_2(2n+1)) and b(m)b(m-1)...b(1)b(0) is the binary representation of 2*n+1.

a(n) = 2n-A000120(n)-A070939(n). - Chai Wah Wu, Sep 18 2024

cp's OEIS Frontend

User: Ryota Inagaki

A381463 Limiting sequence of the possible number of inversions in stable configurations of 4^n-1 chips in a chip firing-game directed 4-ary tree resulting from a permutation-based strategy of firing chips.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Python

A381462 Limiting sequence of the possible number of inversions in stable configurations of 3^n-1 chips in a chip firing-game directed 3-ary tree resulting from a permutation-based strategy of firing chips.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Python

A376790 Table T(n,k) read by antidiagonals: T(n,k) (n >=1, k >= 2) is the number of inversions in the radix-k digit reversal permutation of 0, 1, ..., k^n-1.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Python

Formula

A376132 First differences of A376131.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Formula

A376131 Total number of times all nodes fire in a chip-firing game starting with 2n chips at the root on an infinite binary tree with a loop at the root.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Python

Formula

A376116 Number of times the root fires in a chip-firing game starting with 2n chips placed at the root on an infinite binary tree with a loop at the root.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Python

Python

Formula