Cyril Banderier - cp's OEIS frontend

A308415 Number of irreducible Egyptian fractions of denominator n which are the sum of 3 unit fractions.

3, 3, 5, 5, 8, 5, 10, 8, 11, 8, 13, 8, 15, 10, 13, 12, 18, 11, 19, 14, 19, 13, 22, 14, 22, 15, 22, 18, 24, 13, 25, 20, 23, 18, 28, 18, 25, 20, 28, 22, 28, 19, 29, 24, 29, 20, 33, 24, 35, 23, 32, 27, 33, 22, 42, 28, 35, 24, 38, 24, 30, 26, 38, 31

Offset: 1

Cyril Banderier, May 25 2019

nonn

			There are a(2)=3 irreducible fractions with denominator n=2 which are the sums of 3 unit fractions: 1/2 = 1/8 + 1/8 + 1/4 and 3/2 = 1/2 + 1/2 + 1/2, and 5/2 = 1/1 + 1/1 + 1/2.

Cyril Banderier, Florian Luca, Francesco Pappalardi, Numerators of Egyptian fractions, 2019.

Cf. A308219, A308220, A308221.

A308221 Number of Egyptian fractions of denominator n which are sum of 3 unit fractions.

Original entry on oeis.org

3, 6, 8, 11, 11, 16, 13, 19, 19, 22, 16, 29, 18, 26, 29, 31, 21, 38, 22, 41, 37, 32, 25, 51, 33, 36, 41, 49, 27, 58, 28, 51, 44, 42, 49, 69, 28, 45, 51, 71, 31, 74, 32, 61, 69, 48, 36, 87, 48, 67, 58, 68, 36, 82, 66, 85, 62, 54, 41, 109, 33, 57, 86, 82, 69, 89, 40, 80, 71, 98, 44, 121, 38, 59, 91, 84, 77, 101, 46, 118, 81, 62, 52, 139, 79, 65, 79, 106, 49, 138, 80, 89, 77, 70, 83, 143, 47, 98, 107, 128

Offset: 1

Cyril Banderier, May 15 2019

nonn

			There are a(1) = 3 Egyptian fractions with denominator n = 1 which are sums of 3 unit fractions: 1/1 = 1/3 + 1/3 + 1/3, 2/1 = 1/1 + 1/2 + 1/2, and 3/1 = 1/1 + 1/1 + 1/1.

Cyril Banderier, Florian Luca, Francesco Pappalardi, Numerators of Egyptian fractions, 2019.

Cf. A308219, A308220, A308415

A308220 Number of irreducible Egyptian fractions of denominator n which are the sum of 2 unit fractions.

Original entry on oeis.org

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

Offset: 1

Cyril Banderier, May 15 2019

nonn

			There are a(2)=2 irreducible fractions with denominator n=2 which are sums of 2 unit fractions: 1/2 = 1/4 + 1/4 and 3/2 = 1/1 + 1/2.

Cyril Banderier, Florian Luca, Francesco Pappalardi, Numerators of Egyptian fractions, 2019.

Cf. A308219, A308221, A308415.

For p prime, a(p) = number_of_divisors(p+1).

A308219 Number of Egyptian fractions of denominator n which are the sum of 2 unit fractions.

Original entry on oeis.org

2, 4, 5, 7, 6, 10, 6, 11, 10, 12, 8, 17, 6, 13, 14, 16, 8, 20, 8, 21, 17, 14, 10, 27, 12, 15, 18, 23, 10, 29, 8, 23, 18, 17, 20, 34, 6, 17, 20, 33, 10, 34, 8, 25, 28, 17, 12, 41, 14, 27, 20, 27, 10, 35, 24, 36, 21, 18, 14, 51, 6, 18, 33, 32, 22, 36, 8, 30, 25, 39, 14, 54, 6, 17, 33, 30, 25, 39, 12, 49, 28, 18, 14, 60, 22, 19, 25, 39, 14, 58, 20, 29, 21, 21, 24, 59, 8, 32, 36, 48

Offset: 1

Cyril Banderier, May 15 2019

nonn

