A132753 -id:A132753 - cp's OEIS frontend

A228196 A triangle formed like Pascal's triangle, but with n^2 on the left border and 2^n on the right border instead of 1.

0, 1, 2, 4, 3, 4, 9, 7, 7, 8, 16, 16, 14, 15, 16, 25, 32, 30, 29, 31, 32, 36, 57, 62, 59, 60, 63, 64, 49, 93, 119, 121, 119, 123, 127, 128, 64, 142, 212, 240, 240, 242, 250, 255, 256, 81, 206, 354, 452, 480, 482, 492, 505, 511, 512, 100, 287, 560, 806, 932, 962, 974, 997, 1016, 1023, 1024

Offset: 1

Boris Putievskiy, Aug 15 2013

The third row is (n^4 - n^2 + 24*n + 24)/12.

For a closed-form formula for generalized Pascal's triangle see A228576. - Boris Putievskiy, Sep 04 2013

			The start of the sequence as a triangular array read by rows:
   0;
   1,  2;
   4,  3,  4;
   9,  7,  7,  8;
  16, 16, 14, 15, 16;
  25, 32, 30, 29, 31, 32;
  36, 57, 62, 59, 60, 63, 64;

Boris Putievskiy, Rows n = 1..140 of triangle, flattened
Rely Pellicer and David Alvo, Modified Pascal Triangle and Pascal Surfaces p.4
Index entries for triangles and arrays related to Pascal's triangle

Cf. We denote Pascal-like triangle with L(n) on the left border and R(n) on the right border by (L(n),R(n)). A007318 (1,1), A008949 (1,2^n), A029600 (2,3), A029618 (3,2), A029635 (1,2), A029653 (2,1), A037027 (Fibonacci(n),1), A051601 (n,n) n>=0, A051597 (n,n) n>0, A051666 (n^2,n^2), A071919 (1,0), A074829 (Fibonacci(n), Fibonacci(n)), A074909 (1,n), A093560 (3,1), A093561 (4,1), A093562 (5,1), A093563 (6,1), A093564 (7,1), A093565 (8,1), A093644 (9,1), A093645 (10,1), A095660 (1,3), A095666 (1,4), A096940 (1,5), A096956 (1,6), A106516 (3^n,1), A108561(1,(-1)^n), A132200 (4,4), A134636 (2n+1,2n+1), A137688 (2^n,2^n), A160760 (3^(n-1),1), A164844(1,10^n), A164847 (100^n,1), A164855 (101*100^n,1), A164866 (101^n,1), A172171 (1,9), A172185 (9,11), A172283 (-9,11), A177954 (int(n/2),1), A193820 (1,2^n), A214292 (n,-n), A227074 (4^n,4^n), A227075 (3^n,3^n), A227076 (5^n,5^n), A227550 (n!,n!), A228053 ((-1)^n,(-1)^n), A228074 (Fibonacci(n), n).

