A145883 -id:A145883 - cp's OEIS frontend

A145882 Triangle read by rows: T(n,k) is the number of even permutations of {1,2,...,n} having k descents (n >= 1, k >= 0).

1, 1, 1, 2, 1, 5, 5, 1, 1, 14, 30, 14, 1, 1, 29, 147, 155, 28, 1, 64, 586, 1208, 605, 56, 1, 127, 2133, 7819, 7819, 2133, 127, 1, 1, 262, 7288, 44074, 78190, 44074, 7288, 262, 1, 1, 517, 23893, 227569, 655315, 655039, 227623, 23947, 496, 1, 1044, 76332, 1101420

Offset: 1

Emeric Deutsch, Nov 11 2008

Number of entries in row n is 1+floor(binomial(n,2)/2)-floor(binomial(n-2,2)/2).

Sum of entries in row n is A001710(n) for n>=2.

			T(4,2) = 5 because we have 4132, 2143, 4213, 2431 and 3241.
Triangle begins with T(1,0):
  1
  1
  1    2
  1    5      5       1
  1   14     30      14       1
  1   29    147     155      28
  1   64    586    1208     605      56
  1  127   2133    7819    7819    2133     127       1
  1  262   7288   44074   78190   44074    7288     262     1
  1  517  23893  227569  655315  655039  227623   23947   496
  1 1044  76332 1101420 4869558 7862124 4868556 1102068 76305 992

Alois P. Heinz, Rows n = 1..142, flattened
J. Shareshian and M. L. Wachs, q-Eulerian polynomials: excedance number and major index, Electronic Research Announcements of the Amer. Math. Soc., 13 (2007), 33-45.
R. P. Stanley, Binomial posets, Möbius inversion and permutation enumeration, J. Combinat. Theory, A 20 (1976), 336-356.
S. Tanimoto, A study of Eulerian numbers for permutations in the alternating group, Integers, Electronic J. of Combinatorial Number Theory, 6 (2006), #A31.

Cf. A001710, A145883.

Cf. A128612 (similar with rows reversed).

for n to 11 do qbr := proc (m) options operator, arrow; sum(q^i, i = 0 .. m-1) end proc; qfac := proc (m) options operator, arrow; product(qbr(j), j = 1 .. m) end proc; Exp := proc (z) options operator, arrow; sum(q^binomial(m, 2)*z^m/qfac(m), m = 0 .. 19) end proc; g := (1-t)/(Exp(z*(t-1))-t); gser := simplify(series(g, z = 0, 17)); a[n] := simplify(qfac(n)*coeff(gser, z, n)); b[n] := (a[n]+subs(q = -q, a[n]))*1/2; P[n] := sort(subs(q = 1, b[n])) end do; for n to 11 do seq(coeff(P[n], t, j), j = 0 .. floor((1/2)*binomial(n, 2)) -floor((1/2)*binomial(n-2, 2))) end do; # yields sequence in triangular form
# second Maple program:
b:= proc(u, o, t) option remember; `if`(u+o=0, t, expand(
       add(b(u+j-1, o-j, irem(t+j-1+u, 2)), j=1..o)+
       add(b(u-j, o+j-1, irem(t+u-j, 2))*x, j=1..u)))
    end:
T:= n-> (p-> seq(coeff(p, x, i), i=0..degree(p)))
        (add(b(j-1, n-j, irem(j, 2)), j=1..n)):
seq(T(n), n=1..12);  # Alois P. Heinz, Nov 19 2013

b[u_, o_, t_] := b[u, o, t] = If[u+o == 0, t, Expand[Sum[b[u+j-1, o-j, Mod[t+j-1+u, 2]], {j, 1, o}] + Sum[b[u-j, o+j-1, Mod[t+u-j, 2]]*x, {j, 1, u}]]]; T[n_] := Function[{p}, Table[Coefficient[p, x, i], {i, 0, Exponent[p, x]}]] [Sum[b[j-1, n-j, Mod[j, 2]], {j, 1, n}]]; Table[T[n], {n, 1, 12}] // Flatten (* Jean-François Alcover, May 26 2015, after Alois P. Heinz *)
Needs["Combinatorica`"];
Table[(Eulerian[n, k] + Sum[Binomial[j-1-Floor[n/2], j] Eulerian[Ceiling[n/2], k-j], {j, Max[0, k-Ceiling[n/2]], Min[Floor[n/2], k]}])/2, {n, 25}, {k, 0, n-1}] // Flatten // DeleteCases[0] (* Robert A. Russell, Nov 14 2018 *)

In the Shareshian and Wachs reference (p. 35) a q-analog of the exponential g.f. of the Eulerian polynomials is given for the joint distribution of (inv, des) (see also the Stanley reference). The first Maple program given below makes use of this function by considering its even part.

