For questions about the study of finite or countable discrete structures, specifically 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.

learn more… | top users | synonyms (4)

0
votes
0answers
47 views

Dynamic “Assignment Problem” (Hungarian Algorithm Extension?)

TL;DR: Trying to optimize assignments using Hungarian algorithm, but cannot determine costs until all assignments have been made due to dependencies. Using the terminology from Wikipedia's Assignment ...
1
vote
1answer
46 views

How to count the latin squares of order 4

a Latin square is an $n × n$ array filled with n different symbols, each occurring exactly once in each row and exactly once in each column. So, Assume that an integer like $4$ is given. How many ...
33
votes
2answers
641 views

Placing the integers $\{1,2,\ldots,n\}$ on a circle ( for $n>1$) in some special order

For which integer $n>1$ can we place the integers $\{1,2,\ldots,n\}$ on a circle (say boundary of $S^1$ ) in some order such that for each $s \in \{1,2,\ldots,\dfrac {n(n+1)}{2}\}$ , there exist a ...
0
votes
2answers
51 views

Slot Machine Win Hits

I'm implementing slot machine for fun and not so far I found one(with PAR sheets) which I tried to use as reference. There are couple of things which are not clear. As example I will take only SHIRT ...
1
vote
2answers
57 views

number of cylces in a graph

Consider a connected graph with e edges and v vertices, let x = e - v for a given x what are the maximum and minimum number of cycles a graph can have? Examples: x = 0 the maximum number of cycles ...
1
vote
1answer
31 views

Let T be a spanning tree of a connected graph G..

Let $T$ be a spaning tree of a connected graph $G$ and let $e$ be an edge of $G$ not in $T$.Show that $T+e$ contains a unique cycle. So we know that if $T$ is spanning tree $\rightarrow$ $T$ is ...
1
vote
0answers
106 views

What distribution describes the number of balls in bins of limited size