Cf. A000290 (row 1), A153056 (row 2), A000079 (column 1), A000225 (column 2), A132753 (column 3), A118885 (row sums of triangle array + 1), A228576 (generalized Pascal's triangle).

T:= function(n,k)
    if k=0 then return n^2;
    elif k=n then return 2^n;
    else return T(n-1,k-1) + T(n-1,k);
    fi;
  end;
Flat(List([0..12], n-> List([0..n], k-> T(n,k) ))); # G. C. Greubel, Nov 12 2019

T:= proc(n, k) option remember;
      if k=0 then n^2
    elif k=n then 2^k
    else T(n-1, k-1) + T(n-1, k)
      fi
    end:
seq(seq(T(n, k), k=0..n), n=0..10); # G. C. Greubel, Nov 12 2019

T[n_, k_]:= T[n, k] = If[k==0, n^2, If[k==n, 2^k, T[n-1, k-1] + T[n-1, k]]]; Table[T[n, k], {n,0,10}, {k,0,n}]//Flatten (* G. C. Greubel, Nov 12 2019 *)
Flatten[Table[Sum[i^2 Binomial[n-1-i, n-k-i], {i,1,n-k}] + Sum[2^i Binomial[n-1-i, k-i], {i,1,k}], {n,0,10}, {k,0,n}]] (* Greg Dresden, Aug 06 2022 *)

T(n,k) = if(k==0, n^2, if(k==n, 2^k, T(n-1, k-1) + T(n-1, k) )); \\ G. C. Greubel, Nov 12 2019

def funcL(n):
   q = n**2
   return q
def funcR(n):
   q = 2**n
   return q
for n in range (1,9871):
   t=int((math.sqrt(8*n-7) - 1)/ 2)
   i=n-t*(t+1)/2-1
   j=(t*t+3*t+4)/2-n-1
   sum1=0
   sum2=0
   for m1 in range (1,i+1):
      sum1=sum1+funcR(m1)*binomial(i+j-m1-1,i-m1)
   for m2 in range (1,j+1):
      sum2=sum2+funcL(m2)*binomial(i+j-m2-1,j-m2)
   sum=sum1+sum2

@CachedFunction
def T(n, k):
    if (k==0): return n^2
    elif (k==n): return 2^n
    else: return T(n-1, k-1) + T(n-1, k)
[[T(n, k) for k in (0..n)] for n in (0..12)] # G. C. Greubel, Nov 12 2019

T(n,0) = n^2, n>0; T(0,k) = 2^k; T(n, k) = T(n-1, k-1) + T(n-1, k) for n,k > 0. [corrected by G. C. Greubel, Nov 12 2019]
Closed-form formula for general case. Let L(m) and R(m) be the left border and the right border of Pascal like triangle, respectively. We denote binomial(n,k) by C(n,k).
As table read by antidiagonals T(n,k) = Sum_{m1=1..n} R(m1)*C(n+k-m1-1, n-m1) + Sum_{m2=1..k} L(m2)*C(n+k-m2-1, k-m2); n,k >=0.
As linear sequence a(n) = Sum_{m1=1..i} R(m1)*C(i+j-m1-1, i-m1) + Sum_{m2=1..j} L(m2)*C(i+j-m2-1, j-m2), where i=n-t*(t+1)/2-1, j=(t*t+3*t+4)/2-n-1, t=floor((-1+sqrt(8*n-7))/2); n>0.
Some special cases. If L(m)={b,b,b...} b*A000012, then the second sum takes form b*C(n+k-1,j). If L(m) is {0,b,2b,...} b*A001477, then the second sum takes form b*C(n+k,n-1). Similarly for R(m) and the first sum.
For this sequence L(m)=m^2 and R(m)=2^m.
As table read by antidiagonals T(n,k) = Sum_{m1=1..n} (2^m1)*C(n+k-m1-1, n-m1) + Sum_{m2=1..k} (m2^2)*C(n+k-m2-1, k-m2); n,k >=0.
As linear sequence a(n) = Sum_{m1=1..i} (2^m1)*C(i+j-m1-1, i-m1) + Sum_{m2=1..j} (m2^2)*C(i+j-m2-1, j-m2), where i=n-t*(t+1)/2-1, j=(t*t+3*t+4)/2-n-1, t=floor((-1+sqrt(8*n-7))/2).
As a triangular array read by rows, T(n,k) = Sum_{i=1..n-k} i^2*C(n-1-i, n-k-i) + Sum_{i=1..k} 2^i*C(n-1-i, k-i); n,k >=0. - Greg Dresden, Aug 06 2022

Cross-references corrected and extended by Philippe Deléham, Dec 27 2013

A357961 a(1) = 1, and for any n > 0, a(n+1) is the k-th positive number not yet in the sequence, where k is the Hamming weight of a(n).

Original entry on oeis.org

1, 2, 3, 5, 6, 7, 9, 8, 4, 10, 12, 13, 15, 17, 14, 18, 16, 11, 21, 22, 23, 25, 24, 20, 26, 28, 29, 31, 33, 27, 34, 30, 36, 32, 19, 38, 39, 41, 40, 37, 43, 45, 46, 47, 49, 44, 48, 42, 51, 53, 54, 55, 57, 56, 52, 58, 60, 61, 63, 65, 50, 62, 67, 64, 35, 68, 66

Offset: 1

Rémy Sigrist, Oct 22 2022

This sequence is a permutation of the positive integers:
- Let e = A000523 and w = A000120.
- Lemma: a(n) <= n + e(n)
    - This property is true for n = 1.
    - Assume that a(n) <= n + e(n) for some n >= 1.
    - Then a(n+1) <= n + w(a(n))
                  <= n + e(a(n))
                  <= n + e(n + e(n))
                  <= n + e(2*n)
                  <= n + 1 + e(n)
                  <= n + 1 + e(n + 1) - QED.
- If this sequence is not a permutation, then some number is missing.
- Let v be the least number that does not appear in the sequence.
- At some point, v is the least number not yet in the sequence.
- From now on, powers of 2 can no longer appear in the sequence.
- So there are infinitely many numbers that do not appear in the sequence.
- Let w be the least number > v that does not appear in the sequence.
- At some point, v and w are the two least numbers not yet in the sequence.
- Say this happens after m terms and max(a(1), ..., a(m)) < 2^k (with k > 0).
- From now on, powers of 2 and sums of two powers of 2 can no longer appear.
- So the numbers 2^k, 2^k + 2^i where i = 0..k-1 won't appear,
  and the numbers 2^(k+1), 2^(k+1) + 2^i where i = 0..k won't appear.
- So among the first 2^(k+2) terms, by the pigeonhole principle,
  we necessarily have a term a(n) >= 2^(k+2) + 2*k + 3.
- But we also know that a(n) <= 2^(k+2) + e(2^(k+2)) = 2^(k+2) + k + 2.
- This is a contradiction - QED.
Conjecture: this permutation has only finite cycles because it appears that for each interval a(1..2^m) the maximal observed displacement is smaller than 2^m and this maximal displacement is realized by only one element in this interval for m > 3. - Thomas Scheuerle, Oct 22 2022

			The first terms, alongside their Hamming weight and the values not yet in the sequence so far, are:
  n   a(n)  A000120(a(n))  values not yet in the sequence
  --  ----  -------------  ---------------------------------------------
   1     1              1  { 2,  3,  4,  5,  6,  7,  8,  9, 10, 11, ...}
   2     2              1  { 3,  4,  5,  6,  7,  8,  9, 10, 11, 12, ...}
   3     3              2  { 4,  5,  6,  7,  8,  9, 10, 11, 12, 13, ...}
   4     5              2  { 4,  6,  7,  8,  9, 10, 11, 12, 13, 14, ...}
   5     6              2  { 4,  7,  8,  9, 10, 11, 12, 13, 14, 15, ...}
   6     7              3  { 4,  8,  9, 10, 11, 12, 13, 14, 15, 16, ...}
   7     9              2  { 4,  8, 10, 11, 12, 13, 14, 15, 16, 17, ...}
   8     8              1  { 4, 10, 11, 12, 13, 14, 15, 16, 17, 18, ...}
   9     4              1  {10, 11, 12, 13, 14, 15, 16, 17, 18, 19, ...}
  10    10              2  {11, 12, 13, 14, 15, 16, 17, 18, 19, 20, ...}
  11    12              2  {11, 13, 14, 15, 16, 17, 18, 19, 20, 21, ...}
  12    13              3  {11, 14, 15, 16, 17, 18, 19, 20, 21, 22, ...}
  13    15              4  {11, 14, 16, 17, 18, 19, 20, 21, 22, 23, ...}
  14    17              2  {11, 14, 16, 18, 19, 20, 21, 22, 23, 24, ...}
  15    14              3  {11, 16, 18, 19, 20, 21, 22, 23, 24, 25, ...}
  16    18              2  {11, 16, 19, 20, 21, 22, 23, 24, 25, 26, ...}

Rémy Sigrist, Table of n, a(n) for n = 1..10000
Thomas Scheuerle, Scatter plot of log_2(2^4 + n - a(n)) for n = 1..10000
Rémy Sigrist, PARI program
Index entries for sequences that are permutations of the natural numbers

Cf. A000120, A000523, A132753, A217122, A357993, A358057 (inverse).

function a = A357961( max_n )
    a = 1;
    num = [2:max_n*floor(log2(max_n))];
    for n = 2:max_n
        k = num(length(find(bitget(a(n-1),1:64)==1)));
        a(n) = k; num(num == k) = [];
    end
end % Thomas Scheuerle, Oct 22 2022

PARI
```
See Links section.
```

a(n) <= n + A000523(n).

Empirically: a(n) = n + A000523(n) iff n = 1 or n belong to A132753 \ {3, 4}.

A132752 Triangle T(n, k) = 2*A132749(n, k) - 1, read by rows.

Original entry on oeis.org

1, 3, 1, 3, 3, 1, 3, 5, 5, 1, 3, 7, 11, 7, 1, 3, 9, 19, 19, 9, 1, 3, 11, 29, 39, 29, 11, 1, 3, 13, 41, 69, 69, 41, 13, 1, 3, 15, 55, 111, 139, 111, 55, 15, 1, 3, 17, 71, 167, 251, 251, 167, 71, 17, 1

Offset: 0

Gary W. Adamson, Aug 28 2007

			First few rows of the triangle are:
  1;
  3,  1;
  3,  3,  1;
  3,  5,  5,  1;
  3,  7, 11,  7,  1;
  3,  9, 19, 19,  9,  1;
  3, 11, 29, 39, 29, 11, 1;
  ...

G. C. Greubel, Rows n = 0..100 of the triangle, flattened

Cf. A109128, A132749, A132753.

A132752:= func< n,k | k eq n select 1 else k eq 0 select 3 else 2*Binomial(n,k) -1 >;
[A132752(n,k): k in [0..n], n in [0..12]]; // G. C. Greubel, Feb 16 2021

T[n_, k_]:= If[k==n, 1, If[k==0, 3, 2*Binomial[n, k] -1 ]];
Table[T[n, k], {n,0,12}, {k,0,n}]//Flatten (* G. C. Greubel, Feb 16 2021 *)

def A132752(n,k): return 1 if k==n else 3 if k==0 else 2*binomial(n,k) -1
flatten([[A132752(n,k) for k in [0..n]] for n in [0..12]]) # G. C. Greubel, Feb 16 2021

T(n, k) = 2*A132749(n, k) - 1, an infinite lower triangular matrix.
From G. C. Greubel, Feb 16 2021: (Start)
T(n, k) = A109128(n, k) with T(n, 0) = 3.
Sum_{k=0..n} T(n, k) = 2^(n+1) -n +1 -2*[n=0] = A132753(n) - 2*[n=0]. (End)

cp's OEIS Frontend

A228196 A triangle formed like Pascal's triangle, but with n^2 on the left border and 2^n on the right border instead of 1.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

GAP

Maple

Mathematica

PARI

Python

Sage

Formula

Extensions

A357961 a(1) = 1, and for any n > 0, a(n+1) is the k-th positive number not yet in the sequence, where k is the Hamming weight of a(n).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

MATLAB

PARI

Formula

A132752 Triangle T(n, k) = 2*A132749(n, k) - 1, read by rows.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Magma

Mathematica

Sage

Formula