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
How do I determine the number of "second degree" derangements?
The answer depends on the cycle structure of $D_1$. Let $n:=|S|$ and $c_i$ be the number of cycles of length $i$ in $D_1$ (with $\sum_i ic_i=n$). Since $D_1$ is a derangement, we have $c_1=0$, but wha …
- 29.5k
0
votes
Count of binary matrices that avoids a certain sub-matrix
It is worth to mention that if we forbid also $2\times 2$ submatrices of all zeros, then there will be no such matrices as soon as $m,n\geq 5$.
In other words, every binary $5\times 5$ matrix contains …
- 29.5k
0
votes
What is this restricted sum of multinomial coefficients?
Another way to approach the original problem is to recall the formula:
$$\cos(y)^k = \frac{1}{2^k} \sum_{j=0}^k \binom{k}{j}\cos((k-2j)y).$$
Plugging in $y=\frac{\pi}{2} - x$ would give an expansion f …
- 29.5k
3
votes
Sequences without repeated objects
See
L. Q. Eifler, K. B. Reid Jr., D. P. Roselle, Sequences with adjacent elements unequal. Aequationes Mathematicae 6:2-3 (1971), 256-262.
http://dx.doi.org/10.1007/BF01819761
P.S. I have a PARI/GP …
- 29.5k
3
votes
Accepted
Sum over integer compositions of $m$ with $n$ parts of a fixed monomial in the parts
I'm not sure if there is anything simpler than $f_m(a_1,\dots,a_n)$ being the coefficient of $x^m$ in the product of polylogarithms:
$$\mathrm{Li}_{-a_1}(x)\cdot \mathrm{Li}_{-a_2}(x)\cdots \mathrm{Li …
- 29.5k
1
vote
Accepted
Intersection of members in a separating union-closed family of sets
Statement (3) is easier to prove directly by induction on $n=|U(\mathcal{F})|$.
The base case $n=1$ is trivial.
To make the induction step for $n>1$, let $x\in U(\mathcal{F})$ be an element that bel …
- 29.5k
6
votes
An Operation on Multisets
But I don't have a clear proof that the sequence always terminates in a loop. – Martin Erickson
Here is a proof that the sequence always terminates in a loop.
Let $A, B$ be consecutive arrays …
- 29.5k
5
votes
Accepted
Order of a combination when mapping them to whole numbers
Let $N(n;a_1,\dots,a_k)$ where $0\leq a_1 < a_2 < \dots < a_k < n$ be the order number of $(a_1,\dots,a_k)$ as a combination from ($n$ choose $k$).
Since there are exactly $\binom{n-1}{k-1}$ combinat …
- 29.5k
2
votes
A Graph-Theory Related Question
Let $p$ be a path consisting of $m$ shaded unit squares (where every two adjacent shaded squares share a side). Define a binary string $B_p=b_0b_1b_2\dots b_m$, where $b_0b_1=10$ and for $i>1$, $b_i=1 …
- 29.5k
5
votes
Long identity-free sequences of permutations
Construct a bipartite graph $G$ where one part is $[n]$ and the other is $[k]$ such that there is an edge between $i\in[n]$ and $j\in[k]$ iff $i\in A_j$. Then $A_1, \dots, A_k$ are identity free if $G …
- 29.5k
5
votes
A Bernstein-like Combinatorial Sum
First off, it is always worth to remove common factors (not depending on the index of summation) from the summands. The given sum is reduced to (I also assume $k>0$ to have summation start from $j=0$) …
- 29.5k
1
vote
Hitting set problem variant
Let $\mathcal{E} = \bigcup_{k=1}^m E_k.$
For each $j\in\mathcal{E}$, let $A_j = \{ k\in [1,m] : j\in E_k \}$. Then the anticipated subset $I\subset\mathcal{E}$ should satisfy the following requiremen …
- 29.5k
1
vote
Accepted
Deriving a closed form for rolling a sum $n$ with $k$ dice using stars and bars
Answer is given by the coefficient of $z^n$ in
$$(z+z^2+\dots+z^6)^k = \left(z\frac{1-z^6}{1-z}\right)^k = z^k (1-z^6)^k(1-z)^{-k}.$$
An explicit formula for this coefficient is:
$$\sum_{i=0}^{\min(k …
- 29.5k
2
votes
Resolution of multiple edges
First off, let me reformulate the problem. I call edges of $G$ black. Let $K_{k,n}$ be the complete graph on the same partite sets $V_1, V_2$, whose edges I will refer to as red. Let $H$ be the superp …
- 29.5k
2
votes
How to do the sum over integer compositions
Let $n$ be fixed.
The sum in question can rewritten as
$$S_k:=\frac{1}{(n-1)!}\sum_{L=1}^k\sum_{r_1+\dots+r_L=k} (n+3k-L)!\cdot \alpha^{k-L}\cdot f(n,k,L),$$
where $\alpha:=-\frac{a}{a+1}$ and
$$f(n,k …
- 29.5k
2
votes
Accepted
Pairwise combinations of distinct elements
Define the signature of an element $t\in Y^N$ as a monomial $s_t(z_1,z_2,z_3,z_4):=z_1^{k_1}z_2^{k_2}z_3^{k_3}z_4^{k_4}$ where $k_i$ is the number of occurrences of $y_i$ in $t$. It is clear that $k_1 …
- 29.5k
1
vote
Counting partitions avoiding some blocks
So, the question is how many non-crossing partitions have exactly $t$ pairs of the form $(2i-1,2j)$, $2i-1 < 2j$ (i.e., $i\leq j$), none of which have $i=j$. By inclusion-exclusion, the number of such …
- 29.5k
1
vote
Rook polynomial of quasi-Ferrers board?
The given board, call it $D$, can be viewed as the difference of two (unsorted) Ferrers boards with $m=9$ columns each: $A=(4,5,6,7,8,9,8,7,6)$ and $B=(3,2,1,0,1,2,3,4,5)$. We view $B$ as a sub-board …
- 29.5k
3
votes
Accepted
Maximum number of distinct $n$-runs that binary sequence of length $2^n$ can have
I understand that $n$-run here refers just to a substring of length $n$ (sometimes called $n$-mer).
The answer to this question is given by any de Bruijn sequence $B(2,n)$, where all $2^n-n+1$ (or $2^ …
- 29.5k
1
vote
Recurrence formula for boxed plane partitions
At very least, we can symmetrize your recurrence by summing it over the $3!=6$ permutations of $r,s,t$ with element relabeling to keep $[r,s,t]$ in the l.h.s.
This gives the following symmetric recurr …
- 29.5k
0
votes
Accepted
Generalization of multinomial theorem for powers of multinomial coefficients
I doubt there exists an closed-form expression for
\begin{equation}
S_\alpha := \sum_{x_1 + .. + x_k = n} \left( \frac{n!}{x_1!..x_k!}\right)^{\alpha} \theta_1^{x_1}..\theta_k^{x_k}.
\end{equation}
U …
- 29.5k
13
votes
Accepted
How to get a closed form for a possibly simple combinatorial sequence
It's worth to consider the sequence for $n=1$:
$$1,1,0,1,0,1,0,\dots$$
Let $s_k^n$ denote the $k$-th term of the $n$-th sequence.
In particular, $s_1^1=1$ and for $k>1$, $s_k^1$ equals 1 if $k$ is ev …
- 29.5k
1
vote
Coefficients of recursive functional
Consider generating functions: $F(x) := \sum_{n\geq 1} f(n)x^n$ and $G(x) := \sum_{n\geq 1} P(f)(n)x^n$. Then the recurrence translates into
$$G(x) = F(x) + \frac{x}{1-x} G(x),$$
which implies $$G(x) …
- 29.5k
2
votes
permutations and involutions in binary arrays
Not an answer, but a nice sufficient condition for existence of an involution when $m=n$:
If $m=n$ and $\operatorname{perm}(M)>0$, then $M$ has a matching that is an involution.
Proof. Since $\opera …
- 29.5k
6
votes
Accepted
Combinatorial system with parity
After numerous failed attempts to prove this, I found a counterexample with $n=6$ and $|Y|=13$:
$$\{1\}, \{1,2\}, \{3,4\}, \{5,6\}, \{1,2,3\}, \{2,3,4\}, \{3,4,5\}, \{4,5,6\}, \{1,3\}, \{2,4\}, \{3,5\ …
- 29.5k
6
votes
Accepted
Two rows of bounded numbers
The answer is Yes, and it follows from the following claim:
Claim. There exist two non-empty subsets $A\subsetneq \{a_1,\dots a_n\}$ and $B\subsetneq \{b_1,\dots b_n\}$ such that $|sum(A)-sum(B)|\ …
- 29.5k
9
votes
A question about certain sets of permutations of the ordered pairs $(1,1),(1,2),\cdots,(1,n)...
UPDATE (2022-07-13). The generating function for $A_k$ can be expressed as
$$\sum_{k\geq0} A_k t^k = {\cal L}_{x_1,\dots,x_n,y_1,\dots,y_n} \sum_{\lambda} e_{\lambda}(x_1,\dots,x_n)\cdot m_{\bar\lambd …
- 29.5k
1
vote
Accepted
Number of couples of columns "connecting" top to bottom of a matrix
We can view (unordered) pairs of zeros in each row as covering the pairs of columns (and thus eliminating them from being counted by $c$). Since we want to minimize $c$, the more pairs are covered the …
- 29.5k
1
vote
Accepted
Number of sets of columns "connecting" top to bottom of a matrix
Quite similarly to my answer to your other question, we have
$$c(h,n) \geq \binom{4n-h}m - h\binom{2n-h}m.$$
I'm not sure how good is this bound.
- 29.5k
3
votes
Accepted
How many combinations of magic square on a white Rubik's cube?
I assume that each magic square must be composed of numbers $1,2,\dots,9$ (or $1,2,\dots, n^2$ in general), and that under filling a cube with magic squares we understand assigning a number to each $1 …
- 29.5k
13
votes
Accepted
What is this restricted sum of multinomial coefficients?
$\binom{\ell}{a_1,\dots,a_k}$ is the coefficient of $x_1^{a_1}\cdots x_k^{a_k}$ in the expansion of
$$(x_1 + x_2 + \dots + x_k)^{\ell}.$$
The sum of all these coefficients is obtained by substituting …
- 29.5k
1
vote
Reproducing an ordered list of numbers from partial sums
This problem is considered and solved in the course of sequencing peptides - e.g. see algorithms described in Chapter 4. How Do We Sequence Antibiotics?. In reality they solve even harder problem obsc …
- 29.5k
0
votes
Accepted
Non-recursive solution to expected size of set
Your recurrence has explicit solution:
$$E[|F(n)|] = H_n,$$
where $H_n$ is the $n$th harmonic number.
- 29.5k
5
votes
Accepted
An upper bound on families of subsets with a small pairwise intersection
The maximum size is attained by a Steiner system $S(t+1,r,n)$ when it exists. It consists of $\binom{n}{t+1}/\binom{r}{t+1}$ blocks.
See http://en.wikipedia.org/wiki/Steiner_system
- 29.5k
3
votes
Accepted
Is there a generalisation of the Polya Enumeration Theorem to actions of wreath products?
A good starting point with some useful references is
Enumeration under two representations of the wreath product by Palmer and Robinson.
- 29.5k
2
votes
Simultaneous lcms
For each prime $p|d$, let $q_p$ be the number of $n_i$ with $p|n_i$.
Then the number of ordered but not necessarily distinct solutions $(m_1,\dots,m_r)$ is given by
$$f(r)=\prod_{p|d} S(r,q_p)\cdot q_ …
- 29.5k
7
votes
Accepted
Generating function of a sequence involving reciprocals of binomial coefficients
Let's solve Martin Rubey's differential equation, which I write as
$$g(x)G'(x) = f_1(x)G(x) + f_0(x),$$
where $g(x) = x(x-1)(xz-1)$, $f_1(x) = -x(2x-1)z+(k+1)x-k$, and $f_0(x)=k$.
Then by the general …
- 29.5k
8
votes
When do such regular set systems exist?
Switching to complements, the question is if we can choose 77 6-subsets of an 11-set $M$ such that any 5-subset of $M$ is contained in a chosen 6-subset (it is clear that this subset would be unique b …
- 29.5k
3
votes
Accepted
How many distinct sets of n collinear points are there in an evenly-spaced two-dimensional g...
Let $L_n(m)$ be defined as in this answer. Then the function $f(n,m)$ questioned here (aware that it is different from $f$ in the linked answer) can be computed as
$$f(n,m) = \sum_{k=n}^{m} \binom{k} …
- 29.5k
4
votes
Minimal number of n/2-subsets of [n] that contains every d-subset
These are called covering designs. See https://www.ccrwest.org/cover.html for references and tables of known values and bounds.
- 29.5k
0
votes
Accepted
Integer solution
I doubt that the lower bound $\frac{p-1}{2} - 2cp^{1/3}$ holds for all $p$. Here is a proof for the weaker bound $\frac{p-1}{2} - cp^{1/2}$.
First of all, the inequality $\frac{p-1}{2}-cp^{1/2} \leq …
- 29.5k
2
votes
The combinations of a finite multiset
It can be easily seen that $C(k;m_1,\dots,m_n)$ equals the coefficient of $x^k$ in
$$\prod_{i=1}^n (1+x+\dots+x^{m_i}) = \prod_{i=1}^n \frac{1-x^{m_i+1}}{1-x} = (1-x)^{-n} \prod_{i=1}^n (1-x^{m_i+1}). …
- 29.5k
2
votes
Accepted
A question of terminology regarding integer partitions
Let $\mu=(\mu_1,\dots,\mu_m)$ and $\gamma_i$ be the number of parts equal $i$ in $\mu$. Then
$$\sum_{i=1}^r \gamma_i = m\quad\text{and}\quad\sum_{i=1}^r i\cdot\gamma_i = r.$$
Then $C_{n,\mu}$ equals …
- 29.5k
3
votes
Accepted
Counting matrices of special types
For generic (not necessarily symmetric) $m\times n$ matrices over a set of $k$ elements, the number of those with pairwise distinct columns and rows is
$$\sum_{i=0}^m\sum_{j=0}^n s(m,i)\cdot s(n,j)\cd …
- 29.5k
5
votes
Accepted
Limit of quotients of polynomials at fixed value
First, cancelling common factors we get
$$p(t,n) = \frac{ \sum_{i=0\atop i\equiv 1\pmod{2}}^{2^n-1} \left(\frac{t}{1-t}\right)^{g(i)-f(i)} }{ \sum_{i=0}^{2^n-1} \left(\frac{t}{1-t}\right)^{g(i)-f(i)} …
- 29.5k
5
votes
Accepted
Edge Covering Shortest path
That is Chinese Postman Path. Search for Chinese Postman Problem...
E.g., this section from some book looks comprehensive: http://ie454.cankaya.edu.tr/uploads/files/Chp-03%20044-064.pdf
- 29.5k
5
votes
Ordinary or Rational Generating Function for Associated Stirling Numbers $b(n,k)$
Using the recurrent relation $b(n+1,k) = k\cdot b(n,k) + n\cdot b(n-1,k-1)$ it is easy to get that the ordinary generating function $B(x,y) = \sum_{n,k} b(n,k)\cdot x^n\cdot y^k$ satisfies the followi …
- 29.5k
1
vote
Accepted
Sets of residues with only a single intersection under translation
It is necessary and sufficient that for any nonzero $d\in\Bbb Z/n\Bbb Z$, there exists $i\in\{1,2,\dots,k\}$ such that $d\notin (A_i-A_i)$. In other words,
$$\bigcap_{i=1}^k (A_i-A_i) = \{0\}.$$
This …
- 29.5k
2
votes
Constructing a vector consisting of nonnegative entries
Yes, such construction is always possible.
Consider two sets of pairs of values:
$$\big\{ (2+t,m-t)\quad :\quad t=0\,..\,\lfloor\frac{m-1}{4}\rfloor-1\big\},$$
where differences of elements modulo $m$ …
- 29.5k
3
votes
Accepted
Tight upper bound on the number of high degree vertices
Suppose there are $b$ big vertices. Then there are at least $\frac{mb}{2q}$ edges incident to these vertices. Hence,
$$\frac{mb}{2q} \leq m$$
implying that $b\leq 2q$.
To get an example with $2q$ big …
- 29.5k