Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

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.

0
votes
1answer
15 views

Modified Magic square with sum $15$

Consider the following diagram: The task is to use integers from 1 to 9 (both endpoints inclusive) in a way that the sum of all numbers written in 3 square in the same row or column is 15. I think ...
0
votes
0answers
18 views

Number of way in a permutation where inversion count is equal to some (given below) value

A permutation of length $n$ is consisted of only numbers $\in \{1,2,3 \cdots n\}$ and some $k$, $k \leq n$ initial values of that permutation are given. Found out the number of ways such that the ...
1
vote
1answer
28 views

Calculate cardinality of a set

There is given: set $B=A_{1} \cup...\cup A_{n}$ $|A_{i}|=m_{i}$ for each $i$ every element of $B$ belongs to exactly $k$ sets $A_{i_{1}},...,A_{i_{k}}$ Calculate $|B|$ in terms of $m_{i}$. If it ...
0
votes
0answers
11 views

Cycle length of K-ary Boolean function

Boolean networks have been extensively studied, however I didn't find a reference to the following problem. May be you can provide one, or give hints to a possible solution. Define K Boolean ...
1
vote
1answer
47 views

Infinite number of solutions to ellptic curve?

I am wondering if there are infinitely many solutions to the equation: $$ {n \choose 2} = {m \choose 3} $$ Also, do the solutions have a general form? From what I know, this is an elliptic curve, ...
2
votes
1answer
48 views

When can you uniquely determine a square matrix if you know the sum of its rows and columns?

There is a square matrix consisted of only $0, 1, i$. You know the sum of all the numbers in each row and each column. When can you uniquely determine the matrix? Edit: For clarification, there is a ...
1
vote
2answers
18 views

How many ticket teams can the manager choose if one particular batsman refuses to play when one particular bowler does?

A certain country has a cricket squad of 16 people, consisting of 7 batsmen, 5 bowlers, 2 all- rounders and 2 wicket-keepers. The manager chooses a team of 11 players consisting of 5 batsmen, 4 ...
1
vote
1answer
91 views

Is there a mathematical validity of my claims?

I have a question which is not homework. Actually, I have a hard time asking the question. But I will try to express the question as clearly and clearly as I can. In the question, since I cannot use ...
0
votes
1answer
35 views

Number of permutations differing in at least $d$ spots in pairwise comparisons

A friend and I were thinking about this problem today but we were unable to come up with a solution. Problem: Consider the the numbers $S=\{1,\ldots,n\}$. Given $2\le d \le n$ what is the ...
4
votes
1answer
37 views

Combinatorial proof for $\sum_{k=0}^p (-1)^k {n \choose k} = (-1)^p {n-1 \choose p}$

I am trying to give a combinatorial proof for: $$\sum_{k=0}^p (-1)^k {n \choose k} = (-1)^p {n-1 \choose p}$$ Where $p$ and $n$ are natural numbers. We could easily see that if $p=n$ this reduces ...
0
votes
2answers
24 views

Find the sum of some numbers.

I have a number $a=3145$.At first exercise I need to find how many numbers can be formed with the digits of a. $4!=24$ numbers.My problem is at second exercise where I need to find the sum of these ...
0
votes
0answers
17 views

Technique to improve MIP solve time

Was on a webinar and the presenter mentioned that modelers should "slice" in certain contexts to reduce MIP solve time. The context was in sending a Minimum Cost Network Flow Problem. I believe he was ...
0
votes
0answers
31 views

Suppose that R(s, t − 1) and R(s − 1, t) are both even numbers..

Suppose that R(s, t − 1) and R(s − 1, t) are both even numbers. Prove that R(s, t) ≤ R(s, t − 1) + R(s − 1, t) − 1. I'm trying to learn proofs for graph theory and Ramsey theory but i'm strugging to ...
0
votes
2answers
28 views

Show that any RB-edge coloring of K3,3 contains a monochromatic path of length 3.S [on hold]

I'm trying to learn proofs using Ramsey's theorem but I'm getting stuck while attempting to solve this.. Any help would be greatly appreciated..
3
votes
2answers
100 views

Show that, in a group of n people, everyone has the same number of friends if..

Question: Consider a group of n people with the following properties: • no person is friends with everyone, • any pair of strangers share exactly one friend in common, • no three people are ...
2
votes
2answers
28 views

Words with repeated blocks of letters

If I have the word BARBARIANISM, how many arrangements of this word's letters contain two identical blocks of 3 letters (e.g. 'BAR' repeated twice in the original word, or 'AIR' repeated twice in '...
0
votes
2answers
25 views

Probability on a disc