Another balls into bins question... I have n balls to distribute into k bins which can hold no more than l balls. What probability density function describes the number of balls in a (randomly ...
0
votes
1answer
27 views

Let $S$ be a set of $k$ elements, where $k$ is a whole number. Suppose $n$ is not an element of $S$. Show that $S$ union s has $k + 1$ elements.

Let $S$ be a set of $k$ elements, where $$k \in \omega$$ Suppose $$n \notin S$$Show that $$S \cup \{n\}$$ has $k + 1$ elements. I'm honestly last as to where I should start. I was thinking of maybe ...
3
votes
1answer
108 views

Why is a Pair of Tens better than a Pair of Aces in Texas Hold 'Em?

A couple years ago I developed a program to calculate the optimum betting amount for a round of Texas Hold 'em by using the Kelly criterion. In the process of computing the probability of winning for ...
1
vote
1answer
37 views

Collecting Stickers! Evaluate occurrence of duplicates?

The Sticker Collector You need to collect $n>1$ different Stickers. Each day you get one pack with $1$ random sticker until you don't collect at least one of each kind. * Each ...
0
votes
1answer
388 views

Multiple Choice Knapsack Problem (MCKP) where one class requires more than one item

I have the following problem of which I am attempting to find a near optimal solution: I have one knapsack which can hold a maximum weight. I must select exactly one distinct item from a number of ...
0
votes
1answer
27 views

How to prove this argument with combinatorics

I have an initial thought that the LHS should be equated to be the number of trees with n nodes such that 1 edge is marked on the left side but after that I am a bit lost
0
votes
1answer
22 views

Combinatorics with postman and recepients

A postman has to deliver five letters to five different houses. Mischievously, he posts one letter through each door without looking to see if it is the correct address. In how many different ways ...
5
votes
2answers
173 views

How many integers from $43523$ to $93107$ contain at least one digit $7$

How many integers from $43523$ to $93107$ contain the digit $7$ at least once? I know that if we had $43000$ to $93000$, we would subtract integers that do not contain digit $7$ from the total ...
0
votes
2answers
58 views

Coloring $\{1,2,…,2n\}$ elements in red and blue, such that if $i$ is red, $i-1$ is also red.

The purpose is to find the number of ways to color $2n$ following integers in red and blue, such that if $i$ is red, so is $i-1$. I tried to use Inclusion-Exclusion principle, but I got stuck in the ...
2
votes
1answer
81 views

Example in Combination, is there any solution?!

Is there any idea to solve such a question? I have $40$ pens that includes $20$ white pens and $20$ black pens, I decide to distribute these pens among $4$ students that every student gets at least ...
3
votes
3answers
5k views

number of ordered partitions of integer

Please, help me out How to evaluate the number of ordered partitions of the positive integer 5 Thanks!
0
votes
0answers
29 views

On random subset combinatorics.

Suppose we have $2^n$ elements in a set. We have $cn^\beta$ random subsets of cardinality $\frac{2^n}{c}$ elements each where $c,\beta>1$ holds. Fix a random subset of $n^\alpha$ elements $A$ ...
0
votes
3answers
33 views

forming three-digit integers

Can anyone help me on this? This is probably a simple problem, but I don't know how to do it. I think that I may be lack of the knowledge in this area. To solve similar problems, what materials should ...
1
vote
1answer
16 views

For integers $n>1$ , $k$ , does there exist matrix $A$ with integer entries and first row $(1,2,…,n)$ such that $\det A=k$?

Let $n >1$ be an integer , then is it true that for any integer $k$ , there exist a matrix $A \in M(n,\mathbb Z)$ with first row of $A$ as $(1,2,...,n)$ such that $\det A=k$ ?
1
vote
0answers
33 views

Total Combinations

How many sets of size $5$ exist from the first $n$ natural numbers such that each element in the combination is pairwise coprime. eg. $\{1,2,3,5,7\}$ ,$\{1,4,3,5,7\}$ etc. but $\{1,2,4,5,7\}$ is ...
4
votes
1answer
362 views

Coupon Collector Problem - expected number of draws for some coupon to be drawn twice

Suppose that there are $n$ different coupons, equally likely, from which coupons are being randomly drawn with replacement. Find the expected number of draws for some coupon to be drawn twice. I've ...
2
votes
1answer
26 views

Generating uniform permutations by a particular method

Let $A$ be a uniformly random permutation of the numbers $\{1,2,\cdots,n\}$. I want to generate a uniformly random permutation from $A$ on the numbers $\{1,2,\cdots,n,n+1,\cdots,n+m\}$. In other ...
1
vote
1answer
188 views

How many symmetric and transitive relations are there on ${1,2,3}$?

I'm trying to count the number of relations on ${1,2,3}$ that are symmetric and transitive. I know how to count the symmetric relations but I can't seem to find the method for this one. I've counted ...
1
vote
1answer
278 views

Probability question using PIE

Five people check identical suitcases before boarding an airplane. At the baggage claim, each person takes one of the five suitcases at random. What is the probability that every person ends up with ...
0
votes
1answer
25 views

Combinatorics of vectors in plus minus 1

How many vectors of length n are there with entries in {-1,+1} such that the sum of all entries from 1 to k is positive for all k between 1 and n.
0
votes
0answers
44 views

A possible generalization of an olympiad problem

I was trying my hands on a combinatorics problem from 1978 IMO . The problem was about a conference in which there were delegates from six nations . Corresponding to every delegate there was an ...
0
votes
2answers
54 views

How many ways to pick $25$ objects from $5$ types with at most $10$ of any type?

How many ways to pick $25$ objects from $5$ types with at most $10$ of any type? The answer is: $C(25+5-1,25) - 5C(14+5-1,14) + C(5,2)C(3+5-1,3)$ Where do the numbers in this answer come from? I ...
3
votes
1answer
115 views

Eigenvalues of “almost” complete bipartite graph ?!

Please note that I'm just looking for a partial answer to this question. Definition Let $G=U\cup V$ be a bipartite graph, where $U$ and $V$ are disjoint sets of size $p$ and $q$, respectively. ...
0
votes
2answers
17 views

How many different ways can a pitcher throw $3$ pitches when warming up with $12$ pitches

A pitcher has three pitches, a fastball, a curveball, and a knuckleball. When warming up he wants to throw $3$ fastballs, $5$ curveballs, and $4$ knuckleballs. How many different ways can he throw ...
1
vote
0answers
29 views

Can this sum over the q-Pochhammer symbol be simplified?

While considering the problem of the expected value of a dice fixing strategy on a two-sided die that comes up as $1$ with a probability of $\alpha$ and $0$ otherwise. I was studying the strategy ...
0
votes
0answers
18 views

number of times a sum can be made with three numbers

we are given 4 numbers A, B, C and K with the condition A,B,C >=K. We need to find the sum ...
2
votes
1answer
20 views

How to schedule n jobs on two machines so that their order of execution remains same on both machines?

There are n jobs that have to be scheduled. Each job requires operations on two machines. For reasons of control, the order in which the jobs are processed on the two machines is the same so what is ...
1
vote
0answers
36 views

Combinatorics: Counting Set Partitions with Moebius Function

Let $\pi_n$ be the poset of all set partitions of $\{1,...,n\}$ ordered by refinement, $\sigma = \{B_1,...,B_k\}$ be a set partition with blocks $B_i$, and $max(B_i)$ be the maximum value in the block ...
0
votes
1answer
53 views

Count the number of non-isomorphic 6-regular graphs on 9 vertices.

I know there will be 9 vertices of degree 6, which means there are 54 edges. But then how will I figure out the number of non-isomorphic graphs?
2
votes
0answers
19 views

Bijective mapping between face polytopes of permutohedra and partitions of integers

The OEIS entries A019538, A049019, and A133314, relate a refinement of the face polynomials of the permutohedra (A049019) to partition polynomials (A133314) defined by multiplicative inversion of an ...
0
votes
2answers
34 views

Number of possible team combinations

The baseball team is made up of 7 girls and 8 boys. There are 9 people on the field at the same time in a baseball game. If at least four of the people on the field must be girls, how many different ...
1
vote
0answers
34 views

Number of ways to form N as the sum of array elements?

I have given an Array A containing M elements and i also given two numbers N and K . Now i have to find the number of ways to represent N as the sum of different elements of A but exactly K elements ...
5
votes
4answers
212 views

An identity involving binomial coefficients

Prove the following identity $$\displaystyle \sum_{i+j=m}\frac{(n-1) \binom{ai+n-1}{i} \binom{aj+1}{j}}{(ai+n-1)(aj+1)} = \frac{n\binom{am+n}{m}}{am+n}$$ where $i = 0,1,\cdots,m$ and $m, n$ are ...
0
votes
0answers
19 views

Expected value of removing every ball once [duplicate]

I thought of this question and I somehow I can't figure out an answer Let there be a box with $n$ balls (which have numbers from $1$ to $n$ to that you can distinguish them). When we randomly pick a ...
0
votes
1answer
434 views

About permutation with repeated identical elements.

First up, I do know the general solution but somehow am unable to use it to solve this kind of problem. I am simply lost. The problem is like this: ...
2
votes
1answer
32 views

Probability of a random chair being empty and having a seat to the right which is not empty is $\frac{m(n-m)}{n(n-1)}$

Let there be a round table with $n$ chairs. $m$ people choose their chair (max 1 person per chair) and let $m < n$. I am pretty sure that the probability of a random chair being empty and having a ...
2
votes
0answers
30 views

Properties of transfer matrices and their traces

I'm having difficulties understanding some arguments in my statistical mechanics lecture and would like to make them more rigorous by proving some properties. For the Ising model on a lattice we ...
4
votes
1answer
640 views

Calculating the Shapley value in a weighted voting game.

Given a special case of WVG (Weighted Voting Game) of $a$ 1s and $b$ 2s and a quota q, $ [q:1,1,1,1..1,2,2,..2] $. I need help with calculating the Shapley value of a player with a weight of $2$ and a ...
3
votes
2answers
48 views

Another Hockey Stick Identity

I know this question has been asked before and has been answered here and here. I have a slightly different formulation of the Hockey Stick Identity and would like some help with a combinatorial ...
0
votes
1answer
28 views

How to choose $n$ balls from the bags?

Given $4$ bags A, B, C and D. Bag A contains 'a' number of balls. Bag B contains 'b' number of balls. Bag C contains 'c' number of balls. Bag D contains 'd' number of balls. I have another bag E ...
1
vote
1answer
40 views

How does $\frac{1}{2}(n-s+1)(n-s)$ equal $\binom{n-s+1}{2}$?

Maybe a basic question, but I'm strolling through graph theory at the moment after a few years out of tertiary mathematics. There is a theorem that if a graph $G$ has $s$ connected components, then $$ ...
2
votes
2answers
25 views

Number of non-identity elements of order $7$ in a group

If $x \neq e \in$ group $G$ s.t. $x^7 = e$, then $(x^i)^7 = e$ for all $i \in 1\le i\le $6 implying the number of $x \neq e \in G$ with $x^7 = e$ is $6n$ for any positive integer $n$ ...
2
votes
2answers
217 views

Count pairs with odd XOR

Given an array A1,A2...AN. We have to tell how many pairs (i, j) exist such that 1 ≤ i < j ≤ N and Ai XOR Aj is odd. Example : If N=3 and array is [1 2 3] then here answer is 2 as 1 XOR 2 is 3 ...
1
vote
1answer
32 views

Problem with understanding why 2 solutions of a combinatorics task don't give the same result

The task is: In how many ways can we pick 6 people from a group of 4 girls and 6 boys so that there are at least 2 girls? The first solution, which we did in school, is to divide into 3 different ...