a(n) is the number of fractions of denominator n which are the sum of two unit fractions: m/n = 1/r + 1/s (m and n not necessarily coprime).

			a(2)=4, as there are 4 fractions with denominator 4 which are the sums of 2 unit fractions: 1/2 = 1/4 + 1/4, 2/2 = 1/2 + 1/2, 3/2 = 1/1 + 1/2, 4/2 = 1/1 + 1/1.

Cyril Banderier, Florian Luca, Francesco Pappalardi, Numerators of Egyptian fractions, 2019.

Cf. A000005, A308220, A308221, A308415.

For p prime, a(p) = 2 + tau(p+1) with tau = A000005.

A307555 Number of Motzkin meanders of length n with an even number of humps.

Original entry on oeis.org

1, 2, 4, 8, 17, 40, 106, 307, 927, 2818, 8480, 25142, 73555, 213204, 615074, 1773036, 5121195, 14843518, 43190084, 126112096, 369264395, 1083378784, 3182684838, 9357797643, 27529874201, 81028448678, 238599098824, 702932296258, 2072003987285, 6111009331876

Offset: 0

Cyril Banderier, Apr 14 2019

nonn

A Motzkin meander is a lattice path with steps from the set {D=-1, H=0, U=1} that starts at (0,0) and never goes below the x-axis.

A hump is an occurrence of the pattern UHH...HD (the number of Hs in the pattern is not fixed, and can be 0).

			For n = 3, the a(3) = 8 paths are HHH, HHU, HUH, HUU, UHH, UHU, UUU.
For n=5, there are a(5) = 40 paths: 32 paths with no humps, {H, U}^5; and 8 paths with two humps, HUDUD, UDHUD, UDUDH, UDUDU, UDUHD, UDUUD, UHDUD, UUDUD.

Andrei Asinowski, Axel Bacher, Cyril Banderier, Bernhard Gittenberger, Analytic combinatorics of lattice paths with forbidden patterns, the vectorial kernel method, and generating functions for pushdown automata, Algorithmica (2019).

Cf. A307557.

a:=gfun[rectoproc]({(15*n^2+45*n+30)*u(n)+(-92*n^2-532*n-696)*u(n+1)+(62*n^2+426*n+672)*u(n+2)+(-32*n^2-264*n-524)*u(n+3)+(-20*n^2-192*n-428)*u(n+4)+(84*n^2+988*n+2848)*u(n+5)+(-70*n^2-906*n-2864)*u(n+6)+(24*n^2+336*n+1140)*u(n+7)+(-3*n^2-45*n-162)*u(n+8), u(0) = 1, u(1) = 2, u(2) = 4, u(3) = 8, u(4) = 17, u(5) = 40, u(6) = 106, u(7) = 307},u(n),remember):
seq(a(n), n=0..30);

G.f.: (sqrt((-t^2+1)/(3*t^2-4*t+1))+sqrt((t^2+1)/(5*t^2-4*t+1))-2)/(4*t).

D-finite with recurrence -3*(n+1)*(n-2)*a(n) +12*(2*n^2-4*n-1)*a(n-1) +2*(-35*n^2+107*n-48)*a(n-2) +4*(21*n^2-89*n+80)*a(n-3) +4*(-5*n^2+32*n-43)*a(n-4) +4*(-8*n^2+62*n-115)*a(n-5) +2*(31*n^2-283*n+616)*a(n-6) -4*(23*n-97)*(n-6)*a(n-7) +15*(n-6)*(n-7)*a(n-8)=0. - R. J. Mathar, Jan 25 2023

A307030 Number of permutations of [n] with overlapping adjacent runs.

Original entry on oeis.org

1, 1, 3, 11, 49, 263, 1653, 11877, 95991, 862047, 8516221, 91782159, 1071601285, 13473914281, 181517350571, 2608383775171, 39824825088809, 643813226048935, 10986188094959045, 197337931571468445, 3721889002400665951, 73539326922210382215, 1519081379788242418149, 32743555520207058219615, 735189675389014372317381

Offset: 1

Cyril Banderier, Mar 20 2019

