Skip to main content

Questions tagged [combinatorics]

For questions about the study of finite or countable discrete structures, especially how to count or enumerate elements in a set (perhaps of all possibilities) or any subset. It includes questions on permutations, combinations, bijective proofs, and generating functions.

Filter by
Sorted by
Tagged with
1 vote
1 answer
25 views

Number of vector of length $n$ over ${A,C,T,G}$ that do not have $k$ consecutive $A$'s

In this problem, $k$ is a constant, and we need to find a recursive function that depends only on $n$, i,e $f(n)$. Here is my (wrong) solution: Say there's a valid vector of length $n$. Let's separate ...
natitati's user avatar
  • 391
2 votes
0 answers
25 views

Does there exist an oriented graph with fixed amount of vertices and fixed possible indegree and outdegree?

I am considering an oriented graph without loops and multiple edges. The question is: Does there exist an oriented graph with $100$ vertices, where the indegrees of vertices is either $2$ or $10$ and ...
NeoFanatic's user avatar
1 vote
0 answers
24 views

Combinatorial Structure and Combinatorial Configuration

I often encounter the terms Combinatorial Structure and Combinatorial Configuration in combinatorial literature. I find few definitions for them, and even when provided, they differ. I am unsure about ...
Math_fun2006's user avatar
-3 votes
0 answers
29 views

How many 10 letter words are there using the letters a,b,c,d,e,f if [closed]

(a) the letters in the word appear in alphabetical order? (b) each letter occurs at least once and the letters in the word appear in alphabetical order?
MJ713's user avatar
  • 5
0 votes
0 answers
61 views

How many unique circuits can be made given n equal resistors?