T(n,k) = (euler(n,k) + Sum_{j=max(0, k+1-ceiling(n/2))..min(floor(n/2), k)} binomial(j-1-floor(n/2), j) * euler(ceiling(n/2), k-j)) / 2, where euler(n,k) is the Eulerian number A173018 (not A008292, which has different indexing). - Robert A. Russell, Nov 15 2018

A293500 Number of orientable strings of length n using a maximum of k colors, array read by descending antidiagonals, T(n,k) for n >= 1 and k >= 1.

Original entry on oeis.org

0, 0, 0, 0, 1, 0, 0, 3, 2, 0, 0, 6, 9, 6, 0, 0, 10, 24, 36, 12, 0, 0, 15, 50, 120, 108, 28, 0, 0, 21, 90, 300, 480, 351, 56, 0, 0, 28, 147, 630, 1500, 2016, 1053, 120, 0, 0, 36, 224, 1176, 3780, 7750, 8064, 3240, 240, 0, 0, 45, 324, 2016, 8232, 23220, 38750, 32640, 9720, 496, 0

Offset: 1

Andrew Howroyd, Oct 10 2017

Reversing the string does not leave it unchanged. Only one string from each pair is counted.
Equivalently, the number of nonequivalent strings up to reversal that are not palindromes.
Except for the first term, column k is the "BHK" (reversible, identity, unlabeled) transform of k,0,0,0,... [Corrected by Petros Hadjicostas, Jul 01 2018]
From Petros Hadjicostas, Jul 01 2018: (Start)
Consider the input sequence (c_k(n): n >= 1) with g.f. C_k(x) = Sum_{n>=1} c_k(n)*x^n. Let a_k(n) = BHK(c_k(n): n >= 1) be the output sequence under Bower's BHK transform. It can be proved that the g.f. of BHK(c_k(n): n >= 1) is A_k(x) = (C_k(x)^2 - C_k(x^2))/(2*(1-C_k(x))*(1-C_k(x^2))) + C_k(x). (See the comments for sequences A032096, A032097, and A032098.)
For column k of this two-dimensional array, the input sequence is defined by c_k(1) = k and c_k(n) = 0 for n >= 1. Thus, C_k(x) = k*x, and hence the g.f. of column k (with the term C_k(x) = k*x excluded) is (C_k(x)^2 - C_k(x^2))/(2*(1-C_k(x))*(1-C_k(x^2))) = (1/2)*(k - 1)*k*x^2/((k*x^2 - 1)*(k*x - 1)), from which we can easily prove Howroyd's formula.
(End)
Comment from Bahman Ahmadi, Aug 05 2019: (Start)
We give an alternative definition for the square array A(n,k) = T(n,k) with n >= 2 and k >= 0. A(n,k) is the number of inequivalent "distinguishing colorings" of the path on n vertices using at most k colors.  The rows are indexed by n, the number of vertices of the path, and the columns are indexed by k, the number of permissible colors.
A vertex-coloring of a graph G is called "distinguishing" if it is only preserved by the identity automorphism of G. This notion is considered in the context of "symmetry breaking" of simple (finite or infinite) graphs. Two vertex-colorings of a graph are called "equivalent" if there is an automorphism of the graph which preserves the colors of the vertices.  Given a graph G, we use the notation Phi_k(G) to denote the number of inequivalent distinguishing colorings of G with at most k colors. This sequence gives A(n,k) = Phi_k(P_n), i.e., the number of inequivalent distinguishing colorings of the path P_n on n vertices with at most k colors.
For n=3, we can color the vertices of P_3 with at most 2 colors in 3 ways such that all the colorings distinguish the graph (i.e., no non-identity automorphism of the path P_3 preserves the coloring) and that all the three colorings are inequivalent.
We have Phi_k(P_n) = binomial(k,2)*k^(n-2) + k*Phi_k(P_(n-2)) for n >= 4; Phi_k(P_2) = binomial(k,2); Phi_k(P_3) = k*binomial(k,2).
(End)

			Array begins:
======================================================
n\k| 1   2    3     4      5      6       7       8
---|--------------------------------------------------
1  | 0   0    0     0      0      0       0       0...
2  | 0   1    3     6     10     15      21      28...
3  | 0   2    9    24     50     90     147     224...
4  | 0   6   36   120    300    630    1176    2016...
5  | 0  12  108   480   1500   3780    8232   16128...
6  | 0  28  351  2016   7750  23220   58653  130816...
7  | 0  56 1053  8064  38750 139320  410571 1046528...
8  | 0 120 3240 32640 195000 839160 2881200 8386560...
...
For T(4,2)=6, the chiral pairs are AAAB-BAAA, AABA-ABAA, AABB-BBAA, ABAB-BABA, ABBB-BBBA, and BABB-BBAB.

Andrew Howroyd, Table of n, a(n) for n = 1..1275
B. Ahmadi, F. Alinaghipour and M. H. Shekarriz, Number of Distinguishing Colorings and Partitions, arXiv:1910.12102 [math.CO], 2019.
C. G. Bower, Transforms (2).

