Representation of numbers by cascades
HTML articles powered by AMS MathViewer
- by C. C. Chen and D. E. Daykin PDF
- Proc. Amer. Math. Soc. 59 (1976), 394-398 Request permission
Abstract:
A cascade $C$ is defined as a sum of binomial coefficients \[ C = \left ( {\begin {array}{*{20}{c}} {{a_h}} \\ h \\ \end {array} } \right ) + \left ( {\begin {array}{*{20}{c}} {{a_{h - 1}}} \\ {h - 1} \\ \end {array} } \right ) + \cdots + \left ( {\begin {array}{*{20}{c}} {{a_t}} \\ t \\ \end {array} } \right )\] where ${a_h} > {a_{h - 1}} > \cdots > {a_t}$. In this expression, we assume that $(_h^a) = 0$ whenever $a < h$. Given a cascade $C$ and a sequence $\varepsilon = \langle {\varepsilon _h},{\varepsilon _{h - 1}}, \ldots ,{\varepsilon _t}\rangle$ of signs (i.e. ${\varepsilon _i} = + 1\;{\text {or}}\; - 1$ for each $i$), we define \[ \varepsilon C = {\varepsilon _h}\left ( {\begin {array}{*{20}{c}} {{a_h}} \\ h \\ \end {array} } \right ) + \cdots + {\varepsilon _t}\left ( {\begin {array}{*{20}{c}} {{a_t}} \\ t \\ \end {array} } \right ).\] Also, we put \[ \alpha C = \left ( {\begin {array}{*{20}{c}} {{a_h}} \\ {h + 1} \\ \end {array} } \right ) + \left ( {\begin {array}{*{20}{c}} {{a_{h - 1}}} \\ h \\ \end {array} } \right ) + \cdots + \left ( {\begin {array}{*{20}{c}} {{a_t}} \\ {t + 1} \\ \end {array} } \right ).\] In the paper, we prove that for any sequence $\langle {n_0}, {n_1}, \ldots ,{n_s}\rangle$ of integers, there exist a cascade $C$ and a corresponding sequence $\varepsilon$ of signs such that ${n_i} = \varepsilon {\alpha ^i}C$ for $i = 0,\;1, \ldots ,s$ where ${\alpha ^0}C = C,\;{\alpha ^1}C = \alpha C,\;{\alpha ^2}C = \alpha ({\alpha ^1}C)$, and recursively, ${\alpha ^n}C = \alpha ({\alpha ^{n - 1}}C)$.References
- Joseph B. Kruskal, The number of simplices in a complex, Mathematical optimization techniques, Univ. California Press, Berkeley, Calif., 1963, pp. 251–278. MR 0154827
- G. Katona, A theorem of finite sets, Theory of graphs (Proc. Colloq., Tihany, 1966) Academic Press, New York, 1968, pp. 187–207. MR 0290982
- D. E. Daykin, Jean Godfrey, and A. J. W. Hilton, Existence theorems for Sperner families, J. Combinatorial Theory Ser. A 17 (1974), 245–251. MR 416931, DOI 10.1016/0097-3165(74)90011-9
- D. E. Daykin, A simple proof of the Kruskal-Katona theorem, J. Combinatorial Theory Ser. A 17 (1974), 252–253. MR 416932, DOI 10.1016/0097-3165(74)90012-0 —, Cascade algorithms giving Katona-type inequalities, Nanta. Math. (to appear). —, The average size set in an antichain, Nanta. Math. (to appear).
Additional Information
- © Copyright 1976 American Mathematical Society
- Journal: Proc. Amer. Math. Soc. 59 (1976), 394-398
- MSC: Primary 05A17
- DOI: https://doi.org/10.1090/S0002-9939-1976-0414385-X
- MathSciNet review: 0414385