Really stumped by this one (I'm not an EE!). Suppose we are given $1, 2, 3, 4, 5$, and $6$ one-ohm resistors. They can be arranged in series, parallel, bridge, and so forth circuits. No dangling ...
Ken Bannister's user avatar
2 votes
2 answers
80 views

Compute the value of a double sum

I need some help computing a(n apparently nasty) double sum: $$f(l):=\sum_{j = \frac{l}{2}+1}^{l+1}\sum_{i = \frac{l}{2}+1}^{l+1} \binom{l+1}{j}\binom{l+1}{i} (j-i)^2$$ where $l$ is even. I'm not ...
Matt M's user avatar
  • 39
-1 votes
1 answer
60 views

Number of ways to write n as a sum of k different nonnegative integers

I need find a recursive function ( Withdrawal formula ) $\operatorname{f}\left(n,k\right)$ for the problem: What is the number of ways to write $n$ as a sum of $...
user25778822's user avatar
1 vote
0 answers
29 views

Calculation of special subsets in high-dimensional binary matrices

I need to solve a rather specific problem related to binary matrices. The task is to count the number of specific "combinations", where "combination" means the following: this is ...
Disciple's user avatar
  • 345
4 votes
0 answers
43 views

How to prove crossing number is 3?

Find the crossing number of the following graph I find that there are 3 edge crossings in the given graph. So I can conclude that the crossing number is less than or equal to 3. However, I am confused ...
Olivia's user avatar
  • 841
3 votes
3 answers
64 views

Prove that $\frac{(n + 1)!}{((n + 1) - r)!} = r \sum_{i=r - 1}^{n} \frac{i!}{(i - (r - 1))!}$

I Need Help proving That $$\frac{(n + 1)!}{(n - r + 1)!} = r \cdot \sum_{i=r - 1}^{n} \frac{i!}{(i - r + 1)!}$$ Or in terms of Combinatorics functions: $P_{r}^{n+1} = r \cdot \sum_{i = r-1}^{n} {P_{r-...
BGOPC's user avatar
  • 179
2 votes
0 answers
47 views

What is the number of facets of a $d$-dimensional cyclic polytope?

A face of a convex polytope $P$ is defined as $P$ itself, or a subset of $P$ of the form $P\cap h$, where $h$ is a hyperplane such that $P$ is fully contained in one of the closed half-spaces ...
A. H.'s user avatar
  • 152
0 votes
3 answers
138 views

Confused about a counting problem

This question is reproduced from a text by Sheldon Ross: Example 5k. A football team consists of $20$ offensive and $20$ defensive players. The players are to be paired in groups of $2$ for the ...
Vacation Due 20000's user avatar
-2 votes
0 answers
46 views

How to "arrange things in groups"? [closed]

I was studying combinatorics in my textbook and I was trying to get through arrangements in groups and here's what I couldn't get Can anyone please help to explain this stuff ?
Dipanjan Das's user avatar
0 votes
0 answers
22 views

Does there exist at least two sets whose union gives the universe in a certain intersection-closed family of sets?

This is a slightly simplified version of a mathoverflow question without answers. Let $\mathcal{F}$ be a family of $n$ finite sets. In this case, the family can be regarded as a multiset, since it is ...
Fabius Wiesner's user avatar
1 vote
1 answer
27 views

Subset of index that minimizes a sum of real values

Given a series of real numbers $c_1, \ldots, c_n$ with $ n \in \mathbb{N} $, is there an algorithm or method to find the subset of indices such that the absolute value of the sum of the values within ...
mcmat23's user avatar
  • 1,070
1 vote
0 answers
69 views

IMO 2024 p-3,Sequence of Counts - Are Odd or Even Terms Eventually Periodic?

Let $a_1, a_2, a_3, \dots$ be an infinite sequence of positive integers, and let $N$ be a positive integer. We define $a_n$ for $n > N$ as the number of times $a_{n-1}$ appears in the list $a_1, ...
Saucitom's user avatar
1 vote
1 answer
44 views

Does any permutation "cover" a permutation with less inversions?

Let $\mathcal{S}_n$ be the symmetric group on $n$ objects. For any permutation $\pi\in\mathcal{S}_n$, define $E(\pi)=\{(i,j):\ i<j,\ \pi(i)>\pi(j)\}$ as the set of reversed pair of indices ...
Johnson's user avatar
  • 13
0 votes
0 answers
38 views

Same number of lists of integers [duplicate]

Have a following problem for which I'll show my reasoning (the problem is $1.6$ from book Problem solving methods in combinatorics by Pablo Soberon): If we want to write all the lists of length $n$ ...
slomil's user avatar
  • 176
0 votes
1 answer
33 views

How the modified Bernoulli numbers relate to the ordinary Bernoulli numbers

The modified Bernoulli numbers are defined as the numbers $b_k$ whose generating series is $$\frac 1 2\log\left(\frac{\sinh \frac t 2}{\frac t 2}\right) = \sum_k b_k t^k.$$ (I use a slightly different ...
red_trumpet's user avatar
  • 9,487
0 votes
0 answers
25 views

Circular Permutations of Repeated Objects with Restraints

Bob wants to use 8 indistinguishable black beads and 32 indistinguishable white beads to make a necklace such that there are at least 2 white beads between any 2 black beads. In how many ways can this ...
Alt User's user avatar
1 vote
0 answers
33 views

Sum with constraints in maple or mathematica [closed]

I'm looking for a code in Maple or Mathematica to evaluate and give a list of terms in expressions like $\newcommand{\on}[1]{\operatorname{#1}}$ $$ \sum_{a\ +\ b\ +\ c\ =\ 6}\on{f}\left(a\right)\on{f}\...
wkmath's user avatar
  • 13
1 vote
0 answers
21 views

Number of distinct minimal fundamental cycle matrix of rank $k$

For a graph $G=(E,V)$ and a fundamental cycle basis $C_1,\ldots,C_k$, we can create a incident matrix $M$ between the edges and the fundamental cycles. Namely, $M_{i,j}=1$ if $e_i\in C_j$, and $M_{i,j}...
Chao Xu's user avatar
  • 5,848
-1 votes
1 answer
76 views

Probability that at least one option is selected exactly once [closed]

I'm having trouble with the following question: Suppose $n$ persons each select, uniformly and independently, one of $k$ options. Show that the probability that at least one option is chosen exactly ...
user675763's user avatar
0 votes
1 answer
43 views

Unit ball with dual set

Let $X\subseteq \mathbb{R}^d,$ we define the set dual to $X$, denoted by $X^*$, as follows: $$X^*=\{y\in \mathbb{R}^d \mid \langle y,x\rangle\leq 1, \forall x\in X\}.$$ Geometrically, $X^*$ is the ...
D. S.'s user avatar
  • 148
-2 votes
0 answers
28 views

If we combine two trees in a particular way, how many spanning trees does the new graph have? [closed]

Given two trees $T_1 = (V_1, E_1)$ and $T_2 = (V_2, E_2)$ with $V_1$ and $V_2$ disjoint, generate a new graph $G = (V, E)$ by \begin{align*} V &= V_1 \cup V_2 \\ E &= E_1 \cup E_2 \cup \{(x, y)...
test123's user avatar
0 votes
0 answers
33 views

How to permute the rows and cols of a matrix to maximize the set of pivots?

Given an $m\times n$ matrix $A$, how can I find permutations $\sigma,\tau$, such that for the matrix $B=A[\sigma,\tau]$ with shuffled columns and rows, the number of nonzero entries that have zeros ...
Leo's user avatar
  • 10.7k
8 votes
1 answer
286 views

Seeking a Purely Formal Power Series Solution

Seeking a Purely Formal Power Series Solution When I read about generating functions, I encountered the following problem: Suppose that the set of nonnegative integers is partitioned into a finite ...
Math_fun2006's user avatar
0 votes
0 answers
34 views

Let A be a 2n-element set. Find the number of pairings of A.

I am having trouble understanding how one of the solutions to this problem works: Let a pairing of A partition the set into 2-element subsets. Example: a pairing of {a, b, c, d, e, f, g, h} is {{a, b},...
Alt User's user avatar
0 votes
0 answers
20 views

Notational change for linearity condition in analysis of Boolean functions

On Wikipedia, it clearly states that a Boolean function $f: \{-1, 1\}^n \rightarrow \{-1,1\}$ is linear iff it satisfies $f(xy)=f(x)f(y)$ where $xy = (x_1 y_1, \dots, x_n y_n)$. However, on another ...
Saksham Sethi's user avatar
0 votes
0 answers
47 views

Show that $K_{a \times b}$ is a robust expander.

Let $\nu, \tau>0$, $G$ be a graph on $n$ vertices. We define a $\nu$-robust neighbourhood $RN_{\nu,G}(S)$ of a set $S \subset V(G)$ in $G$ to be the set of vertices of $G$ which has at least $\nu n$...
Tony Deng's user avatar
-2 votes
0 answers
23 views

Hadamard Matrix Alternative Construction

I've been researching on this topic when I saw this construction in Wikipedia of the Hadamard Matrix: Alternative Hadamard Construction From the link: https://en.wikipedia.org/wiki/Hadamard_matrix I ...
Asier's user avatar
  • 1
0 votes
0 answers
40 views

How are there $2^n$ $n$-variable parity functions?

Source: https://www.cs.cmu.edu/~odonnell/boolean-analysis/lecture2.pdf Context: Linearity testing of boolean functions is being discussed, and they just introduced parity functions which I didn't know ...
Saksham Sethi's user avatar
0 votes
0 answers
75 views

confused with the notion of probability

I understand probability as two processes; We "do" something (or something is "happening"). lets call it the random experiment, and We "expect" something from this ...
Sonu Gupta's user avatar
2 votes
0 answers
47 views

Find the number of matrices over the finite field $\mathbb F_{19}$, whose minimal polynomial has a certain degree $m$.

I am collaborating with some colleagues to create a TACA (a test assessing knowledge in Calculus, Linear Algebra, and Elementary Group Theory) practice test. During this process, I devised the ...
1048576's user avatar
  • 31
1 vote
0 answers
39 views

Count the number of dice whose faces sum to 21 [duplicate]

You are given a blank six sided die and 21 dot stickers. You can distribute the stickers on the die as you please, but you must use all 21 of them. How many distinct dice can be formed? Note that we ...
kiston's user avatar
  • 11
0 votes
1 answer
40 views

Minimum number of edges to be removed from a square grid so that no rectangles remain.

I encountered the following problem: "Find the number of edges to be removed from a $8*8$ square grid so that no rectangles remain on the board. I was able to use my intuition to find a formula ...
tensorman666's user avatar
2 votes
1 answer
38 views

Lower bound on the number of transitive sub-tournaments of size k in a tournament of size N.

Given a tournament of size $N$, what are the lower bounds on the number of transitive sub-tournaments of size $k$? What about specific values of $k$? For $k = 3$ I know the number of transitive sub-...
Will's user avatar
  • 23
1 vote
0 answers
34 views

Solution of recurrence relation with summation

I have the following recurrence relation: $b(n,k)=\sum _{\text{i}=0}^{2 n-1} \left(b(n-1,k-\text{i})+\frac{\text{i} (2 n-\text{i}) \binom{2 n-1}{\text{i}} \binom{(n-2)^2}{k-\text{i}}}{2 n-1}\right)$ ...
Cardstdani's user avatar
-2 votes
2 answers
59 views

Asymptotic behavior of $\sum_{k=1}^n k^{n-k+1}$ as $n$ goes to $+\infty$ [duplicate]

I am in front of the sum $\sum_{k=1}^n k^{n-k+1}$. I find no way to evaluate it in closed form. Is there any? Is there a way to find an equivalent as $n$ goes to infinity?
Aristodog's user avatar
  • 369
-1 votes
0 answers
30 views

Problems with non prime order diagonal latin squares [closed]

$$ \text{A Diagonal Latin square is an } n \times n \text{ square where data is not repeated among all the diagonals, rows, and columns.} $$ $$ \text{Diagonal Latin square solutions only exist for } n ...
IllTime00qw's user avatar
6 votes
1 answer
111 views

Diving $m$ pizzas among $n$ students

I'm working on problem 4.1.14 from the book Graph Theory by Bondy and Murty. I'd appreciate a solution or hint for part 2. Problem Statement: $m$ identical pizzas are to be shared equally amongst $n$ ...
Benny's user avatar
  • 300
0 votes
0 answers
36 views

A simple bound on the proportion of primes less than $2^k$.

Fix $k > 1$ and let $P = \{x \mid 0 \le x < 2^k - 1 \text{ and } x \text{ is prime }\}$. Then I want to show that $$ \frac{|P|}{2^k} \ge \frac{1}{2k}. $$ I know how to prove this by using ...
barrel's user avatar
  • 1
3 votes
2 answers
59 views

Combinatorics Permutations/Cycles question

Suppose $n\geq 5$. How many permutations of the set with $n$ elements are there such that some cycle contains elements 1,2,3, and a different cycle contains 4 and 5? I have seen the solution to this ...
Sachin's user avatar
  • 71
5 votes
5 answers
223 views

Closed formula for probability of n-digit numbers containing three consecutive sixes

I'm trying to find a closed formula $f(n)$ for the probability of choosing a number with $n$ digits that contains at least three consecutive sixes. Ideally, the formula should not depend on $f(n-1)$. ...
Aldo Roberto Pessolano's user avatar
1 vote
2 answers
73 views

Number of vectors of length $n$ over ${A,C,T,G}$ such that there are no $k$ consecutive $A$'s, $k\geq 2$

I have to come up with a recursive solution to the problem in the title. Here is my attempt: Let $u(n)$ be a function given the number of valid such vectors of length $n$. Assume we have a valid ...
natitati's user avatar
  • 391
0 votes
0 answers
27 views

Voter Count(similar to Bertrands ballot theorem)

This question is from Quantguide: Voter Mayhem2: Two candidates, say A and B, are running for office. Candidate A received n votes, while Candidate B received m votes, with n>m. The n+m votes are ...
Md Kaif Faiyaz's user avatar
0 votes
1 answer
45 views

Number of lattices over a finite set

I'm interested in finding a general formula for the number of lattices possible over a finite set $S$ as a function of the set's cardinality. For instance, how many lattices over $\{1, 2, 3\}$ are ...
lafinur's user avatar
  • 3,468
0 votes
0 answers
31 views

Arrangements of fixed k-polyplets in a $n\times n$ matrix

Recently, I asked a question about the number of arrangements of $k$ elements inside a $n\times n$ matrix with certain restrictions. The one I´m actually interested in for this question is in its 2. ...
Cardstdani's user avatar
0 votes
1 answer
64 views

Find a sequence function for combinatorial sequences

I´m trying to find a sequence function for the following sequence: $0, 1, 85, 419, 973, 1747, 2741, 3955, 5389, 7043, 8917, 11011, 13325, 15859, 18613, 21587, 24781, 28195$ The first term is generated ...
Cardstdani's user avatar
1 vote
1 answer
98 views

Two numbers written on a board get replaced

Question: "Several (at least two) nonzero numbers are written on a board. One may erase any two numbers, say $a$ and $b$, and then write the numbers $a+\frac{b}{2}$ and $b−\frac{a}{2}$ instead. ...
mathisdagoat's user avatar

1
2 3 4 5
1187