nonn

The one-line notation of any permutation p has a unique factorization into runs p = B1,B2,...,Bk, where each Bi is a run (a sequence of increasing values), and the first element of B(i+1) is smaller than the last element of Bi. If the permutation p is such that each pair of adjacent runs Bi, B(i+1) have an overlapping range, that is the intervals [min(Bi),max(Bi)] and [min(B(i+1)),max(B(i+1))] have a nonempty intersection, then we say that p has overlapping runs.

a(n) is also the number of permutations of size n transformed by a pop-stack sorting (see Links below).

			For n = 3 the a(3) = 3 permutations with overlapping runs are 123, 132, 213.

Bjarki Ágúst Guðmundsson, Table of n, a(n) for n = 1..450
Andrei Asinowski, Cyril Banderier, Sara Billey, Benjamin Hackl and Svante Linusson, Pop-stack sorting and its image: Permutations with overlapping runs (2019), preprint.
Anders Claesson, Bjarki Ágúst Guðmundsson and Jay Pantone, Counting pop-stacked permutations in polynomial time, arXiv:1908.08910 [math.CO], 2019.
Colin Defant and Nathan Williams, Semidistrim Lattices, arXiv:2111.08122 [math.CO], 2021.

Cf. A001855, A008292.

Row sums of A309993.

Added more terms (from the Claesson/Guðmundsson/Pantone reference), Joerg Arndt, Aug 26 2019

Definition corrected by Bjarki Ágúst Guðmundsson, Aug 26 2019

A306699 Periods of A265165(k) mod n.

Original entry on oeis.org

2, 12, 8, 1, 12, 84, 8, 36, 2, 1, 24, 104, 84, 12, 16, 544, 36, 1, 8, 84, 2, 1012, 24, 1, 104, 108, 168, 1, 12, 1, 32, 12, 544, 84, 72, 2664, 2, 312, 8, 1, 84, 3612, 8, 36, 1012, 4324, 48, 588, 2, 1632, 104, 5512, 108, 1, 168, 12, 2, 1, 24, 1, 2, 252, 64, 104, 12, 2948, 544, 3036, 84, 1, 72, 10512, 2664

Offset: 2

Cyril Banderier, Mar 05 2019

nonn

Let b(k) be the sequence A265165(k).
a(n) = period({b(k) mod n}) = smallest p > 0 such that b(k+p) = b(k) mod n (for all large enough k).
The sequences b(k) and a(n) were introduced in the Banderier-Baril-Moreira article, they have many noteworthy arithmetical properties (proven in the Banderier-Luca article).

			A265165(k) mod 15 = (10,5,10,10,0,10,5,10,5,5,0,5)... and this pattern of length 12 repeats, therefore a(15) = 12.

Cyril Banderier, Jean-Luc Baril, Céline Moreira Dos Santos, Right jumps in permutations, DMTCS 18:2#12, p. 1-17, 2017.
Cyril Banderier, Florian Luca, On the period mod m of polynomially-recursive sequences: a case study, arXiv:1903.01986 [math.NT], 2019.

Cf. A265163, A265164, A265165.

The Banderier-Luca article proves the following properties:
a(n) = 1 iff n is a product of primes in 0,1,4 mod 5.
a(n) = 2 iff n/2 is a product of primes in 0,1,4 mod 5.
If a(n) is not 1, then it is an even number.
For any prime p, a(p) | 2 p (p-1).
For any prime p not in 0,1,4 mod 5, (and p^r <> 4), a(p^r) = p^r a(p).
a(n) is an "lcm-multiplicative" sequence: a(n1*n2) = lcm(a(n1), a(n2)) (for n1,n2 coprime), this implies that if n = p1^e1 ... pk^ek (factorization in distinct primes) then a(n) = lcm(a(p1^e1), ..., a(pk^ek)).

A318266 Number of legal chess positions with a total of n black and white pieces, reduced for symmetry.

Original entry on oeis.org

462, 368079, 125246598, 25912594054, 3787154440416, 423836835667331, 38176306877748245

Offset: 2

Cyril Banderier, Aug 22 2018