Columns 2-5 for n > 1 are A032085, A032086, A032087, A032088.
Column 6 is A320524.
Rows 2-6 are A161680, A006002(n-1), A083374, A321672, A085744.
Cf. A277504, A293496.
Cf. A003992 (oriented), A277504 (unoriented), A321391 (achiral).

Table[Function[n, (k^n - k^(Ceiling[n/2]))/2][m - k + 1], {m, 11}, {k, m, 1, -1}] // Flatten (* Michael De Vlieger, Oct 11 2017 *)

PARI
```
T(n,k) = (k^n - k^(ceil(n/2)))/2;
```

T(n,k) = (k^n - k^(ceiling(n/2)))/2.
G.f. for column k: (1/2)*(k - 1)*k*x^2/((k*x^2 - 1)*(k*x - 1)). - Petros Hadjicostas, Jul 07 2018
From Robert A. Russell, Nov 16 2018: (Start)
T(n,k) = (A003992(k,n) - A321391(n,k)) / 2.
T(n,k) = = A003992(k,n) - A277504(n,k) = A277504(n,k) - A321391(n,k).
G.f. for row n: (Sum_{j=0..n} S2(n,j)*j!*x^j/(1-x)^(j+1) - Sum_{j=0..ceiling(n/2)} S2(ceiling(n/2),j)*j!*x^j/(1-x)^(j+1)) / 2, where S2 is the Stirling subset number A008277.
G.f. for row n>1: x * Sum_{k=1..n-1} A145883(n,k) * x^k / (1-x)^(n+1).
E.g.f. for row n: (Sum_{k=0..n} S2(n,k)*x^k - Sum_{k=0..ceiling(n/2)} S2(ceiling(n/2),k)*x^k) * exp(x) / 2, where S2 is the Stirling subset number A008277.
T(0,k) = T(1,k) = 0; T(2,k) = binomial(k,2); for n>2, T(n,k) = k*(T(n-3,k)+T(n-2,k)-k*T(n-1,k)).
For k>n, T(n,k) = Sum_{j=1..n+1} -binomial(j-n-2,j) * T(n,k-j). (End)

A321672 Number of chiral pairs of rows of length 5 using up to n colors.

Original entry on oeis.org

0, 0, 12, 108, 480, 1500, 3780, 8232, 16128, 29160, 49500, 79860, 123552, 184548, 267540, 378000, 522240, 707472, 941868, 1234620, 1596000, 2037420, 2571492, 3212088, 3974400, 4875000, 5931900, 7164612, 8594208, 10243380, 12136500

Offset: 0

Robert A. Russell, Nov 16 2018

			For a(0)=0 and  a(1)=0, there are no chiral rows using fewer than two colors. For a(2)=12, the chiral pairs are AAAAB-BAAAA, AAABA-ABAAA, AAABB-BBAAA, AABAB-BABAA, AABBA-ABBAA, AABBB-BBBAAA, ABAAB-BAABA, ABABB-BBABA, ABBAB-BABBA, ABBBB-BBBBA, BAABB-BBAAB, and BABBB-BBBAB.

Index entries for linear recurrences with constant coefficients, signature (6, -15, 20, -15, 6, -1).

Row 5 of A293500.

Cf. A000584 (oriented), A168178 (unoriented), A000578 (achiral).

Table[(n^5-n^3)/2,{n,0,40}]
LinearRecurrence[{6, -15, 20, -15, 6, -1}, {0, 0, 12, 108, 480, 1500}, 40]

a(n)=(n^5-n^3)/2 \\ Charles R Greathouse IV, Oct 21 2022

a(n) = (n^5 - n^3) / 2.
a(n) = (A000584(n) - A000578(n)) / 2.
a(n) = A000584(n) - A168178(n) = A168178(n) - A000578(n).
G.f.: (Sum_{j=1..5} S2(5,j)*j!*x^j/(1-x)^(j+1) - Sum_{j=1..3} S2(3,j)*j!*x^j/(1-x)^(j+1)) / 2, where S2 is the Stirling subset number A008277.
G.f.: x * Sum_{k=1..4} A145883(5,k) * x^k / (1-x)^6.
E.g.f.: (Sum_{k=1..5} S2(5,k)*x^k - Sum_{k=1..3} S2(3,k)*x^k) * exp(x) / 2, where S2 is the Stirling subset number A008277.
For n>5, a(n) = Sum_{j=1..6} -binomial(j-7,j) * a(n-j).

cp's OEIS Frontend

A145882 Triangle read by rows: T(n,k) is the number of even permutations of {1,2,...,n} having k descents (n >= 1, k >= 0).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A293500 Number of orientable strings of length n using a maximum of k colors, array read by descending antidiagonals, T(n,k) for n >= 1 and k >= 1.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A321672 Number of chiral pairs of rows of length 5 using up to n colors.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula