A011847 Triangle of numbers read by rows: T(n,k) = floor( C(n,k)/(k+1) ), where k=0..n-1 and n >= 1.

1, 1, 1, 1, 1, 1, 1, 2, 2, 1, 1, 2, 3, 2, 1, 1, 3, 5, 5, 3, 1, 1, 3, 7, 8, 7, 3, 1, 1, 4, 9, 14, 14, 9, 4, 1, 1, 4, 12, 21, 25, 21, 12, 4, 1, 1, 5, 15, 30, 42, 42, 30, 15, 5, 1, 1, 5, 18, 41, 66, 77, 66, 41, 18, 5, 1, 1, 6, 22, 55, 99, 132, 132, 99, 55, 22, 6, 1, 1, 6, 26, 71, 143, 214, 245, 214, 143, 71, 26, 6, 1

Offset: 1

Author

N. J. A. Sloane

Keywords

• nonn
• tabl

Comments

When k+1 is a prime >= 2, then T(n,k) = floor(C(n,k)/(k+1)) is the number of aperiodic necklaces of n+1 beads of 2 colors such that k+1 of them are black and n-k of them are white. This is not true when k+1 is a composite >= 4. For more details, see the comments for sequences A032168 and A032169. - Petros Hadjicostas, Aug 27 2018

Differs from A245558 from row n = 9, k = 4 on. - M. F. Hasler, Sep 29 2018

Examples

			Triangle begins:
  1;
  1, 1;
  1, 1,  1;
  1, 2,  2,   1;
  1, 2,  3,   2,   1;
  1, 3,  5,   5,   3,   1;
  1, 3,  7,   8,   7,   3,    1;
  1, 4,  9,  14,  14,   9,    4,    1;
  1, 4, 12,  21,  25,  21,   12,    4,    1;
  1, 5, 15,  30,  42,  42,   30,   15,    5,    1;
  1, 5, 18,  41,  66,  77,   66,   41,   18,    5,   1;
  1, 6, 22,  55,  99, 132,  132,   99,   55,   22,   6,   1;
  1, 6, 26,  71, 143, 214,  245,  214,  143,   71,  26,   6,   1;
  1, 7, 30,  91, 200, 333,  429,  429,  333,  200,  91,  30,   7,  1;
  1, 7, 35, 113, 273, 500,  715,  804,  715,  500, 273, 113,  35,  7, 1;
  1, 8, 40, 140, 364, 728, 1144, 1430, 1430, 1144, 728, 364, 140, 40, 8, 1;
...
More than the usual number of rows are shown in order to distinguish this triangle from A245558, from which it differs in rows 9, 11, 13, ....
From _Petros Hadjicostas_, Aug 27 2018: (Start)
For k+1 = 2 and n >= k+1 = 2, the n-th element of column k=1 above, [0, 1, 1, 2, 2, 3, 3, 4, 4, ...] (i.e., the number A008619(n-2) = floor(n/2)), gives the number of aperiodic necklaces of n+1 beads of 2 colors such that 2 of them are black and n-1 of them are white. (The offset of sequence A008619 is 0.)
For k+1 = 3 and n >= k+1 = 3, the n-th element of column k=2 above, [0, 0, 1, 2, 3, 5, 7, 9, 12, ...] (i.e., the number A001840(n-2) = floor(C(n,2)/3)), gives the number of aperiodic necklaces of n+1 beads of 2 colors such that 3 of them are black and n-2 of them are white. (The offset of sequence A001840 is 0.)
For k+1 = 5 and n >= k+1 = 5, the n-th element of column k=4 above, [0, 0, 0, 0, 1, 3, 7, 14, 25, 42, ... ] (i.e., the number A011795(n) = floor(C(n,4)/5)), gives the number of aperiodic necklaces of n+1 beads of 2 colors such that 5 of them are black and n-4 of them are white. (The offset of sequence A011795 is 0.)
Counterexample for k+1 = 4: It can be proved that, for n >= k+1 = 4, the number of aperiodic necklaces of n+1 beads of 2 colors such that 4 of them are black and n-3 of them are white is (1/4)*Sum_{d|4} mu(d)*I(d|n+1)*C(floor((n+1)/d) - 1, 4/d - 1) = (1/4)*(C(n, 3) - I(2|n+1)*floor((n-1)/2)), where I(a|b) = 1 if integer a divides integer b, and 0 otherwise. For n odd >= 9, the number (1/4)*(C(n, 3) - I(2|n+1)*floor((n-1)/2)) = A006918(n-3) is not equal to floor(C(n,3)/4) = A011842(n).
(End)
		

Links

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

Crossrefs

Columns include A008619, A001840, A011842, A011795, A011843, A011797, A011844, A011845, A011846, A032169.

Sums: A095718 (row), A095719 (diagonal).

Cf. A006918, A245558.

Programs

Magma

A011847:= func< n,k | Floor(Binomial(n+1,k+1)/(n+1)) >;
[A011847(n,k): k in [0..n-1], n in [1..20]]; // G. C. Greubel, Oct 20 2024

Mathematica

Table[Floor[Binomial[n,k]/(k+1)],{n,20},{k,0,n-1}]//Flatten (* Harvey P. Dale, Jan 09 2019 *)

PARI

A011847(n,k)=binomial(n,k)\(k+1) \\ M. F. Hasler, Sep 30 2018

SageMath

def A011847(n,k): return binomial(n+1,k+1)//(n+1)
flatten([[A011847(n,k) for k in range(n)] for n in range(1,21)]) # G. C. Greubel, Oct 20 2024

Formula

The rows are palindromic: T(n, k) = T(n, n-k-1) for n >= 1 and 0 <= k <= n-1.

Sum_{k=0..floor((n-1)/2)} T(n-k, k) = A095719(n). - G. C. Greubel, Oct 20 2024