Search Results
| Search type | Search syntax |
|---|---|
| Tags | [tag] |
| Exact | "words here" |
| Author |
user:1234 user:me (yours) |
| Score |
score:3 (3+) score:0 (none) |
| Answers |
answers:3 (3+) answers:0 (none) isaccepted:yes hasaccepted:no inquestion:1234 |
| Views | views:250 |
| Code | code:"if (foo != bar)" |
| Sections |
title:apples body:"apples oranges" |
| URL | url:"*.example.com" |
| Saves | in:saves |
| Status |
closed:yes duplicate:no migrated:no wiki:no |
| Types |
is:question is:answer |
| Exclude |
-[tag] -apples |
| For more details on advanced search visit our help page | |
Results tagged with co.combinatorics
Search options not deleted
user 7076
Enumerative combinatorics, graph theory, order theory, posets, matroids, designs and other discrete structures. It also includes algebraic, analytic and probabilistic combinatorics.
1
vote
Combinatorial identity involving the square of $\binom{2n}{n}$
The generating function for $b_n$ can be expressed as
\begin{split}
\sum_{n\geq 0} b_n z^{2n} &=
\frac{2}{z(z+2)}\cdot\log\frac{1+z-\sqrt{1-z^2}}z \\
&+ \frac{2}{z(z-2)}\cdot\log\frac{\sqrt{1-z^2}-1+ …
- 29.5k
3
votes
Accepted
Simplifying a Taylor polynomial that involves Stirling numbers of the second kind
Changing the order of summation, we get
$$ \sum_{n=1}^k \frac{x^n}{n!} \sum_{m=1}^n (-1)^{m-1} (m-1)!S(n,m) a^m$$
$$ = \sum_{m=1}^k (-1)^{m-1} (m-1)! a^m \sum_{n=m}^k \frac{x^n}{n!} S(n,m).$$
Using f …
- 29.5k
1
vote
How to compute number of ways to partition a set under certain constraints?
Stirling numbers of second kind can be expressed as the sum:
$$S(n,k) = \sum_{{j_1 + j_2 + \dots + j_n = k\atop j_1 + 2 j_2 + \dots + nj_n = n}} \frac{n!}{j_1!1!^{j_1}j_2!2!^{j_2}\cdots j_n!n!^{j_n}}, …
- 29.5k
4
votes
Number of Lyndon words of given weight
A Lyndon word can be characterized as the lexicographically smallest word among its cycle rotations. Hence, Lyndon words can be viewed as (representatives of) equivalence classes of non-periodic words …
- 29.5k
1
vote
Modular arithmetic: Reaching an interval
I think there is no "compact representation" for $k$.
The problem is equivalent to the following integer linear programming problem:
$$\begin{cases}
\text{minimize}\ k,\\
k\geq 0,\\
c_1 \leq x+k\del …
- 29.5k
0
votes
Computing Permutations with Partial Duplicates
The number of $K$-permutations of the numtiset $\{ 1^D, 2^D, \ldots, N^D \}$ is
$$\sum_{j_1+j+2+\dots+j_N=K\atop 0 \leq j_i \leq D} \binom{K}{j_1,j_2,\dots,j_N}.$$
(summands here are multinomial coeff …
- 29.5k
1
vote
Constructing a generating function using a series with all negative and positive powers of a...
This is not a complete answer, but a simpler analogous example with a known solution.
Consider a $n\times n$ square grid and let us compute the number of paths (known as Dyck paths) from the bottom …
- 29.5k
2
votes
A congruence involving binomial coefficients
I'd like to draw your attention to a recent paper On p-adic approximation of sums of binomial coefficients where we briefly discuss (in Section 4) the divisibility of this kind. Namely, we claim that …
- 29.5k
1
vote
Accepted
Number of positive integer solutions with a lower bound
Subtracting $\lceil n^\beta\rceil-1$ from every $x_i$ translates the problem to the number of partitions of $\lceil n^\alpha\rceil - t(\lceil n^\beta\rceil-1)$ into $t$ parts:
$$p_t(\lceil n^\alpha\rc …
- 29.5k
14
votes
Accepted
Does there exist a Latin square of order 9 for which its 9 broken diagonals and 9 broken ant...
I've verified with ILP that such Latin squares do not exist for $n\in\{9,15,21,27\}$.
The ILP formulation is based on binary indicator variables $p_{c,i,j}$ telling whether Latin square has character …
- 29.5k
6
votes
How many Hamiltonians Paths there are in almost regular graph ?
Explicit values for $k\leq 9$ and small $n$ are given in the OEIS:
k=2: http://oeis.org/A003274 (contains some references and a generating function)
k=3: http://oeis.org/A174700
k=4: http://oeis.or …
- 29.5k
8
votes
Important formulas in combinatorics
Burnside Lemma and Redfield-Polya Theorem are celebrated results in combinatorics. They allow to enumerate objects modulo group actions. One of the classic (and simplest) examples is enumeration of ne …
12
votes
Important formulas in combinatorics
Faà di Bruno's formula generalizes the chain rule to higher order derivatives. Most compact form of Faà di Bruno's formula involves Bell polynomials $B_{n,k}\left(x_1,x_2,\dots,x_{n-k+1}\right)$ and i …
10
votes
Important formulas in combinatorics
Series multisection is a folklore formula (Riordan called it an "ancient vintage" in his 1968 book "Combinatorial identities"), which from a given analytical generating function for some numerical seq …
10
votes
Important formulas in combinatorics
No doubts, the inclusion-exclusion principle generates most common type of formulae used in enumerative combinatorics. Examples include explicit formulae for derangements, Striling numbers, rook polyn …
3
votes
Important formulas in combinatorics
Lagrange Inversion (Lagrange–Bürmann formula) plays an important role in combinatorics. There is a dedicated MO discussion of its applications (in combinatorics and beyond). In particular, see my answ …
9
votes
Important formulas in combinatorics
An elegant and rather unexpected formula for the powers of the generating function for Catalan numbers $C_n = \frac{1}{n+1}\binom{2n}{n}$:
$$\left(\sum_{n=0}^{\infty} \frac{1}{n+1}\binom{2n}{n} \cdot …
2
votes
A question relating to certain algebraic manipulation of a formal power series written in th...
The question is rather vague, and thus it may have multiple answers. Here is one.
Let $P$ denote the product of interest and let $Q:=\log(P)$, i.e.
$$Q = \sum_{d\geq 1} a_d\log(1+\frac{u^d}{q^d-1}).$ …
- 29.5k
5
votes
Accepted
$\sum_{1\leq a,b\leq n}\mathcal{P}(\gcd(a,b,n))$
Introducing $d:=\gcd(a,b,n)$, we get
$$\sum_{1\leq a,b\leq n} \mathcal{P}(\gcd(a,b,n)) = \sum_{d\mid n} \mathcal{P}(d) J_2(\tfrac{n}d),$$
where $J_2(\cdot)$ is the Jordan totient function (see also OE …
- 29.5k
2
votes
Counting permutations defined by a simple process
If we view permutation as runs of red balls interspaced with runs of blue balls, then the requirement is that the marked ball is at the even position within its run.
Let $t$ be the number of red runs; …
- 29.5k
2
votes
Accepted
Counting multisets satisfying a fixed property
In other words, every element $x\in M\cap (S\setminus R)$ has even multiplicity $\nu(x)$, while the multiplicity of elements of $M\cap R$ is unrestricted.
Then, the generating functions is
\begin{spl …
- 29.5k
2
votes
Accepted
simple formula for a finite sum of multinomial numbers
First notice that
$$\Omega(k,m,r) = \binom{k}{m-2r,r,k-m+r}.$$
It follows that $\Omega(k,m)$ equals the coefficient of $x^{m-k}$ in $(1+x+x^{-1})^k$, which is the same as the coefficient of $x^{m}$ in …
- 29.5k
6
votes
Compositions $(n_1,...,n_r)$ of an integer $m$ such that $i$ divides $n_i$
For a fixed $r$, these are in an one-to-one correspondence with conventional partitions of $m$ into parts $\leq r$ where each part $i$ is present at least once (just set $n_i$ equal the sum of all par …
- 29.5k
2
votes
Equivalence classes of a circle of n bits upon flipping 3 consecutive 0s to 1s or vice versa
It's unclear if you consider $n$-bit circular strings up to rotations, and this would affect the answer. Still, in either case a rough idea is as follows.
Transform $111$ to $000$ until no $111$ rema …
- 29.5k
1
vote
Number of edge-invariant walks in complete graph
I'm not sure if the formula below is useful, but at least it can be used to numerically count edge-invariant walks classes for small $n,l$.
Let's assign a unique variable to each edge and each vertex …
- 29.5k
2
votes
Inversion inequalities
The smallest $k$ when such permutations exist is $k=4$. Namely, the set of $\pi_i$ given by
$$\big\{\ [1, 2, 3, 4], [1, 3, 4, 2], [1, 4, 2, 3], [2, 1, 3, 4], [2, 3, 4, 1], [2, 4, 1, 3],$$
$$ [3, 4, 1 …
- 29.5k
12
votes
Do you recognize this sequence of polynomials?
The recurrence $f_{n+1} = (t-2)f_n - f_{n-1}$ with $f_0=1$ and $f_1=t-1$ suggests that $f_n$ can be expressed in terms of Chebyshev polynomials as:
\begin{split}
f_n(t) &= T_n(\tfrac{t}2-1) + \frac{t} …
- 29.5k
6
votes
Proof for alternating binomial sum over even powers
This sum can be expressed in terms of $2n$-th forward difference:
\begin{split}
\sum_{k=1}^n (-1)^k\frac{k^{p}}{n+k}\binom{2n-1}{n-k} &=
\frac1{2n} \sum_{k=1}^n (-1)^k k^{p} \binom{2n}{n+k} \\
&\matho …
- 29.5k
3
votes
Number of ways of distributing indistinguishable balls into distinguishable boxes with extra...
Let's first consider the unrestricted case, and let $f(m,k)$ denote the number of ways to distribute $m$ unlabeled balls into $k$ labeled boxes. Then we have the following generating function:
\begin{ …
- 29.5k
3
votes
Accepted
Does anyone have ideas about how to simplify this combinatorial expression (mod 2)?
First we may notice that
$$\sum_{i=0}^m \binom{n}{i} = [x^m]\ \frac{(1+x)^n}{1-x} \equiv_2 [x^m]\ \frac{(1+x)^n}{1+x} = [x^m]\ (1+x)^{n-1} = \binom{n-1}m,$$
which was already pointed out by @FedorPetr …
- 29.5k
4
votes
Accepted
direct proof of an identity regarding certain symmetry of integer partitions?
I assume you meant $j_t\leq a_t$ (not $j_t<a_t$).
It's sufficient to prove that for any analytic function $f(x)$, the function
$$F(a_1,a_2) := \sum_{l\geq 0} \sum_{j=0}^{a_2} \frac{(-1)^ll!}{(a_1+l+1) …
- 29.5k
5
votes
How to calculate the sum of general type $\sum_{k=0}^n {n\choose k} {n\choose k+a} {2 k- n +...
Alternatively, one can get an explicit expression for a fixed $r$ via generating functions by noticing that the given sum equals
$$[y^{n+a}z^r]\ (y+1+z)^n (1+y(1+z))^n (1+z)^{-n}$$
and rewriting it as …
- 29.5k
2
votes
Accepted
Asymptotics for the sums from the inclusion-exclusion principle
Another way to approach this from the generating function perspective. Notice that
$$\sum_{k=l}^u (-1)^k [x^k]\, f(x) = [x^u]\,\frac{f(-x)}{1-x} - [x^{l-1}]\,\frac{f(-x)}{1-x},$$
and so the question r …
- 29.5k
2
votes
Accepted
Quick enumeration for the coloring of the vertices of an n-dimensional cube
The group of symmetries of a hypercube is known as the hyperoctahedral group. For $n$-dimensional hypercube, it is formed by the wreath product of symmetric groups $S_2$ and $S_n$. The classic referen …
- 29.5k
3
votes
How many residues mod p do you need to take to ensure that you can always find some multiple...
For simplicity, I'll assume nonstrict inequality: $x,y,z\leq \epsilon$.
For each integer $t\in [1,\epsilon]$, let $T_t := \{ (\lambda,\mu)\in \mathbb{Z}_p^\star\times \mathbb{Z}_p\mid t\in \lambda S+ …
- 29.5k
1
vote
Closed form of $ \sum_{i=1}^{n-k} {n-1-i\choose k-1}i^a + \sum_{i=1}^k {n-1-i\choose n-1-k}$
If we assume that $a$ is fixed, then the first sum can be rewritten in a closed form with $a+1$ terms:
$$\sum_{j=0}^a \left\langle a\atop j\right\rangle \binom{n+a-1-j}{k+a},$$
where $\left\langle a\a …
- 29.5k
5
votes
Accepted
Asymptotics of an alternating sum involving the prefix sum of binomial coefficients
The sum $\sum_{j=0}^{k} \binom{cn+k}{j}$ equals the coefficient of $x^k$ in $(1+x)^{cn+k}(1-x)^{-1}$, and by Lagrange–Bürmann formula it is also the coefficient of $t^k$ in $(1-2t)^{-1}(1-t)^{-cn}$. I …
- 29.5k
2
votes
Lower/Upper bounds for $ \sum\limits_{i=0}^k \binom ni x^i $
Let $p=\frac{x}{1+x}$ and $q=\frac{1}{1+x}$, and thus
$$\sum_{i=0}^k \binom{n}{i} x^i=(1+x)^n\sum_{i=n-k}^n \binom{n}{i} p^{n-i} q^i.$$
Then for $k<np$ Chernoff bound gives
$$\sum_{i=n-k}^n \binom{n …
- 29.5k
3
votes
How many ways to pick k integers with fixed sum and product
Let $B_k({\cal S},{\cal P},{\cal X})$ be a bound for the number of solutions for any $S\leq {\cal S}$, $P\leq {\cal P}$ and ${\cal X} \leq x_1 \leq x_2 \leq \dots \leq x_k$.
Using Iverson's bracket no …
- 29.5k
1
vote
Accepted
Summing the max value of the distinct pairs in a multiset
This is a corrected and extended version of my earlier comment. Let $A = \{ b_1^{m_1}, \dots, b_k^{m_k}\}$ where $b_1 < \dots < b_k$ and $m_i$ are their multiplicities with $\sum_{i=1}^k m_i = n$.
The …
- 29.5k
1
vote
Bounding a sum of products of binomial coefficients
Suppose that $k$ is fixed. The sums represent polynomials of degree $k$ in $n$. To answer your question, it's enough to compute two first leading terms of these polynomials. Let me do that for the sec …
- 29.5k
0
votes
Sum of 'the first k' binomial coefficients for fixed $N$
Two bounds that work uniformly for all $k$:
$$f(n,k) \leq \binom{n+1}{k} + \binom{n+k-1}{k-1},$$
$$f(n,k)\leq \binom{n+k}{k},$$
where the former is tighter for $k\geq 2$.
For a proof, see this answer. …
- 29.5k
9
votes
Accepted
Asymptotic of a certain double sum involving binomial coefficients
The inner summation from $k=1$ looks a bit suspicious, since starting with $k=0$ appears to be more natural. So I assume that the inner summation starts with $k=0$ (the case of $k=1$ easily follows) a …
- 29.5k
1
vote
Factoring a multiset into a product of two multisets
I assume the positive integers case and rely on existence of unique prime factorizations and linear order for them.
Let $P$ be the product of all elements of $S$.
Assuming we can find prime factoriz …
- 29.5k
4
votes
Counting refinements of partitions
If I'm not mistaken, this simple Sage code computes $F(n)$:
def F(n):
P = Posets.IntegerPartitions(n)
return sum( len(P.closed_interval(p,P.top())) for p in P )
The values of $F(n)$ for $n=0,1, …
- 29.5k
4
votes
Accepted
Tweaking the Catalan recurrence and $2$-adic valuations
This is not true. In fact, we can show that $\nu_2(u_{6,t}) = t+1$.
Indeed, computing first terms modulo $2^{t+2}$ for $t\geq 2$, we have
\begin{split}
u_{0,t} &= 1,\\
u_{1,t} &= 1,\\
u_{2,t} &= 2,\\
…
- 29.5k
1
vote
Accepted
Is there a systematic relation between the generating functions for the rows vs that for col...
Assume that $f_c(x) = x^c q_c(x)$, where $q_c(0)\ne 0$. Then the generating function for the row $r$ in the left matrix is
$$g_r(t)=\sum_{c=0}^{\infty} [x^{r+c}]\ q_{-c}(x)\cdot t^c,$$
where the opera …
- 29.5k
4
votes
Accepted
Number of walks on integer lattice with self-edge at zero
There are two types of paths from $a$ to $b$: those that do not visit the origin ($0$) and those that do visit it. I start with analyzing the second kind of paths.
Paths that visit the origin
A path …
- 29.5k
2
votes
Accepted
Algorithm for Removing Inverted Elements from a Permutation
Create a doubly-linked list $L$, initially empty. Scan a given permutation $p=(p_1,p_2,\dots,p_n)$ from left to right, and for each element $p_i$ perform the following operations:
(loop) While $L$ i …
- 29.5k
12
votes
Combinatorial identity: $\sum_{i,j \ge 0} \binom{i+j}{i}^2 \binom{(a-i)+(b-j)}{a-i}^2=\frac{...
Let us denote
$$S=\sum_{i,j \ge 0} \binom{i+j}{i}^2 \binom{(a-i)+(b-j)}{a-i}^2.$$
First, let $s=i+j$ so that
$$S = \sum_{s\geq 0}\sum_{i=0}^s \binom{s}{i}^2 \binom{a+b-s}{a-i}^2.$$
Consider the gener …
- 29.5k