A334622
A(n,k) is the sum of the k-th powers of the descent set statistics for permutations of [n]; square array A(n,k), n>=0, k>=0, read by antidiagonals.
Original entry on oeis.org
1, 1, 1, 1, 1, 2, 1, 1, 2, 4, 1, 1, 2, 6, 8, 1, 1, 2, 10, 24, 16, 1, 1, 2, 18, 88, 120, 32, 1, 1, 2, 34, 360, 1216, 720, 64, 1, 1, 2, 66, 1576, 14460, 24176, 5040, 128, 1, 1, 2, 130, 7224, 190216, 994680, 654424, 40320, 256, 1, 1, 2, 258, 34168, 2675100, 46479536, 109021500, 23136128, 362880, 512
Offset: 0
Square array A(n,k) begins:
1, 1, 1, 1, 1, 1, 1, ...
1, 1, 1, 1, 1, 1, 1, ...
2, 2, 2, 2, 2, 2, 2, ...
4, 6, 10, 18, 34, 66, 130, ...
8, 24, 88, 360, 1576, 7224, 34168, ...
16, 120, 1216, 14460, 190216, 2675100, 39333016, ...
32, 720, 24176, 994680, 46479536, 2368873800, 128235838496, ...
...
-
b:= proc(u, o, t) option remember; expand(`if`(u+o=0, 1,
add(b(u-j, o+j-1, t+1)*x^floor(2^(t-1)), j=1..u)+
add(b(u+j-1, o-j, t+1), j=1..o)))
end:
A:= (n, k)-> (p-> add(coeff(p, x, i)^k, i=0..degree(p)))(b(n, 0$2)):
seq(seq(A(n, d-n), n=0..d), d=0..10);
-
b[u_, o_, t_] := b[u, o, t] = Expand[If[u + o == 0, 1,
Sum[b[u - j, o + j - 1, t + 1] x^Floor[2^(t - 1)], {j, 1, u}] +
Sum[b[u + j - 1, o - j, t + 1], {j, 1, o}]]];
A[n_, k_] := Function[p, Sum[Coefficient[p, x, i]^k, {i, 0, Exponent[p, x]}]][b[n, 0, 0]];
Table[Table[A[n, d - n], {n, 0, d}], {d, 0, 10}] // Flatten (* Jean-François Alcover, Dec 20 2020, after Alois P. Heinz *)
A335308
Number of permutations p of [n] such that the sequence of ascents and descents of p is encoded by the 0's and 1's, respectively, in the binary expansion of n (read from right to left and using leading 0's if necessary).
Original entry on oeis.org
1, 0, 0, 1, 3, 16, 26, 20, 69, 370, 1006, 945, 1266, 3015, 2365, 1001, 4367, 24736, 76960, 69615, 138397, 322944, 286824, 133056, 159391, 546504, 978054, 674245, 531530, 957320, 495495, 142506, 906191, 5537808, 18828096, 16231039, 37000909, 81351936, 71761536
Offset: 0
a(0) = 1: (), the empty permutation.
a(3) = 1: 321 (down, down).
a(4) = 3: 1243, 1342, 2341 (up, up, down).
a(5) = 16: 21435, 21534, 31425, 31524, 32415, 32514, 41325, 41523, 42315, 42513, 43512, 51324, 51423, 52314, 52413, 53412 (down, up, down, up).
a(6) = 26: 143256, 153246, 154236, 163245, 164235, 165234, 243156, 253146, 254136, 263145, 264135, 265134, 342156, 352146, 354126, 362145, 364125, 365124, 452136, 453126, 462135, 463125, 465123, 562134, 563124, 564123 (up, down, down, up, up).
a(7) = 20: 4321567, 5321467, 5421367, 5431267, 6321457, 6421357, 6431257, 6521347, 6531247, 6541237, 7321456, 7421356, 7431256, 7521346, 7531246, 7541236, 7621345, 7631245, 7641235, 7651234 (down^3, up^3).
-
b:= proc(u, o, t) option remember; `if`(u+o=0, `if`(t=0, 1, 0),
`if`(irem(t, 2)=0, add(b(u-j, o+j-1, iquo(t, 2)), j=1..u),
add(b(u+j-1, o-j, iquo(t, 2)), j=1..o)))
end:
a:= n-> b(n, 0, 2*n):
seq(a(n), n=0..42);
A291903
Sums of the fourth powers of the descent set statistics for permutations on n elements.
Original entry on oeis.org
1, 1, 2, 34, 1576, 190216, 46479536, 21246061600, 16505196258944, 20569621110703360, 39048520577674054912, 108556407221350072075840, 427386074980323385950161920, 2317659324414032887611600999424, 16904848426143946143993568391307264, 162490636486997482412425606460112242944, 2021898321663894965658036079204603050491904
Offset: 0
For n=4, we have a(4) = 1^4 + 3^4 + 5^4 + 3^4 + 3^4 + 5^4 + 3^4 + 1^4 = 1576.
A334623
Sum of the n-th powers of the descent set statistics for permutations of [n].
Original entry on oeis.org
1, 1, 2, 18, 1576, 2675100, 128235838496, 265039489112493900, 31306198216486969509375104, 278983981168082455883720325976751040, 235157286166918393786165504356030195355598048512, 23075317400822150539572583950910707053701314350537805923757600
Offset: 0
-
b:= proc(u, o, t) option remember; expand(`if`(u+o=0, 1,
add(b(u-j, o+j-1, t+1)*x^floor(2^(t-1)), j=1..u)+
add(b(u+j-1, o-j, t+1), j=1..o)))
end:
a:= n-> (p-> add(coeff(p, x, i)^n, i=0..degree(p)))(b(n, 0$2)):
seq(a(n), n=0..12);
-
b[u_, o_, t_] := b[u, o, t] = Expand[If[u + o == 0, 1,
Sum[b[u - j, o + j - 1, t + 1]*x^Floor[2^(t - 1)], {j, 1, u}] +
Sum[b[u + j - 1, o - j, t + 1], {j, 1, o}]]];
a[n_] := Function[p, Sum[Coefficient[p, x, i]^n, {i, 0, Exponent[p, x]}]][ b[n, 0, 0]];
a /@ Range[0, 12] (* Jean-François Alcover, Dec 20 2020, after Alois P. Heinz *)
A335845
Irregular triangular array T(n,k) read by rows. Row n gives the number of permutations of {1,2,...,n} whose descent set is S for each subset S of {1,2,...,n-1} ordered lexicographically within the rows.
Original entry on oeis.org
1, 1, 1, 1, 1, 2, 2, 1, 1, 3, 5, 3, 3, 5, 3, 1, 1, 4, 9, 9, 4, 6, 16, 11, 11, 16, 6, 4, 9, 9, 4, 1, 1, 5, 14, 19, 14, 5, 10, 35, 40, 19, 26, 61, 40, 26, 35, 10, 10, 35, 26, 40, 61, 26, 19, 40, 35, 10, 5, 14, 19, 14, 5, 1, 1, 6, 20, 34, 34, 20, 6, 15, 64, 99
Offset: 0
T(5,5) = 6 because there are 6 permutations of [5] whose descent set is {1,2}: (3,2,1,4,5), (4,2,1,3,5), (4,3,1,2,5), (5,2,1,3,4), (5,3,1,2,4), (5,4,1,2,3).
Triangle T(n,k) begins:
1;
1;
1, 1;
1, 2, 2, 1;
1, 3, 5, 3, 3, 5, 3, 1;
1, 4, 9, 9, 4, 6, 16, 11, 11, 16, 6, 4, 9, 9, 4, 1;
...
-
T:= proc(n) option remember; local b, i, l; l:=
map(x-> add(2^(i-1), i=x), [seq(combinat[choose](
[$1..n-1], i)[], i=0..n-1)]); h(0):=0;
for i to nops(l) do h(l[i]):= (i-1) od: b:=
proc(u, o, t) option remember; `if`(u+o=0, x^h(t),
add(b(u-j, o+j-1, t), j=1..u)+
add(b(u+j-1, o-j, t+2^(u+o-1)), j=1..o))
end; (p->
seq(coeff(p, x, i), i=0..degree(p)))(b(n, 0$2))
end:
seq(T(n), n=0..7); # Alois P. Heinz, Feb 03 2023
-
f[list_] := (-1)^(Length[list] + 1) Apply[Multinomial, list];
Table[g[S_] :=Abs[Total[Map[f, Map[Differences,Map[Prepend[#, 0] &, Map[Append[#, n] &, Subsets[S]]]]]]];Map[g, Subsets[Range[n - 1]]], {n, 1, 5}] // Grid
A357611
A refinement of the Mahonian numbers (canonical ordering).
Original entry on oeis.org
1, 1, 1, 1, 2, 2, 1, 1, 3, 5, 3, 3, 5, 3, 1, 1, 4, 9, 9, 6, 4, 16, 11, 11, 16, 4, 6, 9, 9, 4, 1, 1, 5, 14, 19, 10, 14, 35, 5, 40, 26, 19, 61, 10, 40, 26, 35, 35, 26, 40, 10, 61, 19, 26, 40, 5, 35, 14, 10, 19, 14, 5, 1
Offset: 1
The first nontrivial terms in the sequence are a(11) = a(12) = 3, corresponding to the refinement T(4, 3) = 6 = 3 + 3. The terms from a(1) to a(10) are the Mahonian numbers themselves, because the refinement is trivial for them (there is only one partition satisfying the given constraints).
Specifically, the row T(N, d) with N=4 and d=3 corresponds to Young ribbon diagrams with 4 cells such that the sum of the row indices of cells (with the top row having index 0) is equal to 3. There are two such diagrams:
(A) ## (B) #
# ###
#
3 = 2+1+0+0 = 1+1+1+0 are the corresponding integer partitions, which are referenced in the Comments section, listed in the lexicographic order. These partitions have descent sets (indices of elements followed by a smaller element) {1,2} and {3}, respectively (they both sum up to 3, necessarily).
Diagram (A) can be filled in as a standard Young diagram in 3 ways:
12 14 13
3 2 2
4 3 4
Diagram (B) can be filled in in 3 ways, too:
2 3 1
134 124 234
Thus, the row T(4, 3) is 3, 3. These standard Young ribbon diagrams, when read bottom-left to top-right, become permutations of 1234 with major index 3, namely 4312, 3214, 4213 with the descent set {1,2} and 1342, 1243, 2341 with the descent set {3} (same descent sets as those of the corresponding partitions!).
The data in triangular form are:
N, d
1, 0 1,
2, 1 1,
0 1,
3, 3 1,
2 2,
1 2,
0 1,
4, 6 1,
5 3,
4 5,
3 3, 3,
2 5,
1 3,
0 1,
5,10 1,
9 4,
8 9,
7 9, 6,
6 4, 16,
5 11, 11,
4 16, 4,
3 6, 9,
2 9,
1 4,
0 1,
6,15 1,
14 5,
13 14,
12 19, 10,
11 14, 35,
10 5, 40, 26,
9 19, 61, 10,
8 40, 26, 35,
7 35, 26, 40,
6 10, 61, 19,
5 26, 40, 5,
4 35, 14,
3 10, 19,
2 14,
1 5,
0 1
One can check the generating function for the number of terms in a row, e.g., for N = 4: (1 + q)(1 + q^2)(1 + q^3) = q^6 + q^5 + q^4 + 2q^3 + q^2 + q + 1.
-
def possible_classes(n, degree):
for stub in Partitions(degree, max_part = n-1, max_length = n-1, min_slope = -1):
cls = list(stub)
if cls:
if cls[-1] < 2:
yield cls + (n - len(cls)) * [0]
else:
yield n * [0]
#
def count_tableaux(cls):
inner = []
outer = [1]
right = 1
previous_part = cls[0]
for part in cls[1:]:
if part == previous_part:
right += 1
outer[-1] = right
else:
previous_part = part
outer += [right]
if right > 1:
inner += [right-1]
outer.reverse()
inner.reverse()
return StandardSkewTableaux([outer, inner]).cardinality()
#
def refine_mahonian(N, d, total = False):
"""
Eq. (50) in DOI:10.48550/arXiv.2209.02523 was
generated by the call refine_mahonian(8, 16, True).
"""
res = []
for cls in possible_classes(N,d):
res += [count_tableaux(cls)]
if total:
res = (res, sum(res)) # the sum should be T(N, d)
return res
#
def refine_mahonians_table(Nmax, total = False, canonical = True):
res = []
for N in range(1, Nmax + 1):
r = []
if canonical:
ordering = range(N * (N - 1) // 2, -1, -1)
else:
ordering = range(N * (N - 1) // 2 + 1)
for d in ordering:
r += [refine_mahonian(N, d, total = total)]
res += [r]
return res
#
def refine_mahonians(Nmax, canonical = True):
"""
Nmax = 6, canonical = True gives seq. A357611 in the OEIS.
Nmax = 6, canonical = False gives seq. A356802 in the OEIS.
"""
return flatten(refine_mahonians_table(Nmax, total = False, canonical = canonical))
-
from collections import Counter
def part(n, descents):
r = tuple(sum(i <= d for d in descents) for i in (1..n))
return (sum(r), r) # replace sum(r) by -sum(r) to obtain A356802 instead
def row(n):
return [x[1] for x in sorted(Counter((part(n, p.descents()) for p in Permutations(n))).items())]
print(sum([row(n) for n in (1..6)], [])) # Andrey Zabolotskiy, Oct 19 2024
A291902
Sums of the cubes of the descent set statistics for permutations on n elements.
Original entry on oeis.org
1, 1, 2, 18, 360, 14460, 994680, 109021500, 17815754880, 4147063256448, 1323985303267200, 562636176102554400, 310405397451855552000, 217731000904433587359360, 190749857434239995742090240, 205540893695782384696324368000, 268793206446238988670401236992000
Offset: 0
For n=4, we have a(4) = 1^3 + 3^3 + 5^5 + 3^3 + 3^3 + 5^3 + 3^3 + 1^3 = 360.
A368070
a(n) is the number of sequences of binary words (w_1, ..., w_k) such that w_1 corresponds to the binary expansion of n (without leading zeros), for m = 1..k-1, w_{m+1} is obtained by removing one bit from w_m, and w_k is the empty word.
Original entry on oeis.org
1, 1, 2, 1, 3, 5, 3, 1, 4, 11, 16, 9, 6, 9, 4, 1, 5, 19, 40, 26, 35, 61, 40, 14, 10, 26, 35, 19, 10, 14, 5, 1, 6, 29, 78, 55, 99, 181, 132, 50, 64, 181, 272, 155, 111, 169, 78, 20, 15, 55, 111, 71, 90, 155, 99, 34, 20, 50, 64, 34, 15, 20, 6, 1, 7, 41, 133, 99
Offset: 0
For n = 5:
- the binary expansion of 5 is "101",
- we have the following appropriate sequences of binary words:
("101", "11", "1", "")
("101", "10", "1", "")
("101", "10", "0", "")
("101", "01", "1", "")
("101", "01", "0", "")
- hence a(5) = 5.
-
\\ See Links section.
-
def A368070(n):
m=0
r=[1]
for k in range(n.bit_length()):
if m!=(m:=n>>k&1): r=r[::-1]
for j in range(k): r[j+1]+=r[j]
r.insert(0,0)
return sum(r) # Natalia L. Skirrow, Apr 20 2025
-
from fractions import Fraction as frac
inte=lambda p: [0]+[frac(c,i+1) for i,c in enumerate(p)]
from math import factorial as fact
def A368070(n):
r=[1]
for k in range(n.bit_length()):
i=inte(r)
r=i if n>>k&1 else [sum(i)]+[-c for c in i[1:]]
return int(fact(n.bit_length()+1)*sum(inte(r)))
#without the multiplication, this is the probability that a sequence of real numbers in [0,1] satisfies the chain of inequalities. # Natalia L. Skirrow, Apr 20 2025
A360308
Number T(n,k) of permutations of [n] whose descent set is the k-th finite subset of positive integers in Gray order; triangle T(n,k), n>=0, 0<=k<=ceiling(2^(n-1))-1, read by rows.
Original entry on oeis.org
1, 1, 1, 1, 1, 2, 1, 2, 1, 3, 3, 5, 3, 1, 5, 3, 1, 4, 6, 9, 11, 4, 16, 9, 6, 9, 1, 4, 16, 9, 11, 4, 1, 5, 10, 14, 26, 10, 35, 19, 26, 40, 5, 19, 61, 35, 40, 14, 10, 26, 19, 35, 5, 1, 14, 10, 35, 61, 14, 40, 40, 26, 19, 5, 1, 6, 15, 20, 50, 20, 64, 34, 71, 111
Offset: 0
T(5,5) = 4: there are 4 permutations of [5] with descent set {1,2,3} (the 5th subset in Gray order): 43215, 53214, 54213, 54312.
Triangle T(n,k) begins:
1;
1;
1, 1;
1, 2, 1, 2;
1, 3, 3, 5, 3, 1, 5, 3;
1, 4, 6, 9, 11, 4, 16, 9, 6, 9, 1, 4, 16, 9, 11, 4;
...
-
a:= proc(n) a(n):= `if`(n<2, n, Bits[Xor](n, a(iquo(n, 2)))) end:
b:= proc(u, o, t) option remember; `if`(u+o=0, x^a(t),
add(b(u-j, o+j-1, t), j=1..u)+
add(b(u+j-1, o-j, t+2^(o+u-1)), j=1..o))
end:
T:= n-> (p-> seq(coeff(p, x, i), i=0..degree(p)))(b(n, 0$2)):
seq(T(n), n=0..7);
-
a[n_] := a[n] = If[n<2, n, BitXor[n, a[Quotient[n, 2] ]]];
b[u_, o_, t_] := b[u, o, t] = If[u + o == 0, x^a[t], Sum[b[u - j, o + j - 1, t], {j, 1, u}] + Sum[b[u + j - 1, o - j, t + 2^(o + u - 1)], {j, 1, o}]];
T[n_] := CoefficientList[b[n, 0, 0], x];
Table[T[n], {n, 0, 7}] // Flatten (* Jean-François Alcover, Feb 14 2023, after Alois P. Heinz *)
A367019
a(n) is the number of strictly decreasing sequences (w_1, ..., w_k) such that w_1 = n, for m = 1..k-1, w_{m+1} is obtained by removing one significant binary digit from w_m, and w_k = 0.
Original entry on oeis.org
1, 1, 2, 1, 3, 4, 3, 1, 4, 8, 12, 6, 6, 8, 4, 1, 5, 13, 26, 15, 25, 38, 25, 8, 10, 22, 30, 15, 10, 13, 5, 1, 6, 19, 46, 29, 59, 96, 69, 24, 44, 106, 156, 82, 66, 92, 42, 10, 15, 45, 88, 52, 75, 118, 75, 24, 20, 45, 58, 29, 15, 19, 6, 1, 7, 26, 73, 49, 114, 194
Offset: 0
For n = 5:
- the binary expansion of 5 is "101",
- we have the following appropriate sequences:
(5, 3, 1, 0)
(5, 2, 1, 0)
(5, 2, 0)
(5, 1, 0)
- hence a(5) = 4.
Comments