Todd Simpson - cp's OEIS frontend

User: Todd Simpson

Todd Simpson has authored 2 sequences.

A367313 Triangle read by rows: T(n,k) is the number of permutations of [n] with weighted inversion index k.

1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 2, 3, 3, 4, 3, 3, 2, 1, 1, 1, 1, 2, 3, 5, 5, 8, 9, 10, 10, 12, 10, 10, 9, 8, 5, 5, 3, 2, 1, 1, 1, 1, 2, 3, 5, 7, 9, 12, 16, 20, 23, 28, 31, 36, 38, 41, 43, 44, 44, 43, 41, 38, 36, 31, 28, 23, 20, 16, 12, 9, 7, 5, 3, 2, 1, 1

Offset: 0

Todd Simpson, Nov 13 2023

T(n,k) represents two statistics that can be shown to be equal:
(1) Permutations of {1,2,...,n} counted by a "weighted inversion index": for a permutation pi, the weighted inversion index is the sum of i over all pairs i,j with i < j and pi(i) > pi(j).
(2) Partitions lambda with at most n-1 parts counted by weight, where the inequality lambda(i) - lambda(i+1) <= n - i holds for 1 <= i < n (with lambda(n) = 0).
Possible values of this index range from 0 to (n-1)*n*(n+1)/6.  The permutation with the largest weighted inversion index is (n,n-1,...,2,1) and the partition with the largest weight is (n(n-1)/2,(n-1)(n-2)/2,...,3,1).
Let t_n(q) be the sum of T(n,k)q^k, for 0 <= k <= (n-1)*n*(n+1)/6.  Then t_n(q) is the product of (1 - q^(k*(n+1-k)))/(1 - q^k), for 1 <= k <= n-1.

			The permutation pi = (2,5,3,1,4) has these inversions, with the given contributions to weighted inversion index:
   (2,1), 1
   (5,3), 2
   (5,1), 2
   (5,4), 2
   (3,1), 3
The corresponding partition can be created as follows.  For each i <= 5, write the number of j > i with pi(i) > pi(j): (1,3,1,0,0).
For each i, the i-th number in this sequence is at most n-i.
Let lambda(i) be the sum of the values of the sequence starting with the i-th value: lambda = (5,4,1,0,0).
This permutation and partition are counted by T(5,10).  In the product expansion of t_5(q), they correspond to the following choice of terms:
   (1 - q^5)/(1 - q) = 1 + q + q^2 + q^3 + q^4:  choose q,
   (1 - q^8)/(1 - q^2) = 1 + q^2 + q^4 + q^6:  choose q^6,
   (1 - q^9)/(1 - q^3) = 1 + q^3 + q^6:  choose q^3,
   (1 - q^8)/(1 - q^4) = 1 + q^4:  choose 1.
Triangle T(n,k) begins:
  1;
  1;
  1, 1;
  1, 1, 2, 1, 1;
  1, 1, 2, 3, 3, 4, 3, 3,  2,  1,  1;
  1, 1, 2, 3, 5, 5, 8, 9, 10, 10, 12, 10, 10, 9, 8, 5, 5, 3, 2, 1, 1;
  ...

Alois P. Heinz, Rows n = 0..25, flattened

Row sums give A000142.
Row n contains A050407(n+2) terms.
T(n+1,n) gives A000041(n).
Cf. A000165, A001754, A175929.

From Alois P. Heinz, Nov 25 2023: (Start)
Sum_{k=0..A050407(n+2)-1} k * T(n,k) = A001754(n+1).
Sum_{k=0..A050407(2n+3)-1} (-1)^k * T(2n+1,k) = A000165(n). (End)

A001444 Bending a piece of wire of length n+1 (configurations that can only be brought into coincidence by turning the figure over are counted as different).

Original entry on oeis.org

1, 2, 6, 15, 45, 126, 378, 1107, 3321, 9882, 29646, 88695, 266085, 797526, 2392578, 7175547, 21526641, 64573362, 193720086, 581140575, 1743421725, 5230206126, 15690618378, 47071677987, 141215033961, 423644570442, 1270933711326, 3812799539655, 11438398618965

Offset: 0

Todd Simpson

The wire stays in the plane, there are n bends, each is R,L or O.

			There are 2 ways to bend a piece of wire of length 2 (bend it or not).
G.f. = 1 + 2*x + 6*x^2 + 15*x^3 + 45*x^4 + 126*x^5 + 378*x^6 + ...

Todd Andrew Simpson, "Combinatorial Proofs and Generalizations of Weyl's Denominator Formula", Ph. D. Dissertation, Penn State University, 1994.

Vincenzo Librandi, Table of n, a(n) for n = 0..1000
Index entries for sequences obtained by enumerating foldings
Index entries for linear recurrences with constant coefficients, signature (3,3,-9).

Cf. A001997, A001998.

Cf. A000244.

a001444 n = div (3 ^ n + 3 ^ (div n 2)) 2
-- Reinhard Zumkeller, Jun 30 2013

Maple
```
f := n->(3^floor(n/2)+3^n)/2;
```

CoefficientList[Series[(1-x-3*x^2)/((1-3*x)*(1-3*x^2)),{x,0,30}],x] (* Vincenzo Librandi, Apr 15 2012 *)
LinearRecurrence[{3,3,-9},{1,2,6},40] (* Harvey P. Dale, Dec 30 2012 *)

a(n) = (3^n + 3^floor(n/2))/2.
G.f.: G(0) where G(k) = 1 + x*(3*3^k + 1)*(1 + 3*x*G(k+1))/(1 + 3^k). - Sergei N. Gladkovskii, Dec 13 2011 [Edited by Michael Somos, Sep 09 2013]
E.g.f. E(x) = (exp(3*x)+cosh(x*sqrt(3))+sinh(x*sqrt(3))/sqrt(3))/2 = G(0); G(k) = 1 + x*(3*3^k+1)/((2*k+1)*(1+3^k) - 3*x*(2*k+1)*(1+3^k)/(3*x + (2*k+2)/G(k+1))); (continued fraction). - Sergei N. Gladkovskii, Dec 13 2011
From Colin Barker, Apr 02 2012: (Start)
a(n) = 3*a(n-1) + 3*a(n-2) - 9*a(n-3).
G.f.: x*(1-x-3*x^2)/((1-3*x)*(1-3*x^2)). (End)

Interpretation in terms of bending wire from Colin Mallows.

cp's OEIS Frontend

User: Todd Simpson

A367313 Triangle read by rows: T(n,k) is the number of permutations of [n] with weighted inversion index k.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

A001444 Bending a piece of wire of length n+1 (configurations that can only be brought into coincidence by turning the figure over are counted as different).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

Formula

Extensions