a(n) is the number of legal chess positions with n pieces on the board.
See Kirill Kryukov's webpage (in the Links section) for the explanations of these computations and of symmetries taken into account to avoid double counting, and for the definition of "legal" position. Note that some "legal" positions are not reachable in a game: e.g., white Ka1 vs. black Kc3 + Qc2 + Qb3 (black to move) is counted in a(4), although it is impossible to reach such a position.
The rapid growth of this sequence illustrates why exhaustive endgame databases at chess quickly require several hundred terabytes, even with a small number of pieces on the board.

			There are 3612 ways to place 2 kings on a chessbard so that they are not in check, which would not be a legal position: this decomposes as 3612 = 4*(64-4) [when white king is in a corner] + 6*4*(64-6) [when white king is on a side] + (64-28)*(64-9) [when white king is not touching any side of the board]. Killing "isomorphic" positions due to symmetries reduces this number to 462 remaining different positions. Symmetries roughly lead to a division by 8, but not exactly, because they have some fixed points (e.g., the position with kings on A1 and H8 is a fixed point for the diagonal symmetry). Therefore a(2)=462.

Kirill Kryukov, Number of Unique Legal Positions in chess endgames

Cf. A048987 for another enumeration of chess positions.

A293653 Young urn sequence (number of possible evolutions in n steps of the "Young" Pólya urn).

Original entry on oeis.org

1, 2, 6, 30, 180, 1440, 12960, 142560, 1710720, 23950080, 359251200, 6107270400, 109930867200, 2198617344000, 46170964224000, 1061932177152000, 25486372251648000, 662645678542848000, 17891433320656896000, 518851566299049984000, 15565546988971499520000, 498097503647087984640000

Offset: 0

Cyril Banderier, Feb 06 2018

nonn

			We based the following explanations on Figure 1 from the Banderier et al. reference:
We have an urn with black and white balls in it.
At odd-numbered steps, we apply rule M1: we choose a ball, check its color, and add to the urn a ball of the same color.
At even-numbered steps, we apply rule M2: we choose a ball and check its color;
  if it is black, we add 1 white ball and 1 black ball;
  if it is white, we add 2 white balls.
At step 0, we start with the urn containing 1 black ball and 1 white ball (in short, 1b/1w). Accordingly, a(0)=1.
At step 1, we apply rule M1. This leads to 2 compositions: 2b/1w and 1b/2w. Accordingly, a(1) = 1 + 1 = 2.
At step 2, we apply rule M2. This leads to 3 compositions: 3b/2w, 2b/3w, and 1b/4w, each having multiplicity two. Accordingly, a(2) = 2 + 2 + 2 = 6. This leads to 4 compositions at step 3: 4b/2w (with multiplicity 6), and 3b/3w, 2b/4w, and 1b/5w (each of these last three with multiplicity 8). Accordingly, a(3) = 6 + 8 + 8 + 8 = 30.

Robert G. Wilson v, Table of n, a(n) for n = 0..422
Cyril Banderier, Philippe Marchal, and Michael Wallner, Periodic Pólya urns and an application to Young tableaux, Leibniz International Proceedings in Informatics (LIPIcs), 29th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2018), 1-12, also arXiv:1806.03133 [cs.DM], 2018.
Cyril Banderier, Philippe Marchal, Michael Wallner, Periodic Pólya Urns, the Density Method, and Asymptotics of Young Tableaux, arXiv:1912.01035 [math.PR], 2019.

Cf. A123144.

a:=[1,2];; for n in [3..25] do a[n]:=(3/2)*a[n-1]+(9*(n-3)^2+21*n-51)/4*a[n-2]; od; a; # Muniru A Asiru, Dec 19 2018

a:=proc(n) if n mod 2= 0 then 3^n /GAMMA(2/3) * GAMMA(n/2+2/3) * GAMMA(n/2+1);
else 3^n /GAMMA(2/3) * GAMMA(n/2+7/6) * GAMMA(n/2+1/2);  fi; end:
seq(a(n), n=0..30);