I was solving some questions of probability and I came across the following one: Question: Given an arbitrary disc with radius $r> 0$. A point is chosen randomly on the disk. Determine the ...
0
votes
1answer
9 views

Number of Ways to Arrange Two Couples and A Single Person

Two couples and a single person are seated at random in a row of five chairs. What is the probability at least one person is not beside his/her partner? Let $P(A)$ denote the probability that both ...
0
votes
1answer
42 views

There is no magic cube of order 2. [on hold]

I tried it to solve like for order 3, but it does not work here for order 2. Can anyone help me on this how this can be solved.
1
vote
0answers
38 views

Calculating factorial in terms of certain powers

Factorial $n!$ is defined to be$$n!=1·2·3·4\cdots n$$Let's choose base $2$ to represent $n!$, thus$$n!=2^0·2^1·(2^1+2^0)·2^2·(2^2+2^0)·(2^2+2^1)·(2^2+2^1+2^0)\cdots$$Of course, it is just binary ...
1
vote
0answers
23 views

Intuition behind combinations

Example problem: Suppose you have to select 5 cards from a deck: what is the probability of getting 4 diamonds and 1 spade. The solution should be : $$\ \frac{\binom{13}{4} \binom{13}{1}}{{52}\...
1
vote
1answer
15 views

Permutation and Combination in probability question - Choose team members

I would like to have your help and explanation on following question. For an 8-a-side football match, a coach has to choose the team from a squad of 12 boys. Only three of them can play as a ...
6
votes
4answers
92 views

Computing how many distinct digital products are below $10^n$

Given a number $n$, its digital product is the product of its digit. So the digital product of $15$ is $1\times 5=5$, and the digital product of $760$ is $0$, etc. I recently saw a nice video on ...
0
votes
0answers
27 views

Graph factorisation

I have a graph having 6 vertices and its presentation is $E_{12}^4E_{13}^5E_{14}^6E_{24}^9E_{25}^2E_{35}^9E_{36}L_5^4L_6^{14}$. This means that there are $4$ edges connecting the vertices $1$ and $2$, ...
0
votes
0answers
17 views

Issue w/ extracting coefficients from generating function using IDTFT

This q will make use of these 3 DTFT pairs... $$ \require{extpfeil}\Newextarrow{\xleftrightarrow}{15,15}{0x2194} \begin{array}{rcl} \alpha x_1[n] + \beta x_2[n] & \xleftrightarrow{\mathscr{F}} &...
0
votes
1answer
59 views

Showing that a certain “norm-like” function fails to satisfy triangle inequality

For any symmetric measurable function $h: I \times I \to \mathbb{R}$, define $$|h| =\sqrt[6]{\int h(x,y)h(x,y')h(x',y)h(x',y')h(x,x')h(y,y') d\mu(x,y,x',y')} $$ where $\mu$ denotes the Lebesgue ...
0
votes
0answers
27 views

Likelihood of getting flush, straight, etc

On Planet X, cards can take on a numerical value from $1$ to $7$ (inclusive) and their suit can be either red or blue. In a game of poker, each player gets three cards. 1) What is the probability of ...
0
votes
0answers
21 views

Prove that each set of 2-distant points on the plane has at most 5 elements. [duplicate]

I need to show that each set of 2-distant points on the plane has at most 5 elements. Can anyone help? Thanks in advance.
12
votes
2answers
1k views

Why aren't these two solutions equivalent? Combinatorics problem

I was given the following fact: there is a set $S$ of $11$ people, among which there are $4$ professors and $7$ students, $S=\{p_1, p_2, p_3,p_4, s_1, s_2,...,s_7\}$ We are requested to form from ...
0
votes
1answer
23 views

Characterization of Strongly Regular Graphs

I am looking for a reference in which I can find a proof of the following result. A strongly regular graph is disconnected if and only if it is a disjoint union of complete graphs $K_n$ of the same ...
0
votes
1answer
29 views

What possible combinations of single-rooms, double-rooms and triple-rooms

A sports association with 40 persons want to book a hotel. The hotel have single-rooms for 40 euros , double-rooms for 60 euros and triple-rooms for 70 euros. What possible combination of single-...
0
votes
1answer
28 views

Ways of putting n indistinguishable objects into exactly k boxes out of n boxes

For integers $k$ and $n$ satisfying $1 \le k \le n$, let $b(k, n)$ be the number of ways of putting $n$ indistinguishable objects into $n$ distinguishable boxes such that exactly $k$ boxes are ...
3
votes
1answer
567 views

How many ways are there to win Settlers of Catan?

The object of the board game "The Settlers of Catan" is to obtain 10 "victory points". There are five ways to obtain victory points: Settlements, worth 1 victory point. Each player starts the game ...
0
votes
1answer
28 views

