0
votes
0answers
116 views

a question on sum of Gaussian binomial coefficients

I was trying to calculate something and at some point I get the following sum: \begin{equation} \sum_{t=0,t \text{ even}}^{s}{s+3n \brack s-t}\sum_{i = 0}^{t/2}q^{2i^2}{t/2+2n-i \brack t/2-i}{n ...
16
votes
2answers
343 views

Shortest supersequence of all permutations of $n$ elements

Given an alphabet with $n$ characters, what is the shortest sequence that contains all $n!$ permutations as subsequences? A subsequence can be obtained from a sequence by deleting any characters, ...
17
votes
3answers
2k views

Where in mathematics do these polynomials appear?

Does anyone recognize the following sequence of polynomials? $f_0(x) = x-1$ $f_1(x) = x^2-x$ $f_2(x) = x^4-2x^2+x$ $f_3(x) = x^8-3x^4+3x^2-x$ $f_4(x) = x^{16}-4x^8+6x^4-4x^2+x$ $\vdots$ The ...
-1
votes
1answer
243 views

Does anyone recognize this generating function [closed]

$a_1=1, a_2=1, a_3=3, a_4=15, a_5=105$ Reccurence formula is $a_{k+1}=\sum\limits_{\lambda_1+\lambda_2+\ldots+\lambda_s=k,\ \lambda_i\geq1} a_{\lambda_1}a_{\lambda_2}...a_{\lambda_s}{k \choose ...
-2
votes
1answer
79 views

Monotonic sequence (edited) [closed]

For any two n-dim vector $v$ and $v'$ define $v\leq v'$ iff for each $1\leq i\leq n$, $v_i\leq v_i'$. Suppose further that the entry of vectors can only take values from $m$ distinct values $\{a_1, ...
0
votes
0answers
82 views

Usage of multinomial theorem with infinite series

What are the conditions for using the multinomial theorem with infinite series? I have an expression but I don't know if I can use it. The expression is: $$ \left[\sum_{m=0}^{\infty} \frac{\mu^m ...
2
votes
2answers
307 views

Asymptotic behaviour of sequence

I am interested in the sequence $$a(n)=\sum_{k=0}^n {p(n-k) \choose k}$$ where $p(n)$ is a polynomial equation. When $p(n)=n$ this reduces to the Fibonacci sequence, but what about when $p(n)$ is ...
0
votes
0answers
100 views

Multivariate generating function

I am investigating the perturbation of the Jordan canonical form. In my work I must calculate the number of ways to factor $p^ {n-k} q^k$ where $p$ and $q$ are distinct primes ...
3
votes
1answer
193 views

A question on graphic sequences

Let $G$ be a graph and $d_{G}(u)$ denotes degree of a vertex $u$ in $G$. Consider the next multiset $$M_{G}:=\{|d_{G}(u)-d_{G}(v)|:\ uv\in E(G)\}.$$ Conjecture: $M_{G}$ is graphical for every $G$. ...
38
votes
2answers
1k views

Numbers that are generic w.r.t. exponentiation

This is a follow-up to my old question Number of distinct values taken by $x\hat{\phantom{\hat{}}}x\hat{\phantom{\hat{}}}\dots\hat{\phantom{\hat{}}}x$ with parentheses inserted in all possible ways. ...
12
votes
0answers
512 views

How to explain the picturesque patterns in François Brunault's matrix?

How to explain the patterns in the matrix defined in François Brunault's answer to the question Freeness of a Z[x] module depicted below? -- Choosing colors according to the highest power of 2 which ...
5
votes
0answers
328 views

Number of Configurations in the optimal Hanoi tower

There is a unique strategy how to move $n$ disks from the first rod to the second optimally and it takes $2^n-1$ steps, solution is obtained by simple recursion. I am interested into the following ...
3
votes
0answers
258 views

Convolution inverse of recursively defined sequence is alternating

Consider the double sequence $A(n,k)$ which is recursively defined by $$A(n,n)=1 \text{ for } n=0,1,2,\dots \text{ and }$$ $$A(n,k)=2\sum_{l=1}^{k+1} \binom{2n+1}{2l} A(n-l,k+1-l) \text{ for }0\leq k ...
6
votes
1answer
959 views

Cycling through the Zeta Garden: Zeta functions for graphs, cycle index polynomials, and determinants

Zeta functions abound in mathematics. Audrey Terras describes in Zeta Functions and Chaos three zeta functions--the zeta fct. of a projective non-singular algebraic variety; the Artin-Mazur zeta ...
4
votes
2answers
673 views

series expansion of the q-Pochhammer symbol

The following identity arose while I was working on a recent MO question: $-\sum_{n=1}^{\infty}\frac{1}{n}\frac{(-x)^n}{1-x^n}=\sum_{n=1}^{\infty}\frac{1}{n}\frac{x^n}{1-x^{2n}}.$ I have no doubt ...
1
vote
1answer
283 views

Maximal difference between k randomly drawn numbers from 1 to n – Looking for formula to sequence

Hello! I have an interesting problem that seemed simple to me, but I'm unable to solve it on my own. Suppose I am drawing k numbers out of n numbers labeled from 1 to n. Considering all ...
1
vote
2answers
372 views

Converting a recursive definition to an explicit one

Is there an explicit form for $a_x$ (whole numbers x) given that $a_x = \displaystyle\sum_{i=1}^{x-1} \binom{x-1}{i} a_i$? I've listed out the first few terms: for $x=0,1,2,3,4,5,6, 7$ we have $a_x ...
6
votes
2answers
294 views

Equidecomposable graphs, unimodality and asymptotics

I will call two graphs $G$ and $H$, $r$-equidecomposable (in analogy with Hilbert's third problem) if they can be written as unions of disjoint subgraphs $$G\cong \bigsqcup_{i=1}^r G_i\quad ,\quad ...
4
votes
1answer
2k views

sum calculation

I would like to calculate, or bound from above, the following sum $$ \sum_{i=0}^n(n-2i)^p{p \choose i}, $$ here $p\geq 2$. Any references are very welcome. Thank you.
2
votes
0answers
366 views

How to calculate/approximate expectation of function of a binomial random variable?

Hi, I am stuck at following problem in my research. Suppose that $M=m$ is a random variable with binomial distribution with parameters $n,p$. The constants $r$ and $\gamma$ are greater than zero. ...
2
votes
1answer
304 views

differential operator power coefficients

Let $(F(x)\frac{d}{dx})^n=\sum_{i=1}^n H_{n,i}(F, F', F^{(2)}, \ldots , F^{(n)})\frac{d^i}{dx^i}$. I'm curious about the exact formula for $H_{n,i}(y_0, y_1, \ldots , y_n)$. What is known about it?
6
votes
2answers
748 views

Is there a combinatorial interpretation of this triangle sequence? Is there a “simpler” formula?

Hi. I was wondering about this. I've got this triangle sequence: $$a_{n,k} = \sum_{1 = m_1 < m_2 < \cdots < m_k = n}\ \prod_{j=2}^k S(m_j, m_{j-1})$$. where the $S(n, k)$ are Stirling ...
4
votes
0answers
193 views

Number of times lead changes in a multi-candidate election (reference-request)

In a two candidate election where votes are distributed uniformly at random between the candidates, the probability that the lead changes when tallying the $i$-th vote is the same as the probability ...
18
votes
3answers
1k views

Zeroes of the random Fibonacci sequence

Let X_n be the "random Fibonacci sequence," defined as follows: $X_0 = 0, X_1 = 1$; $X_n = \pm X_{n-1} \pm X_{n-2}$, where the signs are chosen by independent 50/50 coinflips. It is known that ...
3
votes
0answers
670 views

Method for variable substitution in multiple summation

I want to ask: is there any general method for variable substitution in multiple summation? For example in the following equation a new variable $\lambda=n+m-2\mu$ is introduced to transform the LHS ...
5
votes
1answer
939 views

Is there a theory about these kinds of recurrence equations? Is this a known formula?

(New information at bottom) Hi. For a while, I've been toying around with solving recurrence equations of the form $$a_1 = r_{1,1}$$ $$a_n = \sum_{m=1}^{n-1} r_{n,m} a_m$$ What are these kind of ...
28
votes
3answers
3k views

Is there an “elegant” non-recursive formula for these coefficients? Also, how can one get proofs of these patterns?

Hi. Not sure if this is a "good" question for this forum or if it'll get panned, but here goes anyway... Consider this problem. I've been trying to find a formula to expand the "regular iteration" ...
1
vote
2answers
434 views

Trying to sum a series (related to catalan numbers perhaps)

Whilst trying to solve a combinatorics problem I am faced with summing this series: 1+ 2C_1 2/(3^2) + 4C_2 (2^2)/(3^4) + 6C_3 (2^3)/(3^6)+ ... + 2nC_n (2^n)/(3^(2n))+... Where 4C_2 is 4 choose 2. ...
23
votes
4answers
1k views

Asymptotic growth of a certain integer sequence

Some time ago, while putting my nose in the Sloane's Online Encyclopedia of Integer Sequences, I came over the sequence A019568 defined as follows: $a(n):=$ the smallest positive integer $k$ such ...
4
votes
1answer
457 views

Degree sequences of multigraphs with bounded multiplicity

I got to thinking about this problem while sifting through the math puzzles for dinner thread. There's a fun puzzle by rgrig which asks the guests to prove that when they came to dinner two of them ...
1
vote
1answer
1k views

Explicit formula for Euler zigzag numbers(Up/down numbers)

I have derived an explicit formula for the Euler zigzag numbers, the number of alternating permutations for n elements: $$A_n = i^{n+1}\sum _{k=1}^{n+1} \sum _{j=0}^k {k\choose{j}} ...
2
votes
2answers
186 views

Indexing schemes of binary sequences

I am looking for "low-complexity" indexing methods to enumerate binary sequences of a given length and a given weight. Formally, let $T_k^n = \{x_1^n \in \{0,1\}^n: \sum_{i=1}^n x_i = k\}$. How to ...
11
votes
2answers
768 views

Non-arithmetic proof of the integrality of a rational expression

The following expression is an integer for any natural $n,k$ $$c(n,k)=\frac{k^n\prod_{m=0}^{n-1}(1+mk)}{n!}.$$ The generating function for these numbers is $\sum_{n\geq 0} c(n,k)x^n=(1-k^2x)^{-1/k}$, ...
11
votes
5answers
840 views

Asymptotics of a Bernoulli-number-like function

Tony Lezard asked me the following question which seemed like it should not be too hard but which I did not immediately see how to answer. Define $f(n,k)$ recursively by $f(1,k) = 1$ and $$f(n,k) = ...
2
votes
10answers
6k views

Uniquely generate all permutations of three digits that sum to a particular value?

I'm looking for a way of generating all permutations of three digits (actually xyz) that sum to the same value. For example: ...