f[n_] := FullSimplify[ 3^n/Gamma[2/3]*If[OddQ@ n, Gamma[n/2 + 7/6] Gamma[n/2 + 1/2], Gamma[n/2 + 2/3]Gamma[n/2 + 1]]]; Array[f, 20, 0] (* Robert G. Wilson v, Feb 07 2018 *)

a(n+2) = (3/2)*a(n+1) + (9*n^2+21*n+12)/4*a(n), a(0) = 1, a(1) = 2.

Also, a(2n+k) has a hypergeometric expression (for k=0,1, see Maple code below) (proved).

A265163 Array of basis permutations, seen as a triangle read by rows: Row k (k >= 0) gives the values of b(n, k) = number of permutations of size n (2 <= n <= 2(k+1)) in the permutation basis B(k) (see Comments for further details).

Original entry on oeis.org

1, 0, 2, 1, 0, 0, 6, 8, 1, 0, 0, 0, 24, 58, 18, 1, 0, 0, 0, 0, 120, 444, 244, 32, 1, 0, 0, 0, 0, 0, 720, 3708, 3104, 700, 50, 1, 0, 0, 0, 0, 0, 0, 5040, 33984, 39708, 13400, 1610, 72, 1, 0, 0, 0, 0, 0, 0, 0, 40320, 341136, 525240, 244708, 43320, 3206, 98, 1

Offset: 0

Cyril Banderier, Dec 07 2015, with additional comments added Feb 06 2017

A right-jump in a permutation consists of taking an element and moving it somewhere to its right.
The set P(k) of permutations reachable from the identity after at most k right-jumps is a permutation-pattern avoiding set: it coincides with the set of permutation avoiding a set of patterns.
We define B(k) to be the smallest such set of "forbidden patterns" (the permutation pattern community calls such a set a "basis" for P(k), and its elements can be referred to as "right-jump basis permutations").
The number b(n,k) of permutations of size n in B(k) is given by the array in the present sequence.
The row sums give the sequence A265164 (i.e. this counts the permutations of any size in the basis B(k)).
The column sums give the sequence A265165 (i.e. this counts the permutations of size n in any B(k)).

			The number b(n, k) of basis permutations of length n where 2<=n<=11.
k\n |  2  3  4   5   6    7    8     9     10      11  |  #B_k
0   |  1                                               |     1
1   |  0  2  1                                         |     3
2   |  0  0  6   8   1                                 |    15
3   |  0  0  0  24  58   18    1                       |   101
4   |  0  0  0   0 120  444  244    32      1          |   841
5   |  0  0  0   0   0  720 3708  3104    700      50  |  8232
6   |  0  0  0   0   0    0 5040 33984  39708   13400  | 78732
----+--------------------------------------------------+------
Sum |  1  2  7  32 179 1182 8993 77440 744425 7901410  |
----+--------------------------------------------------+------

Cyril Banderier, Jean-Luc Baril, Céline Moreira Dos Santos, Right jumps in permutations, Permutation Patterns 2015.

Cf. A265164 (row sums B(k)), A265165 (column sums).

cp's OEIS Frontend

User: Cyril Banderier

A308415 Number of irreducible Egyptian fractions of denominator n which are the sum of 3 unit fractions.

Views

Author

Keywords

Examples

Links

Crossrefs

A308221 Number of Egyptian fractions of denominator n which are sum of 3 unit fractions.

Views

Author

Keywords

Examples

Links

Crossrefs

A308220 Number of irreducible Egyptian fractions of denominator n which are the sum of 2 unit fractions.

Views

Author

Keywords

Examples

Links

Crossrefs

Formula

A308219 Number of Egyptian fractions of denominator n which are the sum of 2 unit fractions.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

A307555 Number of Motzkin meanders of length n with an even number of humps.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Formula

A307030 Number of permutations of [n] with overlapping adjacent runs.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Extensions

A306699 Periods of A265165(k) mod n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

A318266 Number of legal chess positions with a total of n black and white pieces, reduced for symmetry.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A293653 Young urn sequence (number of possible evolutions in n steps of the "Young" Pólya urn).

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

GAP

Maple