What is the probability that the original sign was plus?

A slip of paper is given to A, who marks it with either a plus or a minus sign; the probability of his writing a plus is $\frac{1}{3}$. He then passes the slip to B, who may either leave it or change ...
0
votes
0answers
23 views

the number of ways to change an element in the permutation cycles from outside those cycles

I've been thinking about this issue for a while! For the set of $n$ elements, consider that there is a permutation over the whole set $\{1,\dots, n\}$ where $n-k$ elements are fixed. A way of ...
0
votes
0answers
14 views

combinatorics of connected components of a bicolored polyhedron skeleton

Consider the skeleton of a 3-dimensional convex polyhedron with all vertices being either red or black. We have n red and m black vertices. n < m. Take the largest sub-graph that consists of black ...
1
vote
0answers
41 views

Efficient calculation of difference sets from finite fields

A while ago I wrote a program to generate, amongst other things, difference sets from finite fields. Generating these sets is rather slow. Is there some theorem or construction I could use to speed it ...
0
votes
0answers
28 views

Finding the number of ways of dealing a poker hand

A man is dealt a poker hand (consisting of 5 cards) from an ordinary pack of 52 playing cards. Find the number of ways in which he can be dealt a "straight" (a straight is five consecutive values ...
-2
votes
1answer
67 views

how many integers between $1000$ and $9999$ is the sum of digits equal $11$ [on hold]

I have already known that all cases is $\binom{13}{3}$, but I don' know how to handle the bad cases, such like putting $10$ objects in the first box.
1
vote
0answers
31 views

the number of the longest paths of a complete undirected graph $K_n$

I am trying to find the number of the longest paths of a complete undirected graph $K_n$. My guess is $\frac{n!}{2}$. Any longest path in $K_n$ should have $n$ vertices. And given one longest path $...
-1
votes
0answers
22 views

Three boxes across, two rows. Numbers 1,2,3,4,5,6, and restrictions. [duplicate]

The numbers 1, 2, 3, 4, 5, and 6 are to be entered into a three boxes across, two rows , so that there is one number per box, and each number is used exactly once. In addition, in each row, the ...
0
votes
1answer
18 views

Seating arrangements for a five-seater car [on hold]

A car has one driver's seat and four different passenger seats. A group of five students wants to use the car to go to school, but only two of those five students are legally allowed to drive the car. ...
0
votes
0answers
16 views

Help finding generating function for this problem

find a generating function for the number of partitions of n into: a) at most four summands b) exactly four summands Are these correct: (top is A and bottom is B)
0
votes
1answer
37 views

How many pairs of guests should we expect to only have to swap places?

I have a party and I invite $n$ people. I create a seating plan and assign each person a specific seat. When they arrive, however, they completely ignore the plan and sit down randomly. I’m strict ...
2
votes
2answers
35 views

Probability of matching pair of 10-item baskets out of 100M people shopping 100 times in a year

This is from Exercise 1.2.2 of MMDS MMDS Book Suppose we have information about the supermarket purchases of 100 million people. Each person goes to the supermarket 100 times in a year and buys ...
0
votes
0answers
19 views

question on finding generating function for a partition

find a generating function for the number of partitions of n into: a) summands no larger than 4 b) summands the largest of which is 4 are my answers correct? :
3
votes
3answers
70 views

Combinatorics Proof of $\sum_{i=0}^n \sum_{j=0}^{i-1} j = {n+1 \choose 3}$

Proof of $\sum_{i=0}^n \sum_{j=0}^{i-1} j = {n+1 \choose 3}$ I am trying to generate a combinatorics proof of this identity, but have been stuck for hours. I've been trying to think of someway to ...
5
votes
2answers
47 views

how many ways can you write a number n as a sum of 1s, 2s and 3s [duplicate]

Given $n \in \mathbb{N}$ how many ways can one write $n=a+2b+3c$ for $a,b,c \in \mathbb{N}$. I have an idea as if I use a a 3-tuple to represent $(a,b,c)$, I can list all of them using two functions $...
2
votes
1answer
70 views

If $k$ balls are thrown into $n$ bins, how many positions $i$ are there such that, bin $i$ and $ i+1$ are empty?

Assume the $k$ balls are thrown independently and uniformly at random, into $n$ labeled bins. What is the expected number of positions $i$ such that the bins labeled $i$ and $i+1$ are both empty?
1
vote
1answer
79 views

On an island of 20 wizards, every set of three cast a spell on another. Show that there must be a wizard targeted by at least 9 wizards.

Twenty wizards meet on an island. Every set of 3 wizards cast a spell together on another wizard. Show that there must be a wizard who had been targeted by at least 9 wizards. (Each wizard can be in ...